哈希表实验报告 定稿.doc

数据结构课程设计报告设计题目： 哈希表的设计与实现专 业 通信工程 班 级_学 生_学 号_指导 教师 _起止 时间 XXXXXX学院 2011 年 上 学期目 录一设计要求-1二数据结构选择与概要设计2.1 数据结构选择-12.2 流程图-2 以号码为关键字哈希流程-2 以姓名为关键字哈希流程-3 添加信息节点流程图-4 姓名查找流程图-5 号码查询流程图-6三设计算法3.1 建立节点-73.2 哈希函数的定义-73.3 哈希查找-8四测试结果 4.1 操作说明-8 4.2 主菜单截图-9 4.3 添加记录截图-9 4.4 散列结果截图-10 4.5 查找记录截图-10 4.5 清空记录截图-11五程序源代码及实验心得 5.1 源代码-1120 5.2 实验心得-2021一设计要求【问题描述】设计哈希表实现电话号码查询系统。设计程序完成以下要求：【基本要求】：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。（6）在哈希函数确定的前提下，尝试各种不同类型冲突吃力方法（至少两种），考察平均查找长度思路：（1）对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。得到的数作为地址。对于以用户名为关键字的散列函数，是将所有字母的ASCLL码值 相加，然后对20求余。（2）要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数；（3）要实现查找函数，则必须包括一个查找结点的函数；另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个主函数（main()）。（4）测试数据的选择最后，程序完成后要对程序进行编译调试，执行后要选择数据进行测试，这里选择的测试数据为：1.姓名：郑治华；电话地址：湖北蕲春；2.姓名：蔡翔；电话地址：江苏宿迁；3.姓名：朱利庆；电话地址：湖北阳新；二数据结构选择与概要设计2.1数据结构选择本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链接地址法结点结构如图：name8num11address20next其中name8和num11是分别为以电话号码和用户名为关键字域，存放关键字（key）；address20(data)为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。2.2流程图Hash函数流程图以号码为关键字的hash函数流程图取整型num2赋给keyi从3开始取numi!=0Key=key+(int) numii+Key=key%20开 始结束 以姓名为关键字的hash函数流程图取整型name0赋给key2i从0开始取namei不为空Key2+=nameii+Key2=key%20 开 始结束添加信息节点流程图开始申请新的结点newphone,newname即新的号码和名字Newname指向newphoneNewphone=input()调用hash()函数拉链法处理冲突利用用户名为关键字插入调用hash()函数结束姓名查找流程图开始调用hash()函数中新结点q指向phonekey-nextq 不为空q=q-nextq不为空输出无记录输出相应记录结束号码查询流程图开始调用hash2()函数中新结点q指向phonekey-nextq 不为空q=q-nextq不为空输出无记录输出相应记录结束三 设计算法3.1建立节点 struct node char name8,address20; char num11; node * next; ; typedef node* pnode; /可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指针typedef node* mingzi; node *phone; node *nam; node *a;3.2哈希函数的定义本程序要设计两个hash（）函数，分别对应电话号码和用户名。对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，方法如下：以电话号码为关键字建立哈希函数hash(char num11)。以用户名为关键字建立哈希函数hash2(char name8)。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。void hash(char num11); /以电话号码为关键字建立哈希函数/哈希函数的主旨是将电话号码的十一位数字全部加起来 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; /利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数 void hash2(char name8); /哈希函数 以用户名为关键字建立哈希函数 int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; 3.3哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字，首先，都需要利用hash函数来计算出地址。再通过比对，如果是以电话号码为关键字，比较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输出“无此记录”。void find(char num11) ; /在以电话号码为关键字的哈希表中查找用户信息 hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) printf(%s_%s_%sn,q-name,q-address,q-num);else printf(无此记录n); void find2(char name8) ;/ 在以用户名为关键字的哈希表中查找用户信息 hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; 四测试结果4.1操作说明：地址可输入的最大字符数是20，姓名可输入的最大字符数是8，电话号码都为11位。部分截图：4.2主菜单记录截图4.3添加记录截图4.4散列结果截图4.5查找记录4.6清空记录截图五程序源代码及实验心得5.1源代码#include /输入输出流函数#include string.h /字符串处理函数#include fstream /文件操作函数unsigned int key; /电话号码哈希关键字unsigned int key2; /姓名哈希关键字struct node /建立基本查询信息节点 char name20,address50; char num11; node * next; ; typedef node* pnode; /新建电话信息的指针typedef node* mingzi; /新建姓名信息的指针node *phone; /初始化前电话指针没有具体地址值node *nam; /初始化前姓名指针没有具体地址值/电话号码哈希函数void hash(char num11) /printf(在hash函数内部执行); int i = 2; key=(int)num1; while(numi!=NULL) key+=(int)numi; i+; key=key%20;/电话号码再哈希函数void rehash(char num11) int i=1; key=(int)num0; while(numi!=NULL) key+=(int)numi; i+; key=(key+i)%20;void clash() /电话号码冲突处理 node *q=phonekey-next; while(q-name)!=NULL) key=key+1; q=phonekey-next; /姓名冲突处理void clash2() node *q=namkey2-next; while(q-name)!=NULL) key2=key2+1; q=namkey2-next; /姓名哈希函数 void hash2(char name20) int i=1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() /输入节点基本信息 /printf(成功执行); node *temp; temp = new node; temp-next=NULL; printf(输入姓名：n); scanf(%s,&(temp-name); printf(输入地址：n); scanf(%s,&(temp-address); printf(输入电话：n); scanf(%s,&(temp-num); return temp; int apend() /添加节点 node *newphone; node *newname; newphone=input(); newname=newphone; newphone-next=NULL; newname-next=NULL; hash(newphone-num); /电话号码冲突处理 clash(); hash2(newname-name); printf(电话号码冲突处理后key的值：%dn,key); /姓名冲突处理 clash2(); printf(姓名冲突处理后key的值：%dn,key2); newphone-next = phonekey-next; phonekey-next=newphone; newname-next = namkey2-next; namkey2-next=newname; return 0; void create() /新建节点电话信息 int i; phone=new pnode20; for(i=0;inext=NULL; void create2() /新建节点姓名信息 int i; nam=new mingzi20; for(i=0;inext=NULL; void list() /显示号码列表 int i; node *p; node *q=namkey2-next; if(q= NULL) printf(n没有存储信息n); for(i=0;inext; while(p) printf(nn|-|n); printf(电话：%sn,p-num); printf(地址：%sn,p-address); printf(姓名：%sn,p-name); printf(|-|nnn); p=p-next; void list2() /显示姓名散列 int i; node *p; node *q=namkey2-next; if(q= NULL) printf(n没有存储信息n); for(i=0;inext; while(p) printf(nn|-|n); printf(姓名：%sn,p-name); printf(地址：%sn,p-address); printf(电话：%sn,p-num); void list(); printf(|-|nnn); p=p-next; void find(char num11) /查找用户信息 hash(num); /printf(key的值是%d,key); /printf(可以执行hash函数); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; /printf(是否进行判断？n); if(q) /printf(是，判断成功); printf(nn|-|n); printf(姓名：%sn,q-name); printf(地址：%sn,q-address); printf(电话：%sn,q-num); printf(|-|nnn); else printf(n无此记录nn); /电话号码冲突处理后的查找void find01(char num11) hash(num); node *p=phonekey-next; if(p=NULL) printf(n无此记录nn); else while(p!=NULL) if(strcmp(num,p-num)=0) printf(nn|-|n); printf(姓名：%sn,p-name); printf(地址：%sn,p-address); printf(电话：%sn,p-num); printf(|-|nnn); if(keynext; void find2(char name20) /查找用户信息 hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(nn|-|n); printf(姓名：%sn,q-name); printf(地址：%sn,q-address); printf(电话：%sn,q-num); printf(|-|nnn); else printf(n无此记录nn); /姓名冲突处理后的查找void find02(char name20) hash(name); node *q=namkey2-next; if(q= NULL) printf(n无此记录nn); else while(q!= NULL) if(strcmp(name,q-name)=0) printf(nn|-|n); printf(姓名：%sn,q-name); printf(地址：%sn,q-address); printf(电话：%sn,q-num); printf(|-|nnn); if(key20) key2=key2-1; q=namkey2-next; /菜单 void menu() printf(n|-|n); printf(|-1.添加记录-|n); printf(|-2.查找记录-|n); printf(|-3.姓名散列-|n); printf(|-4.号码散列-|n); printf(|-5.清空记录-|n); printf(|-6.退出系统-|n); printf(|-7.显示已有信息-|n); printf(|-|n); int main() char num11; char name20; create(); create2() ; int sel; while(1) menu(); scanf(%d,&sel); if(sel=2) printf(9从