散列法的实验研究.docx

散列法的实验研究.docx

《散列法的实验研究.docx》由会员分享，可在线阅读，更多相关《散列法的实验研究.docx（32页珍藏版）》请在冰点文库上搜索。

散列法的实验研究

散列法的实验研究

学生姓名:

学号:

学院:

专业:

信息管理与信息系统

题目:

散列法的实验研究

成绩

指导教师

2010年12月20日

1设计目的

《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简

单的分析和讨论。

进行数据结构课程设计要达到以下目的:

（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;

（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;

（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力;训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

2.设计内容和要求

设计内容:

（1）散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。

两者是影响查询算法性能的关键因素。

（2）程序实现几种典型的散列函数构造方法，并观察，不同的解决冲突方法对查询性能的影响。

设计要求:

（1）符合课题要求，实现相应功能;

（2）要求界面友好美观，操作方便易行;

（3）注意程序的实用性、安全性;

3（本设计所采用的数据结构

本设计采用散列法，用直接定址法、数字分析法、平方取中法、折叠法、除留余数法五种构造函数及开放定址法（线性探测再散列、二次探测再散列）、链地址法三种解决冲突的方法对散列法进行实验研究。

直接定址法:

将待处理数据x直接赋值给adr,adr为关键字存储在散列表内的位置

adr=x

数字分析法:

提取用户所要求进行分析的数字的位数，将组成新的数字，然后按照直接

定址法对新数字进行存储

intadr,p2=1,q2=1,i;

intp3=p1,q3=q1;//p1为程序接收用户输入的待分析数字所在的位数

//q1为程序接收用户输入的待分析数字所在的位数

intnum=2;

if（p1==1）

p3=x%10;

1

else

{

for（i=1;i

{

p2=p2*10;

p3=x/p2;

p3=p3%10;

}

}

for（i=1;i

{

q2=q2*10;

q3=x/q2;

q3=q3%10;

}

adr=p3+10*q3;

平方取中法:

将待处理数据平方，取平方后的百位、十位作为存储地址

x1=x*x;

a=（x1/100）%10;

b=（x1/10）%10;

adr=a*10+b;

折叠法:

本程序内将待处理数字从低位到高位每三位组成一个新数字，并将所有新数字求

和，产生的新数作为存储地址

if（x<1000）

{

a1=x;

sum=a1;

}

else

{

2

a1=x%1000;

a2=x/1000;

sum=a1+a2;

}

adr=sum;

除留余数法:

将待处理数据除M=979所得余数作为数据的存储地址

adr=x%M;

线性探测再散列:

adr=（adr+d）%Md=1,2……

二次线性探测再散列:

adr=（adr+d）%Md=1*1,-1*1,2*2,-2*2……

intp=1,q=0,b=-1;

p=b*（p+q）*（p+q）;

if（num%2==1）

p=-p;

else

q++;

num++;

adr=（abs（x+p））%M;

链地址法:

本程序采用二维数组P[60][60]代替链表对数据进行处理与存储，用二维数组的

行存储数据存储的地址，二维数字的列存储已经进行处理的数据

intj;

for（j=0;j<60;j++）

{

if（P[adr][j]==0）

{

ha[adr].location=adr;

ha[adr].key=x;

P[adr][j]=x;

}

开放定址法查找成功的平均查找长度:

inti;

3

ints=0,n=0;

for（i=0;i

{

if（ha[i].key!

=0）

{

s=s+ha[i].count;

n++;

}

}

ASL=s*1.0/n

链地址法查找成功的平均查找长度:

intp,q,s=0;

for（p=0;p<60;p++）

{

for（q=0;q<60;q++）

{

if（array[p][q]!

=0）s=s+（q+1）;

elsebreak;

}

}

ASL=s*1.0/n;

4（功能模块详细设计

4.1详细设计思想

散列法中，散列函数构造方法多种多样，而且对于同种散列函数解决冲突的方法也各有不同。

因此我们要关注不同构造方法结合不同解决冲突的方法对算法性能的影响，以此来判定在存储某类数据时，不同方法对查询性能。

本程序主要就直接定址法、数字分析法、平方取中法、折叠法、除留余数法五种构造函数及开放定址法（线性探测再散列、二次探测再散列）、链地址法三种解决冲突的方法对散列法进行实验研究。

根据不同的待处理数据类型选择不同的构造函数及处理冲突的方法，由采用的不同的方法对其查找成功的平均查找长度进行计算，以此来比较不同算法的性能。

4

用户首先根据提示输入待处理数据的个数及待处理的数据，再由程序所给的选项选择构造函数及处理冲突的方法，本程序设计共设计了十五种构造函数及解决冲突的方法:

线性探测再散列）函数名称:

addressDirectlyColl11.直接地址法（

该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用开放

定址法中的线性探测再散列处理冲突，H=（H（key）+d）%M,d为增量序列，且d=1,2…2.直接地址法（二次线性探测再散列）函数名称:

addressDirectlyColl2

该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用开放

定址法中的二次线性探测再散列处理冲突，H=（H（key）+d）%M,d为增量序列，且

d=1,-1,4，-4…

3.直接地址法（链地址法）函数名称:

addressDirectlyColl3

该方法取关键字直接作为散列表的地址，若将要存入的地址已经有关键字，则运用链地

址法处理冲突，将所有关键字为同义词的记录存储在同一线性表中。

但在此程序中将二

维数组代替链表，二维数组的行定义为散列地址，列依次存放关键字。

4.数字分析法（线性探测再散列）函数名称:

numericalMethodColl1

若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址，

遇到冲突时的解决方法与第一个函数的解决冲突方法相同。

5.数字分析法（二次线性探测再散列）函数名称:

numericalMethodColl2

若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址，

遇到冲突时的解决方法与第二个函数的解决冲突方法相同。

6.数字分析法（链地址法）函数名称:

numericalMethodColl3

若所有关键字可知，则可取关键字其中任意两位出现频率较随机的数字作为散列地址，

遇到冲突时的解决方法与第三个函数的解决冲突方法相同。

7.平方取中法（线性探测再散列）函数名称:

mid_squareMethodColl1

取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第一个函数的解决冲

突方法相同。

8.平方取中法（二次线性探测再散列）函数名称:

mid_squareMethodColl2

取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第二个函数的解决冲

突方法相同。

9.平方取中法（链地址法）函数名称:

mid_squareMethodColl3

取关键字平方后的中间几位为散列地址，遇到冲突时的解决方法与第三个函数的解决冲

5

突方法相同。

10.折叠法（线性探测再散列）函数名称:

foldMethodColl1

将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突

时的解决方法与第一个函数的解决冲突方法相同。

函数名称:

foldMethodColl211.折叠法（二次线性探测再散列）

将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突

时的解决方法与第二个函数的解决冲突方法相同。

12.折叠法（链地址法）函数名称:

foldMethodColl3

将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址，遇到冲突

时的解决方法与第三个函数的解决冲突方法相同。

13.除留余数法（线性探测再散列）函数名称:

divisionMethodColl1

取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方

法与第一个函数的解决冲突方法相同。

14.除留余数法（二次线性探测再散列）函数名称:

divisionMethodColl2

取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方

法与第二个函数的解决冲突方法相同。

15.除留余数法（链地址法）函数名称:

divisionMethodColl3

取关键字被某个不大于散列表表长的数除后所得余数为散列地址，遇到冲突时的解决方

法与第三个函数的解决冲突方法相同。

在对待处理数据全部处完毕后再有程序输出所用方法查找数据成功的平均查找长度。

根据程序输出的数据存储位置及存储的次数以及查找数据成功的平均查找长度来分析使用不同的构造方法及处理冲突的方法对算法性能的影响。

4.2核心代码

#include

#include

#include

#include

#include

#defineSUCCESS1

#defineMAXSIZE800

6

#defineM797

/*元素类型的定义*/

typedefstruct{

intlocation;

intkey;

intcount;

}HashTable[MAXSIZE];

HashTableha;

/*散列表初始化*/

voidinit（HashTableha）

{

inti;

for（i=0;i<800;i++）

{

ha[i].location=0;

ha[i].key=0;

ha[i].count=0;

}

}

/*选择构造函数界面*/

voidfunctionUI1（）

{

printf（"*************************请选择构造函数:

**************************\n"）;

printf（"*1、直接地址法（线性探测再散列）*\n"）;

printf（"*2、直接地址法（二次线性探测再散列）*\n"）;

printf（"*3、直接地址法（链地址法）*\n"）;

printf（"*4、数字分析法（线性探测再散列）*\n"）;

7

printf（"*5、数字分析法（二次线性探测再散列）*\n"）;

printf（"*6、数字分析法（链地址法）*\n"）;

printf（"*7、平方取中法（线性探测再散列）*\n"）;

printf（"*8、平方取中法（二次线性探测再散列）*\n"）;

printf（"*9、平方取中法（链地址法）*\n"）;

printf（"*10、折叠法（线性探测再散列）*\n"）;

printf（"*11、折叠法（二次线性探测再散列）*\n"）;

printf（"*12、折叠法（链地址法）*\n"）;

printf（"*13、除留余数法（线性探测再散列）*\n"）;

printf（"*14、除留余数法（二次线性探测再散列）*\n"）;

printf（"*15、除留余数法（链地址法）*\n"）;

printf（"*0、退出实验系统*\n"）;

printf（"******************************************************************\n\n

"）;

}

/*计算查找成功的平均长度*/

voidcompASL（HashTableha,intlength）

{

inti;

ints=0,n=0;

for（i=0;i

{

if（ha[i].key!

=0）

{

s=s+ha[i].count;

n++;

}

}

printf（"********查找成功的ASL=%f********

8

\n",s*1.0/n）;

printf（"******************************************************************\n\n

"）;

}

/*链地址法的平均查找长度*/

voidColl3ASL（intarray[60][60],intn）{

intp,q,s=0;

for（p=0;p<60;p++）

{

for（q=0;q<60;q++）

{

if（array[p][q]!

=0）s=s+（q+1）;

elsebreak;

}

}

printf（"********查找成功的ASL=%f********

\n",s*1.0/n）;

printf（"******************************************************************\n\n"）;

}

/*线性探测散列*/

voidColl1（HashTableha,intx,intadr,intnum）{

adr=（adr+1）%M;

A:

if（ha[adr].key==0）

9

{

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=num;

}

else{adr=（adr+1）%M;num++;gotoA;}

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表\n",ha[adr].key,ha[adr].location,ha[adr].count）;

}

/*二次线性探测再散列*/

voidColl2（HashTableha,intadr,intx,intnum）

{

intp=1,q=0,b=-1;

A:

p=b*（p+q）*（p+q）;

if（num%2==1）

p=-p;

else

q++;

num++;

adr=（abs（x+p））%M;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=num;

}

else{p=abs（p）;gotoA;}

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表

10

\n",ha[adr].key,ha[adr].location,ha[adr].count）;

num=1;

}

/*链地址法*/

voidColl3（HashTableha,intP[60][60],intadr,intx）

{

intj;

for（j=0;j<60;j++）

{

if（P[adr][j]==0）

{

ha[adr].location=adr;

ha[adr].key=x;

P[adr][j]=x;

printf（"*%d在散列表的第%d个位置\n",x,ha[adr].location）;

break;

}

}

}

/*直接地址法线性探测再散列*/

voidaddressDirectlyColl1（HashTableha,intn,intx,intj）

{

intnum=2;

intadr;

if（j==0）

{

printf（"**本方法构造函数为:

直接地址法，解决冲突的方法为:

线性探测再散列**\n"）;

11

}

adr=x;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=1;

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表\n",x,ha[adr].location,ha[adr].count）;

}

else

{

Coll1（ha,x,adr,num）;

}

}

/*直接地址法二次线性探测再散列*/

voidaddressDirectlyColl2（HashTableha,intn,intx,intj）

{

intnum=1;

intadr;

if（j==0）

{

printf（"*本方法构造函数为:

直接地址法，解决冲突的方法为:

二次线性探测再散列*\n"）;

}

adr=x;

if（ha[adr].key==0）

{

12

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=1;

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表\n",x,ha[adr].location,ha[adr].count）;

}

else

{

Coll2（ha,adr,x,num）;

}

}

/*直接地址法链地址法*/

voidaddressDirectlyColl3（HashTableha,intn,intx,intj,intP[60][60]）

{

intadr;

if（j==0）

{

printf（"*****本方法构造函数为:

直接地址法，解决冲突的方法为:

链地址法*****\n"）;

}

adr=x;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

P[adr][0]=x;

13

printf（"*%d在散列表的第%d个位置\n",x,ha[adr].location）;

}

else

Coll3（ha,P,adr,x）;}

/*数字分析法线性探测再散列*/

voidnumericalMethodColl1（HashTableha,intn,intx,intj,intp1,intq1）

{

intadr,p2=1,q2=1,i;

intp3=p1,q3=q1;

intnum=2;

if（p1==1）

p3=x%10;

else

{

for（i=1;i

{

p2=p2*10;

p3=x/p2;

p3=p3%10;

}

}

for（i=1;i

{

q2=q2*10;

q3=x/q2;

q3=q3%10;

14

}

adr=p3+10*q3;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=1;

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表

\n",x,ha[adr].location,ha[adr].count）;

}

else

{

Coll1（ha,x,adr,num）;

}

}

/*数字分析法二次线性探测再散列*/

voidnumericalMethodColl2（HashTableha,intn,intx,intj,intp1,intq1）

{

intp=1,q=0,num=1,b=-1;

intadr,p2=1,q2=1,i;

if（p1==1）

p1=x%10;

else

{

for（i=1;i

{

p2=p2*10;

p1=x/p2;

15

p1=p1%10;

}

}

if（q1==1）

q1=x%10;

else

{

for（i=1;i

{

q2=q2*10;

q1=x/q2;

q1=q1%10;

}

}

if（p1>q1）

adr=q1+10*p1;

else

adr=p1+10*q1;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

ha[adr].count=1;

printf（"*%d在散列表的第%d个位置，第%d次放入哈希表

\n",x,ha[adr].location,ha[adr].count）;

}

else

{

Coll2（ha,adr,x,num）;

}

16

}

/*数字分析链地址法*/

voidnumericalMethodColl3（HashTableha,intn,intx,intj,intp1,intq1,intP[60][60]）

{

intp=1,q=0,num=1,b=-1;

intadr,p2=1,q2=1,i;

if（p1==1）

p1=x%10;

else

{

for（i=1;i

{

p2=p2*10;

p1=x/p2;

p1=p1%10;

}

}

if（q1==1）

q1=x%10;

else

{

for（i=1;i

{

q2=q2*10;

q1=x/q2;

q1=q1%10;

}

}

if（p1>q1）

17

adr=q1+10*p1;

else

adr=p1+10*q1;

if（ha[adr].key==0）

{

ha[adr].location=adr;

ha[adr].key=x;

P[adr][0]=x;

printf（"*%d在散列表的第%d个位置\n",x,ha[adr].location）;

}

else

Coll3（ha,P,adr,x）;

}

/*平方取中法线性探测再散列*/

voidmid_squareMeth