数据结构课程设计-散列法的研究

数据结构课程设计说明书学院：信息科学与工程学院班级：计算机科学与技术完成人：姓名：学号：指导教师：山东科技大学2013年12月25日课程设计任务书一、课程设计题目：散列法的实验研究二、课程设计应解决的主要问题：（1）数据元素的输入和输出（2）线性再散列法建立哈希表（3）二次探测再散列法建立哈希表（4）链地址法建立哈希表（5）线性再散列法进行数据查找（6）二次探测再散列法进行数据查找（7）链地址法进行数据查找（8）退出系统三、任务发出日期：2013-10-01课程设计完成日期：2013-12-20小组分工说明小组编号7题目：散列法的实验研究小组分工情况：一人独立完成所有工作。组长签字：2013年12月31日指导教师对课程设计的评价成绩：指导教师签字：年月日1．需求分析说明-32．概要设计说明3．详细设计说明4．调试分析-4-5-75．用户使用说明6．课程设计总结7．测试结果-8-10-10-128．参考书目需求分析说明内部排序教学软件的总体功能要求：散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。基本功能如下：（1）界面友好，易与操作。采用菜单方式进行选择。（2）实现三种方法进行哈希表的构造。包括线性再散列法、二次探测再散列法和链地址法。（3）根据三种构造方法分别进行数据元素的查找，若查找成功，则同时输出探查/冲突次数。以下是各功能模块的功能描述：1．主函数模块本模块的主要功能是初始化图形界面，调用各模块，实现功能。2．构造哈希表子模块本模块的主要功能是采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表。3．查找功能及输出子模块本模块的主要功能是在采用线性再散列法、二次探测再散列法、链地址法三种方法构造哈希表后，采用相应的方法对键入的数据进行查找，并计算探查/冲突次数。4．输入子模块本模块的主要功能是从键盘中输入数据元素用于构造哈希表。5.输出子模块本模块的主要功能是将数据元素显示在屏幕上。概要设计说明模块调用图：各种构造方法的哈希表数据类型定义为：typedefstruct{intkey;/*关键字*/intsi;/*插入成功时的次数*/}HashTable1;/*哈希表线性探测再散列数据类型定义*/typedefstructHa{intelem;/*数据项*/structHa*next2;/*指向下一个结点的指针*/}HashTable2;/*哈希表链地址法数据类型定义*/typedefstruct{intelem[HashSize];/*表中储存数据元素的数组*/intcount;/*表中储存数据元素的个数*//*哈希表的尺寸*/intsize;}HashTable3;/*哈希表二次探测再散列法数据类型定义*/#defineHashSize53/*哈希表最大长度*/intnum;/*输入数据的个数*/voidGetIn(int*a)/*从键盘输入数据*/voidGetOut(int*a)/*在屏幕上输出数据*/voidCreateHashTable1(HashTable1*H,int*a,intnum)/*线性探测在散列哈希表*/voidSearchHash1(HashTable1*h,intdata)/*线性探测在散列法查找*/voidCreateHashTable2(HashTable2*H,int*a,intnum)/*哈希表链地址*/intSearchHash2(HashTable2*h,intdata,intnum)/*链地址法查找*/voidCreateHash3(HashTable3*h,int*a,intnum)/*二次探索表*/intCollision(intp,intc)/*二次探测再散列法解决冲突*/voidSearchHash3(HashTable3*h,intdata)/*哈希表二次探索再散列查找*/intsystem(constchar*string)/*清屏*/详细设计说明1．主函数模块首先构造三种类型的哈希表，并对哈希表进行初始化。进入循环后在屏幕上输出相应的操作指示，然后通过输入0-8调用所选择的函数进行相应操作。主函数代码如下：intmain(){intdata,i;HashTable1hash1[HashSize];HashTable2hash2[HashSize];HashTable3*ha;/*定义三种类型的哈希表*/ha=(HashTable3*)malloc(sizeof(HashTable3));for(i=0;i<HashSize;i++)ha->elem[i]=0;ha->count=0;ha->size=HashSize;inta[HashSize];a[0]=0;/*哈希表的初始化*/while(1){printf("\nprintf("\n┏━━━━━━━━━━━━━━━┓");┃");┃欢迎使用本系统printf("\n┏〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┓");printf("\n┃★★★★★★散列法的实验研究★★★★★┃");printf("\n┃【1】.添加数据信息┃");printf("\n┃printf("\n┃printf("\n┃【2】.数据的输出┃");【3】.建立哈希表(线性再散列)┃");┃");【4】.建立哈希表(二次探测再散列)printf("\n┃printf("\n┃printf("\n┃printf("\n┃printf("\n┃【5】.建立哈希表(链地址法)【6】.线性再散列法查找【7】.二次探测再散列法查找【8】.链地址法查找┃");┃");┃");┃");┃");【0】.退出程序printf("\n┗〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒〒┛");printf("\n");printf("\n");printf("请输入一个任务选项>>>");intx;scanf("%d",&x);switch(x){case1:GetIn(a);break;/*调用输入函数，从键盘键入需要添加的数据*//*若已有数据输入，则调用数据输出函数*/case2:if(a[0]==0)printf("您还没有输入任何数据!\n");elseGetOut(a);break;case3:/*调用函数用线性再散列法构造哈希表*/if(a[0]==0)printf("您还没有输入任何数据!\n");elseCreateHashTable1(hash1,a,num);break;case4:/*调用函数用二次探测再散列法构造哈希表*/if(a[0]==0)printf("您还没有输入任何数据!\n");elseCreateHash3(ha,a,num);break;case5:/*调用函数用链地址法构造哈希表*/if(a[0]==0)printf("您还没有输入任何数据!\n");elseCreateHashTable2(hash2,a,num);break;case6:/*调用函数用线性再散列法查找*/if(a[0]==0)printf("您还没有输入任何数据!\n");else{printf("请输入你查找的数据");scanf("%d",&data);SearchHash1(hash1,data);}break;case7:if(a[0]==0)/*调用函数用二次探测再散列法查找*/printf("您还没有输入任何数据!\n");else{printf("请输入你查找的数据");scanf("%d",&data);SearchHash3(ha,data);}break;case8:/*调用函数用链地址法查找*/if(a[0]==0)printf("您还没有输入任何数据!\n");else{printf("请输入你查找的数据");scanf("%d",&data);SearchHash2(hash2,data,num);}break;case0:/*退出系统*/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。代码如下：voidCreateHashTable1(HashTable1*H,int*a,intnum)//哈希表线性探测再散列{inti,d,cnt;for(i=0;i<HashSize;i++)/*给新哈希表初始化数据*/{H[i].key=0;H[i].si=0;}for(i=0;i<num;i++){cnt=1;d=a[i]%HashSize;/*构造哈希函数*/if(H[d].key==0)/*无冲突时，直接插入数据*/{H[d].key=a[i];H[d].si=cnt;}Else/*有冲突时，进行冲突处理后再插入*/{do{d=(d+1)%HashSize;cnt++;}while(H[d].key!=0);H[d].key=a[i];H[d].si=cnt;}}printf("\n线性再探索哈希表已建成!");}2.二次探测再散列法建立哈希表：构造哈希函数h(x)=h(key)%HashSize，当冲突发生时，地址增量di依次取,,···,数列,即di=,,···,。代码如下：typedefstruct{intelem[HashSize];/*表中储存数据元素的数组*/intcount;/*表中储存数据元素的个数*//*哈希表的尺寸*/intsize;}HashTable3;intCollision(intp,intc)/*二次探测再散列法解决冲突*/{inti,q;i=c/2+1;while(i<HashSize){if(c%2==0)/*增量为正数时*/{c++;q=(p+i*i)%HashSize;if(q>=0)returnq;elsei=c/2+1;}else{/*增量为负数时*/q=(p-i*i)%HashSize;c++;if(q>=0)returnq;elsei=c/2+1;}}return(-1);}voidCreateHash3(HashTable3*h,int*a,intnum)//二次探测再散列构造哈希表{inti,p=-1,c,pp;for(i=0;i<num;i++){c=0;p=a[i]%HashSize;/*哈希函数*/pp=p;while(h->elem[pp]!=0)/*发生冲突*/{pp=Collision(p,c);c++;if(pp<0)/*冲突无法处理*/{printf("第%d个记录无法解决冲突\n",i+1);continue;}}h->elem[pp]=a[i];h->count++;printf("第%d个记录冲突次数为%d\n",i+1,c);}printf("\n建表完成\n此哈希表容量为%d,当前表内存储的记录个数%d.\n",num,h->count);}3.链地址法建立哈希表：将所有关键字为同义词的记录存储在同一线性链表中。在链表中插入位置可以为表头或表尾，也可以在中间，以保持同义词在同一线性链表中按关键字有序。（本程序采用在表尾插入）代码如下：typedefstructHa{intelem;/*数据项*/structHa*next2;/*指向下一个结点的指针*/}HashTable2;voidCreateHashTable2(HashTable2*H,int*a,intnum)//哈希表链地址构造法{intkey,i;HashTable2*q,*qq;q=NULL;for(i=0;i<HashSize;i++)/*对哈希表进行初始化*/{H[i].elem=0;H[i].next2=NULL;}for(i=0;i<num;i++){key=a[i]%HashSize;if(H[key].elem==0)H[key].elem=a[i];else{if(q!=NULL)/*若该位置已有数据*/{qq=q;q=q+1;q->elem=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.线性再散列法进行查找：根据线性再散列法的构造方式进行相应查找。代码如下：voidSearchHash1(HashTable1*h,intdata){intd,i;d=data%HashSize;/*哈希函数*/i=d;if(h[d].key==data)/*一次查找成功*/printf("数字%d的探查次数为%d\n",h[d].key,h[d].si);else{while(i<HashSize&&h[d].key!=data){d=(d+1)%HashSize;i+=1;}if(i<HashSize)printf("数字%d的探查次数为%d.\n",h[d].key,h[d].si);elseprintf("没有查找到你所输入的数\n");}}5.二次探测再散列法进行查找：根据二次探测再散列法的构造方式进行相应查找。代码如下：voidSearchHash3(HashTable3*h,intdata)//哈希表二次探索再散列查找{intc=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);elseprintf("\n没有查到此数!\n");}6.链地址法进行查找：根据链地址法的构造方式进行相应查找。代码如下：intSearchHash2(HashTable2*h,intdata,intnum){intd,cnt=1;HashTable2*q;d=data%HashSize;q=&h[d];/*哈希函数*/if(q->elem==0){/*该位置上没有数据元素*/printf("没有找到你要查找的那个数\n");return0;}while(q!=NULL){if(q->elem==data){printf("数字%d的查找次数为%d\n",data,cnt);return0;}elseif(q->next2!=NULL){q=q->next2;cnt++;}else{printf("没有找到你要查找的那个数\n");return0;}}return0;}7.输入函数：从键盘中键入数据。代码如下：voidGetIn(int*a){//输入数据函数printf("输入添加的个数");scanf("%d",&num);inti;for(i=0;i<num;i++)scanf("%d",&a[i]);printf("数据已经输入完毕!\n");}8.输出函数：在屏幕上输出数据。代码如下：voidGetOut(int*a){inti;printf("你所输入的数据");for(i=0;i<num-1;i++)printf("%d,",a[i]);printf("%d.",a[num-1]);printf("\n输出已完毕!");}调试分析我遇到的问题：●链地址法查找时，原设计在有冲突时表尾插入，写出的程序却是在表头进行插入。在加入了一个判断语句和移动指针位置的语句后问题得到解决。●图形界面下输入数据●在程序显示结果后无法返