数据结构课程设计散列表的设计与实现分析.ppt

“ ” “ ” 散列表的设计与实现 计14本1 1412210116 王国栋 榆林学院14届课程设计 散列表 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。 处理冲突的方法 1.?开放寻址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k=m-1），其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1.1. di=1,2,3，…，m-1，称线性探测再散列； 1.2. di=1^2,-1^2,2^2,-2^2，⑶^2，…，±（k)^2,(k=m/2）称二次探测再散列； 1.3. di=伪随机数序列，称伪随机探测再散列。 2. 再散列法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。 3. 链地址法（拉链法） 4. 建立一个公共溢出区 通讯录的实现 每个记录需要有存储的数据：姓名、电话、地址； 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 采用一定的方法解决冲突； 查找并显示给定电话号码的记录； 查找并显示给定用户名的记录。 【进一步完成内容】 1)系统功能的完善； 2)设计不同的散列函数，比较冲突率； 3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 系统运行流程 系统功能如下: 添加用户信息; 读取所有用户信息; 以姓名建立哈希表; 以电话号码建立哈希表; 查找并显示给定用户名的记录; 查找并显示给定电话号码的记录; 清屏以及保存功能； 程序主要代码 Status collision(int p,int c) { //冲突处理函数，采用二次探测再散列法解决冲突 int i,q; i=c/2+1; while(iHASHSIZE) { if(c%2==0) { c++; q=(p+i*i)%HASHSIZE; if(q=0) return q; else i=c/2+1; } else{ q=(p-i*i)%HASHSIZE; c++; if(q=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;iNUM_BER;i++) { c=0; p=Hash1(a[i].name); pp=p; while(H-elem[pp]!=NULL) { pp=collision(p,c); if(pp0) { printf(第%d记录无法解决冲突,i+1);//需要显示冲突次数时输出 continue; } //无法解决冲突，跳入下一循环 } H-elem[pp]=(a[i]); //求得哈希地址，将信息存入 H-count++; printf(第%d个记录冲突次数为%d。\n,i+1,c);//需要显示冲突次数时输出 } printf(\n建表完成!\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n,HASHSIZE,H-count); benGetTime(); } 程序主要代码 void SearchHash1(HashTable* H,int c) { //在通讯录里查找姓名关键字，若查找成功，显示信息 //c用来记录冲突次数,查找成功时显示冲突次数 benGetT