散列表的设计与实现报告.doc

1、数据结构课程设计一、 需求分析：1.任务需求：设计散列表实现电话号码查找系统；2.功能需求：. 设每个记录有下列数据项：电话号码、用户名、地址；. 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；. 采用一定的方法解决冲突；. 查找并显示给定电话号码的记录；. 查找并显示给定用户名的记录；3.其他功能：. 系统功能的完善；. 设计不同的散列函数，比较冲突率；. 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化；二、 总体设计：1. 系统功能设计：定义电话本记录数量（MAXSIZE）、表长（HASHSIZE）、姓名长度(MAX_SIZE)以及结构体typ

2、edef struct的内容，构造两个哈希函数hash1和hash2。功能示意图：录入子系统查询子系统姓名地址号码姓名查找号码查询电话号码管理系统功能示意图2. 系统功能设计：增加系统功能如下: 添加用户信息; 读取所有用户信息; 以姓名建立哈希表;以电话号码建立哈希表; 查找并显示给定用户名的记录; 查找并显示给定电话号码的记录; 清屏以及保存功能；处理流程示意图：开始进入录入系统获得关键字key用Hash1(key)计算地址比较nam_2(d)的值是否和关键字相等输出记录用探查序列d+i*hash2(key)计算（寻找）散列地址结束比较nam_Ht(d)的值是否和关键字相等未找到记录处理流

3、程图 3. 功能模块设计：. 运用main函数输出电话本信息系统的整体界面，在调试运行后如下：. 利用添加功能void getin(Record* a)实现用户信息的录入，在调试运行后如下：.利用哈希函数CREATEHASH1.2来构造哈希表并用Status collision函数的相应功能来查找并解决冲突：.利用void SearchHash1(HashTable* H,int &c)在通讯录里查找姓名关键字，若查找成功，显示信息，c用来记录冲突次数,查找成功时显示冲突次数：三、 详细设计与实现部分：定义头文件及基本属性#include#include#include#include#inc

4、lude #define MAXSIZE 20 /电话薄记录数量 #define MAX_SIZE 20 /人名的最大长度#define HASHSIZE 53 /定义表长 #define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NAMAX_SIZE;定义结构体typedef struct/记录NA name;NA tel;NA add;Record;typedef struct/哈希表Record *elemHASHSIZE; /数据元素存储基址int

5、count; /当前数据元素个数int size; /当前容量HashTable;关键字比较功能的实现Status eq(NA x,NA y)/关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)=0) return SUCCESS;else return UNSUCCESS;记录个数功能的实现Status NUM_BER; /记录的个数输入信息功能void getin(Record* a)/键盘输入各人的信息coutNUM_BER;int i; for(i=0;iNUM_BER;i+) cout请输入第i+1ai.name; cout请输入第i+1ai.

6、tel; cout请输入第i+1ai.add; /gets(str2);?显示输入信息的实现void ShowInformation(Record* a)/显示输入的用户信息 int i;for( i=0;iNUM_BER;i+) coutn第i+1个用户信息:n 姓 名：ai.namen 电话号码：ai.teln 联系地址：ai.addn; 清屏功能的实现void Cls(Record* a)cout*; system(cls);long fold(NA s)/人名的折叠处理char *p;long sum=0;NA ss;strcpy(ss,s);/复制字符串，不改变原字符串的大小写str

7、upr(ss);/将字符串ss转换为大写形式p=ss;while(*p!=0) sum+=*p+; coutnsum=sum; return sum;构造哈希函数int Hash1(NA str)/哈希函数long n;int m;n=fold(str);/先将用户名进行折叠处理m=n%HASHSIZE; /折叠处理后的数，用除留余数法构造哈希函数return m; /并返回模值int Hash2(NA str)/哈希函数long n;int m;n = atoi(str);/把字符串转换成整型数.m=n%HASHSIZE; /用除留余数法构造哈希函数return m; /并返回模值冲突处理函

8、数，用于解决冲突Status 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 UNSUCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a)/建表，以人的姓名为关键字，建立相应的散列表benGetTime();int i,p=-1,c,pp; f

9、or(i=0;ielempp!=NULL) pp=collision(p,c); if(pp0) cout第i+1elempp=&(ai); /求得哈希地址，将信息存入 H-count+; cout第i+1个记录冲突次数为c.n;/需要显示冲突次数时输出coutn建表完成!n此哈希表容量为HASHSIZE,当前表内存储的记录个数为count.n;benGetTime();查找功能的实现void SearchHash1(HashTable* H,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息benGetTime();NA str;coutstr;int p,pp;p=Hash1(

10、str);pp=p;while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1) pp=collision(p,c);if(H-elempp!=NULL&eq(str,H-elempp-name)=1) coutn查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn; cout姓 名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;benGetTime();void benGetTime()SYSTEMTIME sys; GetLocalTime( &sys

11、); coutsys.wYearsys.wMonthsys.wDaysys.wHoursys.wMinutesys.wSecondsys.wMilliseconds; void CreateHash2(HashTable* H,Record* a)/建表，以电话号码为关键字，建立相应的散列表benGetTime();int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(pp0) cout第i+1elempp=&(ai); /求得哈希地址，将信息存入 H-count+; cout第i+1个记录冲突次数为c。n;/需要显示冲突次

12、数时输出coutn建表完成!n此哈希表容量为HASHSIZE,当前表内存储的记录个数为count.n;benGetTime();void SearchHash2(HashTable* H,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息benGetTime();NA tele;couttele;int p,pp;p=Hash2(tele);pp=p;while(H-elempp!=NULL)&(eq(tele,H-elempp-tel)=-1) pp=collision(p,c);if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1) coutn

13、查找成功！n查找过程冲突次数为c以下是您需要要查找的信息：nn; cout姓 名：elempp-namen电话号码：elempp-teln联系地址：elempp-addn;else coutn此人不存在，查找不成功!n;benGetTime();存盘功能的实现：void Save()FILE *fp;if(fp=fopen(c:test.txt, w)=NULL) printf(nERROR opening customet file);fclose(fp); 主界面功能的实现：int main(int argc, char* argv)int c,flag=1;HashTable *H;H=

14、(HashTable*)malloc(LEN);for(int i=0;ielemi=NULL; H-size=HASHSIZE; H-count=0;Record aMAXSIZE;while (1) coutn ; coutn 欢迎使用电话号码查找系统 ; coutn ; coutn 哈希表的设计与实现 ; coutn 【1】. 添加用户信息 ; coutn 【2】. 读取所有用户信息 ; coutn 【3】. 以姓名建立哈希表(再哈希法解决冲突) ; coutn 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ; coutn 【5】. 查找并显示给定用户名的记录 ; coutn 【6

15、】. 查找并显示给定电话号码的记录 ; coutn 【7】. 清屏 ; coutn 【8】. 保存 ; coutn 【9】. 退出程序 ; coutn 温馨提示： ; coutn .进行5操作前 请先输出3 ; coutn .进行6操作前 请先输出4 ; coutn ; coutn; cout; coutnum; switch(num) case 1: getin(a); break; case 2: ShowInformation(a); break; case 3: CreateHash1(H,a); /* 以姓名建立哈希表 */ break; case 4: CreateHash2(H,

16、a); /* 以电话号码建立哈希表 */ break; case 5: c=0; SearchHash1(H,c); break; case 6: c=0; SearchHash2(H,c); break; case 7: Cls(a); break; case 8: Save(); break; case 9: return 0; break; default: cout你输错了，请重新输入!; coutn; system(pause); return 0;四、程序测试 1、程序经测试后大部分功能正常，但是在建立哈希表后存盘出现错误，经仔细查找发现是由于定义时范围过小造成的溢出现象，经处理后程序功能一切运行正常。2、调试后的界面：五、总结 课程设计顺利完成，在这几天的程序测试中，虽然是按照课程设计所要求的功能进行编程，但是还是有一些功能的实现不尽人意，比如在处理冲突时，遇到寻址失败利用再哈希法解决冲突的过程中会有一些异常现象的产生。同时经过这阶段的课程设计可以体会出团队合作的重要性。