数据结构实验七查找.docVIP

下载本文档

231
0
约3.58千字
约 6页
2017-01-18 发布于重庆
举报
版权申诉

数据结构实验七查找.doc

1、本文档共6页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
8、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

数据结构实验七查找

实验七查找一、实验目的 1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。二、实验内容和要求 1. 静态查找表技术依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的比较次数：查找key=35的比较次数：算法实现代码 2、哈希表的构造与查找 /* 采用开放地址法构造哈希表*/ #includestdio.h #includemalloc.h #define MAXSIZE 25 #define P 13 #define OK 1 #define ERROR 0 #define DUPLICATE -1 #define TRUE 1 #define FALSE 0 typedef struct{ /*哈希表元素结构*/ int key; /*关键字值*/ int flag; /*是否存放元素*/ }ElemType; typedef struct { ElemType data[MAXSIZE]; int count; /*元素个数*/ int sizeindex; /*当前哈希表容量*/ }HashTable; int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/ int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/ void dataset(int ds[],int *len); int InsertHash(HashTable *H,int e,int d[]); int CreateHash(HashTable *H,int ds[],int len,int d[]); int SearchHash(HashTable *H, int e,int d[]); void menu(); /*输入查找表*/ void dataset(int ds[],int *len){ int n,m; n=0; printf(\n查找表输入：); while(scanf(%d,m)==1){ /*以输入一个非整数作为结束*/ ds[n]=m; n++; } *len=n; } /*计算哈希地址，插入哈希表*/ int InsertHash(HashTable *H,int e,int d[]){ int k,i=1; k=e%P; while(H-data[k].flag==TRUE||k0){ k=(e%P+d[i])%MAXSIZE;i++; if(i=15) return ERROR; } H-data[k].key=e; H-data[k].flag=TRUE; H-count++; return OK; } /*构造哈希表*/ int CreateHash(HashTable *H,int ds[],int len,int d[]){ int i; for(i=0;ilen;i++){ if(SearchHash(H,ds[i],d)!=-1) return DUPLICATE; InsertHash(H,ds[i],d); if(H-count=MAXSIZE) return ERROR; } return OK; } /*初始化哈希表*/ void InitHash(HashTable *H){ int i; for(i=0;iMAXSIZE;i++){ H-data[i].key=0; H-data[i].flag=FALSE; } }