《散列法的课程设计说明书.doc》由会员分享，可在线阅读，更多相关《散列法的课程设计说明书.doc（25页珍藏版）》请在三一办公上搜索。
1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名: 淮华瑞学 号：1021010908学 院:软件学院专 业:软件工程题 目:散列表的实验研究指导教师康珺2011年12月20日1. 设计任务概述（包括系统总体框图及功能描述）建立散列表系统总体框图二次探测再散列线性探测再散列链地址法链地址法查找二次探测再散列查找线性探测再散列查找问题描述 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。概要设计 散列又称哈希或杂凑。散列法（Hashing）在
2、表项的存储位置与它的关键码之间建立一个确定的对应函数关系Hash（），以使每个关键码与结构中的唯一存储位置相对应，该关系可用下式表示：Address=Hash（Record.key）相应的表称为哈希表，这种方法的基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。 哈希函数是一个映象，哈希函数的设定灵活，只要使得任何关键字所得的哈希函数值都落在表长范围之内即可。
3、当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1k2，但H(k1)=H(k2)，这种现象称为冲突，此时称k1和k2为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。 综上所述，哈希法主要包括以下两方面的内容。 (1）如何构造哈希函数； (2） 如何处理冲突。2. 本设计所采用的数据结构（如：链表、栈、树、图等）一、散列函数 通常，构造散列函数应该注意的几个问题包括：首先，散列函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址，其值域必须在1m-1之间;其次，散列函数计算出来的地址应能均匀分布在整个地址空间中；再次，散列函数
4、应当是尽量简单的。1直接定址法 直接定址法蓝颜元素关键码的某个线性函数值作为该元素的散列地址（散列地址，即元素最终在字典中的存储位置）。如下面的函数式：Hash（key）=akey+b式中，a，b为常数。采用该种方法，当向字典中加入某一新元素时算法自动调用此函数，以确定该元素最终的存储位置。若某元素关键码key为1，上式中，a=2，b=3则该元素最终会存储在字典第5个位置中。 直接定址法的优点是实现方法简单，算法时间复杂度较小，而且不会产生冲突。但是，直接定址法要求散列地址空间的大小与关键码集合的大小一致，而这种要求是苛刻的，一般很难实现。例如当关键码的范围为11000000时，元素散列地址的
5、个数也要达到1000000。这么大的散列地址是不合实际的。2.除留余数法 设散列表中允许的地址数为m，取一个不大于m，但最接近或等于m的质数k，或选取一个不含有小于20的质因子的合数作为除数。利用下面的式子计算元素的散列地址的方法称为除留余数法。Hash（key）=key%k，km其中，“%”是整数除余法取余的运算，要求这时的质数不是接近2的幂。例如，当元素的关键码key为2008，散列地址总数为50，这时取k=47，则散列地址为Hash（2008）=2008%47=34，所以运算将存储在字典第47个位置中。 除留余数法将有效缩减散列地址空间的大小，例如上例散列地址空间中只有50个有效的散列地
6、址。除留余数法的缺点是极易发生冲突，如关键码为1914的元素经过上述教例函数计算后也将获得散列地址34。此时出现的两个不同元素争用同一存储地址的情况就称为冲突。3.平方取中法 平方取中法是一种常用的实现散列函数的方法。 平方取中法是一种先放大再集合的构造方法，这种构造模式先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值，这种取中间数的方法是一种类随机方案，因此也可以认为平方取中法是一种产生伪随机数的方法。因为一个乘积的中间几位数和乘数的每一位都相关，所以有此产生的散列地址较为均匀。 利用平方取中法实现散列函数的过程：首先，利用一定的编码规则把元素的关键码转换成
7、标识符。然后，求出标识符的内码表示并计算内码的平方值。最后，取内码平方数的中间x位作为元素最终的散列地址。简而言之，即先计算构成关键码表示符的内码平方，然后按照散列表的大小取中间的若干位作为散列地址。 在平方取中法中，地址空间内散列地址的数目一般为2的k次幂，并在计算出内码平方的平方后，根据k的大小决定最终散列地址的位数。例如某个地址空间中散列地址的个数为128，则最终取内码平方中间7位作为元素最终的散列地址。4.乘余取整法 乘余取整法利用下面的式子计算元素的散列地址。Hash（key）=Z（akey%1） 其中，a为一个常数且0a1，Z为一个整数。式akey%1表示akey取小数部分，即ak
8、ey%1= akey- akey 。例如，当元素关键码为2008， 小数a为0.6180339，整数Z为10000，则散列地址计算为Hash（2008）=10000（0.61803392008%1）=120。 乘余取整法不但会缩减散列地址空间的大小，还能极大减小冲突情况的发生几率。Knuth对常数a的取法做了仔细的研究，发现虽然a取任何值都可以，但一般取黄金分割数0.6180339比较好。5.折叠法折叠法的工作方式很有趣，此方法把关键吗从左至右划分为位数相等的几部分，每一部分的位数与散列地址数相同。当关键码位数不能被散列地址位数整除时，最后一部分可取得短些。 折叠法有两种，即位移法和分界法。
9、其中，位移法所采取的具体方式是把各部分的最后一位对齐相加。分界法所采用的具体方式是各部分不折断，而沿各部分的分界来回折叠，然后对齐相加，并将相加的结果当做散列地址。折叠法适用于关键码位数很多，且每一位上数字分布比较均匀的情况。下面通过实例演示这两种方法的工作方式。 设关键码key=987654321，散列地址为4位。位移法和分界法计算散列地址的算式如图所示。9876 98765432 2345 + 1 + 1 15309 12222 移位法 分界法由式可见，位移法计算结果为15309，由于散列地址为4位，所以舍去最高位数字1，元素最终的散列地址为5309。分界法结算结果为12222，同样舍去最
10、高位数字1，元素最终的散列地址为2222。二、散列冲突解决方法在构造散列函数的过程中，不可避免地会出现冲突的情况。所谓处理冲突，就是在有冲突发生时，为产生冲突的关键字找到另一个地址存放该关键字。在解决冲突的过程中，可能会得到一系列散列地址hi（i=1,2，n),也就是发生第一冲突时，经过处理后得到第一新地址记作h1，如果h1仍然会冲突，则处理后得到第二个地址h2，依此类推，直到hn不产生冲突，将hn作为关键字的储存地址。处理冲突的方法比较常用的主要有开放定址法、再散列法和链地址法。1. 开放定址法开放定址法是解决冲突比较常用的方法。开放定址法就是利用散列表中的空地址存储产生冲突的关键字。当冲突
11、发生时，按照下列公式处理冲突：hi=（h（key）+di）%m，其中i=1,2，m-1其中，h（key）为散列函数，m为散列表长，di为地址增量。地址增量di可以以下三种方法获得：（1） 线性探测再散列：当冲突发生时，地址增量di依次取1,2，m-1自然数列，即di=1,2，m-1。（2） 二次探测再散列：在冲突发生时，地址增量di依次取自然数的平方，即di=12，12,22，22，k2，k2。（3） 伪随机数再散列：在冲突发生时，地址增量di依次取随机数序列。例如，在长度为14的散列表中，在将关键字183,123,230,91存放在散列表中的情况如图所示。Hash地址 0 1 2 3 4 5
12、 6 7 8 9 10 11 12 13 18312323091散列表冲突发生前示意图当要插入关键字149时，有散列函数h（149）=149%13=6，而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=（6+1）%14=7，将149储存在单元7中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314923091插入关键字149后的示意图当要插入关键字227时，由散列函数h（227）=227%13=6，而单元6已经存在关键字，产生冲突，利用线性探测再散列法解决冲突，即h1=（6+1）%14=7，仍然冲突，继续利用线性探测法
13、，即h2=（6+2）%14=8，单元8空闲，因此将227存储在单元8中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18312314922723091插入关键字227后的示意图当然，在冲突发生时，也可以利用二次探测再散列解决冲突。在图11.33中，如果要插入关键字227，因为产生冲突，利用二次探测再散列法解决冲突，即h1=（6+1）%14=7，再次产生冲突时，有h2=（61）%14=5，将227储存在单元5中，如图所示。Hash地址 0 1 2 3 4 5 6 7 8 9 10 11 12 13 18322712314923091利用二次探测再散列解
14、决冲突示意图2. 再散列法再散列法就是在冲突发生时，利用另外一个散列函数再次求散列函数的地址，直到冲突不再发生为止，即hi=rehash（key），i=1,2，n其中，rehash表示不同的散列函数。这种再散列法一般不容易再次发生冲突，但是需要事先构造多个散列函数，这是一件不太容易的也不现实的事情。3. 链地址法 数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法链地址法，我们可以理解为“链
15、表的数组”，如图： 左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。三、 哈希法性能分析由于冲突的存在，哈希法仍需进行关键字比较，因此仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个：哈希函数、处理冲突的方法以及哈希表的装填因子。哈希表的装填因子的定义如下： 线性探测再散列 查找成功时 查找失败时 伪随机探测再散列、 二次探测 查找成功时 查找失败时 链址法 查找成功时查找失败时 从以上讨论可知：哈希
16、表的平均查找长度是装填因子的函数，而与待散列元素数目n无关。因此，无论元素数目n有多大，都能通过调整，使哈希表的平均查找长度较小。 3. 功能模块详细设计3.1 详细设计思想 (1)程序中结构体的定义typedef structint key;int si;HashTable1;typedef struct node int key; int si; struct node *next;Node;typedef struct Node *link;HashTable2;typedef struct int * elemHashSize; int count; int size;HashTabl
17、e3;(2) 主函数模块 void main() int data; HashTable1 hash1HashSize; HashTable2 * hash2HashSize; HashTable3 * ha; ha=(HashTable3 *)malloc(sizeof(HashTable3); for(int i=0;ielemi=NULL; ha-count=0; ha-size=HashSize; int aMaxSize; while(1) printf(n ); printf(n 欢迎使用本系统 ); printf(n ); printf(n 散列法的实验研究 ); printf(
18、n 【1】. 添加数据信息 【2】 数据的输出 ); printf(n 【3】. 建立哈希表(线性再散列) ); printf(n 【4】. 建立哈希表(二次探测再散列) ); printf(n 【5】. 建立哈希表(链地址法) ); printf(n 【6】. 线性再散列法查找 ); printf(n 【7】. 二次探测再散列法查找 ); printf(n 【8】. 链地址法查找 ); printf(n 【0】. 退出程序 ); printf(n ); printf(n); printf(n); printf(请输入一个任务选项); int x; scanf(%d,&x); switch(x
19、) case 1: GetIn (a);break; case 2: GetOut(a);break; case 3: CreateHashTable1(hash1,a,num);break; case 4: CreateHash3(ha,a,num);break; case 5: CreateHashTable2(hash2,a,num);break; case 6: printf(请输入你查找的数据：); scanf(%d,&data); SearchHash1(hash1,data);break; case 7: printf(请输入你查找的数据：); scanf(%d,&data);
20、SearchHash3(ha,data);break; case 8: printf(请输入你查找的数据：); scanf(%d,&data); SearchHash2(hash2,data,num);break; case 0:exit(-1); 3.2 核心代码#include#include#define HashSize 53#define MaxSize 20typedef structint key;int si;HashTable1;void CreateHashTable1(HashTable1 *H,int *a,int num)/哈希表线性探测在散列； int i,d,cn
21、t; for(i=0;iHashSize;i+) Hi.key=0; Hi.si=0; for(i=0;inum;i+) cnt=1; d=ai%HashSize; if(Hd.key=0) Hd.key=ai; Hd.si=cnt; else do d=(d+1)%HashSize; cnt+; while(Hd.key!=0); Hd.key=ai; Hd.si=cnt; printf(n线性再探索哈希表已建成!);void SearchHash1(HashTable1 *h,int data) int d; d=data%HashSize; if(hd.key=data) printf(
22、数字%d的探查次数为：%dn,hd.key,hd.si); else do d=(d+1)%HashSize; while(hd.key!=data & dHashSize); if(dHashSize) printf(数字%d的探查次数为：%dn,hd.key,hd.si); else printf(没有查找到你所输入的数n); typedef struct node int key; int si; struct node *next;Node;typedef struct Node *link;HashTable2;void CreateHashTable2(HashTable2 *ht
23、,int *a,int num)/哈希表链地址； int i,d,cnt; Node *s,*q; for(i=0;ilink=NULL; for(i=0;ikey=ai;s-next=NULL; d=ai%num; if(htd-link=NULL) htd-link=s; s-si=cnt; else q=htd-link; while(q-next!=NULL) q=q-next;cnt+; cnt+; s-si=cnt; q-next=s; void SearchHash2(HashTable2 * h,int data,int num) int d; Node *q; d=data%
24、num; q=hd-link; while(q-key!=data & q-next!=NULL) q=q-next; if(q-next!=NULL) printf(数字%d的查找次数为：%dn,q-key,q-next); else printf(没有找到你要查找的那个数n);typedef struct int * elemHashSize; int count; int size;HashTable3;int Collision(int p,int &c)/二次探测再散列法解决冲突 int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1;
25、 else q=(p-i*i)%HashSize; c+; if(q=0)return q; else i=c/2+1; return (-1);void CreateHash3(HashTable3 *h,int *a,int num)/二次探索表 int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=Collision(p,c); if(ppelempp=&(aai); h-count+; printf(第%d个记录冲突次数为%dn,i+1,c); printf(n建表完成！n此哈希表容量为%d,当前表内存储的记录个数%d.n,HashSize,h-coun
26、t);void SearchHash3(HashTable3 *h,int data)/哈希表二次探索再散列查找 int c=0,p,pp; p=data%HashSize; pp=p;while(h-elempp!=NULL)&(*(h-elempp)!=data) pp=Collision(p,c);if(h-elempp!=NULL)&(*(h-elempp)=data) printf(n查找成功!n查找冲突次数为%d:,c);elseprintf(n没有查到此数!n);int num;void GetIn(int *a) printf(输入添加的个数：); scanf(%d,&num)
27、; for(int i=0;inum;i+) scanf(%d,&ai); printf(数据已经输入完毕!n);void GetOut(int *a) printf(你所输入的数据：); for(int i=0;inum;i+) printf(%d,ai); printf(n输出已完毕!);void main() int data; HashTable1 hash1HashSize; HashTable2 * hash2HashSize; HashTable3 * ha; ha=(HashTable3 *)malloc(sizeof(HashTable3); for(int i=0;iele
28、mi=NULL; ha-count=0; ha-size=HashSize; int aMaxSize; while(1) printf(n ); printf(n 欢迎使用本系统 ); printf(n ); printf(n 散列法的实验研究 ); printf(n 【1】. 添加数据信息 【2】 数据的输出 ); printf(n 【3】. 建立哈希表(线性再散列) ); printf(n 【4】. 建立哈希表(二次探测再散列) ); printf(n 【5】. 建立哈希表(链地址法) ); printf(n 【6】. 线性再散列法查找 ); printf(n 【7】. 二次探测再散列法
29、查找 ); printf(n 【8】. 链地址法查找 ); printf(n 【0】. 退出程序 ); printf(n ); printf(n); printf(n); printf(请输入一个任务选项); int x; scanf(%d,&x); switch(x) case 1: GetIn (a);break; case 2: GetOut(a);break; case 3: CreateHashTable1(hash1,a,num);break; case 4: CreateHash3(ha,a,num);break; case 5: CreateHashTable2(hash2,a
30、,num);break; case 6: printf(请输入你查找的数据：); scanf(%d,&data); SearchHash1(hash1,data);break; case 7: printf(请输入你查找的数据：); scanf(%d,&data); SearchHash3(ha,data);break; case 8: printf(请输入你查找的数据：); scanf(%d,&data); SearchHash2(hash2,data,num);break; case 0:exit(-1); 3.3 程序运行结果（拷屏） 利用线性再散列法，二次探查再散列，链地址法解决冲突
31、4. 课程设计心得、存在问题及解决方法(1) 收获通过本次课程设计，使我对计算机语言有了更深一层的了解，也使我对算法的运用有了更多的体会，对算法和生活的联系也有了更多的体会。更进一步了解和熟悉了关于哈希表的创建和运用。现在，计算机领域，他只向我展现了冰山一角，以后我会继续探索。好的算法源于我们不断的思考，思考源于我们对梦想的追寻。(2) 心得体会 在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现。书本上理论性的东西在实际应用中还是有一定的出入的。所以有些问题要不断的更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践结合的重要意义。学会了坚持、耐心和努力，这将为自己今后的学习和工作打下牢固的基础。通过学习，对专业知识了解更多，学会如何把自己平时所学的东西应用到实际中。
