数据结构C语言实现散列：创建、解决冲突、查找元素

1、实验课题：做这个实验时采用OpenAddressing框架，也可加做SeparateChaining以形成比较。1构造散列表，把字符串数组中的各项加入到散列表中stringMyBirds13=robin,sparrow,hawk,eagle,seagull,bluejay,owl,cardinal,Jakana,Moa,Egret,Penguin,hawk;用C表示，可以是char*MyBirds13=robin,sparrow,hawk,eagle,seagull,bluejay,owl,cardinal,Jakana,Moa,Egret,Penguin,hawk;为便于观察冲突现象，初始构

2、造散列表时，表的容量不要过大，对OpenAddressing，装载因子为0.5左右，对于SeparateChaining，装载因子为1左右即可。也不要做rehash（应该改源代码的哪里，如何改）。建议对源代码做些改动、增加一些输出（建议用条件编译控制这些输出），以便于观察冲突的发生和解决；对于OpenAddressing，参考代码的冲突解决方案是用的平方探测（quadraticprobing）,如果用线性探测（linearprobing）的策略，应该对函数findPos做什么修改（冲突解决的策略都集中在那里,？2观察不同的散列函数产生冲突散列地址的情况教科书上给了3个以字符串作输入的散列函数（

3、两教科书第3个不一样,，观察记录它们产生冲突散列地址的情况，写入你的实验报告。还可对下列散列函数（所谓ELFhash，UnixSystemV用的,作观察 inthash(conststring&key)inthash(char*key)/C+version/Cversionunsignedlongh=0;unsignedlongh=0;for(inti=0;ikey.length();i+)h=(h24;h&=g;while(*key)h=(h24;h&=g；returnh;/%Mreturnh;/%M3对散列表做查找。程序代码：#include#include#includehashquad

4、.h#include#defineMinTableSize26typedefunsignedintIndex;typedefIndexPosition;structHashTbl;typedefstructHashTbl*HashTable;enumKindOfEntryLegitimate,Empty,Deleted;structHashEntrychar*Element;enumKindOfEntryInfo;typedefstructHashEntryCell;structHashTblintTableSize;Cell*TheCells;staticintNextPrime(intN)

5、inti;if(N%2=0)N+;for(;N+=2)for(i=3;i*i=N;i+=2)if(N%i=0)gotoContOuter;returnN;ContOuter:;IndexHash(constchar*Key,intTableSize)return*Key%TableSize;HashTableInitializeTable(intTableSize)HashTableH;inti;/*1*/if(TableSizeTableSize=NextPrime(TableSize);/*AllocatearrayofCells*/*8*/H-TheCells=(structHashEn

6、try*)malloc(sizeof(Cell)*H-TableSize);/*9*/if(H-TheCells=NULL)/*10*/printf(Outofspace!);/*11*/for(i=0;iTableSize;i+)H-TheCellsi.Element=(char*)malloc(10*sizeof(char);H-TheCellsi.Info=Empty;/*12*/*13*/returnH;PositionFind(char*Key,HashTableH)PositionCurrentPos;intCollisionNum;/*1*/CollisionNum=0;/*2*

7、/CurrentPos=Hash(Key,H-TableSize);/printf(%dn,CurrentPos);/*3*/while(H-TheCellsCurrentPos.Info!=Empty&strcmp(H-TheCellsCurrentPos.Element,Key)!=0)/*Probablyneedstrcmp!*/%sn,if(H-TheCellsCurrentPos.Element!=NULL)printf(冲突:%sandH-TheCellsCurrentPos.Element,Key);/*4*/CurrentPos+=2*+CollisionNum-1;/*5*/

8、if(CurrentPos=H-TableSize)/*6*/CurrentPos-=H-TableSize;/*7*/returnCurrentPos;voidInsert(char*Key,HashTableH)PositionPos;Pos=Find(Key,H);if(H-TheCellsPos.Info!=Legitimate)/*OKtoinserthere*/H-TheCellsPos.Info=Legitimate;strcpy(H-TheCellsPos.Element,Key);/*Probablyneedstrcpy!*/*char*Retrieve(PositionP,

9、HashTableH) returnH-TheCellsP.Element;*/voidDestroyTable(HashTableH)free(H-TheCells);free(H);voidmain()inti,x,n;chars10;HashTableH; char*MyBirds13=robin,sparrow,hawk,eagle,seagull,owl,cardinal,Jakana,Moa,printf(printf(”原来的MyBirds：nn);printf(”字符串位置n);for(i=0;iTableSize);for(i=0;i13;i+)printf(%8s:%2dn,MyBirdsi,i+1);*/H=InitializeTable(29);printf(printf(”生成散列表：nn);printf(”字符串散列值位置n);for(i=0;i13;i+)Insert(MyBirdsi,H);Egret,Penguin,hawkn);n);n);bluejay,; # #for(i=0;iTheCellsi.Info!=Empty)printf(%8s:%2d%dn,H-TheCellsi.Element,x=Hash(H-TheCellsi.Element,29),n=Find(H-TheCe