数据结构课程设计散列法的研究_数据结构课程设计说明

数据结构课程设计散列法的研究由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计说明”。

学 院：班 级：完 成 人：姓 指导教师：

数据结构课程设计

说 明 书

信息科学与工程学院 计算机科学与技术 名： 学 号：

山 东 科 技 大 学 2013年12月25日

课 程 设 计 任 务 书

一、课程设计题目： 散列法的实验研究

二、课程设计应解决的主要问题：

（1）数据元素的输入和输出（2）线性再散列法建立哈希表（3）二次探测再散列法建立哈希表（4）链地址法建立哈希表（5）线性再散列法进行数据查找（6）二次探测再散列法进行数据查找（7）链地址法进行数据查找（8）退出系统

三、任务发出日期： 2013-10-01 课程设计完成日期： 2013-12-20

小组分工说明

小组编号 7 题 目： 散列法的实验研究 小组分工情况： 一人独立完成所有工作。

组长签字： 2013 年 12 月 31 日

指导教师对课程设计的评价

成绩：

指导教师签字：

年 月 日

目 录

1．需求分析说明

2．概要设计说明

3．详细设计说明

4．调试分析

5．用户使用说明

6．课程设计总结

7．测试结果

8．参考书目

-3-4-5-7-8-10-10-12

需求分析说明

内部排序教学软件的总体功能要求：

散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。

基本功能如下：

（1）界面友好，易与操作。采用菜单方式进行选择。

（2）实现三种方法进行哈希表的构造。包括线性再散列法、二次探测再散列法和链地址法。

（3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时输出探查/冲突次数。

以下是各功能模块的功能描述： 1．主函数模块

本模块的主要功能是初始化图形界面，调用各模块，实现功能。2．构造哈希表子模块

本模块的主要功能是采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表。

3．查找功能及输出子模块

本模块的主要功能是在采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算探查/冲突次数。4．输入子模块

本模块的主要功能是从键盘中输入数据元素用于构造哈希表。5.输出子模块

本模块的主要功能是将数据元素显示在屏幕上。

概要设计说明

模块调用图：

各种构造方法的哈希表数据类型定义为： typedef struct { int key;/*关键字*/ int si;/*插入成功时的次数*/ } HashTable1;/*哈希表线性探测再散列数据类型定义*/

typedef struct Ha { int elem;/*数据项*/ struct Ha *next2;/*指向下一个结点的指针*/ } HashTable2;/*哈希表链地址法数据类型定义*/

typedef struct { int elem[HashSize];/*表中储存数据元素的数组*/ int count;/*表中储存数据元素的个数*/ int size;/*哈希表的尺寸*/ } HashTable3;/*哈希表二次探测再散列法数据类型定义*/

#define HashSize 53 /*哈希表最大长度*/ int num;/*输入数据的个数*/

void GetIn(int *a)/*从键盘输入数据*/ void GetOut(int *a)/*在屏幕上输出数据*/ void CreateHashTable1(HashTable1 *H,int *a,int num)/*线性探测在散列哈希表*/ void SearchHash1(HashTable1 *h,int data)/*线性探测在散列法查找*/ void CreateHashTable2(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,int data)/*哈希表二次探索再散列查找*/ int system(const char *string)/*清屏*/

详细设计说明

1． 主函数模块

首先构造三种类型的哈希表，并对哈希表进行初始化。进入循环后在屏幕上输出相应的操作指示，然后通过输入0-8调用所选择的函数进行相应操作。主函数代码如下：

int main(){ int data,i;HashTable1 hash1[HashSize];HashTable2 hash2[HashSize];HashTable3 * ha;/*定义三种类型的哈希表*/ ha=(HashTable3 *)malloc(sizeof(HashTable3));for(i=0;ielem[i]=0;ha->count=0;ha->size=HashSize;int a[HashSize];a[0]=0;while(1){ printf(“n ┏━━━━━━━━━━━━━━━┓ ”);printf(“n ┃ 欢迎使用本系统 ┃ ”);printf(“n ┏〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┓”);printf(“n ┃★ ★ ★ ★ ★ ★散列法的实验研究★ ★ ★ ★ ★┃”);printf(“n ┃ 【1】.添加数据信息 ┃”);printf(“n ┃ 【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){ case 1: /*调用输入函数，从键盘键入需要添加的数据*/ GetIn(a);break;case 2: /*若已有数据输入，则调用数据输出函数*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else GetOut(a);break;case 3: /*调用函数用线性再散列法构造哈希表*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else CreateHashTable1(hash1,a,num);break;case 4: /*调用函数用二次探测再散列法构造哈希表*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else CreateHash3(ha,a,num);break;case 5: /*调用函数用链地址法构造哈希表*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else CreateHashTable2(hash2,a,num);break;case 6: /*调用函数用线性再散列法查找*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else { printf(“”);scanf(“%d”,&data);SearchHash1(hash1,data);} break;case 7: /*调用函数用二次探测再散列法查找*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else { printf(“”);scanf(“%d”,&data);SearchHash3(ha,data);} break;case 8: /*调用函数用链地址法查找*/ if(a[0]==0)printf(“您还没有输入任何数据!n”);else {

printf(“”);scanf(“%d”,&data);SearchHash2(hash2,data,num);} break;case 0: /*退出系统*/ exit(-1);break;

} getchar();printf(“n请按回车键返回n”);getchar();system(“cls”);/*清屏*/ } } 2． 查找功能及输出子模块

根据题目要求，可将这个系统分为以下几个模块：

1.线性再散列法建立哈希表：构造哈希函数 h(x)=h(key)%HashSize，当冲突发生时，地址增量di依次取1,2,···,HashSize-1自然数列,即di=1,2,···,HashSize-1。

代码如下：

void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表线性探测再散列 { int i,d,cnt;for(i=0;i

代码如下：

typedef struct { int elem[HashSize];/*表中储存数据元素的数组*/ 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;} 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;ielem[pp]!=0)/*发生冲突*/ { pp=Collision(p,c);c++;if(ppelem[pp]=a[i];h->count++;printf(“第%d个记录冲突次数为%dn”,i+1,c);} printf(“nn此哈希表容量为%d,当前表内存储的记录个数%d.n”,num,h->count);}

3.链地址法建立哈希表：将所有关键字为同义词的记录存储在同一线性链表中。在链表中插入位置可以为表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。（本程序采用在表尾插入）

代码如下：

typedef struct Ha { int elem;/*数据项*/ struct Ha *next2;/*指向下一个结点的指针*/ } HashTable2;

void CreateHashTable2(HashTable2 *H,int *a,int num)// { int key,i;HashTable2 *q,*qq;q=NULL;for(i=0;ielem=a[i];/*添加到已存在的结点后面*/ q->next2=qq->next2;qq->next2=q;} else { q=(HashTable2*)malloc(sizeof(HashTable2));if(!q){ printf(“申请内存失败!请重新运行程序n”);exit(1);} q->elem=a[i];/*添加到首结点后面*/ q->next2=H[key].next2;H[key].next2=q;} } } printf(“链表探索哈希表已建成!n”);}

4.线性再散列法进行查找：根据线性再散列法的构造方式进行相应查找。代码如下：

void SearchHash1(HashTable1 *h,int data){ int d,i;d=data%HashSize;/*哈希函数*/ i=d;if(h[d].key==data)/*一次查找成功*/ printf(“数字%d%dn”,h[d].key,h[d].si);else { while(i

5.二次探测再散列法进行查找：根据二次探测再散列法的构造方式进行相应查找。

代码如下：

void SearchHash3(HashTable3 *h,int data)//哈希表二次探索再散列查找 { int c=0,p,pp;p=data%HashSize;pp=p;while((h->elem[pp])!=data && pp!=-1){ pp=Collision(p,c);c++;} if((h->elem[pp]!=0)&&(h->elem[pp])==data)printf(“n查找成功!n查找冲突次数为%d.”,c);else printf(“n没有查到此数!n”);}

6.链地址法进行查找：根据链地址法的构造方式进行相应查找。代码如下：

int SearchHash2(HashTable2 *h,int data,int num){ int d,cnt=1;HashTable2 *q;d=data%HashSize;/*哈希函数*/ q=&h[d];if(q->elem==0)/*该位置上没有数据元素*/ { printf(“没有找到你要查找的那个数n”);return 0;} while(q!=NULL){ if(q->elem==data){ printf(“数字%d%dn”,data,cnt);return 0;} else if(q->next2!=NULL){ q=q->next2;cnt++;} else { printf(“没有找到你要查找的那个数n”);return 0;} } return 0;}

7.输入函数：从键盘中键入数据。代码如下：

void GetIn(int *a){ //输入数据函数 printf(“”);scanf(“%d”,&num);int i;for(i=0;i

8.输出函数：在屏幕上输出数据。代码如下：

void GetOut(int *a){ int i;printf(“”);for(i=0;i

调试分析

我遇到的问题：

 链地址法查找时，原设计在有冲突时表尾插入，写出的程序却是在表头进行插入。在加入了一个判断语句和移动指针位置的语句后问题得到解决。

 图形界面下输入数据  在程序显示结果后无法返回界面0 在结果界面上增加一个按钮Restart，利用goto语句即可返回到界面0。

用户使用说明

运行程序时，首先进入主菜单界面：

根据需要，从0-8选项中选择进入相应模块的操作界面。

测试结果

测试数据：19，14，23，67，68，20，84，27，55，11，10，79 选择1进行数据信息的添加

返回后，选择3用线性再散列法建立哈希表

返回后，选择6进行线性再散列法查找，如查找19

返回后，选择4用线性再散列法建立哈希表

返回后，选择7进行二次探测再散列法查找，如查找67 若查找成功，可得到冲突次数。

返回后，选择5用链地址法建立哈希表

返回后，选择8进行二次探测再散列法查找，如查找67

最后，选择0可退出程序。

课程设计总结

通过这次数据结构课程设计，使我对计算机语言有了更深一层的了解，也使我对算法的运用有了更熟练的掌握，对算法和生活的联系也有了更多的体会。更进一步了解和熟悉了关于哈希表的创建和运用。现在，计算机领域只向我展现了冰山一角，以后我会继续探索。好的算法源于我们不断的思考，思考源于我们对梦想的追寻。

书本上理论性的东西在实际应用中还是有一定的出入的，因此在这次数据结构设计中遇到了很多实际性的问题。很多问题要不断的更正以前的错误思维。通过这次设计，我懂得了学习的重要性，了解到理论知识与实践结合的重要意义。学会了坚持、耐心和努力，这将为自己今后的学习和工作打下牢固的基础。通过学习，对专业知识了解更多，学会如何把自己平时所学的东西应用到实际中。

一个人要完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意各个方面的能力的协调发展，选择一两门技术进行深入研究，成为一个既可以统筹全局，又有一定技术专长的优秀的程序开发人员。

参考书目

[1] 数据结构（C语言版），严蔚敏，清华大学出版社 [2] 数据结构题集（C语言版），严蔚敏，清华大学出版社 [3] C语言课程设计案例精编，郭翠英，中国水利出版社