카테고리 없음

Hash table

Sumin Lim 2018. 3. 12. 01:11
반응형
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#define MAX_TABLE 10
int arr_idx;
struct NODE {
char data[7];
NODE *prev;
} a[20000];
NODE *my_arr_alloc(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;
}
cout << "out:" << hash % MAX_TABLE<<endl;
return hash % MAX_TABLE;
}
int main(void) {
//freopen("input.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;
}
}
*/
//Initialize
arr_idx = 0;
for (int i = 0; i < MAX_TABLE; i++) {
hTable[i] = nullptr;
}
NODE *p;
int key;//hash key int
char in[7];
int test_case;
cin >> test_case;
//Add char @Hash table
for (int t = 0; t < test_case; t++) {
cin >> in;
cout << "in:" << in<< endl ;
key = (int)myhash(in);
cout << "Add to Hash Table" << key << ":" << in << endl;
p = my_arr_alloc();
strncpy(p->data, in, 7);
p->prev = hTable[key];
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 search
char search[7] = "vrvipy";
cout << "Searching: " << search << endl;
int k = (int)myhash(search);
cout << "Hash table key: " << k << endl;
// Search @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;
}
}
}


































반응형