登 录
#include <conio.h><br /> #include <memory.h><br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <string.h><br /> #define szNAME 80<br /> #define HASH_ROOT 47 /*用于计算哈希地址的随机数*/<br /> #define szHASH 50 /*哈希表总长度*/<br /> #define POPULATION 30 /*学生总数*/</p> <p>/*哈希表结构体*/<br /> struct THash {<br /> int key; /*钥匙码*/<br /> char name[10]; /*姓名*/<br /> int depth; /*检索深度*/<br /> };</p> <p>/*根据钥匙码和哈希根计算哈希地址*/<br /> int GetHashAddress(int key, int root)<br /> {<br /> return key % root;<br /> }/*end GetHashAddress*/</p> <p>/*冲突地址计算，如果发现地址冲突，则用当前地址和钥匙码、哈希根重新生成一个新地址*/<br /> int GetConflictAddress(int key, int address, int root)<br /> {<br /> int addr = address + key % 5 + 1;<br /> return addr % root;<br /> }/*end GetConflictAddress*/</p> <p>/*根据字符串生成哈希钥匙码，这里的方法是将串内所有字符以数值形式求累加和*/<br /> int CreateKey(char * name)<br /> {<br /> int key = 0;<br /> unsigned char * n = (unsigned char *)name;<br /> while(*n) key += *n++;<br /> return key;<br /> }/*end CreateKey*/</p> <p>/*输入一个名字，并返回哈希钥匙码*/<br /> int GetName(char * name)<br /> {<br /> scanf("%s", name);<br /> return CreateKey(name);<br /> }/*end CreateKey*/</p> <p>/*根据学生人数、长度和哈希根构造哈希表*/<br /> struct THash * CreateNames(int size, int root, int population)<br /> {<br /> int i =0, key = 0, addr = 0, depth = 0; char name[10];<br /> struct THash * h = 0, *hash = 0;</p> <p> /*哈希根和长度不能太小*/<br /> if(size < root || root < 2) return 0;</p> <p> /*根据哈希表长度构造一个空的哈希表*/<br /> hash = (struct THash *)malloc(sizeof(struct THash) * size);</p> <p> /*将整个表清空*/<br /> memset(hash, 0, sizeof(struct THash) * size);</p> <p> for(i = 0; i < population; i++) {<br /> /*首先产生一个随机的学生姓名，并根据姓名计算哈希钥匙码，再根据钥匙码计算地址*/<br /> key = GetName(name);<br /> addr = GetHashAddress(key, root);<br /> h = hash + addr;<br /> if (h->depth == 0) { /*如果当前哈希地址没有被占用，则存入数据*/<br /> h->key = key;<br /> strcpy(h->name , name);<br /> h->depth ++;<br /> continue;<br /> }/*end if*/<br /> /*如果哈希地址已经被占用了，就是说有冲突，则寻找一个新地址，直到没有被占用*/<br /> depth = 0;<br /> while(h->depth ) {<br /> addr = GetConflictAddress(key, addr, root);<br /> h = hash + addr;<br /> depth ++;<br /> }/*end while*/<br /> /*按照新地址存放数据，同时记录检索深度*/<br /> h->key = key;<br /> strcpy(h->name , name);<br /> h->depth = depth + 1;<br /> }/*next*/<br /> return hash;<br /> }/*end CreateNames*/</p> <p>/*在哈希表中以特定哈希根查找一个学生的记录*/<br /> struct THash * Lookup(struct THash * hash, char * name, int root)<br /> {<br /> int key = 0, addr = 0; struct THash * h = 0;<br /> /*不接受空表和空名称*/<br /> if(!name || !hash) return 0;<br /> key = CreateKey(name);<br /> addr = GetHashAddress(key, root);<br /> h = hash + addr;<br /> /*如果结果不正确表示按照冲突规则继续寻找*/<br /> while(strcmp(h->name , name)) {<br /> addr = GetConflictAddress(key, addr, root);<br /> h = hash + addr;<br /> if(h->key == 0) return 0;<br /> }/*end while*/<br /> return hash + addr;<br /> }/*end Lookup*/</p> <p>/*根据一条哈希表记录打印该记录的学生信息*/<br /> void Print(struct THash * record)<br /> {<br /> if (!record) {<br /> printf("【查无此人】/n");<br /> return ;<br /> }/*end if*/<br /> if(record->depth)<br /> printf("【钥匙码】%04d/t【姓名】%s/t【检索深度】%d/n", record->key, record->name, record->depth );<br /> else<br /> printf("【空记录】/n");<br /> /*end if*/<br /> }/*end Print*/</p> <p>/*打印学生花名册*/<br /> void Display(struct THash * hash, int size)<br /> {<br /> struct THash * h = 0;<br /> if (!hash || size < 1) return ;<br /> printf("学生花名册：/n");<br /> printf("--------------------/n");<br /> for(h = hash; h < hash + size; h++) {<br /> printf("【地址】%d/t", h - hash);<br /> Print(h);<br /> }/*next*/<br /> printf("--------------------/n");<br /> }/*end Display*/</p> <p>/*主函数，程序入口*/<br /> int main(void)<br /> {<br /> /*哈希表变量声明*/<br /> struct THash * hash = 0, * h = 0;<br /> int cmd = 0; /*命令*/<br /> char name[10]; /*学生姓名*/</p> <p> /*生成30个学生用的哈希表*/<br /> hash = CreateNames(szHASH, HASH_ROOT, POPULATION);<br /> for(;;) {<br /> printf("哈希表展示：1-显示哈希表；2-检索姓名；其他任意键退出：/n");<br /> cmd = getch();<br /> cmd -= '0';<br /> switch(cmd) {<br /> case 1: Display(hash, szHASH); break;<br /> case 2:<br /> printf("请输入要检索的学生姓名：");<br /> scanf("%s", name);<br /> h = Lookup(hash, name, HASH_ROOT);<br /> printf("【地址】%d/t", h - hash);<br /> Print(h);<br /> break;<br /> default:<br /> free(hash);<br /> return 0;<br /> }/*end case*/<br /> }/*next*/<br /> return 0;<br /> }/*end main*/
抱歉!评论已关闭.