数据结构课程设计

1、数据结构课程设计说明书学院:信息科学与工程学院班级:计算机科学与技术宀兀成人:姓名：学号：指导教师：山东科技大学2013年12月25日课程设计任务书一、 课程设计题目：散列法的实验研究二、课程设计应解决的主要问题：（1）数据元素的输入和输出（2）线性再散列法建立哈希表（3）二次探测再散列法建立哈希表（4）链地址法建立哈希表（5）线性再散列法进行数据查找（6）二次探测再散列法进行数据查找（7）链地址法进行数据查找（8）退出系统三、 任务发出日期：2013-10-01课程设计完成日期：2013-12-20小组分工说明小组编号7题目：散列法的实验研究小组分工情况：一人独立完成所有工作组长签字：201

2、3 年12 月31 日指导教师对课程设计的评价成绩：指导教师签字:目录1需求分析说明-32概要设计说明-43详细设计说明-54调试分析-75用户使用说明-86课程设计总结-107测试结果-108参考书目-12需求分析说明内部排序教学软件的总体功能要求： 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲 突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型 的散列函数构造方法， 做实验观察， 不同的解决冲突方法对查询性能的影响。基本功能如下：（1）界面友好，易与操作。采用菜单方式进行选择。（2）实现三种方法进行哈希表的构造。包括线性再散列法、二次探测再 散列法和链地址

3、法。（ 3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时 输出探查 / 冲突次数。以下是各功能模块的功能描述：1主函数模块 本模块的主要功能是初始化图形界面，调用各模块，实现功能。2构造哈希表子模块本模块的主要功能是采用线性再散列法、 二次探测再散列法、 链地址法三 种方法构造哈希表。3查找功能及输出子模块本模块的主要功能是在采用线性再散列法、 二次探测再散列法、 链地址法 三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算探 查 / 冲突次数。4输入子模块 本模块的主要功能是从键盘中输入数据元素用于构造哈希表。5. 输出子模块本模块的主要功能是将数据元素显示在屏幕

4、上。概要设计说明模块调用图：各种构造方法的哈希表数据类型定义为:typedef structint key; /* int si; /* HashTablel; /*关键字*/ 插入成功时的次数*/哈希表线性探测再散列数据类型定义*/typedef struct Haint elem; /* struct Ha *n ext2; HashTable2; /*数据项*/*指向下一个结点的指针*/哈希表链地址法数据类型定义*/typedef struct int elemHashSize; /* int count;/*表中储存数据元素的数组*/ 表中储存数据元素的个数*/int size;/*哈

5、希表的尺寸*/ HashTable3; /*哈希表二次探测再散列法数据类型定义*/#define HashSize 53 /* 哈希表最大长度*/int num; /*输入数据的个数*/void GetIn(int *a) /*从键盘输入数据*/void GetOut(int *a) /*在屏幕上输出数据*/void CreateHashTable1(HashTable1 *H,i nt *a,i nt num)/* 线性探测在散列 哈希表*/void SearchHash1(HashTable1 *h,int data) /*线性探测在散列法查找 */void CreateHashTable

6、2(HashTable2 *H,int *a,int num)/* 哈希表链地址*/int SearchHash2(HashTable2 *h,int data,int num) /*链地址法查找 */void CreateHash3(HashTable3 *h,int *a,int num) /*二次探索表 */int Collision(int p,int c) /*二次探测再散列法解决冲突*/void SearchHash3(HashTable3 *h,i nt data) /*哈希表二次探索再散列查找*/int system(c onst char *stri ng) /*清屏 */详

7、细设计说明1. 主函数模块首先构造二种类型的哈希表，并对哈希表进行初始化。进入循环后在屏幕 上输出相应的操作指示，然后通过输入0-8调用所选择的函数进行相应操作。主函数代码如下：int mai n()int data,i;HashTablel hash1HashSize;HashTable2 hash2HashSize;HashTable3 * ha;/*定义三种类型的哈希表*/ha=(HashTable3 *)malloc(sizeof(HashTable3);for(i=0; ivHashSize; i+)/*哈希表的初始化 */ha-elemi=0;ha-co un t=0;ha-siz

8、e=HashSize;int aHashSize;a0=0;while(1)printf(nprintf(n1 ); 欢迎使用本系统丨);printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n printf(n); 散列法的实验研究);I【1】.添加数据信息丨);I【2】.数据的输出丨);I【3】.建立哈希表(线性再散列)丨);I【4】.建立哈希表(二次探测再散列)丨);I【5】.建立哈希表(链地址法)丨);I【6】.线性再散列法查找丨

9、);I【7】.二次探测再散列法查找丨);I【8】.链地址法查找丨);I【0】.退出程序丨)；匚);printf(n);printf( 请输入一个任务选项 );int x;scanf(%d,&x); switch(x)case 1: /* GetIn (a); break;case 2: /* if(a0=0) printf( else调用输入函数，从键盘键入需要添加的数据 */若已有数据输入，则调用数据输出函数 */您还没有输入任何数据 !n);GetOut(a); break;case 3:/*if(a0=0) printf( else调用函数用线性再散列法构造哈希表 */您还没有输入任何数

10、据 !n);CreateHashTable1(hash1,a,num);break;case 4:/*调用函数用二次探测再散列法构造哈希表 */if(a0=0) printf( else您还没有输入任何数据 !n);CreateHash3(ha,a,num);break;case 5:/*调用函数用链地址法构造哈希表 */if(a0=0)printf(您还没有输入任何数据 !n); break;case 7:/*if(aO=O) printf( elseprintf( getchar(); prin tf(n getchar();system(cls); 请按回车键返回n);/*清屏*/Cre

11、ateHashTable2(hash2,a ,nu m);break;case 6:/*调用函数用线性再散列法查找*/if(a0=0)printf(您还没有输入任何数据!n);elserprintf(出谕入你代找的戮册);scan f(%d,&data);SearchHash1(hash1,data);调用函数用二次探测再散列法查找*/ 您还没有输入任何数据!n);曲谕入你含找的级据);scan f(%d,&data); SearchHash3(ha,data);break;case 8:/*调用函数用链地址法查找*/if(a0=0)printf(您还没有输入任何数据!n);elseprint

12、f();scan f(%d,&data);SearchHash2(hash2,data ,nu m);break;case 0:/*退出系统*/exit(-1);break;2. 查找功能及输出子模块根据题目要求，可将这个系统分为以下几个模块：1.线性再散列法建立哈希表： 构造哈希函数h(x)二h(key)%HashSize，当 冲突发生时，地址增量di依次取1,2, ，HashSize-1自然数列，即di=1,2, ,HashSize-1 。代码如下：void CreateHashTable1(HashTable1 *H,i nt *a,i nt num)哈希表线性探测再散列int i,d,

13、cnt;for(i=0; ivHashSize; i+)/*Hi.key=0;Hi.si=0;for(i=0; ivnum; i+)cn t=1;d=ai%HashSize; /*给新哈希表初始化数据*/构造哈希函数*/if(Hd.key=0)/*Hd.key=ai;Hd.si=cnt;Else/*无冲突时，直接插入数据*/有冲突时，进行冲突处理后再插入*/dod=(d+1)%HashSize;cnt+;while(Hd.key!=O);Hd.key=ai;Hd.si=cnt;printf(n线性再探索哈希表已建成!);2.二次探测再散列法建立哈希表： 构造哈希函数h(x)=h(key)%Ha

14、shSize , 当冲突发生时，地址增量di依次取-1A2 , -2A2 , ，-kA2数列，即 di= -1A2, -2A2, , -kA2。代码如下：typedef structint elemHashSize; /* int count;/*int size;/* HashTable3;表中储存数据元素的数组 */ 表中储存数据元素的个数 */ 哈希表的尺寸 */int Collision(int p,int c) /*int i,q;i=c/2+1;while(i =0)return q;elsei=c/2+1;else /* 增量为负数时 */q=(p-i*i)%HashSize;c

15、+;if(q=0)return q; elsei=c/2+1; return (-1);void CreateHash3(HashTable3 *h,int *a,int num)/ 二次探测再散列构造哈希表int i,p=-1,c,pp;for(i=0; ielempp!=0) /* 发生冲突 */ pp=Collision(p,c);c+;if（ppvO） /*冲突无法处理*/printf（第个记录无法解决冲突n,i+1）;con ti nue;h-elempp=ai;h-co un t+;printf（第（:个记录冲突次数为%dn,i+1,c）;printf（nn此哈希表容量为%d,当前

16、表内存储的记录个数 %d.n ,n um,h-cou nt）;3. 链地址法建立哈希表：将所有关键字为同义词的记录存储在同一线性链 表中。在链表中插入位置可以为表头或表尾，也可以在中间，以保持同义词 在同一线性链表中按关键字有序。（本程序采用在表尾插入）代码如下：typedef struct Haint elem; /*数据项 */struct Ha *next2; /*指向下一个结点的指针*/ HashTable2;void CreateHashTable2(HashTable2 *H,i nt *a,i nt num)/int key,i;HashTable2 *q,*qq;q=NULL;

17、for (i=0; ivHashSize; i+)/*对哈希表进行初始化*/Hi.elem = 0;Hi. next2=NULL;for (i=0; ivnum; i+)key=ai%HashSize;if(Hkey.elem=0)Hkey.elem=ai;elseif(q!=NULL) /*若该位置已有数据*/qq=q;q=q+1；q-elem=ai;/*添加到已存在的结点后面*/q-n ext2=q q-n ext2;qq-n ext2=q;elseq=(HashTable2*)malloc(sizeof(HashTable2);if(!q)printf(申请内存失败！请重新运行程序n);

18、exit(1);q-elem=ai;/*添加到首结点后面*/q- next2=Hkey. next2;Hkey. next2=q;printf(链表探索哈希表已建成!n);4. 线性再散列法进行查找：根据线性再散列法的构造方式进行相应查找 代码如下：void SearchHash1(HashTable1 *h,i nt data)int d,i; d=data%HashSize; /*哈希函数 */i=d;if(hd.key=data) /*一次查找成功 */printf(数字 %d%dn,hd.key,hd.si);else while(ielempp)!=data & pp!=-1)pp=

19、Collisio n(p,c);C+；if(h-elempp!=0)&(h-elempp)=data)printf(n查找成功!n查找冲突次数为%d.,c);elseprintf(n没有查到此数!n);6. 链地址法进行查找：根据链地址法的构造方式进行相应查找 代码如下：int SearchHash2(HashTable2 *h,i nt data,i nt num)int d,c nt=1;HashTable2 *q;d=data%HashSize; /*哈希函数 */q=&hd;if(q-elem=0) /*该位置上没有数据元素*/printf(没有找到你要查找的那个数n);return

20、0;while(q!=NULL) if(q-elem=data) printf(数字 d勺住找次敛为%dn,data,c nt);return 0;else if(q-n ext2!=NULL)q=q-n ext2;cn t+;elseprintf(没有找到你要查找的那个数n);return 0;return 0;7. 输入函数：从键盘中键入数据。代码如下：void Getl n(int *a)/输入数据函数printf();scan f(%d,&nu m);int i;for(i=0; ivnum; i+)sca nf(%d,&ai);printf(”数据已经输入完毕!n);8. 输出函数：

21、在屏幕上输出数据。代码如下：void GetOut(i nt *a)int i;prin tf(你序倫入的敏据);for( i=0; i根据需要，从0-8选项中选择进入相应模块的操作界面测试结果测试数据：19，14，23, 67, 68，20，84，27, 55, 11，10，79选择1进行数据信息的添加I欢迎使用本系统I厂 ! 散列法的实验研究 1 .添加数据信息|2 .数据的输岀|3 建立哈希表（线性再散列）|I41建立哈希表（二次探测再散列）|I【5】.建立哈希表（链地址法）|61 _线性再散列法查找|7.二次探测再散列法查找|【8】.链地址法查找【0】退出程序II-请输入一个任务选项输

22、入添加的个数1219 14 23 67 68 20 84 27 55 11 10 79 数据已经输入完毕！请按回车键返回返回后，选择3用线性再散列法建立哈希表I欢迎使用本系统厂 散列法的实验研究 II【1】*添加数据信息|II口】-数据的输出III【3】.建立哈希表（线性再散列）|II4.建立哈希表（二次探测再散列）|II5.建立哈希表（链地址法）【6】.线性再散列法查找II7.二次探测再散列法查找|I【8】.链地址法查找|I【0】.退出程序|*-请输入一个任务选项线性再探索哈希表己建成！请按回车键返回返回后，选择6进行线性再散列法查找，如查找19rTTTTTTTTTTTTTTTTTTTTTT

23、TTT欢迎使用本系统 散列法的实验研究 11添加数据信息数据的输出3.建立哈希表（线性再散列）【4】.建立哈希表（二次探测再散列）5.建立哈希表（链地址法）.线性再散列法查找【了】.二次探测再散列法查找【8】.链地址法查找0.退出程序*-请输入一个任务选项 请输入你查找的数据19 数字19的探查次数为1请按回车键返回返回后，选择4用线性再散列法建立哈希表【5】建立哈希表（链地址注）【6】线性再散列注查找71二次探测再散列法查找L8J .链地址法查找0.退岀程序请输入一个任务选顶4第1个记录冲突次数为0第2个记录冲突次数为0第3个记录神突次数为0第4个记录冲突次数为1第5个记录神突次数为1 第6

24、个记录神突次数为0第了个记录冲突次数为。第8个记录神突次数为0 第9个记录神突次数为0第10个记录神突次数为0 第11个记录冲突次数为0 第12个记录冲突次数为0建表完咸此哈希表容量为12,当前表内存储的记录个数12.请按回车键返回返回后，选择7进行二次探测再散列法查找，如查找 67 若查找成功，可得到冲突次数。r欢迎使用本系统1厂 !* * * 散列法的实验硏究 【1】添加数据信息21数据的输岀【3】建立哈希表（线性再散列）【4】建立哈希表（二次探测再散列）欢迎使用本系统厂- * 散列法的实验研究* 【1】.添加数据信息【2】.数据的输出【3】-建立哈希表（线性再散列）4 ,建立哈希表（二次探测再散列）【5】.建立哈希表（链地址法）【6】.线性再散列法查找nr二次探测再散列法查找81 .链地址铉查找0J.退岀程序T 丁 T 丁 丁 丁 T 丁 T T 丁 T T 丁 丁 T 丁 T _找成功!找冲突次数为1请按回车键返回返回后，选择5用链地址法建立哈希表I卷理便毋杏垂邈II 散列法的实验硏究 11 添1IQ数据信息L21数据的输岀