哈希表操作代码.docx

上传人:王** 文档编号:55121 上传时间:2022-12-10 格式:DOCX 页数:4 大小:19.40KB
下载 相关 举报
哈希表操作代码.docx_第1页
第1页 / 共4页
哈希表操作代码.docx_第2页
第2页 / 共4页
哈希表操作代码.docx_第3页
第3页 / 共4页
哈希表操作代码.docx_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述

《哈希表操作代码.docx》由会员分享,可在线阅读,更多相关《哈希表操作代码.docx(4页珍藏版)》请在优知文库上搜索。

1、哈希表操作代码.txt20假如你努力去发觉美妙,美妙会发觉你;假如你努力去敬重他人,你也会获得别人敬重;假如你努力去关心他人,你也会得到他人的关心。生命就像一种回音,你送出什么它就送回什么,你播种什么就收获什么,你赐予什么就得到什么。itincludeincludeinclude*malloc()等*/ttinclude*INLMAX等*/ttinclude*EOF(=N或F6),NULL*/include*atoi()*/ttinclude*eof()*/#include*floor(),cei1(),abs()*/ttinclude*exit()*/*函数结果状态代码*/defineTRU

2、E1#defineFALSE0#defineOK1#defineERROR0defineINFEASIBLE-1*StatUS是函数的类型,其值是函数结果状态代码,如OK等*/defineNULLKEY0*0为无纪录标志*/defineN10/*数据元素个数*/typedefintKeyType;/*设关键字域为整型*/typedefintStatus;typedefstruct(KeyTypekey;intord;ElemType;*数据元素类型*/#defineEQ(a,b)(a)=(b)inthashsize=ll,19,29,37);*哈希表容量递增表,一个合适的素数序列*/intm=

3、0;/*哈希表表长,全局变量*/typedefstruct(ElemType*elcm;/*数据元素存储基址,动态安排数组*/intcount;/*当前数据元素个数*/intsizeindex;*hashsizesizeindex为当前容量*/JHashTable;#defineSUCCESS1defineUNSUCCESS0#defineDUPLICATE-1StatusInitHashTable(HashTable*H)*操作结果:构造一个空的哈希表*/inti;(*H).count=0;/*当前元素个数为0*/(*H).Sizeindcx=O;/*初始存储容量为hashsize0*/m=

4、hashsizeO;(*H).elem=(ElemType*)malloc(m*sizeof(ElcmTypc);if(!(*H).elem)exit(OVERFLOW);*存储安排失败*/for(i=0;im;i+)(*H).elemi.key=NULLKEY;*未填纪录的标志*/returnOK;)voidDestroyHashTable(HashTable*H)*初始条件:哈希表H存在。操作结果:销毁哈希表H*/free(*H).elem);(*H).eIem=NULL;(*H).count=0;(*H).Sizeindex=O;)unsignedHash(KeyTypeK)/*一个简洁

5、的哈希函数(m为表长,全局变量)*/returnK%m;)voidcollision(int*p,intd)/*线性探测再散列*/*开放定址法处理冲突*/*p=(*p+d)%m;)StatusSearchHash(HashTableH,KeyTypeK,int*p,int*c)/*在开放定址哈希表H中查找关键码为K的元素,若查找胜利,以P指示待查数据*/*元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS*/*C用以计冲突次数,其初值置零,供建表插入时参考。*/*p=Hash(K);/*求得哈希地址*/whiIe(H.elem*p.key!=NULLKEY&

6、!EQ(K,H.elem*p.key)(/*该位置中填有纪录.并且关键字不相等*/(*c)+;if(*cm)collision(p,*c);/*求得下一探查地址P*/elsebreak;)ifEQ(K,H.elem*p.key)returnSUCCESS;*查找胜利,P返回待查数据元素位置*/elsereturnUNSUCCESS;/*查找不胜利(H.elemp.key=NULLKEY),p返回的是插入位置*/)StatusInsertHash(HashTable*,ElemType);/*对函数的声明*/voidRccreateHashTable(HashTable*H)/*重建哈希表*/*

7、重建哈希表*/inti,count=(*H).count;ElemType*p,*elem=(ElemType*)malloc(count*sizeof(ElcmType);p=elem;Printf(重建哈希表n);for(i=0;ikey!=NULLKEY)/*该单元有数据*/*p+*(*H).elem+i);(*H).count=0;(*H).sizeindex+;/*增大存储容量*/m=hashsize(*H).sizeindex;p=(ElemType*)realloc(*H).elem,m*sizeof(ElemType);if(!p)exit(OVERFLOW);*存储安排失败*

8、/(*H).elcm=p;for(i=0;im;i+)(*H).elemi.key=NULLKEY;*未填纪录的标志(初始化)*/for(p=elem;pelem+count;p+)/*将原有的数据根据新的表长插入到重建的哈希表中*/InsertHash(H,*p);)StatusInsertHash(HashTable*H,ElemTypee)/*查找不胜利时插入数据元素e到开放定址哈希表H中,并返回0K;*/*若冲突次数过大,则重建哈希表。*/intc,p;c=0;if(SearchHash(*H,e.key,&p,&c)*表中已有与C有相同关键字的元素*/returnDUPLICATE;

9、elseif(chashsize(*H).sizeindex/2)*冲突次数C未达到上限,(c的阀值可调)*/(/*插入e*/(*H).elcmp=e;+(*H).count;returnOK;)elseRecreateHashTable(H);*重建哈希表*/returnERROR;)voidTraverseHash(HashTableFI,void(*Vi)(intfElemType)*按哈希地址的挨次遍历哈希表*/inti;Printf(哈希地址0%dn”,m-l);for(i=0;im;i+)if(H.elemi.key!=NULLKEY)/*有数据*/Vi(i,H.elemi);)S

10、tatusFind(HashTableH,KeyTypeK,int*p)*在开放定址哈希表H中查找关键码为K的元素,若查找胜利,以P指示待查数据*/*元素在表中位置,并返回SUCCESS;否则,返回UNSUCCESS*/intc=0;*p=Hash(K);/*求得哈希地址*/whiIe(H.c1em*p.key!=NULLKEYM!EQ(K,H.elem*p.key)/*该位置中填有纪录.并且关键字不相等*/c+;if(cm)collision(p,c);/*求得下一探查地址P*/elsereturnUNSUCCESS;/*查找不胜利(H.elcmp.key=NULLKEY)*/)ifEQ(K

11、,H.elem*p.key)returnSUCCESS;*查找胜利,P返回待查数据元素位置*/elsereturnUNSUCCESS;/*查找不胜利(H.clcmp.key=NULLKEY)*/)voidprint(intp,ElemTyper)(printf(,address=%d(%d,%d八n”,p,r.key,r.ord);)voidmain()(ElemTyperN=17,1,60,2,29,3,(38,4,l,5f2,6,3,7t4,8,60,9,13,10);HashTableh;inti,p;Statusj;KeyTypek;InitHashTablc(&h);for(i=0;

12、iN-l;i+)(*插入前N-I个纪录*/J=InsertHash(&h,ri);if(j=DUPLICATE)printfC表中已有关键字为%d的纪录,无法再插入纪录(%d,%d)n”,ri.key,ri.key,ri.ord);)Printf(按哈希地址的挨次遍历哈希表:n);TraverseHash(h,print);Printf(请输入待查找纪录的关键字:);scanf(%d,&k);j=Find(h,k,&p);if(j=SUCCESS)print(p,h.elemp);elsePrintf(“没找到n);J=InsertHashUh,ri);*插入第N个纪录*/if(j=ERROR)/*重建哈希表*/J=InsertHash(&h,ri);/*重建哈希表后重新插入第N个纪录*/Printf(按哈希地址的挨次遍历重建后的哈希表:n);TraverseHash(h,print);Printf(请输入待查找纪录的关键字:);scanf(%d,&k);j=Find(h,k,&p);if(j=SUCCESS)print(p,h.elemp);elsePrintf(“没找到n);DestroyHashTable(&h);

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!