哈希表--数据结构课设

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

2、程 设 计 评 语成绩： 指导教师： 年 月 日洛 阳 理 工 学 院 课 程 设 计 报 告【问题描述】如何设计一个结构体数组使该数组中每个元素包含电话号码、用户名、地址。如何分别以电话号码和用户名为关键字建立哈希表。如何利用线性探测再散列法解决冲突。如何实现用哈希法查找并显示给定电话号码的记录。如何查找并显示给定用户的记录。手工计算查找不成功的平均查找长度。 【基本要求】设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）、设每个记录有下列数据项：电话号码、用户名、地址；（2）、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）、采用再哈希法解决冲突（4）、查找并显

3、示给定电话号码的记录；（5）、查找并显示给定用户的记录。（6）、在哈希函数确定的前提下，考察平均查找长度的变化。【测试数据】1.用户名：weiguo，号码：123，地址：gansu2.用户名：zhangkui，号码：321，地址：shanxi【算法思想】进入主函数,用户输入1:输入哈希表元素，然后再选择2或者3按照用户名或者电话号码散列，在这下面又有分支语句选择解决冲突的办法，用线性探测再散列还是再哈希法。生成哈希表之后，选择查找操作3分别以用户名和电话号码为关键字进行查找。最后，输出查找不成功的平均查找长度。在本程序当中用了两种解决冲突的办法，分别是线性探测再散列和再哈希法。哈希函数构造方法

4、是，除留余数法。具体流程图1所示:开始选择1调用Create创建辅助数组按0结束选择3以号码为关键字创建哈希表creat_num选择2以姓名为关键字创建哈希表creat_name解决冲突解决冲突线性探测再哈希法再哈希法线性探测按号码查找，调用Search_num函数按用户名查找，调用Search_name函数查找不成功的平均查找长度选择0退出图 1 具体流程图【模块划分】本程序在菜单选项下包含六个子模块，如图2所示图2 模块划分【数据结构】本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈

5、希查找。/*哈希表结构体*/typedef struct char name20; /用户名char phone20;/电话char add30; /地址Record;Record InfM;/全局变量Record HM; /全局变量【测试情况】1. 运行程序，显示主菜单并选择选项1来创建哈希表2.执行选项1，输入元素内容3.执行选项2，按用户名散列创建哈希表4.执行选项3，按号码散列创建哈希表5.执行选项4，按用户名查找6.执行选项4，按号码查找7.执行选项5，输出查找不成功的平均查找长度【心得】 【源程序】/*电话号码查询系统*/#include<stdio.h>#includ

6、e<string.h>#include<stdlib.h>#define M 10#define NULLKEY "0"/*哈希表结构体*/typedef struct char name20; /用户名char phone20;/电话char add20; /地址Record;Record InfM;/定义辅助数组为全局变量Record HM; /定义哈希表为全局变量/*菜单函数*/int menu() int m; system("cls"); system("color 0a"); printf(&quo

7、t;tt*电话号码查询系统*n");printf("n");printf("tt_ 主 菜 单 _n"); printf("tt| 1. 哈希表的创建 |n"); printf("tt| 2. 按用户名散列 |n"); printf("tt| 3. 按 号 码散列 |n"); printf("tt| 4. 查 找 操 作 |n"); printf("tt| 5. 平均查找长度 |n");printf("tt| 0. 退 出 程 序 |n

8、"); printf("tt-n"); printf("n");printf("ttt 请输入您的选项<0-5>:n"); scanf("%d",&m); return(m); /创建辅助数组int Create(Record HM)int i;char sign; for(i=0;i<10;i+)/初始化哈希表strcpy(Hi.add,"0");strcpy(Hi.phone,"0");strcpy(H,"0&qu

9、ot;);i=0; while(sign!='n'&&sign!='N') printf("请输入名字n"); scanf("%s",I); printf("请输入号码n"); scanf("%s",Infi.phone); printf("请输入地址n"); scanf("%s",Infi.add); printf("ttt还需要继续输入吗?(Y/N)"); scanf("ttt%

10、c",&sign); i+; return i;/以用户名为关键字的哈希函数int Hash_name(char name20)int i=0;int a=0;while(namei!='0')a=a+namei;i+;a=a%7;/对小于哈希表的最大素数求余，此处哈希表长为10，对7求余return(a);/再哈希 int name_again(char name20) int i,h;h=(int)name1;for(i=2;i<20;i+)h=h+(int)namei;h=h%7;return h;/以用户名为关键字创建哈希表void creat_

11、name(Record InfM,int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_name(I);/计算哈希地址 while(1) if(strcmp(H,NULLKEY)=0)/判断该位置是否为空，不为空就把辅助数组中的元素存到该位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key+;/如果为空，采用线性探测法，将元素后移 /再哈希法voi

12、d again_put(Record InfM,int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_name(I);/计算哈希地址 while(1) if(strcmp(H,NULLKEY)=0)/辅助数组中的元素存到该位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key=name_again(I);/再哈希 /以号码为关键字的哈

13、希函数int Hash_phone(char phone20)int i=0;int b=0;while(phonei!='0')/计算电话号码中每个字符的ASCII码值相加b=b+phonei;i+;b=b%7;/对小于哈希表的最大素数求余，此处哈希表长为10，对7求余return(b);/再哈希int phone_again(char phone20) int i,h;h=(int)phone1;for(i=2;i<20;i+)h=h+(int)phonei;h=h%7;return h;/以电话号码为关键字创建哈希表void creat_phone(Record I

14、nfM,int m,Record HM)int j,key=0;for(j=0;j<m;j+) key=Hash_phone(Infj.phone);/计算哈希地址 while(1) if(strcmp(Hkey.phone,NULLKEY)=0)/把辅助数组中的元素存到该位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key+;/如果为空，采用线性探测法，将元素后移 /再哈希法void again_put2(Record InfM,

15、int m,Record HM)int j,key=0; for(j=0;j<m;j+) key=Hash_phone(Infj.phone);/计算哈希地址 while(1) if(strcmp(Hkey.phone,NULLKEY)=0)/判断该位置是否为空，不为空就把辅助数组中的元素存到该位置 strcpy(H,I); strcpy(Hkey.phone,Infj.phone); strcpy(Hkey.add,Infj.add); break; else key=phone_again(Infj.phone);/再哈希 /按姓名查找int Sear

16、ch_name(Record HM,char name20)int h0;int i;int hi;int result;h0=Hash_name(name);if (H=NULLKEY) printf("查找名字不存在!n");return (-1);else result = strcmp(H,name);if (result = 0) return (h0);else / 用线性探测再散列解决冲突 for (i=1; i<=M-1; i+)hi=(h0+i) % M;if (H=NULLKEY) return (-1);

17、elseresult = strcmp(H,name);if (result = 0) return (hi);return (-1);/按 号码查找int Search_phone(Record HM,char phone20)int h0;int i;int hi;int result;h0=Hash_phone(phone);if (Hh0.phone=NULLKEY) printf("查找号码不存在!n");return (-1);else result = strcmp(Hh0.phone,phone);if (result = 0) return

18、(h0);else / 用线性探测再散列解决冲突 for (i=1; i<=M-1; i+)hi=(h0+i) % M;if (Hhi.phone=NULLKEY) return (-1);elseresult = strcmp(Hhi.phone,phone);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(H

19、,"0")!=0)printf("t%dtt%stt%stt%sn",i,H,Hi.phone,Hi.add);/以电话号码为关键字的哈希表的输出函数void Print_phone(Record HM)int i;printf("t哈希地址t用户名tt号码tt地址n");for(i=0;i<10;i+)if(strcmp(Hi.phone,"0")!=0) printf("t%dtt%stt%stt%sn",i,H,Hi.phone,Hi.add);/查找不成功的

20、平均查找长度void unsucc_length(int m) char phone20;int i,j;int count;int asl=0;float unasl;Hash_phone(phone);for(i=0;i<7;i+)j=i;count=1;while(strcmp(H,NULLKEY)!=0)count+;j=(j+1)%7;asl=asl+count;unasl=(float)asl/7;printf("查找不成功的平均查找长度为:%5.2fn",unasl);void main()/主函数char name20,phone20;in

21、t m;int n,p;int find;int w,k; while(1)switch(menu()case 1:m=Create(H);/创建辅助数组break;case 2:printf("ttt*n");printf("ttt* 1.线性再散列*n");printf("ttt* 2.再哈希法散列 *n");printf("ttt* 3.退出本菜单 *n");printf("ttt*n"); printf("输入散列选项 <0-2> :n"); scanf(

22、"%d",&p); switch(p)case 1:creat_name(Inf,m,H);Print_name(H);break;case 2:again_put(Inf,m,H);Print_name(H);break;break;case 3:printf("ttt*n");printf("ttt* 1.线性再散列*n");printf("ttt* 2.再哈希法散列 *n");printf("ttt* 3.退出本菜单 *n");printf("ttt*n");

23、printf("输入散列选项 <0-2> :n"); scanf("%d",&n); switch(n)case 1:creat_phone(Inf,m,H);Print_phone(H);break;case 2:again_put(Inf,m,H);Print_phone(H);break;break;case 4:printf("ttt*n");printf("ttt* 1.按用户名查询*n");printf("ttt* 2.按电话查询 *n");printf(&quo

24、t;ttt* 3.退出本菜单 *n");printf("ttt*n"); printf("输入查找条件 <0-2> :n"); scanf("%d",&find); switch(find) case 1: printf("n请输入要查找的名字：n"); scanf("%s",name); k=Search_name(H,name);/k=Hash_again( H, name);if(k!=-1) printf("查找该人的信息是:n"); printf(&qu