下载文档原格式
实验目的：1．训练与培养解决实际问题的能力2．学会面对一个问题时应该如何分析问题，设计解决方法，实际编码及结果测试。
3．熟悉哈希表的使用4．设计哈希表实现电话号码查询系统。
5．设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，以电话号码为关键字建立哈希表（至少要有12个以上的记录，哈希表的长度为8）；（3）采用链地址法解决冲突；（4）显示建立好的哈希表，对于学有余力的同学可以实现哈希表的查找。
实验仪器与设备：计算机实验内容：（1）采用除留余数法进行哈希表的散列，即以电话号码作为主关键字，将电话号码的11位相加，按照模7取余；（2）解决冲突用链地址法。
、（3）实现哈希表的显示与号码的查询实验方法与步骤：1.根据问题进行分析，明确要解决的问题是什么，怎样解决2.根据分析设计问题求解算法3.用特定语言对设计进行编码4.对程序进行测试实验原理：1．对于哈希电话本问题的分析：哈希表问题实际上和图问题一样，先创建一个数组。
在号码存入时，如果数组中哈希关键字位置没有写入号码，则在该处写入，并把该处设置为已写入。
如果该处已写入号码，则在该处建立新的结点，并写入号码。
2．号码显示用for和while两个循环，具体实现过程可看附录代码。
3．号码查询按号码显示的函数书写，只是实现函数不同。
实验心得：通过这次的实验，我更加熟练了分析问题的方法。
深刻题解算法的重要性。
本次的算法实现中，对算法的时间空间复杂度进行了优化处理。
这是一个以前没做过的地方。
在哈希表的显示与查询中，出了一个错误，在纸上模拟了很久也没看出问题。
后来睡觉时才突然想到写少了一个函数，这提示我，写程序要细心，不能大意。
实验具体代码如下：// 哈希表问题.cpp : 定义控制台应用程序的入口点。
#include"stdafx.h"#include<iostream>usingnamespace std;class PNQS{private:char num[11];char name[8],address[18];int numwrited;PNQS *p;public :void setname(char cname[8],int n){int i;for (i=0;i<n;i++)name[i]=cname[i];name[i] = 0;}void setnum(char cnum[11],int n){int j;numwrited=1;for (j=0;j<n;j++)num[j]=cnum[j];num[n] = 0;}void setaddress(char cadd[18]){int i;for ( i=0;i<18;i++)address[i]=cadd[i];address[i] = 0;}void displaynpa(){cout<<"姓名：";cout<<name<<endl;cout<<"号码：";cout<<num<<endl;cout<<"地址：";cout<<address<<endl;}void displaynum(){cout<<num<<" ";}bool Isnumwrited(){if (numwrited==0)return 0;elsereturn 1;}bool Ispemp(){if (p==NULL)return 1;elsereturn 0;}void find(char Fnum[11],int n,int& ftrue){int b=0;for (int i=0;i<n;i++)if (num[i]!=Fnum[i])b++;if (b==0 && strlen(num)==strlen(Fnum)){displaynpa();ftrue=1;}}void movenext(PNQS *&mp){mp=p;}PNQS(){for(int i=0;i<16;i++)num[i]='0';num[16]=0;p=NULL;numwrited=0;}PNQS(char num2[4],int n){numwrited=0;p=NULL;for(int i=0;i<n;i++)num[i]=num2[i];num[n]=0;cout<<"请输入姓名："<<endl;cin>>name;cout<<"请输入地址："<<endl;cin>>address;}void CreatNewP(char num3[4],int n){p=new PNQS(num3,n);}};int keyword(char nums[16],int n){int count=0;for(int i=0;i<n;i++){count=count+nums[i]-48;}nums[n]=0;return count%7;}void main(){PNQS *p=new PNQS[8];bool exit=1;do{cout<<"输入存储，输入显示表，输入查找电话，输入退出"<<endl;int slect;cin>>slect;if (slect==1){staticint counts=0;counts++;cout<<"输入你要存入的号码："<<counts<<endl;char num[16];cin>>num;if ( (p+keyword(num,strlen(num)))->Isnumwrited()==0){(p+keyword(num,strlen(num)))->setnum(num,strlen(num));cout<<"输入此主号码的姓名："<<endl;char name[8];cin>>name;(p+keyword(num,strlen(num)))->setname (name,strlen(name));cout<<"输入此主号码的地址："<<endl;char add[18];cin>>add;(p+keyword(num,strlen(num)))->setaddress (add);}else{PNQS *nextp=(p+keyword(num,strlen(num)));while(!nextp->Ispemp ()){nextp->movenext(nextp);}nextp->CreatNewP(num,strlen(num));}}PNQS *q;if(slect==2){cout<<"存入的表为："<<endl;for(int ii=0;ii<8;ii++){cout<<endl;cout<<"第"<<ii<<"个位置：";if((p+ii)->Isnumwrited()==1 &&(p+ii)->Ispemp ()==1)(p+ii)->displaynum ();if ((p+ii)->Isnumwrited()==1 &&(p+ii)->Ispemp ()==0){q=(p+ii);q->displaynum ();do{q->movenext (q);q->displaynum ();}while(!q->Ispemp());}}}int findrigt;if(slect==3){findrigt=0;cout<<"输入要查的号码："<<endl;char f[16];cin>>f;if((p+keyword(f,strlen(f)))->Isnumwrited()==1 &&(p+keyword(f,strlen(f)))->Ispemp ()==1){(p+keyword(f,strlen(f)))->find (f,strlen(f), findrigt);}if ((p+keyword(f,strlen(f)))->Isnumwrited()==1 &&(p+keyword(f,strlen(f)))->Ispemp ()==0){q=(p+keyword(f,strlen(f)));q->find (f,strlen(f), findrigt);do{q->movenext (q);q->find (f,strlen(f), findrigt);}while(!q->Ispemp());}if ( findrigt==0)cout<<"无此号码"<<endl;}if(slect==4)exit=0;}while(exit);system("pause"); }结果图附表：。
123456789101112131415161718123456789101112131415161718 // HashTableInitializeTable(int TableSize) {HashTable H;int i;// 為散列表分配空間// 有些编譯器不支持為struct HashTable 分配空間，聲稱這是一個不完全的結構，// 可使用一个指向HashTable的指針為之分配空間。
// 如：sizeof(Probe)，Probe作为HashTable在typedef定義的指針。
H = malloc(sizeof(struct HashTable));// 散列表大小为一个質数H->TableSize = Prime;// 分配表所有地址的空間H->Cells = malloc(sizeof(Cell) * H->TableSize);// 地址初始為空for (i =0; i < H->TableSize; i++)H->Cells[i].info = Empty;return H;}查找空单元并插入：// PositionFind(ElementType Key, HashTable H) {Position Current;int CollisionNum;// 冲突次数初始为0// 通過表的大小對關鍵字進行處理CollisionNum =0;Current = Hash( Key, H->TableSize );// 不為空時進行查詢while (H->Cells[Current].info != Empty &&H->Cells[Current].Element != Key) {Current =++CollosionNum *++CollisionNum;// 向下查找超過表範圍時回到表的開頭if (Current >= H->TableSize)Current -= H->TableSize;}return Current;}分離連接法散列表的查找过程基本上和造表过程相同。
哈希表（hash）详解哈希表结构讲解：哈希表（Hash table，也叫散列表），是根据关键码值(Key value)⽽直接进⾏访问的数据结构。
也就是说，它通过把关键码值映射到表中⼀个位置来访问记录，以加快查找的速度。
这个映射函数叫做散列函数，存放记录的数组叫做散列表。
记录的存储位置 = function(关键字)这⾥的对应关系function称为散列函数，⼜称为哈希（Hash函数），采⽤散列技术将记录存储在⼀块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。
哈希表hashtable(key，value) 就是把Key通过⼀个固定的算法函数function既所谓的哈希函数转换成⼀个整型数字，然后就将该数字对数组长度进⾏取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间⾥。
（或者：把任意长度的输⼊（⼜叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。
这种转换是⼀种压缩映射，也就是，散列值的空间通常远⼩于输⼊的空间，不同的输⼊可能会散列成相同的输出，⽽不可能从散列值来唯⼀的确定输⼊值。
简单的说就是⼀种将任意长度的消息压缩到某⼀固定长度的消息摘要的函数。
）⽽当使⽤哈希表进⾏查询的时候，就是再次使⽤哈希函数将key转换为对应的数组下标【仍通过映射哈希函数function】，并定位到该空间获取value，如此⼀来，就可以充分利⽤到数组的定位性能进⾏数据定位。
Hash的应⽤：1、Hash主要⽤于信息安全领域中加密算法，它把⼀些不同长度的信息转化成杂乱的128位的编码,这些编码值叫做Hash值. 也可以说，Hash 就是找到⼀种数据内容和数据存放地址之间的映射关系。
2、查找：哈希表，⼜称为散列，是⼀种更加快捷的查找技术。
我们之前的查找，都是这样⼀种思路：集合中拿出来⼀个元素，看看是否与我们要找的相等，如果不等，缩⼩范围，继续查找。
