数据结构与算法-散列表查找操作实验

1、广州XX学院数据结构与算法实验报告专业班级姓 名实验名称计科181实验日期2019.12.10XX学 号20181533实验6.散列表查找操作指导教师曾岫成 绩一、实验目的1 .熟悉散列查找方法和特点。2 .掌握散列查找解决冲突的方法。3 .用C语言完成算法和程序设计并上机调试通过；4 .撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分 析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运 行结果（必要时给出多种可能的输入数据和运行结果）。二、实验要求1、程序要求包含头文件以及 main函数2、实验中所设计的函数（算法）需要满足实验的要求3、程序的编译、运行要成

2、功通过4、运行的结果正确，且有相应的提示三、实验环境WIND7 VC+6.0或C与C+程序设计学习与实验系统四、实验内容1 .闭散列表查找的实现2 .开散列表查找的实现五、源代码及算法分析1 .闭散列表查找的实现假定的最大存储单元数*/ 以整型为元素类型*/定义散列表数组*/#include "stdio.h"#define MAXSIZE 20/*typedef int keytype;/*typedef keytype HTableMAXSIZE; /*/*用线性探测再散列法处理冲突建立散列表*/void creHT（HTable HT,int m,int p） /*创

3、建长度为 m的散列表,p 为除留余数中的除数*/ int i,n=0; keytype x;for(i=0;i<m;i+) HTi=-1;/*printf("Input datas(-1:End):"); scanf("%d",&x);while(x!=-1) n+;if(n>m) break; /* n i=x%p;/*while(HTi!=-1)/*i=(i+1)%m;HTi=x;/*scanf("%d",&x);/* 输出散列表*/void list(HTable HT,int m) /* int i

4、;for(i=0;i<m;i+) printf("%5d",i);printf("n");for(i=0;i<m;i+) printf("%5d",HTi);printf("n");初始化散列表*/记录散列表中的元素个数*/计算散列地址*/线性探测*/将元素存入空闲单元*/输出长度为m的散列表*/在长度为m的散列表中取地址*/找到 */没找到*/* 查找算法*/int search(HTable HT,int m,keytype x,int p)/* 查找关键字为x 的元素 */ int i,j;i=x

5、%p;/*j=i;while(HTj!=-1) if(HTj=x) return j; /*j=(j+1)%m;if(j=i) break;/*return -1;/* 计算查找成功时的平均查找长度*/float ASLsucc(HTable HT,int m,int p) /* 计算查找成功时的平均查找长度 */ int i,j,n,s=0;for(i=0,n=m;i<m;i+)/*查找成功的可能性有n 种 */ if(HTi=-1) n-;continue;/*j=HTi%p;s+=(m+i-j+1)%m;/*次数，并进行累加*/return (float)s/n;/* 计算查找失败

6、时的平均查找长度*/float ASLfail(HTable HT,int m,int p) /*度 */ int i,j,k,s=0;for(i=0;i<p;i+)/* k=0;j=i;while(HTj!=-1) k+;j=(j+1)%m;if(j=i) break;/*况 */s+=k;/* k并进行累加*/return (float)s/p;main() HTable HT;int m=9,p=9;keytype key;creHT(HT,m,p);/*列函数的余数为9。以【例7.8】为例 */list(HT,m);/*printf("n"); scanf(&

7、quot;%d",&key);/*printf("%dn",search(HT,m,key,p); /* printf("%6.2fn",ASLsucc(HT,m,p); /*长度*/printf("%6.2fn",ASLfail(HT,m,p); /*长度*/2开散列表查找的实现统计散列表中的元素个数*/计算成功查找HTi 的比较计算查找失败时的平均查找长查找失败的可能性有p 种 */当元素填满整个空间时的情为查找失败时的比较次数，建立散列表，长度为9，散输出散列表*/输入查找元素*/输出查找结果*/输出查找成功时

8、的平均查找输出查找失败时的平均查找#include "stdio.h"/*typedef int keytype; typedef struct node keytype data;struct node *next;slink;/*/* 用拉链法处理冲突建立散列表*/void creHT(slink *HT,int m,int p) /*数 */ int i; keytype x; slink *s; for(i=0;i<m;i+)HTi=NULL;/*printf("Input datas(-1:End):"); scanf("%d&

9、quot;,&x);while(x!=-1) i=x%p;/*s=(slink *)malloc(sizeof(slink); s->data=x;/*s->next=HTi; HTi=s;/*scanf("%d",&x);/* 输出散列表*/void list(slink *HT,int m) /* int i;slink *q;for(i=0;i<m;i+) printf("%5d=> ",i);q=HTi;while(q) printf("%5d ",q->data); q=q-&g

10、t;next; printf("n");关键字类型*/链表结点类型*/建立表长为m的散列表,p为除散列表初始化*/计算散列地址*/生成结点*/用首插法插入结点*/输出散列表，m是表长*/* 查找算法*/int search(slink *HT,int p,keytype x) /* 在散列表中查找指定元素，p 为除数 */ slink *q;int i;i=x%p;/*计算散列地址*/q=HTi;while(q)/* if(q->data=x) return i; /* q=q->next;return -1;/*/* 计算查找成功时的平均查找长度*/float

11、 ASLsucc(slink *HT,int p) /*找长度 ,p 为除数 */ int i,n=0,k,s=0; slink *q;for(i=0;i<p;i+) k=0;q=HTi;while(q) s+=+k;/*加 */n+;/*q=q->next;return (float)s/n;/* 计算查找失败时的平均查找长度*/float ASLfail(slink *HT,int p) /*长度 ,p 为除数 */ int i,n=0; slink *q;for(i=0;i<p;i+) q=HTi; while(q) n+;/* n次数 */q=q->next;return (float)n/p;在相应链表中查找*/找到 */没找到 */计算查找成功时的平均查计算比较次数，并进行累统计表中的元素个数*/计算查找失败时的平均查找既是元素个数，也是比较main() slink *HT9;int m=9,p=9;keytype key;creHT(HT,m,p);/*为例 */list(HT,m);/*scanf("%d",&key);/*printf("%dn",search(HT,p,key); /*printf(