本文共 1609 字,大约阅读时间需要 5 分钟。
#include <cstdlib>#include <iostream>#include <cstdio>using namespace std;const int MAX = 100000;const int HASH_SIZE = 100003;const int STR_LEN = 11;typedef struct _NODE{ int hashIndex; struct _NODE *next;}NODE, *PTRNODE;PTRNODE link[HASH_SIZE] = {NULL};char dic[MAX][STR_LEN];char words[MAX][STR_LEN];int BKDRHash(char *str){ int size = strlen(str); int seed = 131; unsigned long hash = 0; for(int i=0; i<size; i++) hash = (hash * seed) + (*str++); return hash % HASH_SIZE;}int main(int argc, char *argv[]){ //freopen("input.txt", "rt", stdin); //freopen("output.txt", "wt", stdout); char str[50]; PTRNODE ptr = NULL; int index = 0; gets(str); while (strcmp(str,"")!=0) { int i, hashValue; for (i=0;str[i]!=' ';i++) dic[index][i]=str[i]; dic[index][i++]='/0'; strcpy(words[index],str+i); hashValue = BKDRHash(words[index]); ptr = (PTRNODE)malloc(sizeof(NODE)); ptr->hashIndex = index++; ptr->next = link[hashValue]; link[hashValue] = ptr; gets(str); } while (gets(str)!=NULL) { int hashValue = BKDRHash(str); int flag = 0; ptr = link[hashValue]; while(ptr != NULL) { if(strcmp(str, words[ptr->hashIndex]) == 0) { printf("%s/n", dic[ptr->hashIndex]); flag = 1; break; } ptr = ptr->next; } if(!flag) printf("eh/n"); } return EXIT_SUCCESS;}
链地址法解决冲突...
转载地址:http://qdkqb.baihongyu.com/