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

《数据结构课程设计之散列表的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、##大学数据结构课程设计报告题目：散列表的设计与实现院（系）：计算机工程学院学生姓名:班级：学号:起迄日期:2011.6.19-6.30指导教师:指导教师评语：成绩：签名：年月日2010—2011年度第2学期一、需求分析1.问题描述：该题目要求设计散列表实现电话号码的查找，在建立散列表时分别要用姓名和电话号码作为关键字来建立，在建立时设计不同的散列函数以及利用不同的解决冲突的方法记录冲突的次数。2.基本功能：本程序为实现对电话号码及其主要信息进行保存并查找，通过利用散列表实现查找功能。实现了折叠法和除留余数法构造哈希函数，而在处理冲突时又分别用到了线性探测再散列和

2、二次探测再散列。3.输入输出：本程序需要输入的用户信息包含三个数据：姓名、电话号码、地址。所用的数据类型是指针，而三个信息均为字符串（字符数组），并注意在输入姓名时需要输入拼音以便可以用折叠法构造哈希函数。输出的用户信息是字符串。二、概要设计1.设计思路：本程序用到了字符串，所以首先要定义各个字符串的长度；其次创建一个折叠函数，利用大写字母的八进制表示；分别用姓名和电话号码建立哈希表，由于电话号码是字符串，所以用atoi函数将字符串转换成整型。2.数据结构设计：ADTHashTableSearch{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：数据元素

3、同属一个集合。基本操作P：CreatHash(HashTableh,Dataa);初始条件：哈希函数存在操作结果：以a为关键字建立哈希表EQ(x,y);初始条件：哈希表已建立操作结果：验证两个关键字SearchHash(h,c);初始条件：哈希表已经建立操作结果：查找信息并输出冲突数}ADTHashTableSearch3.软件结构设计：Get函数voidgetmessage();打印函数voiddisplay();折叠函数intfloding(char*);哈希函数intHash(char*);冲突函数Statuscollision(int,int);创建哈希表

4、voidCreatHash(HashTable*,Data*);查找函数voidSearchHash(HashTable*,int);三、详细设计#include#include#include#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1#defineMAXSIZE20//数量#defineMAX_SIZE20//信息长度#definehashsize51//hashtable长度最好为质数typedefintStatus;typedefstructD

5、ata{charname[20];chartel[20];charadd[20];};typedefstruct{Data*elem[hashsize];intcount;intsizeindex;}HashTable;intnum;Data*a=0;HashTableh;Get函数voidgetmessage(){printf("需要输入用户的数量：");scanf("%d",&num);a=(Data*)malloc(num*sizeof(Data));for(inti=0;i

6、"%s",a[i].name);printf("输入第%d用户的电话号码：",i+1);scanf("%s",a[i].tel);printf("输入第%d用户的地址：",i+1);scanf("%s",a[i].add);}}打印函数voiddisplay(){inti;for(i=0;i

7、strupr(str);a=str;while(*a!=0){sum+=*a;*a++;}returnsum;}哈希函数intHash1(char*str)//折叠法哈希函数{intn;intm;n=floding(str);m=n%hashsize;returnm;}intHash2(char*str)//除留余数法哈希函数{intn;intm;n=atoi(str);m=n%hashsize;returnm;}解决冲突函数Statuscollision1(int&p,int&c)//线性探测再散列法解决冲突{inti,q;i=c/2+1;while(i

8、hsize