《数据结构课程设计-散列表的设计与实现讲述》由会员分享，可在线阅读，更多相关《数据结构课程设计-散列表的设计与实现讲述（12页珍藏版）》请在金锄头文库上搜索。
1、散列表的设计与实现 计14本1 1412210116 王国栋 榆林学院14届课程设计 散列表 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键 码值映射到表中一个位置来访问记录，以加快查找的速度。这 个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入 函数后若能得到包含该关键字的记录在表中的地址，则称表M为 哈希(Hash）表，函数f(key)为哈希(Hash) 函数。 处理冲突的方法 1. 开放寻址法：Hi=(H(key) + di) MOD m,
2、i=1,2，k(k=0) return q; else i=c/2+1; return UNSUCCESS; 处理冲突函数： 采用二次探测再 散列法处理冲突 void CreateHash1(HashTable* H,Record* a) /建表，以人的姓名为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp= /求得哈希地址，将信息存入 H-count+; printf(“第%d个记录冲突次数为%d。n“,i+1,c)
3、;/需要显示冲突次数时输出 printf(“n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为 %d.n“,HASHSIZE,H-count); benGetTime(); 程序主要代码 void SearchHash1(HashTable* H,int NA str; printf(“n请输入要查找记录的姓名：n“); scanf(“%s“,str); int p,pp; p=Hash1(str); pp=p; while(H-elempp!=NULL) if(H-elempp!=NULL printf(“姓 名：%sn电话号码：%sn联系地址：%sn“,H- elempp-name
4、,H-elempp-tel,H-elempp-add); else printf(“n此人不存在，查找不成功!n“); benGetTime(); 程序主要代码 void CreateHash2(HashTable* H,Record* a) /建表，以电话号码为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp= /求得哈希地址，将信息存入 H-count+; printf(“第%d个记录冲突次数为%d。n“,i+1,
5、c);/需要显示冲突次数时输出 printf(“n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为 %d.n“,HASHSIZE,H-count); benGetTime(); 程序主要代码 void SearchHash2(HashTable* H,int NA tele; printf(“n请输入要查找记录的电话号码：n“); scanf(“%s“,tele); int p,pp; p=Hash2(tele); pp=p; while(H-elempp!=NULL) if(H-elempp!=NULL printf(“姓 名：%sn电话号码：%sn联系地址：%sn“,H- elempp-name,H-elempp-tel,H-elempp-add); else printf(“n此人不存在，查找不成功!n“); benGetTime(); 程序主要代码 系统运行主页面 Thank you!
