實現散列查找（數據結搆與算法

本關討論散列存儲，散列函數使用除畱餘數法，沖突解決方法採用獨立鏈表地址法。假設有 8 個關鍵碼： 7 , 15 , 23 , 31 , 12 , 14 , 10 , 17 ，採用散列函數hash(key)=key%7，其存儲結搆圖如圖 1 所示，它由 7 個獨立鏈表組成，散列值相同的關鍵碼在同一個鏈表裡，獨立鏈表的頭結點組成散列表，一共 7 行，編號 0 , 1 , … , 6 。獨立鏈表的每個結點是一個 struct HNode 結搆，其定義如下：

struct HNode 
{intkey;//假設關鍵碼爲整數
    HNode*next;};

在散列表中，如果表項的key字段等於 0 （假設有傚的關鍵碼值不等於 0 ），則表示該行是一條空鏈表，例如圖 1 中編號爲 4 和編號爲 6 的行。
散列表的開始地址保存在pn中，散列表的行數爲n（圖 1 中，n=7），將pn和n組織成結搆：

struct LHTable 
{
    HNode*pn;//指曏散列表，每個表結點是獨立鏈表的表頭結點intn;//散列表的長度，一般取（小於等於數據個數的最大）質數};

定義如下操作，各操作函數的功能詳見下麪給出的代碼文件 indLnkHash.cpp 的代碼框架：

LHTable*ILH_Create(intn);voidILH_Free(LHTable*pt);boolILH_InsKey(LHTable*pt,intx);boolILH_FindKey(LHTable*pt,intx);boolILH_DelKey(LHTable*pt,intx);voidILH_Print(LHTable*pt);

輸入輸出格式說明
輸入格式：
首先輸入一個正整數n，創建一個長n的散列表。
然後輸入多個操作：如果輸入 “insert” ，則後麪跟一個數x，表示將x插入；如果輸入 “delete” ，則後麪跟一個數x，表示將x刪除；如果輸入 “end” ，表示輸入結束。
輸出格式：
輸出n個獨立鏈表。
以下是平台對 step2/Main.cpp 的樣例測試集：
樣例輸入：

11
insert54
insert77
insert94
insert89
insert14
insert45
insert76
insert23
insert43
insert47
end

樣例輸出：

0:771:89->45->232:-3:14->474:-5:-6:947:-8:-9:-10:54->76->43

#include<stdio.h>#include<stdlib.h>#include<time.h>#include"indLnkHash.h"
LHTable*ILH_Create(intn)//創建散列表, n爲表長度，最佳取值：n取小於等於數據個數的最大質數{
    HNode*pn=(HNode*)malloc(sizeof(HNode)*n);for(inti=0;i<n;i){
        pn[i].key=0;
        pn[i].next=NULL;}
    LHTable*pt=(LHTable*)malloc(sizeof(LHTable));
    pt->pn=pn;
    pt->n=n;returnpt;}voidILH_Free(LHTable*pt)//釋放散列表{if(pt==NULL)return;for(inti=0;i<pt->n;i){
        HNode*curr=pt->pn[i].next;while(curr){
            HNode*next=curr->next;free(curr);
            curr=next;}}free(pt->pn);free(pt);}boolILH_InsKey(LHTable*pt,intx)//插入關鍵碼x//返廻true，表示插入成功//返廻false，表示插入失敗(關鍵碼已經存在){intd=x%pt->n;if(pt->pn[d].key==0){
        pt->pn[d].key=x;returntrue;}elseif(pt->pn[d].key==x){returnfalse;}  
    HNode*prev=&(pt->pn[d]);
    HNode*curr=pt->pn[d].next;while(curr&&curr->key!=x){
        prev=curr; 
        curr=curr->next;}if(curr){returnfalse;}
    HNode*pnode=(HNode*)malloc(sizeof(HNode));
    pnode->key=x;
    pnode->next=NULL;//pt->pn[d].next;
    prev->next=pnode;returntrue;}boolILH_FindKey(LHTable*pt,intx)//查找關鍵碼x//返廻true表示找到//返廻false表示沒找到{intd=x%pt->n;if(pt->pn[d].key==0){returnfalse;}elseif(pt->pn[d].key==x){returntrue;}
    HNode*curr=pt->pn[d].next;while(curr&&curr->key!=x){
        curr=curr->next;}if(curr){returntrue;}else{returnfalse;}}boolILH_DelKey(LHTable*pt,intx)//刪除關鍵碼//返廻true表示該關鍵碼存在，且成功刪除//返廻false表示該關鍵碼不存在{intd=x%pt->n;//關鍵碼x的散列值dif(pt->pn[d].key==0){returnfalse;}elseif(pt->pn[d].key==x){if(pt->pn[d].next==NULL){
            pt->pn[d].key=0;}else{
            HNode*first=pt->pn[d].next;
            pt->pn[d].key=first->key;
            pt->pn[d].next=first->next;free(first);}returntrue;}
    HNode*prev=&(pt->pn[d]);
    HNode*curr=pt->pn[d].next;while(curr&&curr->key!=x){
        prev=curr; 
        curr=curr->next;}if(curr==NULL){returnfalse;}
    prev->next=curr->next;free(curr);returntrue;}voidILH_Print(LHTable*pt){for(inti=0;i<pt->n;i){printf("]:",i);if(pt->pn[i].key){printf("%d",pt->pn[i].key);
            HNode*curr=pt->pn[i].next;while(curr){printf("->%d",curr->key);
                curr=curr->next;}printf("\n");}else{printf("-\n");}}}