/*
2018.11.28
hash 중요 hash key 복사해온 함수 내용 string 적당한 key
사용할 hash table 지난번 single linked list 배열로 만드는 것
single linked list 가 여러개 있음
저장할 데이터를 참고로 적당한 키를 뽑아서 htble[key] 인 싱클 링크드 리스트에 저장함
single linked list, hash는 삭제를 고려하여 만들어진 것이 아니기에 삭제 코드는 어려움
삭제가 반드시 필요한 경우 dummy tail 을 넣어서 삭제하는 방법을 쓰는 것이 편리함
더블 링크드 리스트의 삭제를 참고하기 바람
삭제는 해시키를 계산한 후,
hTable[key]에서 삭제할 데이터를 검색, 검색된 노드의 이전 노드이 prev에 검색된 노드의 prev를 넣어주면 됩니다.
key를 만드는 데이터가 String이 아니더라도 약간의 변경이 적용이 가능함
이름, 부서, 전화번호 등 여러 데이터를 모두 NODE 구조체에 넣고 이중 하나로 hash key로 사용하는 방법도 많이 사용됨
*/
#include <iostream>
using namespace std;
#define MAX_TABLE 10
int arr_idx = 0;
struct NODE {
char data[7];
NODE * prev; //싱글 리스트를 위해 추가.
} a[20000];
NODE *myalloc(void)
{
return &a[arr_idx++];
}
NODE *hTable[MAX_TABLE];
unsigned long myhash(const char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % MAX_TABLE;
}
return hash % MAX_TABLE;
}
int main(void)
{
freopen("test.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
//for (int i = 0; i < 100; i++)
//{
// for (int j = 0; j < 6; j++)
// cout << (char)(rand() % 26 + 'a');
// cout << endl;
//}
arr_idx = 0; //사용할 배열 초기화
for (int i = 0; i < MAX_TABLE; i++)
hTable[i] = nullptr;
NODE *p;
int key;
char in[7];
int test_case;
cin >> test_case;
//Hash table 추가
for (int T = 0; T < test_case; T++)
{
cin >> in; //문자열을 입력 받습니다.
key = (int)myhash(in); //문자열을 바탕으로 key 를 생성합니다.
cout << "Add to Hash table " << key << " : " << in << endl;
p = myalloc(); //저장할 공간을 alloc 합니다.
strncpy(p->data, in, 7); //입력받은 문자열을 복사합니다.
p->prev = hTable[key]; //Hash table 에 저장합니다.
hTable[key] = p;
//추가된 모든 노드 확인
for (int _tKey = 0; _tKey < MAX_TABLE; _tKey++)
{
cout << "Hash table( " << _tKey << " ) :";
for (NODE * pp = hTable[_tKey]; pp != NULL; pp = pp->prev)
{
cout << " " << pp->data;
}
cout << endl;
}
cout << endl << endl;
}
//Hash table 검색
char search[7] = "phqghu";
cout << "Searching : " << search << endl;
int k = (int)myhash(search); // hash key 생성
cout << "Hash table key : " << k << endl;
//hash table [k] 에서 검색
for (NODE * pp = hTable[k]; pp != NULL; pp = pp->prev)
{
if (!strncmp(search, pp->data, 6))
cout << "FOUND : " << pp->data << endl << endl;
}
NODE **del = &hTable[k]; //이전 노드의 위치를 저장할 포인터 변수
for (NODE * iter = hTable[k]; iter != nullptr; iter = iter->prev) //hTable[k]에서 모두 검색
{
if (!strncmp(search, iter->data, 6)) { //삭제할 데이터를 찾으면
cout << "FOUND & DEL : " << iter->data << endl << endl;
*del = iter->prev; //현재 노드에 연결된 prev 노드를 이전 노드에 저장
}
del = &iter->prev; //이전 노드를 변경
}
//삭제 확인
cout << "Check delete";
for (NODE *iter = hTable[k]; iter != nullptr; iter = iter->prev)
{
if (!strncmp(search, iter->data, 6))
cout << "FOUND : " << iter->data << endl << endl;
}
}
댓글