哈希表-实验报告

一、 问题描述1. 实验题目：利用哈希表统计两源程序的相似性2. 基本要求：1）内容： 对于两个 C 语言的源程序清单，用哈希表的方法分别统计两程序中使用C 语言关键字的情况，并最终按定量的计算结果，得出两份源程序的相似性。

2）要求与提示：C 语言关键字的哈希表可以自建，也可以采用下面的哈希函数作为参考： Hash(key)=(key 第一个字符序号*100+key 最后一个字符序号)%41表长m 取43。

此题的工作主要是扫描给定的源程序，累计在每个源程序中C 语言关键字出现的频度。

为保证查找效率，建议自建哈希表的平均查找长度不大于2。

扫描两个源程序所统计的所有关键字不同频度， 可以得到两个向量。

如下面简单的例子所示：根据程序1和程序2中关键字出现的频度，可提取到两个程序的特征向量X1和X2，其中 X1=(4 3 0 4 3 0 7 0 0 2)TX2=(4 2 0 5 4 0 5 2 0 1)T一般情况下，可以通过计算向量Xi 和Xj 的相似值来判断对应两个程序的相似性，相似值的判别函数计算公式为: ji Ti j i X X X X X S ⋅=)(,其中，i T i X X X ⋅=。

S(X i ,X j )的值介于[0,1]之间，也称广义余弦，即S(X i ,X j )=COSθ。

X i =X j 时，显见S(X i ,X j )=1，θ=0；X i X j 差别很大时，S(X i ,X j )接近0，θ接近π/2。

如X1=(1 0)T,X2=(0 1)T,则S(X i ,X j )=0，θ=π/2。

当S 值接近1 的时候，为避免误判相似性（可能是夹角很小，模值很大的向量），应当再次计算之间的“几何距离” D(X i ,X k )。

其计算公式为：)()(),(k i Tk i k i j i X X X X X X X X D --=-= 最后的相似性判别计算可分两步完成：第一步 用式（3-1）计算S ，把接近 1的保留，抛弃接近0的情况（把不相似的排除）； 第二步 对保留下来的特征向量，再用式（3-2）计算D ，如D 值也比较小，说明两者对应的程序确实可能相似（慎重肯定相似的）。

福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx姓名：xxxxxxx2011年12 月31 日实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。

以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。

基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。

完成按姓名查询的操作。

运行的环境：Microsoft Visual C++ 6.0二、算法基本思想描述设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。

建立哈希表并且将其显示出来。

通过要查找的关键字用哈希函数计算出相应的地址来查找人名。

通过循环语句调用数组中保存的数据来显示哈希表。

三、设计1、数据结构的设计和说明（1）结构体的定义typedef struct //记录{NA name;NA xuehao;NA tel;}Record;录入信息结构体的定义，包含姓名，学号，电话号码。

typedef struct //哈希表{Record *elem[HASHSIZE]; //数据元素存储基址int count; //当前数据元素个数int size; //当前容量}HashTable;哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。

2、关键算法的设计（1）姓名的折叠处理long fold(NA s) //人名的折叠处理{char *p;long sum=0;NA ss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写strupr(ss); //将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}（2）建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突int Hash1(NA str) //哈希函数{long n;int m;n=fold(str); //先将用户名进行折叠处理m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数return m; //并返回模值}Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();void CreateHash1(HashTable* H,Record* a) //建表，以人的姓名为关键字，建立相应的散列表{ int i,p=-1,c,pp;system("cls"); //若哈希地址冲突，进行冲突处理benGetTime();for(i=0;i<NUM_BER;i++){c=0;p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL) {pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出continue;} //无法解决冲突，跳入下一循环}H->elem[pp]=&(a[i]); //求得哈希地址，将信息存入H->count++;printf("第%d个记录冲突次数为%d。

//头文件main.c#include<stdio.h>#include<stdlib.h>struct keyNum* hash[100];struct keyNum* insertHash(struct keyNum*,int);//关键字插入链表int searchHash(struct keyNum*,int m);//查找链表中是否存在值为m的整数void print(struct keyNum*);//打印链表struct keyNum{int key;//关键字struct keyNum *next;};void main(){int i,k,m,n,num,flag,l,j;int a[] = {280,700,603,430,641,907,640};struct keyNum *head = NULL;num = sizeof(a)/sizeof(int);for(i=0;i<sizeof(a)/sizeof(int);i++){k = a[i];m=k%(num+1);//计算得到关键字的哈希值hash[m]=insertHash(hash[m],k);//将关键字k插入到哈希值为m的链表中}printf("采用链地址法得到的哈希表为：\n");for(i=0;i<num+1;i++){printf("第%d行：",i);print(hash[i]);printf("\n");}printf("请输入要查找的整数值：\n");scanf("%d",&n);for(i=0;i<num+1;i++){l=searchHash(hash[i],n);if(l==1){j=i;break;}}if(l==1)printf("整数值%d在哈希表中，位置为链表%d\n",n,j);}struct keyNum * insertHash(struct keyNum*head,int m){struct keyNum *p0,*p1,*p2,*temp;temp=(struct keyNum*)malloc(sizeof(struct keyNum));temp->key=m;p1=head;p0=temp;//要插入的节点（值为m);if(head==NULL)//1，原来的链表为空，插入到head后{head=p0;p0->next=NULL;}else//原来的链表不为空{while((p0->key>p1->key)&&(p1->next!=NULL))//移动到适当位置 {p2=p1;p1=p1->next;}if(p0->key<=p1->key){if(head==p1)head=p0;//2，插入到第一个节点之前else p2->next=p0;//3,插入到p2指向的节点之后p0->next=p1;}else//4,插入到结尾处{p1->next=p0;p0->next=NULL;}}return(head);}int searchHash(struct keyNum*head,int m)//查找链表head中是否存在m {int k=0;struct keyNum*p;p=head;if(head!=NULL)do{if(p->key==m) //存在m{k=1;break;}p=p->next;}while(p!=NULL);return(k);//存在m值则返回1，否则返回0；}void print(struct keyNum*head)//打印链表head {struct keyNum*p;p=head;if(head!=NULL){do{printf(" -> %d ",p->key);p=p->next;}while(p!=NULL);}elseprintf("null");}头文件HashTable.htypedef struct KeyNum{int key;struct KeyNum* next;}keyNum;//插入keyNum* insertHash(keyNum* head,int m){keyNum *p0,*p1,*p2,*temp;temp=(keyNum*)malloc(sizeof(keyNum));temp->key=m;p1=head;p0=temp;//要插入的节点（值为m);if(head==NULL)//1，原来的链表为空，插入到head后{head=p0;p0->next=NULL;}else//原来的链表不为空{while((p0->key>p1->key)&&(p1->next!=NULL))//移动到适当位置 {p2=p1;p1=p1->next;}if(p0->key<=p1->key){if(head==p1)head=p0;//2，插入到第一个节点之前else p2->next=p0;//3,插入到p2指向的节点之后p0->next=p1;}else//4,插入到结尾处{p1->next=p0;p0->next=NULL;}}return(head);}//查找int searchHash(keyNum*head,int m)//查找链表head中是否存在m{int k=0;keyNum*p;p=head;if(head!=NULL)do{if(p->key==m) //存在m{k=1;break;}p=p->next;}while(p!=NULL);return(k);//存在m值则返回1，否则返回0；}void print(keyNum* head)//打印链表head{keyNum*p;p = head;if(head!=NULL){do{printf(" -> %d ",p->key);p=p->next;}while(p!=NULL);}elseprintf("null");}测试程序 Main.c#include<stdio.h>#include<stdlib.h>#define mSize 100 //数组最大个数#include "HashTable.h"void main(){int i,k,m,n,num,l,j;int a[] = {180,750,600,430,541,900,640};keyNum* hash[mSize];keyNum* head = NULL;num = sizeof(a)/sizeof(int);for(i=0;i<num+1;i++)hash[i] = NULL;for(i = 0;i<num;i++){k = a[i];m=k%(num+1);//计算得到关键字的哈希值hash[m] = insertHash(hash[m],k);//将关键字k插入到哈希值为m 的链表中}printf("当前哈希表如下：\n");for(i=0;i<num+1;i++){printf("第%d行：",i);print(hash[i]);printf("\n");}printf("\n");printf("请输入要查找的元素：\n");scanf("%d",&n);for(i=0;i<num+1;i++){l=searchHash(hash[i],n);if(l==1){j=i;break;}}if(l==1)printf("\n整数值%d在哈希表中，位置为链表%d\n",n,j);else printf("\n整数值%d不在哈希表中！\n");}。

福建工程学院课程设计课程：算法与数据结构题目：哈希表专业：网络工程班级：xxxxxx班座号：xxxxxxxxxxxx姓名：xxxxxxx2011年12 月31 日实验题目：哈希表一、要解决的问题针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。

以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。

基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。

完成按姓名查询的操作。

运行的环境：Microsoft Visual C++ 6.0二、算法基本思想描述设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。

建立哈希表并且将其显示出来。

通过要查找的关键字用哈希函数计算出相应的地址来查找人名。

通过循环语句调用数组中保存的数据来显示哈希表。

三、设计1、数据结构的设计和说明（1）结构体的定义typedef struct //记录{NA name;NA xuehao;NA tel;}Record;录入信息结构体的定义，包含姓名，学号，电话号码。

typedef struct //哈希表{Record *elem[HASHSIZE]; //数据元素存储基址int count; //当前数据元素个数int size; //当前容量}HashTable;哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。

2、关键算法的设计（1）姓名的折叠处理long fold(NA s) //人名的折叠处理{char *p;long sum=0;NA ss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写strupr(ss); //将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}（2）建立哈希表1、用除留余数法构建哈希函数2、用线性探测再散列法处理冲突int Hash1(NA str) //哈希函数{long n;int m;n=fold(str); //先将用户名进行折叠处理m=n%HASHSIZE; //折叠处理后的数，用除留余数法构造哈希函数return m; //并返回模值}Status collision(int p,int c) //冲突处理函数，采用二次探测再散列法解决冲突{int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();}else printf("\n此人不存在，查找不成功!\n");benGetTime();}（4）显示哈希表void ShowInformation(Record* a) //显示输入的用户信息{int i;system("cls");for( i=0;i<NUM_BER;i++)printf("\n第%d个用户信息:\n 姓名：%s\n 学号：%s\n 电话号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel);}（5）主函数的设计void main(int argc, char* argv[]){Record a[MAXSIZE];int c,flag=1,i=0;HashTable *H;H=(HashTable*)malloc(LEN);for(i=0;i<HASHSIZE;i++){H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;}while (1){ int num;printf("\n ");printf("\n 欢迎使用同学通讯录录入查找系统");printf("\n 哈希表的设计与实现");printf("\n 【1】. 添加用户信息");printf("\n 【2】. 读取所有用户信息");printf("\n 【3】. 以姓名建立哈希表(再哈希法解决冲突) ");printf("\n 【4】. 以电话号码建立哈希表(再哈希法解决冲突) ");printf("\n 【5】. 查找并显示给定用户名的记录");printf("\n 【6】. 查找并显示给定电话号码的记录");printf("\n 【7】. 清屏");printf("\n 【8】. 保存");printf("\n 【9】. 退出程序");printf("\n 温馨提示：");printf("\n Ⅰ.进行5操作前请先输出3 ");printf("\n Ⅱ.进行6操作前请先输出4 ");printf("\n");printf("请输入一个任务选项>>>");printf("\n");scanf("%d",&num);switch(num){case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H,a); /* 以姓名建立哈希表*/break;case 4:CreateHash2(H,a); /* 以电话号码建立哈希表*/break;case 5:c=0;SearchHash1(H,c);break;case 6:c=0;SearchHash2(H,c);break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf("你输错了，请重新输入!");printf("\n");}}system("pause");return 0;3、模块结构图及各模块的功能：四、源程序清单：#include<stdio.h>#include<stdlib.h>#include<string.h>#include <windows.h>#define MAXSIZE 20 #define MAX_SIZE 20 #define HASHSIZE 53 #define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NA[MAX_SIZE];typedef struct {NA name;NA xuehao;NA tel;}Record;typedef struct {Record *elem[HASHSIZE]; int count; int size; }HashTable;Status eq(NA x,NA y) {if(strcmp(x,y)==0)return SUCCESS;else return UNSUCCESS;}Status NUM_BER;void getin(Record* a) {int i;system("cls");printf("输入要添加的个数：\n");scanf("%d",&NUM_BER);for(i=0;i<NUM_BER;i++){printf("请输入第%d个记录的姓名:\n",i+1);scanf("%s",a[i].name);printf("请输入%d个记录的学号:\n",i+1);scanf("%s",a[i].xuehao);printf("请输入第%d个记录的电话号码:\n",i+1);scanf("%s",a[i].tel);}}void ShowInformation(Record* a){int i;system("cls");for( i=0;i<NUM_BER;i++)printf("\n第%d个用户信息:\n 姓名：%s\n 学号：%s\n 电话号码：%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel);}void Cls(Record* a){printf("*");system("cls");}long fold(NA s){char *p;long sum=0;NA ss;strcpy(ss,s);strupr(ss);p=ss;while(*p!='\0')sum+=*p++;printf("\nsum====================%d",sum);return sum;}int Hash1(NA str){int m;n=fold(str);m=n%HASHSIZE;return m;}int Hash2(NA str){long n;int m;n = atoi(str);m=n%HASHSIZE;return m;}Status collision(int p,int c){int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return UNSUCCESS;}void benGetTime();void CreateHash1(HashTable* H,Record* a){ int i,p=-1,c,pp;system("cls"); benGetTime();for(i=0;i<NUM_BER;i++){p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL) {pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1);continue;}}H->elem[pp]=&(a[i]);H->count++;printf("第%d个记录冲突次数为%d。

引言概述：本文旨在对哈希实验进行报告，重点介绍哈希实验的二次探测法、哈希函数、哈希表的查找、插入与删除操作，并分析实验结果。

通过本实验的开展，我们对哈希算法的原理、实现和性能有了更深入的理解，也增加了对数据结构的实践能力。

正文内容：一、二次探测法1.定义与原理2.步骤与流程3.优缺点分析4.实验过程与结果5.实验中的注意事项二、哈希函数1.哈希函数的设计原则2.常见的哈希函数算法3.哈希冲突与解决方法4.哈希函数的优化策略5.实验中的哈希函数选择与应用三、哈希表的查找操作1.哈希表的存储结构与基本操作2.直接定址法查找3.拉链法查找4.其他查找方法与比较5.实验结果与分析四、哈希表的插入与删除操作1.插入操作的实现思路2.插入操作的效率分析3.删除操作的实现思路4.删除操作的效率分析5.实验结果分析与对比五、实验结果与总结1.实验数据的统计与分析2.实验中的问题与解决方案3.实验结论与总结4.对哈希算法的进一步探讨与应用展望5.实验的意义与启示总结：通过对哈希实验的详细阐述，我们对二次探测法、哈希函数、哈希表的查找、插入与删除操作有了更深入的了解。

实验结果与分析表明，在哈希表的实现中，选择合适的哈希函数、解决哈希冲突以及优化插入与删除操作，对提高哈希表的性能至关重要。

哈希算法作为一种重要的数据结构应用，具有广泛的应用前景，在实际问题中具有重要的实践意义。

通过本次实验，我们不仅提升了对数据结构的理论理解，也增强了数据结构算法的实践能力，为今后的学习与研究打下了坚实的基础。

课程实习报告一、需求分析：1.本程序来自于图书馆靠书名来检索想要查找的书问题。

2.本程序要求：（1）根据输入建立图书名称表，采用创建散列表实现。

（2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。

二、哈希表简介结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。

由此，不需比较便可直接取得所查记录。

这个对应关系f称为散列函数(Hash function），按这个思想建立的表为散列表。

* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。

具有相同函数值的关键字对该散列函数来说称做同义词。

* 综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”，作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。

科学家计算过，当负载因子(load factor)不超过75%，查找效率最高。

* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

程序设计流程程序思想(一)哈希函数unsigned int hash_BKDE(char *str)生成映射地址，成为散列表的编号。

(二)哈希表HashTable::HashTable()通过数组储存元素(三)插入函数void HashTable::insert(char*c)插入字符串，先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。

(四)查找函数bool HashTable::find(char*c)进行查找，先计算要生成字符串的地址，再到散列表中进行查找比较。

哈希表设计题目哈希表设计[问题描述]针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

[基本要求]假设人名为中国姓名的汉语拼音形式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

构造哈希函数，用链表法处理冲突。

[测试数据]读取熟悉的30个人的姓名作测试。

一．需求分析：1. 针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

2. 人名为中国姓名的汉语拼音形式。

待填入哈希表的人名共有30个，取平均查找长度的上限为2。

3. 用每个名字各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字，用除余法构造哈希函数，用拉链法处理冲突。

4.输入数据：zhaoxuening ，muchunyang ，lvzhihui，jiangbiwen，zhangye ，libaoling，yulin，wangjie，huangzheng，xiahaiyun，tanyongli，yangjiaqi，liufengbin，wangfeng，huangweilun，chenliang，hezhicong，yaochengzhong，chaozhihao，wangshipeng，ganyongze，luyang，baichongliang，zhurui，chenyiming，pengxuan，equanming，lishiwei，baitian，wuliao。

5.测试数据：lishiwei，zhurui，abcdefg，wangshipeng二．概要设计1.程序流程图2.存储结构：名字表：struct Name{ //名字表char *name; //名字int key; //关键码}哈希表：struct Node;typedef struct Node * PNode;struct Node{ //每条单链表结点结构定义char *name;PNode link;};struct HashDic{ //哈希表结构定义PNode llist[P]; //哈希表所包含的单链表，P为基本区域长度float search; //总查找长度float total; //哈希表中名字数int m; //哈希表长度};};typedef struct HashDic *PHashDic; //哈希表类型3.主要算法: (1). int h(char *py){ }//除余法，返回名字在哈希表中的相应地址(2) PHashDic create_EmptyDic(){ } //创建空哈希表(3)void insert_node(PHashDic phash,char *py) { } //插入算法(4)void search_node(PHashDic phash){ } //查找算法(5)void delete_node(PHashDic phash){ } //删除算法(6)void output_name(){ } //输出姓名表(7)void output_hash(PHashDic phd){ } //输出哈希表(8)void InitNameTable(){ } //姓名表的初始化(9)void print(){ } //打印操作菜单(10)void main(){ } //主函数三．详细设计1. 除余法，返回名字在哈希表中的相应地址int h(char *py){int key;for (int i=0;i<NAME_LEN;i++) //将字符串的各个字符所对应的ASCII码相加，所得的整数做为名字的关键字{int s=0;char *p=py;for (int j=0;*(p+j)!='\0';j++)s+=int(*(p+j));key=s;}return key%P;}2. 创建空哈希表PHashDic create_EmptyDic(){PHashDic phash=(PHashDic)malloc(sizeof(struct HashDic));int i;phash->search=0;phash->total=0;phash->m=P;for(i=0;i<phash->m;i++){phash->llist[i]=NULL;}return phash;}3. 插入算法void insert_node(PHashDic phash,char *py){PNode p,q;int r=1; //查找长度大于2的py的查找长度nt adr=h(py);if(phash->llist[adr]==NULL){ //如果单链表为空，向单链表插入第一个元素p=(PNode)malloc(sizeof(struct Node)); //创建新结点p->name=py;p->link=NULL;phash->llist[adr]=p;phash->total++;phash->search+=1;return;}q=phash->llist[adr];if (strcmp(q->name,py)==0) //如果已有此元素则不再插入{cout<<"名字已经存在"<<endl;return;}while (q->link!=NULL){if(strcmp(q->link->name,py==0{cout<<"名字已经存在"<<endl;return;}q=q->link;r++;}p=(PNode)malloc(sizeof(struct Node)); //否则就插入单链表最后p->name=py;p->link=NULL;q->link=p;r++;phash->search+=r;phash->total++;}4. 查找算法void search_node(PHashDic phash){PNode p;int adr,r; //哈希表地址和查找长度char py[20];cout<<"请输入要查找的名字:\n";cin>>py;adr=h(py);if(phash->llist[adr]==NULL) cout<<"查找结果:\n"<<"没有想要查找的人!!\n";//如果相应单链表为空，则没有所要查找的名字else {p=phash->llist[adr];while(strcmp(p->name,py)!=0 && p->link!=NULL)//否则对比单链表内容直到查找到名字或对比完单链表中数据{p=p->link;r++;}if(strcmp(p->name,py)==0)cout<<"查找结果:\n"<<"名字:"<<py<<" 地址"<<adr<<" 查找长度"<<r<<endl;//查找到名字else cout<<"查找结果:\n"<<"没有想要查找的人\n"; //对比完单链表中数据,没有该名字}}5. 删除算法void delete_node(PHashDic phash){PNode p,q;int r=1; //查找长度char py[20]={0};cout<<"请输入要删除的名字:\n";cin>>py;int adr=h(py);if(phash->llist[adr]==NULL) //如果相应单链表为空，则没有所要删除的名字{cout<<"没有想要删除的名字!!\n";return;}p=phash->llist[adr];if(strcmp(p->name,py)==0) //如果要删除的是单链表第一个元素{phash->llist[adr]=p->link;free(p);cout<<"删除完成!!\n";phash->total--;phash->search-=1;return;}while(p->link!=NULL && strcmp(p->link->name,py)!=0 )//否则对比单链表内容直到查找到名字或对比完单链表中数据{p=p->link;}if(strcmp(p->link->name,py)==0) //查找到名字{q=p->link;p->link=q->link;free(q);cout<<"删除完成!!\n";r++;phash->search-=r;phash->total--;return;}else //对比完单链表中数据,没有该名字{cout<<"没有想要删除的名字!!\n";return;}}6. //输出姓名表void output_name(){ //输出姓名表int i;printf("序号\t\t 姓名\t\t 关键字\n");for (i=0;i<NAME_LEN;i++)printf("%2d %18s \t\t %d \n",i,NameTable[i].name,NameTable[i].key); }7.输出哈希表void output_hash(PHashDic phd){ //输出哈希表PNode p;float ASL; //平均查找长度nt i;cout<<"地址名字\n";for (i=0;i<P;i++){p=phd->llist[i];cout<<i;while(p!=NULL){cout<<" 一> "<<p->name;p=p->link;}cout<<endl;}ASL=phd->search/phd->total;cout<<"平均查找长度："<<ASL<<endl;}8. 姓名表的初始化void InitNameTable(){NameTable[0].name="zhaoxuening";NameTable[1].name="muchunyang";NameTable[2].name="lvzhihui";NameTable[3].name="jiangbiwen";NameTable[4].name="zhangye";NameTable[5].name="libaoling";NameTable[6].name="yulin";NameTable[7].name="wangjie";NameTable[8].name="huangzheng";NameTable[9].name="xiahaiyun";NameTable[10].name="tanyongli";NameTable[11].name="yangjiaqi";NameTable[12].name="liufengbin";NameTable[13].name="wangfeng";NameTable[14].name="huangweilun";NameTable[15].name="chenliang";NameTable[16].name="hezhicong";NameTable[17].name="yaochengzhong";NameTable[18].name="chaozhihao";NameTable[19].name="wangshipeng";NameTable[20].name="ganyongze";NameTable[21].name="luyang";NameTable[22].name="baichongliang";NameTable[23].name="zhurui";NameTable[24].name="chenyiming";NameTable[25].name="pengxuan";NameTable[26].name="equanming";NameTable[27].name="lishiwei";NameTable[28].name="baitian";NameTable[29].name="wuliao";for (int i=0;i<NAME_LEN;i++)//将字符串的各个字符所对应的ASCII码相加，所得的整数做为名字的关键字{int s=0;for (int j=0;NameTable[i].name[j]!='\0';j++)s+=int(NameTable[i].name[j]);NameTable[i].key=s;}}9. 打印操作菜单void print(){cout<<" ********************************************************\n";cout<<" 操作菜单\n";cout<<" 1.输出姓名表\n";cout<<" 2.输出哈希表\n";cout<<" 3.查找\n";cout<<" 4.删除\n";cout<<" 5.插入\n";cout<<" 6.退出\n";cout<<" ********************************************************\n"; }10.主函数void main(){int i,c,k=0;PHashDic phash=create_EmptyDic(); //创建空哈希表phashInitNameTable();for (i=0;i<NAME_LEN;i++) //将名字表中的名字存入哈希表insert_node(phash,NameTable[i].name);print(); //打印操作菜单cout<<"请选择操作:";cin>>c;while(c!=1&&c!=2&&c!=3&&c!=4&&c!=5&&c!=6) {cout<<"请重新选择操作:";cin>>c;}do{//当选择6时结束算法,选择1，2，3，4，5则执行相应操作直到结束switch(c){case 1:output_name();print();break; //输出姓名表case 2: output_hash(phash);print();break; //输出哈希表case 3:search_node(phash);print();break; //查找case 4:delete_node(phash);print();break; //删除case 5:{char py[20]; //插入cout<<"请输入要插入的名字:\n";cin>>py;insert_node(phash,py);}print();break;case 6:cout<<"已退出\n";break;default:cout<<"\n请输入正确的选择!\n:";}if(c!=6){cout<<"请选择操作:";cin>>c;while(c!=1&&c!=2&&c!=3&&c!=4&&c!=5&&c!=6){cout<<"请重新选择操作:";cin>>c;}}}while (c==1||c==2||c==3||c==4||c==5); }四．调试分析1.输出姓名表2.输出哈希表3.查找：lishiwei和abcdefg4.删除：lishiwei,zhurui,abcdefg5.插入：abcdefg和wangshipeng6.退出五．课程设计总结算法分析及改进：1. 由于要对哈希表进行插入，删除等操作字典元素处于动态，而且名字出现无规律可言，因此采用除余法构造哈希函数h(x) = x mod P 。

数据结构实验报告四——哈希表查找名字（字符串）实验题目：哈希表查找名字（字符串）实验目标：输入一组名字（至少50个），将其保存并利用哈希表查找。

输出哈希查找冲突次数，哈希表负载因子、查找命中率。

数据结构：哈希表和数组（二维）。

二维数组用于静态顺序存储名字（字符串），哈希表采用开放定址法，用于存储名字（字符串）对应的关键字并实现对名字（字符串）的查找。

需要的操作有：1.关键字求取（主函数中两次出现，未单独编为函数）关键字key=abs（字符串首位ASCII码值-第二位ASCII码值+第（[]+1）位ASCII码值-最后一位ASCII码值-倒数第二位ASCII码值）*字符串长度（abs为求整数绝对值的函数）。

2.处理关键字的哈希函数（Hash）利用平方取中法求关键值key在哈希表中的位置。

公式add=（key*key）%1000/LENGTH（add 为key在哈希表中的地址）。

int Hash(int key){return((key*key)/1000%LENGTH);}3.处理哈希表中冲突的函数（Collision）利用线性探测再散列处理冲突，利用全局变量count统计冲突次数。

int Collision(int key,int Hashtable[]){int i;for(i=1;i<=LENGTH;i++){if(Hashtable[(Hash(key)+i)%LENGTH]==-1)return((Hash(key)+i)%LENGTH);count++;}}4.哈希表初始化（InitHash）void InitHash(int Hashtable[]){int i;for(i=0;i<LENGTH;i++)Hashtable[i]=-1;}5.向哈希表中插入关键字（InsertHash）void InsertHash(int key,int Hashtable[]){int add;if(Hashtable[add]==-1)Hashtable[add]=key;else{add=Collision(key,Hashtable);Hashtable[add]=key;}}6.查找关键字在哈希表中的存储位置（SearchHash）int SearchHash(int key,int Hashtable[]){int add;add=Hash(key);if(Hashtable[add]==key)return add;while(Hashtable[add]!=key&&Hashtable[add]!=-1)add=Collision(key,Hashtable);return add;}7.输出哈希表（PrintHash）（帮助调试用）void PrintHash(int Hashtable[]){int i;for(i=0;i<LENGTH;i++)if(Hashtable[i]!=-1)printf("%3d:%d\n",i+1,Hashtable[i]);}8.求字符串长度（strlen）（函数库<string.h>包含）以及求整数的绝对值（abs）（函数库<math.h>包含）算法设计：1建立长度为LENGTH的哈希表Hash（LENGTH具体值由宏定义决定）。

实习报告题目：设计一个哈希表，完成相应的建表和查表程序一、班级：1503013 姓名：李睿元学号：完成日期：需求分析1. 假设人名为中国人名的汉语拼音形式；2. 待填入哈希表的姓名共有30个，去平均查找长度的上限为2；3. 哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；4. 取读者周围较熟悉的30个人的姓名。

二、概要设计1. 抽象数据类型的定义：（1）人名数据表：typedef struct Node{char name[20];int key;}Node,NodeList[MAX];（2）哈希表：typedef struct hashtable{char* name;int key;int conflict_time;}HashTable[hashlen];（3）变量：#define P 61主要函数的实现：（1）哈希函数：int Hash(int key)（2）关键字获得：int GetKey(char str[])（3）文件流中读取姓名：void GetName(NodeList &L,int i,FILE* fp)（4）哈希表的初始化：void InitialHashTable(HashTable &ht)（5）伪随机探测序列的生成：void CreatConfilctArray(int n[])（6）哈希表的生成：void CreatHashTable(HashTable &ht,NodeList L,int* n)（7）哈希表的查询：void SearchHashTable(HashTable ht,int* n,char get_name[])三、详细设计#include <>#include <>#include <>#define P 61ame);L[i].key=GetKey(L[i].name); */fscanf(fp,"%s",L[i].name);L[i].key=GetKey(L[i].name);onflict_time=0;ht[n].name=NULL;ht[n].key=0;n++;}}void CreatConfilctArray(int n[]){ey);if(ht[t].conflict_time==0){ht[t].name=L[i].name;ht[t].conflict_time++;ht[t].key=L[i].key;printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,t);}else{int m=0;int d=(t+n[m])%hashlen;while(ht[d].conflict_time!=0){ht[d].conflict_time++;m++;d=(t+n[m])%hashlen;}ht[d].name=L[i].name;ht[d].conflict_time++;ht[d].key=L[i].key;printf("姓名：%s key值：%d 表内存储位置：%d\n",L[i].name,L[i].key,d);}i++;}}void SearchHashTable(HashTable ht,int* n,char get_name[]){onflict_time==0&&ht[h].key!=k){printf("表中未找到无此人！\n");break;}else if(ht[h].key==k){printf("已找到%s，表内存储位置：%d\n",get_name,h);break;}else{p++;h=n[p];}*/if(ht[h].name==NULL){printf("表中未找到无此人！\n");break;}else if(strcmp(ht[h].name,get_name)==0){printf("已找到%s，表内存储位置：%d，查找次数:%d\n",get_name,h,s_time);break;}else{p++;h=(t+n[p])%hashlen;s_time++;}}}int main(){哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；2. 除留余数法对于p的选择很重要，经过分析后的选择是p为小于等于m的最大素数，最终选择了61；3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。

散列表一、问题描述我们希望在浩瀚的图书中，去发现一本书是否存在。

我们不知道书的编号，只知道它的书名。

（其实这已经不错了...）。

通过书名，来查询它是否存在。

为了简化问题，我们假设每本书的书名都是一组小写字母组成，长度不超过100字符。

二、需求分析1.根据输入建立图书名称表，采用散列表实现该表，散列函数自建。

2.数据的输入输出格式：输入分为两部分输入：第一部分，第一行是行数n，n <= 5000。

余下n行，每行一个字符串。

表示已存在的图书记录。

第二部分，第一行是行数m，m <= 1000。

余下m行，每行一个字符串。

表示要查询的图书记录。

输出：输出为m行，如果被查的记录存在，则输出"YES",如果不存在则输出"NO"。

3.测试数据输入：4aansandhellocpp9abanasansandandehellocbbhellocpp输出：YESNONONOYESYESNONOYES三、概要设计抽象数据类型class Node//最基本的抽象数据类型{public:char ch[20];//链表中，记录表中数据，20为查找字符串的长度Node* next;//指向下一个结点Node(const char* in);//构造函数};class List{ //用Node作结点的链表public:Node* head;Node* tail;Node* fence;List();~List();bool append(const char* in);//像链表中，增添结点};class Hash//哈希表的详细设计{private:List* myList;//指向链表数组public:int getSubInt(const char* in) const; //哈希函数，把传进的字符串的ASCII//相加，再mod哈西表大小，得该字符串的位置Hash();~Hash();bool insert(const char*) const;//建立哈希表bool find(const char*) const;//在哈希表中查找};int Hash::getSubInt(const char *in) const//哈希函数的实现{int sum=0,i=0;while(in[i]!='\0')sum+=in[i++];return sum%tableSize;}算法的基本思想本程序采用了开散列表，用一个链表数组实现。