(과제) 해쉬 테이블 구현

english1200.txt

report3.cpp

문제

–별첨 word1200.txt 파일의 1,200개 영어단어 해시 테이블 구성

세부 설명

–1,200개의 영단어/해석 포인터 저장을 위한 배열[1200]을 선언

–각 배열의 내용은 실제 단어/해석 자료구조가 저장된 곳의 포인터

–실제 자료구조에는 영단어, 해석 이외에 해시 충돌 시 다음 단어 저장을 위해 다음 자료구조

에 대한 포인터도 포함되어야 함

–해시 함수를 스스로 만들고

–1,200개를 모두 저장한 뒤 아래에 따라 성능을 평가

§적재밀도 = 저장에 사용된 배열 수/1200

실행 결과 보여주기

–txt 파일을 읽어 해시 테이블을 구성하고 적재밀도를 출력

–영어 단어를 입력하면 해석을 출력

//////////////////////////////////////////////////////////////////

#include <iostream>

#include <fstream>

#include <cstring>

#include <string>

#include <stdlib.h>

#pragma warning ( disable : 4996 )

using namespace std;

int hashGetIndex(char key[]);

void makeHash(char buffer[100]);

void searchWord();

//영어 단어 구조체

typedef struct english {

char word[50]; //단어

char mean[100]; //뜻

struct english* chain = NULL; //충돌을 대비한 체인 포인터

}ENGLISH;

//해시 탐색을 위한 포인터 배열 선언

ENGLISH* englishArray[1200] = {'\0'};

void main() {

int i = 0, index = 0;

ifstream file;

char buffer[100];

file.open("english1200.txt");

if (!file.is_open()) {

cout << "파일 열기 실패!" << endl;

}

while (!file.eof()) {

memset(buffer, 0, sizeof(buffer));

file.getline(buffer, 100);

makeHash(buffer);

}

searchWord();

//해당 인덱스에 저장 상태 체크

/*

ENGLISH *tt = englishArray[1069];

while (tt != NULL) {

cout << tt->word << endl;

cout << tt->word[7] << endl;

tt = tt->chain;

}

*/

file.close();

}

//해시 만들기

void makeHash(char buffer[100]) {

char* token = NULL;

char tk[] = "\t\n";

int index = 0;

ENGLISH *tmp = NULL;

ENGLISH *current = NULL;

tmp = (ENGLISH *)malloc(sizeof(ENGLISH));

memset(tmp, 0, sizeof(ENGLISH));

token = strtok(buffer, tk);

strcat(tmp->word, token);

//cout << tmp->word << "\n\n";

token = strtok(NULL, tk);

strcat(tmp->mean, token);

//cout << tmp->mean << endl;

tmp->chain = NULL;

index = hashGetIndex(tmp->word);

if (englishArray[index] == NULL) {

englishArray[index] = tmp;

}

else {

current = englishArray[index];

while (current->chain != NULL) {

current = current->chain;

}

current->chain = tmp;

}

}

//해시 알고리즘

int hashGetIndex(char key[]) {

int hashKey = 0;

int word1 = key[0]; //첫번째 글자의 아스키코드

int word2 = key[strlen(key) - 1]; //끝글자의 아스키코드

int word3 = strlen(key); //문자열의 길이

int word4 = key[strlen(key) / 2]; //가운데 글자의 아스키코드

//hashKey = ((word1 * 107) + (word2 * 31) + word3) % 1200; //556

//hashKey = ((word1*17) + (word2 * 31) + word3) % 1200;   //514

//hashKey = (((word1 + word2) * word3) * 17) % 1199; //312

//hashKey = (word1 + word2 * word3 * word4) % 1199; //695

//hashKey = (word1 * word2 * word3 * word4) % 1199; //537

//hashKey = (word1 * word2 + word3 - word4) % 1199; //628

//hashKey = (word1 * word2 / word3 - word4) % 1200; //698

//hashKey = (word1 * word2 / word3 * word4) % 1200; //540

//hashKey = (word1 * word2 / word3 * word4) % 1199; //648

//hashKey = (word1 * word2 / word3 - word4) % 1199; //693

//hashKey = (word1 * word2 * word3 * word4) % 1200; //275

//hashKey = ((word1 * word4) + word3 + word2) % 1200; //664

//hashKey = ((word1 * word4) / word3 + word2) % 1200; //705

//hashKey = ((word1 * word4) / word3 * word2) % 1200; //538

hashKey = ((word1 * word4) / word3 + word2) % 1200; //705

//해시키 분포도 보기

cout << hashKey << endl;

return hashKey;

}

//단어 검색 함수

void searchWord() {

char input[50] = {'\0'};

int index = 0;

ENGLISH *tmp = NULL;

while (1) {

cout << "\n\n검색할 단어를 입력해 주세요 (종료: exit) : ";

fflush(stdin);

cin.getline(input, 50);

if (strcmp(input, "exit") != 0) {

index = hashGetIndex(input);

if (englishArray[index] != NULL) {

tmp = englishArray[index];

while ((strcmp(tmp->word, input) != 0) && (tmp->chain != NULL)) {

tmp = tmp->chain;

}

if ((tmp->chain == NULL) && (strcmp(tmp->word, input) != 0)) {

cout << "일치하는 단어가 없습니다" << endl;

} else {

cout << "단어 = " << tmp->word << endl;

cout << "뜻 = " << tmp->mean << endl;

}

} else {

cout << "일치하는 단어가 없습니다" << endl;

}

} else {

cout << "종료합니다..." << endl;

exit(1);

}

}

}