数据结构课程设计之散列表的设计与实现.doc

#大学数据结构课程设计报告题目：散列表的设计与实现 院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.6.19-6.30指导教师: 指导教师评语： 成绩： 签名： 年 月 日20102011年度 第 2 学期一、需求分析1.问题描述： 该题目要求设计散列表实现电话号码的查找，在建立散列表时分别要用姓名和电话号码作为关键字来建立，在建立时设计不同的散列函数以及利用不同的解决冲突的方法记录冲突的次数。2.基本功能： 本程序为实现对电话号码及其主要信息进行保存并查找，通过利用散列表实现查找功能。实现了折叠法和除留余数法构造哈希函数，而在处理冲突时又分别用到了线性探测再散列和二次探测再散列。3.输入输出： 本程序需要输入的用户信息包含三个数据：姓名、电话号码、地址。所用的数据类型是指针，而三个信息均为字符串（字符数组），并注意在输入姓名时需要输入拼音以便可以用折叠法构造哈希函数。输出的用户信息是字符串。二、概要设计1.设计思路： 本程序用到了字符串，所以首先要定义各个字符串的长度；其次创建一个折叠函数，利用大写字母的八进制表示；分别用姓名和电话号码建立哈希表，由于电话号码是字符串，所以用atoi函数将字符串转换成整型。2.数据结构设计： ADT HashTableSearch 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：数据元素同属一个集合。 基本操作P： CreatHash(HashTable h,Data a);初始条件：哈希函数存在 操作结果：以a为关键字建立哈希表 EQ(x,y);初始条件：哈希表已建立 操作结果：验证两个关键字 SearchHash(h,c);初始条件：哈希表已经建立 操作结果：查找信息并输出冲突数ADT HashTableSearch3.软件结构设计： Get函数 void getmessage(); 打印函数 void display(); 折叠函数 int floding(char*); 哈希函数 int Hash(char*); 冲突函数 Status collision(int ,int); 创建哈希表 void CreatHash(HashTable*,Data*); 查找函数 void SearchHash(HashTable*,int );三、详细设计#include#include#include#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1#define MAXSIZE 20 /数量#define MAX_SIZE 20/信息长度#define hashsize 51/hashtable长度最好为质数typedef int Status;typedef struct Datachar name20;char tel20;char add20;typedef structData *elemhashsize;int count;int sizeindex;HashTable;int num;Data *a=0;HashTable h;Get函数void getmessage()printf(需要输入用户的数量：);scanf(%d,&num);a=(Data*)malloc(num*sizeof(Data);for(int i=0;inum;i+)printf(输入第%d用户的名字：,i+1);scanf(%s,); printf(输入第%d用户的电话号码：,i+1);scanf(%s,ai.tel);printf(输入第%d用户的地址：,i+1);scanf(%s,ai.add);打印函数void display()int i;for(i=0;inum;i+)printf(名字 %s 电话号码 %s 地址 %sn,,ai.tel,ai.add);折叠函数int floding(char *s)/ 用户名的折叠法 char str20;char *a;int sum=0;strcpy(str,s);strupr(str); a=str;while(*a!=0)sum+=*a;*a+; return sum;哈希函数int Hash1(char *str)/折叠法哈希函数 int n; int m; n=floding(str); m=n%hashsize; return m;int Hash2(char *str)/除留余数法哈希函数int n;int m;n=atoi(str);m=n%hashsize;return m;解决冲突函数Status collision1(int &p,int &c)/线性探测再散列法解决冲突 int i,q;i=c/2+1;while(i=0)return q;elsei=c/2+1;elseq=(p-i)%hashsize;c+;if(q=0)return q;elsei=c/2+1;return UNSUCCESS;Status collision2(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 UNSUCCESS;构造哈希表函数void CreatHash1(HashTable *h,Data *a)/以姓名为关键字建立哈希表 int i,p,q,c; int n; printf(1.线性探测再散列n); printf(2.二次探测再散列n); printf(请选择解决冲突的方式：); scanf(%d,&n); for(i=0;ielemq!=0) switch(n) case 1:q=collision1(p,c);break; case 2:q=collision2(p,c);break; h-elemq=&ai; h-count+; printf(第%d个用户冲突的次数为%d次n,i+1,c); printf(以姓名方式建表成功n);void CreatHash2(HashTable *h,Data *a)/以电话号码为关键字建立哈希表 int i,p,q,c; int n; printf(1.线性探测再散列n); printf(2.二次探测再散列n); printf(请选择解决冲突的方式：); scanf(%d,&n); for(i=0;ielemq!=0) switch(n) case 1:q=collision1(p,c);break; case 2:q=collision2(p,c);break; h-elemq=&ai; h-count+; printf(第%d个用户冲突的次数为%d次n,i+1,c); printf(以电话号码方式建表成功n);Status EQ(char *x,char *y)/验证两个关键字是否一致 if(strcmp(x,y)=0) return 1; else return 0;查找函数void SearchHash1(HashTable *h,int &c) char str20; int p,q; printf(请输入要查找的姓名：); scanf(%s,str); p=Hash1(str); q=p; while(h-elemq-name!=0&!EQ(str,h-elemq-name) q=collision1(p,c); if(EQ(str,h-elemq-name) printf(查找成功，用户信息为：n); printf(姓名 ：%s 电话号码 ：%s 地址 ：%s n,h-elemq-name,h-elemq-tel,h-elemq-add); else printf(查找的用户不存在);void SearchHash2(HashTable *h,int &c) char str20; int p,q; printf(请输入要查找的电话号码：); scanf(%s,str); p=Hash2(str); q=p; while(h-elemq-tel!=0&!EQ(str,h-elemq-tel) q=collision2(p,c); if(EQ(str,h-elemq-tel) printf(查找成功，用户信息为：n); printf(姓名 ：%s 电话号码 ：%s 地址 ：%s n,h-elemq-name,h-elemq-tel,h-elemq-add); else printf(查找的用户不存在);int main() int m,c; while(1) printf( -n); printf( 欢迎使用电话号码查找系统n); printf( -n); printf( 1.添加用户信息n); printf( 2.显示所有已添加用户的信息n); printf( 3.以姓名建立散列表n); printf( 4.以电话号码建立散列表n); printf( 5.输入姓名查找用户信息n); printf( 6.输入电话号码查找用户信息n); printf( 7.退出系统n); printf( *n); printf( *特别声明：输入名字时请输入拼音，不要输入汉字*n); printf( *n); printf(请输入命令：); scanf(%d,&m); switch(m) case 1:getmessage();break; case 2:display();break; case 3:CreatHash1(&h,a);break; case 4:CreatHash2(&h,a);break; case 5:SearchHash1(&h,c);break; case 6:SearchHash2(&h,c);break; case 7: printf(谢谢您的使用n);return 0;break; default :printf(输入数字不合法，请重新输入n);break; return 0;调用函数图如下：四、调试分析编写程序时，先是没有考虑到程序运行时需要字符串和整型数据之间的转换，修改中用到了atoi函数。数据类型用到了指针，而在Data中还有三个数据程序，这三个成员用到了字符串，在C语言中字符数组表示字符串，在最开始编译时用string类型，调试时出现错误进而改用字符数组。该程序还能继续修改和改善，可以增添一个插入函数，插入新数据并重建哈希表；建立一个文件保存函数，保存已经输入的用户信息。可以增加以下算法：Status Inserthash(HashTable &h,Elemtype e) c=0; if(SearchHash(h,e.key,p,c) return DUPLICATE; else if(chashsizeh.sizeindex/2) h.elemp=e;+h.count;return 1;elseRecreateHashTable(h);return 0;五、测试结果分别输入两组数据，一组姓名为拼音输入数据，另一组姓名是汉字输入，拼音数据是可以运行正确数据 六、用户手册本程序的运行环境是DOS操作系统第一步：输入您想输入的命令，此处最好选择1，然后输入用户个数，键入用户信息第二步：输入2命令，显示所有已键入的信息第三步：建立散列表，可选择3或4，然后选择您要如何处理冲突第四步：查找用户信息，之前如果选择命令3，查找时应选择命令5；同样的之前选择命令4，查找时选择命令6第五步：退出系统命令特别声明处：该程序因用到字符串以及除法运算所以键入姓名时应用拼音字母输入，以免造成程序错误。七、体会与自我评价数据结构的课程设计是大学时期第二个专业课的课程设计，而数据结构这门课也是本学期的一门专业课，经过一个学期对数据结构的学习，应该说对这门课只有初步的认识，掌握的并不是那么牢固。不过，学期末的课程设计又教会了我该如何简单的去运用数据结构去解决问题。数据结构的算法和之前学习的c语言有着一些的区别，在设计中不能一味的去用原来的c语言去实现算法和函数。设计时可以为程序定义全局变量也可以为程序定义局部变量，全局变量可以让程序看起来比较简洁，局部变量虽说比较繁琐但是易懂且避免了一些不必要的错误发生。在本次课程设计中，分别用到了指针和引用两种不同的方式来设计程序，两者各有利弊，但最终选择指针作为最后版本所用到的。这一次我选择的课程设计题目是散列表的设计和查找，可以说经过一个多星期设计，不管是通过自己的努力、查资料还是询问别人该如何做，都是让我更加熟悉这一模块的内容，掌握了哈希表其中的一些用法，比如说折叠法，除留余数法，解决冲突的线性探测再散列和二次探测再散列等一些实用的方法。当然这一部分不是只有这么一些内容，还包括了其他的建立哈希表以及解决冲突的方法，虽然教材中介绍的比较简单，但依然包含了更多的知识，就像整个数据结构一样，一本教材是不可能把所有的知识点都讲到，只是给我们介绍了一些基础知识，一些可能用到相对来说比较简单的方法来解决遇到的问题，这些方法知识对于我们现在处的一个阶段就已经很实用，不能因为掌握了这一模块或者是这一本书就认为掌握了数据结构的全部。在课程设计中，我很清楚的认识到了自己的不足，而自己最大的不足就是少练，对一些算法掌握不熟练，构造函数时不知该如何使它来符合要求，遇到了一些困难的困扰在查阅资料之后才能略微明白这些错误究竟是什么，在自己实践操作下也是彻底明白了函数所要求的以及指针运用的错误。还有一点不足就是基础知识掌握的不牢固，此次课程设计又把哈希表部分内容反反复复的看，尤其是哈希表的算法，将此部分一点一点弄明白才开始动手设计程序。而在不断地学习和设计中，自己也对数据结构产生了浓厚的兴趣，了解了它的实用性和可操作性使得程序设计起来不再是那么复杂和繁琐，易懂也是它的一个有点。数据结构的课程设计的结束也是代表了这个学期的数据结构的结束，当然数据结构这门学问依然充满了吸引力，让我们去探索，这是一个结束同样也是一个开始，掌握好了基础才能更进一步学习和研究。这一次的课程数据也是给了我一个教训，一定要把基础掌握住才能练习才能做设计。数据结构的学习给我其他科目的学习提供了一定帮助，杜绝眼高手低，边学边练，为我接下来几个学期对其他专业课的学习提供了宝贵的经验。这一次两个星期的课程设计给了我足够的时间来让我掌握该部分的知识，并且了解到数据结构奥妙所在，给了我以后努力学习数据结构的动力，程序的成功设计也给了我一定的自信，不再害怕自己设计程序时遇到错误，而要勇于面对它程序中的错误是一定会被一些简单实用的方法给解决掉。程序设计完成并且运行无误，自己也是对自己感到满意，对自己以后学习其他计算机语言也是打下了自信的基础，并有了这一次的经历和所获得的经验，也是对以后的学习提供了保障。源代码#include#include#include#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1#define MAXSIZE 20 /数量#define MAX_SIZE 20/信息长度#define hashsize 51/hashtable长度最好为质数typedef int Status;struct Datachar name20;char tel20;char add20;typedef structData *elemhashsize;int count;int sizeindex;HashTable;int num;Data *a=0;HashTable h;void getmessage()printf(需要输入用户的数量：);scanf(%d,&num);a=(Data*)malloc(num*sizeof(Data);for(int i=0;inum;i+)printf(输入第%d用户的名字：,i+1);scanf(%s,); printf(输入第%d用户的电话号码：,i+1);scanf(%s,ai.tel);printf(输入第%d用户的地址：,i+1);scanf(%s,ai.add);void display()int i;for(i=0;inum;i+)printf(名字 %s 电话号码 %s 地址 %sn,,ai.tel,ai.add);int floding(char *s)/ 用户名的折叠法 char str20;char *a;int sum=0;strcpy(str,s);strupr(str); a=str;while(*a!=0)sum+=*a;*a+; return sum;int Hash1(char *str)/折叠法哈希函数 int n; int m; n=floding(str); m=n%hashsize; return m;int Hash2(char *str)/除留余数法哈希函数int n;int m;n=atoi(str);m=n%hashsize;return m;Status collision1(int &p,int &c)/线性探测再散列法解决冲突 int i,q;i=c/2+1;while(i=0)return q;elsei=c/2+1;elseq=(p-i)%hashsize;c+;if(q=0)return q;elsei=c/2+1;return UNSUCCESS;Status collision2(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 UNSUCCESS;void CreatHash1(HashTable *h,Data *a) int i,p,q,c; for(i=0;ielemq!=0) q=collision1(p,c); h-elemq=&ai; h-count+; printf(第%d个用户冲突的次数为%d次n,i+1,c); printf(以姓名方式建表成功n);void CreatHash2(HashTable *h,Data *a) int i,p,q,c; for(i=0;ielemq!=0) q=collision2(p,c); h-elemq=&ai; h-count+; printf(以电话号码方式建表成功n);Status EQ(char *x,char *y)/验证两个关键字是否一致 if(strcmp(x,y)=0) return 1; else return 0;void SearchHash1(HashTable *h,int &c) char str20; int p,q; printf(请输入要查找的姓名：); scanf(%s,str); p=Hash1(str); q=p; while(h-elemq-name!=0&!EQ(str,h-elemq-name) q=collision1(p,c); if(EQ(str,h-elemq-name) printf(查找成功，用户信息为：n); printf(姓名 ：%s 电话号码 ：%s 地址 ：%s n,h-elemq-name,h-elemq-tel,h-elemq-add); else printf(查找的用户不存在);void SearchHash2(HashTable *h,int &c) char str20; int p,q; printf(请输入要查找的电话号码：); scanf(%s,str); p=Hash2(str); q=p; while(h-elemq-tel!=0&!EQ(str,h-elemq-tel) q=collision2(p,c);