카테고리 없음
Hash table
Sumin Lim
2018. 3. 12. 01:11
반응형
#define _CRT_SECURE_NO_WARNINGS#include <iostream>using namespace std;#define MAX_TABLE 10int 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;}}*///Initializearr_idx = 0;for (int i = 0; i < MAX_TABLE; i++) {hTable[i] = nullptr;}NODE *p;int key;//hash key intchar in[7];int test_case;cin >> test_case;//Add char @Hash tablefor (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 searchchar 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;}}}
반응형