华北电力大学实验报告实验名称哈希表的设计课程名称算法与数据结构实验专业班级：学生姓名：学号：成绩：指导教师：实验日期：一、实验目的及要求1.内容描述设计哈希表实现电话号码查询系统：1）设每个记录有如下数据项：电话号码、用户名、地址；2）从键盘输入各个记录，以电话号码为关键字建立哈希表（至少要有12个以上的记录，哈希表的哈希表的长度为8）；3）用链地址法解决冲突；4）显示建立好的哈希表，并且对其进行查找，删除和插入给定关键字值得记录。
二、所用仪器、设备VC++ 6.0环境三、实验说明1.采用除留余数法进行哈希表的散列，即以电话号码作为主关键字，将电话号码的11位相加，按照模7取余；2.解决冲突用链地址法。
3.将用户信息包装在结构体节点中struct node //建节点{char name[8],address[20];char num[11];node * next;};4.对于用户信息的查找，这里运用了以姓名和电话号码两种查找标准进行查找，链地址的存在使得冲突消除，同时查找实现。
5.清空的实现是设立了一个清空函数，是哈希表的所有成员内容为空，在主函数中进行调用，实现全部信息删除功能。
四、实验源代码#include <iostream>using namespace std;#include "string.h"#include "fstream"#define NULL 0unsigned int key;unsigned int key2;int *p;struct node //建节点{char name[8],address[20];char num[11];node * next;};typedef node *pnode;typedef node *mingzi;node **phone;node **nam;node *a;void Hash(char num[11]) //哈希函数{int i = 3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%7;}void Hash2(char name[8]) //哈希函数{int i = 1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%7;}node* input() //输入节点{node *temp;temp = new node;temp->next=NULL;cout<<"输入姓名："<<endl;cin>>temp->name;cout<<"输入地址："<<endl;cin>>temp->address;cout<<"输入电话："<<endl;cin>>temp->num;return temp;}int apend() //添加节点{node *newphone;node *newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;Hash(newphone->num);Hash2(newname->name);newphone->next = phone[key]->next;phone[key]->next=newphone;newname->next = nam[key2]->next;nam[key2]->next=newname;return 0;}void create() //新建节点{int i;phone=new pnode[20];for(i=0;i<8;i++){phone[i]=new node;phone[i]->next=NULL;}}void create2() //新建节点{int i;nam=new mingzi[20];for(i=0;i<8;i++){nam[i]=new node;nam[i]->next=NULL;}}void list() //显示列表{int i;node *p;for(i=0;i<20;i++){p=phone[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;p=p->next;}}}void list2() //显示列表{int i;node *p;for(i=0;i<20;i++){p=nam[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;p=p->next;}}}void find(char num[11]) //查找用户信息{Hash(num);node *q=phone[key]->next;while(q!= NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q)cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;else cout<<"无此记录"<<endl;}void find2(char name[8]) //查找用户信息{Hash2(name);node *q=nam[key2]->next;while(q!= NULL){if(strcmp(name,q->name)==0)q=q->next;break;}if(q)cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl;else cout<<"无此记录"<<endl;}void save() //保存用户信息{int i;node *p;for(i=0;i<20;i++){p=phone[i]->next;while(p){fstream iiout("out.txt", ios::out);iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl;p=p->next;}}}void menu() //菜单{cout<<"0.添加记录"<<endl;cout<<"1.查找记录"<<endl;cout<<"2.姓名散列"<<endl;cout<<"3.号码散列"<<endl;cout<<"4.清空记录"<<endl;cout<<"5.保存记录"<<endl;cout<<"6.退出系统"<<endl;}int main(){char num[11];char name[8];create();create2() ;int sel;while(1){menu();cin>>sel;if(sel==1){ cout<<"9号码查询，8姓名查询"<<endl;int b;cin>>b;if(b==9){ cout<<"请输入电话号码:"<<endl;cin >>num;cout<<"输出查找的信息:"<<endl;find(num);}else{ cout<<"请输入姓名:"<<endl;cin >>name;cout<<"输出查找的信息:"<<endl;find2(name);}}if(sel==2){ cout<<"姓名散列结果:"<<endl;list2();}if(sel==0){ cout<<"请输入要添加的内容:"<<endl;apend();}if(sel==3){ cout<<"号码散列结果:"<<endl;list();}if(sel==4){ cout<<"列表已清空:"<<endl;create();create2();}if(sel==5){ cout<<"通信录已保存:"<<endl;save();}if(sel==6) return 0;}return 0;}五、实验结果与数据处理1.添加信息2.姓名散列查找3.号码散列查找4.号码查询5.清空与退出六、讨论与结论本程序的功能实现了基本的存储查找添加删除功能模块，达到了实验的基本要求。
通过此次试验，我不仅加深了对哈希表的理解，以及哈希表查找构建原理的掌握，同时，在从整个实验的设计到代码的修改，查阅资料的过程中自己也学到了很多东西。