C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)哈希表詳解

第C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)哈希表詳解/*

*程序名：hash.c，此程序演示哈希表的實(shí)現(xiàn)，數(shù)據(jù)元素單鏈表帶頭結(jié)點(diǎn)。

#includestdio.h

#includestdlib.h

#includestring.h

//哈希表中數(shù)據(jù)元素的結(jié)構(gòu)體。

typedefstructElement

unsignedintkey;//關(guān)鍵字。

intvalue;//數(shù)據(jù)元素其它數(shù)據(jù)項(xiàng)，可以是任意數(shù)據(jù)類型。

//charvalue[1001];//數(shù)據(jù)元素其它數(shù)據(jù)項(xiàng)，可以是任意數(shù)據(jù)類型。

}Element;

//數(shù)據(jù)元素單鏈表。

typedefstructNode

Elementelem;//數(shù)據(jù)元素。

structNode*next;//next指針。

}Node;

//哈希表

typedefstructHashTable

structNode*head;//數(shù)據(jù)元素存儲(chǔ)基址，動(dòng)態(tài)分配數(shù)組。

inttablesize;//哈希表當(dāng)前大小，即表長(zhǎng)。

intcount;//哈希表中數(shù)據(jù)元素的個(gè)數(shù)。

}HashTable;

//初始化哈希表，tablesize為哈希表的表長(zhǎng)，返回哈希表的地址。

HashTable*InitHashTable(constunsignedinttablesize)

//分配哈希表。

HashTable*hh=(HashTable*)malloc(sizeof(HashTable));

hh-tablesize=tablesize;//哈希表長(zhǎng)。

//分配和初始化數(shù)據(jù)元素單鏈表的頭結(jié)點(diǎn)。

hh-head=(Node*)malloc((hh-tablesize)*sizeof(Node));

memset(hh-head,0,(hh-tablesize)*sizeof(Node));

hh-count=0;//哈希表中數(shù)據(jù)元素個(gè)數(shù)置為0。

returnhh;

//哈希函數(shù)。

unsignedintHash(HashTable*hh,unsignedintkey)

returnkey%hh-tablesize;//對(duì)表長(zhǎng)取余。

//在哈希表中查找關(guān)鍵字，成功返回單鏈表結(jié)點(diǎn)的地址，失敗返回空。

Node*LookUp(HashTable*hh,unsignedintkey)

intii;

ii=Hash(hh,key);//獲取關(guān)鍵key的哈希地址。

Node*pp=hh-head[ii].next;

//遍歷單鏈表。

while((pp!=NULL)(pp-elem.key!=key))

pp=pp-next;

returnpp;

//從哈希表中刪除關(guān)鍵及其數(shù)據(jù)，成功返回1，如果關(guān)鍵字不存在返回0。

intDelete(HashTable*hh,unsignedintkey)

intii;

ii=Hash(hh,key);//獲取關(guān)鍵key的哈希地址。

Node*pp=hh-head[ii];

//遍歷單鏈表，pp指針停留在待刪除關(guān)鍵key的前一結(jié)點(diǎn)。

while((pp-next!=NULL)(pp-next-elem.key!=key))

pp=pp-next;

if(pp-next==NULL)return0;//查找失敗。

Node*tmp=pp-next;//tmp為將要?jiǎng)h除的結(jié)點(diǎn)。

pp-next=pp-next-next;//寫成p-next=tmp-next更簡(jiǎn)潔。

free(tmp);//釋放結(jié)點(diǎn)。

hh-count--;//表中元素個(gè)數(shù)減1。

return1;

//向哈希表中插入數(shù)據(jù)元素，成功返回1，如果數(shù)據(jù)元素關(guān)鍵字已存在，返回0。

intInsert(HashTable*hh,Element*ee)

//查找關(guān)鍵字是否已存在，如果存在，插入失敗。

Node*pp=LookUp(hh,ee-key);

if(pp!=NULL){printf("關(guān)鍵字%d已存在。\n",ee-key);return0;}

Node*qq=(Node*)malloc(sizeof(Node));

memcpy(qq-elem,ee,sizeof(Element));

//用頭插法插入新數(shù)據(jù)元素。

intii=Hash(hh,ee-key);

qq-next=hh-head[ii].next;

hh-head[ii].next=qq;

hh-count++;//表中元素個(gè)數(shù)加1。

return1;

//銷毀哈希表

voidFreeHashTable(HashTable*hh)

intii;

Node*pp,*qq;

//釋放全部的單鏈表。

for(ii=0;iihh-tablesize;ii++)

pp=hh-head[ii].next;

while(pp)

qq=pp-next;

free(pp);

pp=qq;

//釋放全部單鏈表的頭結(jié)點(diǎn)數(shù)組。

free(hh-head);

free(hh);//釋放哈希表。

//打印哈希表。

voidPrintTable(HashTable*hh)

intii;

for(ii=0;iihh-tablesize;ii++)

Node*pp=hh-head[ii].next;

while(pp)

printf("[%d-%d]",pp-elem.key,pp-elem.value);

//printf("[%d-%s]",pp-elem.key,pp-elem.value);

pp=pp-next;

printf("^\n");

printf("\n");

intmain()

//初始化哈希表。

HashTable*hh=InitHashTable(10);

Elementee;

//插入數(shù)據(jù)元素，關(guān)鍵字從10到20。

ee.key=10;ee.value=110;Insert(hh,ee);

ee.key=11;ee.value=111;Insert(hh,ee);

ee.key=12;ee.value=112;Insert(hh,ee);

ee.key=13;ee.value=113;Insert(hh,ee);

ee.key=14;ee.value=114;Insert(hh,ee);

ee.key=15;ee.value=115;Insert(hh,ee);

ee.key=16;ee.value=116;Insert(hh,ee);

ee.key=17;ee.value=117;Insert(hh,ee);

ee.key=18;ee.value=118;Insert(hh,ee);

ee.key=19;ee.value=119;Insert(hh,ee);

//插入數(shù)據(jù)元素，關(guān)鍵字從20到30。

ee.key=20;ee.value=120;Insert(hh,ee);

ee.key=21;ee.value=121;Insert(hh,ee);

ee.key=22;ee.value=122;Insert(hh,ee);

ee.key=23;ee.value=123;Insert(hh,ee);

ee.key=24;ee.value=124;Insert(hh,ee);

ee.key=25;ee.value=125;Insert(hh,ee);

ee.key=26;ee.value=126;Insert(hh,ee);

ee.key=27;ee.value=127;Insert(hh,ee);

ee.key=28;ee.value=128;Insert(hh,ee);

ee.key=29;ee.value=129;Insert(hh,ee);

//插入數(shù)據(jù)元素，關(guān)鍵字從30到32。

ee.key=30;ee.value=130;Insert(hh,ee);

ee.key=31;ee.value=131;Insert(hh,ee);

ee.key=32;ee.value=132;Insert(hh,ee);

printf("count=%d\n",hh-count);

PrintTable(hh);//打印哈希表

Delete(hh,12);//刪除哈希表中關(guān)鍵字為12的數(shù)據(jù)元素。

printf("count=%d\n",hh-count);

PrintTable(hh);//打印哈希表

//在哈希表中查找關(guān)鍵字18。

Node*pp=LookUp(hh,18);

if(pp==0)printf("LookUp(18)failed.\n");

else