《哈希表查询设计及实现》由会员分享，可在线阅读，更多相关《哈希表查询设计及实现（2页珍藏版）》请在金锄头文库上搜索。
1、/*1设计哈希表，该表应能够容纳50 个英文单词。2对该哈希表进展查询，实现对 特 定 单 词 的 快 速 查 询 ， 并 显 示 经 过 的 节 点 内 容 已 经 发 到 你 邮 箱 里 了enochwillshotmail szNAME 80 HASH_ROOT 47 /*用于计算哈希地址的随机数 */ szHASH 50 /*哈希表总长度*/ POPULATION 30 /* 同学总数*/哈希表构造体*/ THash int key; /*钥匙码*/ char name10; /* 姓名*/ int depth; /* 检索深度*/ 依据钥匙码和哈希根计算哈希地址*/GetHashAd
2、dress(intkey,introot)returnkey%root; GetHashAddress*/冲突地址计算，假设觉察地址冲突，那么用当前地址和钥匙码、哈希根重新生成一个新地址*/ GetConflictAddress(int key, int address, int root) int addr = address + key % 5 + 1; return addr % root; GetConflictAddress*/依据字符串生 成哈希钥匙码，这里的方法是将串内全部字符以数值形式求累加和*/ CreateKey(char * name) int key = 0; unsi
3、gned char * n = (unsigned char *)name; while(*n) key +=*n+;return key;CreateKey*/ 输入一个名字，并返回哈希钥匙码*/ GetName(char*name)scanf(“%s“,name);returnCreateKey(name); CreateKey*/依据同学人数、长度和哈希根构造哈希表*/ THash * CreateNames(int size, int root, int population) int i =0, key = 0, addr = 0, depth = 0; char name10; s
4、truct THash * h = 0, *hash = 0; /*哈希根和长度不能太小*/ if(size root | root 2) return 0; /*依据哈希表长度构造一个空的哈希表*/ hash = (struct THash *)malloc(sizeof(struct THash) * size); /* 将整个表清空*/ memset(hash, 0, sizeof(struct THash) * size); for(i = 0; i depth = 0) /*假设当前哈希地址没有被占用，那么存入数据*/ h-key = key;strcpy(h-name , name
5、);h-depth +;continue;/*end if*/*假设哈希地址已经被占用了，就是说有冲突，那么查找一个新地址，直到没有被占用 */ depth = 0;while(h-depth ) addr = GetConflictAddress(key, addr, root);h = hash+ addr;depth +;/*end while*/*依据新地址存放数据，同时记录检索深度*/ h-key = key;strcpy(h-name , name);h-depth = depth + 1; /*next*/ return hash; CreateNames*/ 在哈希表中以特定哈
6、希根查找一个同学的记录 */ THash * Lookup(struct THash * hash, char * name, int root) int key = 0, addr = 0; struct THash*h=0;/* 不承受空表和空名称*/if(!name|!hash)return0;key= CreateKey(name); addr = GetHashAddress(key, root); h = hash + addr; /*假设结果不正确表 示 按 照 冲 突 规 那么 继 续 寻 找 */while(strcmp(h-name,name)addr= GetConfli
7、ctAddress(key, addr, root);h = hash + addr;if(h-key = 0) return 0; /*end while*/ return hash + addr; Lookup*/依据一条哈希表记录打印该记录的同学信息*/ Print(struct THash * record) if (!record) printf(“【查无此人】n“); return ; /*end if*/ if(record-depth)printf(“【钥匙码】%04dt【姓名】%st【检索深度】%dn“, record-key, record-name, record-dep
8、th ); elseprintf(“【空记录】n“); if*/ Print*/打印同学花名册*/ Display(struct THash * hash, int size) struct THash* h=0; if (!hash | size 1) return ; printf(“ 同学花名册： n“); printf(“-n“); for(h = hash; h hash + size; h+) printf(“【地址】%dt“, h -hash);Print(h); /*next*/ printf(“n“); Display*/ 主函数，程序入口*/ main(void) /* 哈
9、希表变量声明*/ struct THash * hash = 0, * h = 0; int cmd= 0; /*命令*/ char name10; /*同学姓名*/ /*生成 30 个同学用的哈希表*/ hash =CreateNames(szHASH, HASH_ROOT, POPULATION); for(;) printf(“哈希表呈现：1-显示哈希表；2-检索姓名；其他任意键退出：n“);cmd = getch(); cmd -= ”0”;switch(cmd)case 1: Display(hash, szHASH); break;case 2: printf(“请输入要检索的同学姓名： “);scanf(“%s“, name);h = Lookup(hash, name, HASH_ROOT);printf(“【地址】%dt“,h-hash);Print(h);break;default:free(hash);return 0;/*end case*/ /*next*/ return 0; main*/
