[자료구조] HashTable을 이용한 Spell Check Dictionary 프로그램

소개

인하대학교 자료구조 다섯번째 과제물입니다.
각각의 문제에 대한 소스코드(주석포함) 및 실행파일이 압축되어있습니다.

Hash Table을 이용하여 작성한 Spell Check 프로그램입니다.
프로그램이 실행되면 주어진 파일 “words.txt”에서 단어를 추출하여 해쉬테이블에 입력하며,
이를 통해 사용자로부터 입력받은 인풋값을 테이블로부터 검색합니다.
비슷한 단어를 입력할경우, 테이블 안의 비슷한 단어를 추천합니다.

자세한 문제내용은 아래와 같습니다.

교과서 페이지 384-387의 해쉬테이블을 이용하여 다음과 같은 spell check 프로그램을 작성하시오.

프로그램이 실행되면 주어진 파일 “words.txt”에서 단어를 추출하여 해쉬테이블에 입력한다. 이때 해쉬 테이블의 사이즈는 3001로 하고 중복된 단어는 입력하지 않는다.

프로그램의 인터페이스는 다음과 같다.

Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 1
Enter a word: very
Given word “very” is in the dictionary!!

Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 1
Enter a word: veri
Given word “veri” is not in the dictionary!!
We have the following similar words: verb, very
Do you want to insert “veri” into the dictionary? (y, n): n
Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 1
Enter a word: ik
Given word “ik” is not in the dictionary!!
We have the following similar words: is, it
Do you want to insert “ik” into the dictionary? (y, n): y
Given word “ik” has been inserted into the dictionary.

Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 2
Enter a word: ik
Given word “ik” has been deleted from the dictionary.

Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 3
The dictionary has 1000 words.

Enter your selection (1: New Search, 2: Delete Word, 3: Size, 4: Quit): 4
Bye!!

단어 추천은 영문 소문자만 사용한다.

컴파일 실행환경

Visual Studio 2008

본문내용

#include <iostream>
#include <fstream>
#include <string>
#include "HashTable.h"

using namespace std;

#define SIZE 3001 // Hash Table 크기
#define BUF_SIZE 80 // 입력값을 받는 버퍼 크기
#define KEY_WEIGHT 83 // Hash Key 계산을 위한 가중치

unsigned long makeKey(char str[BUF_SIZE]); // Hash에 insert 하기 위해 가중치를 부여한 키를 생성
void ShowSimilarWord(char inp[BUF_SIZE]); // 입력한 단어와 비슷한 단어를 출력
unsigned long pow(int x, int y); // x의 y승을 계산 (Key값 생성시 가중치 부여를 위해 사용)

HashTable<unsigned long, char*> Hash(SIZE); // Hash Table

int main()
{
int menu; // 메뉴입력
unsigned long key; // 버퍼의 Key값 계산
char yn; // y or n 선택
bool quit = false; // while문 종료변수
ifstream words; // word단위 입력파일스트림

char buf[BUF_SIZE]; // 파일 입력 버퍼
char inbuf[BUF_SIZE]; // 사용자 입력 버퍼

words.open("words.txt");

// word 단위로 파일을 읽어 버퍼에 저장후, 중복되지 않는 단어 Hash Table에 추가
while(!words.eof()) {
words >> buf;
key = makeKey(buf);
if( Hash.find(key) == NULL )
Hash.insert(key,buf);
}

참고자료

· (Data Structures and Algorithms in C++, Goodrich, Tamassia, Mount - WILEY)