数据结构哈希表实验报告优质资料

数据结构哈希表实验报告优质资料(可以直接使用，可编辑优质资料，欢迎下载）

数据结构哈希表实验报告优质资料(可以直接使用，可编辑优质资料，欢迎下载）HUNAN课程实习报告题目：哈希表学生姓名唐鹏学生学号202108080216专业班级物联2班指导老师吴帆2021年4月2日本程序来自于图书馆靠书名来检索想要查找的书问题。本程序要求：（1）根据输入建立图书名称表，采用创建散列表实现。（2）建散列表后，如果想要查找的数据在散列表中输出yes否则输出no。结构中存在关键字和K相等的记录，则必定存储在f(K）的位置上。由此，不需比较便可直接取得所查记录。这个对应关系f称为散列函数(Hashfunction），按这个思想建立的表为散列表。*对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2），这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。*综上所述，根据散列函数H(key）和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”，作为这条记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶中，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当负载因子(loadfactor)不超过75%，查找效率最高。*若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（UniformHashfunction），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。程序设计流程程序思想哈希函数unsignedinthash_BKDE(char*str)生成映射地址，成为散列表的编号。哈希表HashTable::HashTable()通过数组储存元素插入函数voidHashTable::insert(char*c)插入字符串，先计算要插入字符串生成的映射地址，然后在相应的地址插入，如果没有空位查找空位插入。查找函数boolHashTable::find(char*c)进行查找，先计算要生成字符串的地址，再到散列表中进行查找比较。主函数main（）输入：输入散列表内容和要查找的数据个数和数据输出模块：散列表查找的结果。建散列表并查找：建立散列表并递归查找流程图三.实验源程序：#include<iostream>#include<cstdlib>#include<ctime>usingnamespacestd;unsignedinthash_BKDE(char*str)//哈希函数，题目给出{//初始种子seed可取31131131313131131313etc.. unsignedintseed=131; unsignedinthash=0; while(*str) { hash=hash*seed+(*str++); } return(hash&0x7FFFFFFF);}doublek=(double)(rand()%999)/1000;//随机生成小数随机数0<k<1unsignedinthash_rand(unsignedintvalue)//value<2^32，将转化地址转化为seed{ doublea=k*value; doublen=(a-(int)a)*64;//取小数部分与2^5相乘 unsignedintseed=(int)n; returnseed;}unsignedintHash(char*str)//生成最终的地址映射即计算散列地址位置{ returnhash_rand(hash_BKDE(str));}classHashTable//哈希表类{public:HashTable();~HashTable();voidinsert(char*c);boolfind(char*c);private:char**Arr;//二维数组用于保存字符串书名intArrSize;//散列表单元个数在此为2^15=32768};HashTable::HashTable(){ ArrSize=32768; Arr=newchar*[64]; for(inti=0;i<64;i++) { Arr[i]=newchar[100]; Arr[i]=NULL; }}HashTable::~HashTable(){ for(inti=0;i<64;i++) delete[]Arr[i]; delete[]Arr;}voidHashTable::insert(char*c)//插入到哈希表{ unsignedintpos=Hash(c);//计算散列地址位置 while(Arr[pos]!=NULL) pos=(pos+1);//解决冲突的办法，寻找空位，向后面挪动一个 Arr[pos]=c;//插入存储}boolHashTable::find(char*c)//查找{ unsignedintpos=Hash(c);//计算散列地址 while(Arr[pos]!=NULL)//非空时进行查找比较 { if(Arr[pos]==c)returntrue; pos=(pos+1);//寻找下一地址，如果运行这一步，这说明之前产生了冲突 } returnfalse;}intmain(){ boola[20]; char*c1=newchar[100]; HashTableH; cout<<"输入字符串个数n：\n"; intn; cin>>n; cout<<"输入n个字符串：\n"; for(inti=1;i<=n;i++) { cin>>c1; H.insert(c1);//直接插入到散列表的数组中 } cout<<"输入待查的字符串个数m：\n"; intm; cin>>m; cout<<"输入要查找的字符串:"<<endl; for(intj=0;j<m;j++) { cin>>c1; a[j]=H.find(c1);//bool量 } cout<<"查找结果(yes表示存在，no表示不存在)：\n"; for(intk=0;k<m;k++) if(a[k]) cout<<"yes\n"; else cout<<"No\n"; return0;}四、实验截图五、实验感想本次的实验首先要弄清楚哈希表，然后弄清楚最关键的两个模块，插入和查找。插入模块中，首先要有哈希函数生成映射地址，要有哈希表保存元素，然后就是自己设定的解决冲突的办法，这个程序是采用向下挪动一个办法，直到找到为空的地方保存。在查找中也是，先要通过哈希函数生成映射地址，通过这个地址参看哈希表中时候有元素，考虑到会有冲突的产生，那么必须那么必须要通过循环查找，要么找到元素，否则直到为空跳出查找。这也是这个程序的难点所在。总体来说，哈希表对于提高储存和查找效率方面有很大的提升。实验难度不是很大。实习报告题目：设计一个哈希表，完成相应的建表和查表程序班级：1503013姓名：李睿元学号成日期：2021.12.04需求分析1.假设人名为中国人名的汉语拼音形式；2.待填入哈希表的姓名共有30个，去平均查找长度的上限为2；3.哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突；4.取读者周围较熟悉的30个人的姓名。概要设计1.抽象数据类型的定义：（1）人名数据表：typedefstructNode{charname[20];intkey;}Node,NodeList[MAX];（2）哈希表：typedefstructhashtable{char*name;intkey;intconflict_time;}HashTable[hashlen];变量：#defineP61//随机数值#defineMAX30//人数#definehashlen61//哈希表长2.主要函数的实现：（1）哈希函数：intHash(intkey)关键字获得：intGetKey(charstr[])文件流中读取姓名：voidGetName(NodeList&L,inti,FILE*fp)哈希表的初始化：voidInitialHashTable(HashTable&ht)伪随机探测序列的生成：voidCreatConfilctArray(intn[])（6）哈希表的生成：voidCreatHashTable(HashTable&ht,NodeListL,int*n)哈希表的查询：voidSearchHashTable(HashTableht,int*n,charget_name[])详细设计#include<stdio.h>#include<stdlib.h>#include<string.h>#defineP61//随机数值#defineMAX30//人数#definehashlen61//哈希表长typedefstructNode{charname[20];intkey;}Node,NodeList[MAX];typedefstructhashtable{char*name;intkey;intconflict_time;}HashTable[hashlen];intHash(intkey){returnkey%P;}intGetKey(charstr[]){intt=0;char*s=str;while(*s){t+=*s;s++;}returnt;}voidGetName(NodeList&L,inti,FILE*fp){/*printf("请以拼音形式输入第%d个姓名:",i);scanf("%s",L[i].name);L[i].key=GetKey(L[i].name);*/fscanf(fp,"%s",L[i].name);L[i].key=GetKey(L[i].name);//printf("\n");}voidInitialHashTable(HashTable&ht){intn=0;while(n<hashlen){ht[n].conflict_time=0;ht[n].name=NULL;ht[n].key=0;n++;}}voidCreatConfilctArray(intn[]){//n=(int*)malloc(50*sizeof(int));inti=0,j=0;while(i<50){n[i]=rand()%(hashlen+1);for(;j<i;j++){if(n[i]==n[j]){j=0;n[i]=rand()%(hashlen+1);continue;}}i++;}}voidCreatHashTable(HashTable&ht,NodeListL,int*n){//CreatConfilctArray(n);inti=0;intt;while(i<MAX){t=Hash(L[i].key);if(ht[t].conflict_time==0){ht[t].name=L[i].name;ht[t].conflict_time++;ht[t].key=L[i].key;printf("姓名：%skey值：%d表内存储位置：%d\n",L[i].name,L[i].key,t);}else{intm=0;intd=(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("姓名：%skey值：%d表内存储位置：%d\n",L[i].name,L[i].key,d);}i++;}}voidSearchHashTable(HashTableht,int*n,charget_name[]){//printf("请输入要查询的姓名：");//charget_name[20];intp=-1;ints_time=1;//scanf("%s",get_name);inth,k;intt;k=GetKey(get_name);t=h=Hash(k);while(1){/*if(ht[h].conflict_time==0&&ht[h].key!=k){printf("表中未找到无此人！\n");break;}elseif(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;}elseif(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++;}}}intmain(){//printf("请输入建表所需的三十个人名！\n");inti,j;NodeListL;HashTableht;InitialHashTable(ht);charget_name[20]={0};intrand_n[50];CreatConfilctArray(rand_n);FILE*fp;fp=fopen("name.txt","r");for(i=0;i<30;i++){GetName(L,i,fp);}fclose(fp);CreatHashTable(ht,L,rand_n);printf("\n");printf("--------------哈希表建表完成-------------");printf("\n");while(1){get_name[20]={0};printf("请输入要查找的人名(输入“***”表示结束程序):");scanf("%s",get_name);printf("关键字：%d",GetKey(get_name));if(strcmp(get_name,"***")==0)break;SearchHashTable(ht,rand_n,get_name);}return0;}调试分析1.哈希表可以在理想情况下不经过任何比较，一次存取就能得到所查记录；2.除留余数法对于p的选择很重要，经过分析后的选择是p为小于等于m的最大素数，最终选择了61；3.伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。用户手册1.本程序的运行环境为Windows操作系统，执行文件为hashtable.exe；2.本程序的输入的名字存储在name.txt文件中；3.程序进入后已经完成哈希表的构建并进行展示，用户只需进行相应的查找；测试数据1.挑选表中已有的十个姓名进行测试（xiaoli,zhuangshuangshuang,laobai,lujia,xiaohei,huyazhou,abao,haojie,taosiji,wangkun）与上方的哈希表进行对比完全匹配。2.选择5个没有在表中的名字进行查表操作：（lovetianqi,tianjiejie,jiwang,beijing,heheda）数据结构实验报告姓名学号号实验地点数学楼指导教师实验名称队列的表示与实现1、实验目的了解和掌握队列的数据类型描述及其特点；完成链队列的初始化、入队、出队、取对头元素、显示操作的实现；掌握队列的链式存储表示与基本操作算法实现；掌握队列在实际问题中的应用和基本编程技巧。2、实验方法队列的抽象数据类型定义：ADTQueue{ //数据对象:D={a[i]|a[i]∈ElemSet,i=1,2,...,n,n>=0} //数据关系：R1={<a[i-1],a[i]>|a[i-1],a[i]∈D,i=2,...,n} //约定其中a[1]端为队列头，a[n]端为队列尾 //基本操作： InitQueue(&Q)//操作结果：构造一个空队列Q。 DestoryQueue(&Q)//初始条件：队列Q已存在//操作结果：队列Q被销毁，不再存在 ClearQueue(&Q)//初始条件：队列Q已存在//操作结果：将Q清为空队列 QueueEmpty(Q)//初始条件：队列Q已存在 //操作结果：若队列Q为空队列，则返回TRUE,否则FALSE QueueLength(Q)//初始条件：队列Q已存在 //操作结果：返回Q的元素个数，即队列的长度 GetHead(Q,&e)//初始条件：Q为非空队列 //操作结果：用e返回Q的队头元素 EnQueue(&Q,e)//初始条件：队列Q已存在 //操作结果：插入元素e为Q的新的队尾元素 DeQueue(&Q,&e)//初始条件：Q为非空队列 //操作结果：删除Q的队头元素，并用e返回其值 QueueTraverse(Q,visit())//初始条件：Q已存在且非空 //操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。}ADTQueue与线性表类似，队列有两种存储表示链队列和循环队列。//-----基本操作的函数原型说明-----statusINitQueue(LinkQueue&Q)//构造一个空队列QStatusDestoryQueue(LinkQueue&Q)//销毁队列Q,Q不再存在StatusClearQueue(LinkQueue&Q)//将Q清为空队列StatusQueueEmpty(LinkQueueQ)//若队列Q为空队列，则返回TRUE，否则返回FALSEintQueueLength(LinkQueueQ)//返回Q的元素个数，即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e)//若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERRORStatusENQueue(LinkQueue&Q,QElemTypee)//插入元素e为Q的新的队尾元素StatusDeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERRORstatusQueueTraverse(linkQueueQ,visit())//从队头到队尾依次对队列Q中的每个元素调用函数visit()。一旦visit失败，则操作失败。链队列：//单链队列——队列的链式存储结构typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront;//队头指针 QueuePtrrear;//队尾指针}LinkQueue;//-----单链队列的基本操作的算法描述------statusINitQueue(LinkQueue&Q){//构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front)exit(OVERFLOW);//存储分配失败 Q.front->next=NULL; returnOK;}StatusDestoryQueue(LinkQueue&Q){//销毁队列Q,Q不再存在 while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear;} returnOK;}StatusClearQueue(LinkQueue&Q)//将Q清为空队列StatusQueueEmpty(LinkQueueQ)//若队列Q为空队列，则返回TRUE，否则返回FALSEintQueueLength(LinkQueueQ)//返回Q的元素个数，即为队列的长度StatusGetHead(LinkQueueQ,QElemType&e)//若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERRORStatusENQueue(LinkQueue&Q,QElemTypee){//插入元素e为Q的新的队尾元素 p=(QueuePtr)malloc(sizeof(QNode)); if(!p)exit(OVERFLOW);//存储分配失败 p->data=e;p->next=NULL; Q.rear->next=p; Q.rear=p; returnOK;}StatusDeQueue(LinkQueue&Q,QElemType&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}statusQueueTraverse(linkQueueQ,visit())//从队头到队尾依次对队列Q中的每个元素调用函数visit()。//一旦visit失败，则操作失败。循环队列：//循环队列——队列的顺序存储结构#defineMAXQSIZE100//最大队列长度typedefstruct{ QElemType*base;//初始化的动态分配存储空间 intfront;//头指针，若队列不空，指向队列头元素 intrear;//尾指针，若队列不空，指向队列尾元素的下一个位置}SqQueue;//-----循环队列的基本操作的算法描述------StatusInitQueue(SqQueue&Q){ //构造一个空队列Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base)exit(OVERFLOW);//存储分配失败 Q.front=Q.rear=0; returnOK;}intQueueLength(SqQueueQ){//返回Q的元素个数，即队列的长度 return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}statusEnQueue(SqQueue&Q,QElemType){//插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//队列满 Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE; returnOK;}StatusDeQueue(Squeue&Q,QElemType&e){ //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK； //否则返回ERROR if(Q.front==Q.rear)returnERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXQSIZE; returnOK;}3、事先定义的常量和类型/***********************C函数库定义****************/#include<stdio.h>//EOFNULL#include<string.h>#include<malloc.h>//malloc();#include<limits.h>//ENTMAX#include<stdlib.h>#include<math.h>//floor(),fabs(),abs(),ceil(),#include<io.h>//eof()#include<process.h>//exit()#include<iostream.h>//cout,cin/******************函数结果状态代码****************/#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1//#defineOVERFLOW-2//因为math.h中已经定义OVERFLOW为3typedefintQElemType;//ElemType是变量的类型定义typedefintStatus;//Status是函数的类型，其值是函数结果状态代码,如OK，TRUE。4、实验过程链队列#include<stdio.h>#include<stdlib.h>#include<process.h>#defineOK1#defineERROR0#defineOVERFLOW0typedefstructQNode{ intdata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront; QueuePtrrear;}LinkQueue;intInitQueue(LinkQueue&Q){ Q.rear=Q.front=(QueuePtr)malloc(sizeof(QNode)); if(!Q.rear) exit(OVERFLOW); Q.front->next=NULL; returnOK;}voidQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear)printf("该链队为空:"); else printf("该链队不为空:");}voidEnQueue(LinkQueue&Q,inte){ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) printf("error"); p->data=e; Q.rear->next=p; Q.rear=p; printf("元素%d入队成功",e);}intEnnQueue(LinkQueue&Q,inte){ QueuePtrp; p=(QueuePtr)malloc(sizeof(QNode)); if(!p) returnERROR; p->data=e; Q.rear->next=p; Q.rear=p; returnOK;}voidDeQueue(LinkQueue&Q){ QueuePtrp; if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; Q.front->next=p->next; if(Q.rear==p) Q.rear=Q.front; free(p); printf("队首元素删除成功");}voidGetHead(LinkQueue&Q){ QueuePtrp; if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; printf("队首元素为:%d",p->data);}voidOutQueue(LinkQueue&Q){ QueuePtrp; if(Q.front==Q.rear) printf("该链队为空"); p=Q.front->next; while(p!=Q.rear->next) { printf("%d",p->data); p=p->next; }}voidLengthQueue(LinkQueue&Q){ intf=0; QueuePtrp; if(Q.front==Q.rear) printf("该队列的长度是:%d",f); else { p=Q.front->next; while(p!=Q.rear->next) { p=p->next; f++; } printf("该队列的长度是:%d",f); }}voidmain(){ system("cls"); intflag=1,i; LinkQueueQ; InitQueue(Q); printf("************************链队列功能菜单***********************\n"); printf("1:初始化链队列,2:判断链队列是否为空,3:进入队列,4:取出队首元素\n"); printf("5:输出该队列的所有元素,6:输出该队列的长度,7:结束程序,8:清屏\n"); while(flag) { printf("\n请输入操作符:"); scanf("%d",&i); switch(i) { case1: inte,n,k; printf("请输入队列的长度:"); scanf("%d",&n); printf("请输入队列的元素:"); for(e=1;e<=n;e++) { scanf("%d",&k); EnnQueue(Q,k); } printf("初始化链队成功"); break; case2: QueueEmpty(Q); break; case3: intj; printf("请输入要进入队列的元素"); scanf("%d",&j); EnQueue(Q,j); break; case4: GetHead(Q); break; case5: printf("该队列的元素是:"); OutQueue(Q); break; case6: LengthQueue(Q); break; case7: flag=0; break; case8: system("cls"); break; } } printf("程序结束");}循环队列#include<stdio.h>#include<stdlib.h>#include<process.h>#defineMAXSIZE10;#defineOK1;#defineERROR0;#defineOVERFLOW0;typedefstruct{ int*data; intfront; intrear;}SqQueue;intInitQueue_Sq(SqQueue&Q){Q.data=(int*)malloc(10*sizeof(int)); if(!Q.data) exit(0); Q.front=Q.rear=0; returnOK;}intEnQueue_Sq(SqQueue&Q,inte){ if((Q.rear+1)%10==Q.front) returnERROR; Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%10; returnOK;}voidIfEmpty(SqQueueQ){ if(Q.rear=Q.front) printf("该循环队列是空队列\n"); else printf("该循环队列不是空队列\n");}voidIfFull(SqQueueQ){ if((Q.rear+1)%10==Q.front) printf("该循环队列已满\n"); else printf("该循环队列未满\n");}voidInQueue_Sq(SqQueue&Q,inte){ if((Q.rear+1)%10==Q.front) printf("循环队列已满\n"); else { Q.data[Q.rear]=e; Q.rear=(Q.rear+1)%10; printf("元素%d成功进入循环队列\n",e); }}voidDeQueue_Sq(SqQueue&Q