散列表的设计与实现3425215

1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:范晓学 号：1021011537学 院:软件学院专 业:软件开发与测试题 目:散列表的设计与实现指导教师何志英2011年12月20日1. 设计任务概述（包括系统总体框图及功能描述）总体框图:电话号码查询录入子系统查询子系统姓名号码地址号码查找姓名查找功能描述:1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。2. 本设计所采用的数据结构（如：链表、栈、树、图等） 核心数据结构用到

2、的结构体要采用动态内存分配和存放记录的散列表3. 功能模块详细设计 本程序功能模块根据程序设计的需求，综合程序的实用性、人性化、智能化的考虑，将程序划分为几个部分分别编写:键盘输入各人的信息: void getin()显示输入的用户信息: void ShowInformation()除留余数法构造哈希函数: int Hash1()构造把字符串转换成整型数哈希函数: int Hash2()冲突处理函数: Status collision()以姓名为关键字建表: void CreateHash1()以姓名为关键字查表: void SearchHash1()以电话号码为关键字建表: void Cre

3、ateHash2()以电话号码为关键字查表: void SearchHash2()输出菜单函数: int main()3.1 详细设计思想要用散列表设计实现电话号码查询系统，对存入的联系人的名字电话以及地址进行存储,并在输入电话号码或姓名后得出此记录的所有信息,要求有菜单界面和清屏功能.首先，此程序，多次用到哈希函数，此处先用除留余数法对折叠后的数构造哈希函数,再用二次探测再散列法建立冲突处理函数解决冲突,再以电话号码和姓名为关键字建立散列表(若哈西地址冲突进行冲突处理),在此之前,必须先用一系列输出函数输出一个菜单.整个程序的设计思路到此结束。.3.2 核心代码#include#includ

4、e#include#include #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; /

5、数据元素存储基址 int count; /当前数据元素个数 int size; /当前容量HashTable;Status eq(NA x,NA y)/关键字比较，相等返回SUCCESS；否则返回UNSUCCESS if(strcmp(x,y)=0) return SUCCESS; else return UNSUCCESS;Status NUM_BER; /记录的个数void getin(Record* a)/键盘输入各人的信息 printf(输入要添加的个数：n); scanf(%d,&NUM_BER); int i; for(i=0;iNUM_BER;i+) printf(请输入第%d个

6、记录的用户名:n,i+1); scanf(%s,); printf(请输入%d个记录的电话号码:n,i+1); scanf(%s,ai.tel); printf(请输入第%d个记录的地址:n,i+1); scanf(%s,ai.add); /gets(str2);? void ShowInformation(Record* a)/显示输入的用户信息 int i; for( i=0;iNUM_BER;i+) printf(n第%d个用户信息:n 姓 名：%sn 电话号码：%sn 联系地址：%sn,i+1,,ai.tel,ai.add); void Cls(Record

7、* a) printf(*); system(cls);long fold(NA s)/人名的折叠处理 char *p; long sum=0; NA ss; strcpy(ss,s);/复制字符串，不改变原字符串的大小写 strupr(ss);/将字符串ss转换为大写形式 p=ss; while(*p!=0) sum+=*p+; printf(nsum=%d,sum); return sum;int Hash1(NA str)/哈希函数 long n; int m; n=fold(str);/先将用户名进行折叠处理 m=n%HASHSIZE; /折叠处理后的数，用除留余数法构造哈希函数 re

8、turn m; /并返回模值int Hash2(NA str)/哈希函数 long n; int m; n = atoi(str);/把字符串转换成整型数. m=n%HASHSIZE; /用除留余数法构造哈希函数 return m; /并返回模值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 UNS

9、UCCESS;void benGetTime();void CreateHash1(HashTable* H,Record* a)/建表，以人的姓名为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp=&(ai); /求得哈希地址，将信息存入 H-count+; printf(第%d个记录冲突次数为%d。n,i+1,c);/需要显示冲突次数时输出 printf(n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%

10、d.n,HASHSIZE,H-count); benGetTime();void SearchHash1(HashTable* H,int &c)/在通讯录里查找姓名关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); NA str; printf(n请输入要查找记录的姓名：n); scanf(%s,str); int p,pp; p=Hash1(str); pp=p; while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1) pp=collision(p,c); if(H-elempp!=NULL&eq

11、(str,H-elempp-name)=1) printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn,c); printf(姓 名：%sn电话号码：%sn联系地址：%sn,H-elempp-name,H-elempp-tel,H-elempp-add); else printf(n此人不存在，查找不成功!n); benGetTime();void benGetTime() SYSTEMTIME sys; GetLocalTime( &sys ); printf( %4d/%02d/%02d %02d:%02d:%02d.%03d n,sys.wYear,sys.wMo

12、nth,sys.wDay,sys.wHour,sys.wMinute, sys.wSecond,sys.wMilliseconds); void CreateHash2(HashTable* H,Record* a)/建表，以电话号码为关键字，建立相应的散列表 /若哈希地址冲突，进行冲突处理 benGetTime(); int i,p=-1,c,pp; for(i=0;ielempp!=NULL) pp=collision(p,c); if(ppelempp=&(ai); /求得哈希地址，将信息存入 H-count+; printf(第%d个记录冲突次数为%d。n,i+1,c);/需要显示冲突

13、次数时输出 printf(n建表完成!n此哈希表容量为%d,当前表内存储的记录个数为%d.n,HASHSIZE,H-count); benGetTime();void SearchHash2(HashTable* H,int &c)/在通讯录里查找电话号码关键字，若查找成功，显示信息 /c用来记录冲突次数,查找成功时显示冲突次数 benGetTime(); NA tele; printf(n请输入要查找记录的电话号码：n); scanf(%s,tele); int p,pp; p=Hash2(tele); pp=p; while(H-elempp!=NULL)&(eq(tele,H-elemp

14、p-tel)=-1) pp=collision(p,c); if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1) printf(n查找成功！n查找过程冲突次数为%d以下是您需要要查找的信息：nn,c); printf(姓 名：%sn电话号码：%sn联系地址：%sn,H-elempp-name,H-elempp-tel,H-elempp-add); else printf(n此人不存在，查找不成功!n); benGetTime();void Save() FILE *fp; if(fp=fopen(c:test.txt, w)=NULL) printf(nERRO

15、R opening customet file); fclose(fp); int main(int argc, char* argv) int c,flag=1; HashTable *H; H=(HashTable*)malloc(LEN); for(int i=0;ielemi=NULL; H-size=HASHSIZE; H-count=0; Record aMAXSIZE; while (1) printf(n ); printf(n 欢迎使用电话号码查找系统 ); printf(n ); printf(n 哈希表的设计与实现 ); printf(n 【1】. 添加用户信息 ); p

16、rintf(n 【2】. 读取所有用户信息 ); printf(n 【3】. 以姓名建立哈希表(再哈希法解决冲突) ); printf(n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ); printf(n 【5】. 查找并显示给定用户名的记录 ); printf(n 【6】. 查找并显示给定电话号码的记录 ); printf(n 【7】. 清屏 ); printf(n 【8】. 保存 ); printf(n 【9】. 退出程序 ); printf(n 温馨提示： ); printf(n .进行5操作前 请先输出3 ); printf(n .进行6操作前 请先输出4 ); printf

17、(n ); printf(n); printf(请输入一个任务选项); printf(n); int num; scanf(%d,&num); switch(num) case 1: getin(a); break; case 2: ShowInformation(a); break; case 3: CreateHash1(H,a); /* 以姓名建立哈希表 */ break; case 4: CreateHash2(H,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: printf(你输错了，请重新输入!); printf(n); system(pause); return 0;3.3 程序运行结果（拷屏）程序初始界面如下: 1 2:输入1添加用户信息,输入2读取3:以姓名建立哈希表,再哈希表法解决冲突:4:以电话号码建立哈希表,再哈希表法解决冲突5:给定用户名查找记录6:给定电话号码查找记录 4. 课程设计心得、存在问题及解决方法1)