哈希表_数据结构课设

1、洛阳理工学院课程设计说明书课程名称数据结构设计课题哈希表的设计与实现专 业班 级学 号姓 名完成日期2课程设计任务书设计题目：哈希表的设计与实现设计内容与要求：设计哈希表实现电话号码查询系统。基本要求1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表;3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。6在哈希函数确定的前提下，考察平均查找长度的变化。指导教师：2014 年课程设计评语成绩:指导教师：年 月 日【问题描述】如何设计一个结构体数组使 该数组中每个元素包含电话号码、用户名、地址。

2、 如何分别以电话号码和用户名为关键字建立哈希表。如何利用线性探测再散列法解决冲突。如何实现用哈希法查找并显示给定电话号码的记录。如何查找并显示给定用户的记录。手工计算查找不成功的平均查找长度。【基本要求】 设计哈希表实现电话号码查询系统。 设计程序完成以下要求：（1）、设每个记录有下列数据项：电话号码、用户名、地址；（2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表;（3）、采用再哈希法解决冲突（4）、查找并显示给定电话号码的记录；（5）、查找并显示给定用户的记录。（6）、在哈希函数确定的前提下，考察平均查找长度的变化。【测试数据】1. 用户名：weiguo，号码：123,地址

3、：gansu2. 用户名：zhangkui，号码：321，地址：shanxi【算法思想】进入主函数，用户输入1：输入哈希表元素，然后再选择2或者3按照用户名或者电话号码散列，在这下面又有分支语句 选择解决冲突的办法，用线性探测再散列还是再哈希法。生成哈希表之后，选择查找操作 3分别以用户名和电话号码为关键字进行查 找。最后，输出查找不成功的平均查找长度。在本程序当中用了两种解决冲突的办法， 分别是线性探测再散列和再哈希法。 哈希函数构造方法是，除留余数法。具体流程图1所示:图1 具体流程图【模块划分】本程序在菜单选项下包含六个子模块，如图2所示图2模块划分【数据结构】本设计涉及到的数据结构为：

4、哈希表。要求输入电话号码、用户名、地址三 个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到 两个哈希函数，进行哈希查找。/*哈希表结构体*/typedef structchar name20; /用户名char pho ne20;电话char add30; /地址Record;Record In fM;/全局变量Record HM; /全局变量【测试情况】请输人您的选项® 5”x1.运行程序，显示主菜单并选择选项1来创建哈希表'C:Use叭国kto p课设b u g哈希表启炬n单2.执行选项1,输入元素内容请喻入名字ie iguo请输入号码123谙输入地

5、址yansui还需耍继续輸入吗? r /M? Y谙输入名字z：hangfkui321请输入号码121请输入地址shanxl还需要继续输入吗了皿咲3. 执行选项2,按用户名散列创建哈希表输入散列选顼<0-2 > :1哈希地址01-gtt再散列2*再吟* 3”退匕M KKMiMM MM 潮列 菜单 一用户名 zhangihiii321 weigno号码地址321shanxi123gansu授任意键返回4.执行选项3,按号码散列创建哈希表M-M-*« 2,-线性竊列K JC>OC耳 xwaf隔i人歆列选顶<0 > :哈秦地址用户名 ztiagnlkui we

6、iguo号码地址J21123X K M >4 M X JC JW按任意键返回5.执行选项4,按用户名查找X汎If杭赴梵負杭鬓H昭耳貝SMKF NXMiKXW1C：M 拭:MMKW<0-2 >KlffKXifKlifSMUKK >f耳KiMH按用户名萱询*U 3 igla *«* 杲:w是 息是码旳 :mgIojnn 疋 的户话址 人用黑 .nF_£6.执行选项4,按号码查找* i-按用户名查询2 .'输入查拽条件0-2 =号是是 的息是码-& 找查的户话址 要人用蟲 A番的的 主H2:MM 宾 KJtJfKltKHXUM： 按任意键返

7、回Jf耳疋疋:MiM JOEXX疋耳址7.执行选项5,输出查找不成功的平均查找长度请输入您的选项0-5：5查找不成功的平均查找长度为:1-«按仕意犍返回【心得】【源程序】/*电话号码查询系统*/#i nclude<stdio.h>#i ncludevstri ng.h>#i nclude<stdlib.h>#defi ne M 10#define NULLKEY "0"/*哈希表结构体*/typedef structchar name20; /用户名char pho ne20;电话char add20; /地址Record;Recor

8、d In fM;定义辅助数组为全局变量Record HM; /定义哈希表为全局变量/*菜单函数*/int menu()int m;system("cls");system("color 0a");prin tf ("tt*电话号码查询系统*n");prin tf("n");prin tf("tt主菜单n");prin tf("tt|1.哈希表的创建|n");prin tf("tt|2.按用户名散列|n");prin tf("tt|3.按号码散列|

9、n");prin tf("tt|4.查找操作|n");prin tf("tt|5.平均查找长度|n");prin tf("tt|0.:退出程序|n");printf("ttn");prin tf("n");printf("ttt请输入您的选项 <0-5>:n");sca nf("%d",&m);return(m);/创建辅助数组int Create(Record HM)int i;char sig n;for(i=0;i<

10、;10;i+) 初始化哈希表strcpy(Hi.add,"O");strcpy(Hi.pho ne,"O");strcpy(Hi. name,"O");i=0;while(sig n!=' n'&&sig n!='N')printf("请输入名字n");scan f("%s",l nfi. name);printf("请输入号码n");scan f("%s",I nfi.pho ne);printf(&quo

11、t;请输入地址n");scan f("%s",I nfi.add);printf("ttt还需要继续输入吗？(Y/N)");sca nf("ttt%c",&sig n);i+;return i;/以用户名为关键字的哈希函数int Hash_ name(char n ame20) _int i=0;int a=0;while( namei!='0')a=a+namei;i+;a=a%7;/对小于哈希表的最大素数求余，此处哈希表长为10,对7求余return(a);/再哈希int n ame_aga in

12、( char n ame20)int i,h;h=(i nt)n ame1;for(i=2;i<20;i+)h=h+(i nt) namei;h=h%7;return h;/以用户名为关键字创建哈希表void creat_name(Record In fM,i nt m,Record HM) _int j,key=O;for(j=0;j<m;j+) key=Hash_name(l nfj. name);/计算哈希地址while(1)if(strcmp(Hkey. name,NULLKEY)=0)判断该位置是否为空,不为空就把辅助数组中的元素存到该位置strcpy(Hkey. nam

13、e,l nfj. name);strcpy(Hkey.ph on e,I nfj.ph on e);strcpy(Hkey.add,I nfj.add);break;elsekey+;/如果为空，采用线性探测法，将元素后移/再哈希法void again_put(Record InfM,int m,Record HM) _int j,key=0;for(j=0;j<m;j+) key=Hash_name(I nfj. name);/计算哈希地址while(1)if(strcmp(Hkey. name,NULLKEY)=0)辅助数组中的元素存到该位置strcpy(Hkey. name,l n

14、fj. name);strcpy(Hkey.ph on e,I nfj.ph on e);strcpy(Hkey.add,I nfj.add);break;elsekey=n ame_aga in (I nfj. name);/再哈希 一/以号码为关键字的哈希函数int Hash_ph on e(char phon e20)int i=0;int b=0;while(phonei!='0')计算电话号码中每个字符的 ASCII码值相加b=b+ph on ei;i+；b=b%7;对小于哈希表的最大素数求余，此处哈希表长为10,对7求余return(b);/再哈希int phon

15、e_aga in( char phon e20) _int i,h;h=(i nt)pho ne1;for(i=2;i<20;i+)h=h+(i nt)pho nei;h=h%7; return h;/以电话号码为关键字创建哈希表void creat_ph on e(Record In fM,i nt m,Record HM) _int j,key=0;for(j=0;j<m;j+)key=Hash_pho ne(l nfj.pho ne);计算哈希地址while(1)if(strcmp(Hkey.pho ne,NULLKEY)=0)把辅助数组中的元素存到该位strcpy(Hkey

16、. name,l nfj. name);strcpy(Hkey.ph on e,I nfj.ph on e);strcpy(Hkey.add,I nfj.add);break;elsekey+;/如果为空，采用线性探测法，将元素后移/再哈希法void again_put2(Record InfM,int m,Record HM) _int j,key=O;for(j=0;j<m;j+)key=Hash_pho ne(l nfj.pho ne);计算哈希地址while(1)if(strcmp(Hkey.pho ne,NULLKEY)=0)判断该位置是否为空,不为空就把辅助数组中的元素存到该

17、位置strcpy(Hkey. name,l nfj. name); strcpy(Hkey.ph on e,I nfj.ph on e); strcpy(Hkey.add,I nfj.add);break;elsekey=ph on e_aga in (I nfj.ph on e);/再哈希 _/按姓名查找int Search_name(Record HM,char name20)int h0;int i;int hi;int result;h0=Hash_ name( name);if (Hh0. name=NULLKEY)printf("查找名字不存在!n");retu

18、rn (-1);elseresult = strcmp(Hh0. name, name);if (result = 0)return (h0);else /用线性探测再散列解决冲突for (i=1; i<=M-1; i+)hi=(hO+i) % M;if (Hhi. name=NULLKEY)return (-1);elseresult = strcmp(Hhi. name, name); if (result = 0) return (hi);return (-1);/按号码查找int Search_pho ne(Record HM,char pho ne20)int h0;int i

19、;int hi;int result;h0=Hash_ph on e(ph on e);if (Hh0.pho ne=NULLKEY)printf("查找号码不存在!n");return (-1);elseresult = strcmp(Hh0.ph on e,pho ne);if (result = 0)return (h0);else /用线性探测再散列解决冲突for (i=1; i<=M-1; i+)hi=(h0+i) % M;if (Hhi.pho ne=NULLKEY)return (-1);elseresult = strcmp(Hhi.ph on e,p

20、ho ne);if (result = 0) return (hi); return (-1);/以用户名为关键字的哈希表的输出函数void Print_name(Record HM)int i;printf("t哈希地址t用户名tt 号码tt 地址n");for(i=0;i<10;i+)if(strcmp(Hi. name,"0")!=0)prin tf("t%dtt%stt%stt%sn",i,Hi. name,Hi.pho ne,Hi.add)J/以电话号码为关键字的哈希表的输出函数void Print_phone(Rec

21、ord HM) _int i;printf("t哈希地址t用户名tt 号码tt 地址n");for(i=0;i<10;i+)if(strcmp(Hi.pho ne,"0")!=0)prin tf("t%dtt%stt%stt%sn",i,Hi. name,Hi.pho ne,Hi.add);/查找不成功的平均查找长度void un succ_le ngth(i nt m) _char pho ne20; int i,j;int count;int asl=O;float un asl;Hash_pho ne(ph on e);f

22、or(i=0;i<7;i+)j=i;coun t=1;while(strcmp(Hj. name,NULLKEY)!=O)coun t+; j=(j+1)%7;asl=asl+co unt;un asl=(float)asl/7;prin tf("查找不成功的平均查找长度为：5.2fn",u nasi);void ma in()主函数char name20,pho ne20;int m;int n ,p;int find;int w,k;while(1)switch(me nu()case 1:m=Create(H);创建辅助数组 break;case 2:prin

23、tf("ttt*n")printf("ttt* 1.线性再散列 *n");prin tf("ttt* 2.再哈希法散列 *n");prin tf("ttt* 3.退出本菜单 *n");prin tf("ttt*n")printf("输入散列选项 <0-2> :n");scan f("%d",&p);switch(p)case 1: creat_ name(l nf,m,H);Print_n ame(H); break;case 2:ag

24、ain_put(l nf,m,H);Print_n ame(H); break;break;case 3:prin tf("ttt*n")printf("ttt* 1.线性再散列 *n");prin tf("ttt* 2. prin tf("ttt* 3.再哈希法散列*n"); 退出本菜单*n");*prin tf("ttt printf(" 输入散列选项 <0-2> :n");scan f("%d",&n); switch( n)case 1:

25、creat_ph on e(l nf,m,H); Prin t_pho ne(H); break;case 2:again_put(l nf,m,H);Prin t_pho ne(H); break;break;case 4:prin tf("ttt*n")printf("ttt* 1.按用户名查询 *n");prin tf("ttt* 2.按电话查询 *n");prin tf("ttt* 3.退出本菜单 *n");prin tf("ttt*n")printf(" 输入查找条件 <0-2> :n");scan f("%d", &fin d);switch(fi nd)case 1:prin tf("n请输入要查找的名字：n");scan f("%s", name);k=Search_ name( H,n ame);k=Hash_agai n( H, n ame);if(k!=-1)printf(&