#include
#include
#include
#include
#include?
#include
#include
#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0
#define?SUCCESS?1
#define?UNSUCCESS?0
#define?DUPLICATE?-1
#define?NULLKEY?0?//?0為無記錄標志
#define?N?10?//?數據元素個數
#define?EQ（ab）?（（a）==（b））
#define?LT（ab）?（（a）<（b））
#define?LQ（ab）?（（a）<=（b））
typedef?int?Status;?//?Status是函數的類型其值是函數結果狀態代碼，如OK等
typedef?int?Boolean;?//?Boolean是布爾類型其值是TRUE或FALSE
typedef?int?KeyType;?//?設關鍵字域為整型

struct?ElemType?//?數據元素類型
{
???KeyType?key;
???int?ord;
};

int?hashsize[]={11192937};?//?哈希表容量遞增表，一個合適的素數序列
int?m=0;?//?哈希表表長，全局變量
struct?HashTable
{
???ElemType?*elem;?//?數據元素存儲基址，動態分配數組
???int?count;?//?當前數據元素個數
???int?sizeindex;?//?hashsize[sizeindex]為當前容量
};

Status?InitHashTable（HashTable?&H）//?操作結果:?構造一個空的哈希表
{?int?i;
???H.count=0;?//?當前元素個數為0
???H.sizeindex=0;?//?初始存儲容量為hashsize[0]
???m=hashsize[0];
???H.elem=（ElemType*）malloc（m*sizeof（ElemType））;
???if（!H.elem）
?????exit（OVERFLOW）;?//?存儲分配失敗
???for（i=0;i?????H.elem[i].key=NULLKEY;?//?未填記錄的標志
???return?OK;
}

void?DestroyHashTable（HashTable?&H）
{?free（H.elem）;
???H.elem=NULL;
???H.count=0;
???H.sizeindex=0;
}

unsigned?Hash（KeyType?K）//?一個簡單的哈希函數（m為表長，全局變量）
{?return?K%m;
}

void?collision（int?&pint?d）?//?線性探測再散列
{?
???p=（p+d）%m;//?開放定址法處理沖突
}

Status?SearchHash（HashTable?HKeyType?Kint?&pint?&c）//?在開放定址哈希表H中查找關鍵碼為K的元素若查找成功以p指示待查數據
{?p=Hash（K）;?//?求得哈希地址
???while（H.elem[p].key!=NULLKEY&&!EQ（KH.elem[p].key））
???{?//?該位置中填有記錄．并且關鍵字不相等
?????c++;
?????if（c???????collision（pc）;?//?求得下一探查地址p
?????else
???????break;
???}
???if?EQ（KH.elem[p].key）
?????return?SUCCESS;?//?查找成功，p返回待查數據元素位置
???else
?????return?UNSUCCESS;?//?查找不成功（H.elem[p].key==NULLKEY），p返回的是插入位置
}

Status?InsertHash（HashTable?&ElemType）;?//?對函數的聲明
void?RecreateHashTable（HashTable?&H）?//?重建哈希表
{?int?icount=H.count;
???ElemType?*p*elem=（ElemType*）malloc（count*sizeof（ElemType））;
???p=elem;
???printf（“重建哈希表\n“）;
???for（i=0;i???if（（H.elem+i）->key!=NULLKEY）?//?該單元有數據
???*p++=*（H.elem+i）;
???H.count=0;
???H.sizeindex++;?//?增大存儲容量
???m=hashsize[H.sizeindex];
???p=（ElemType*）realloc（H.elemm*sizeof（ElemType））;
???if（!p）
?????exit（OVERFLOW）;?//?存儲分配失敗
???H.elem=p;
???for（i=0;i?????H.elem[i].key=NULLKEY;?//?未填記錄的標志（初始化）
???for（p=elem;p?????InsertHash（H*p）;
}

Status?InsertHash（HashTable?&HElemType?e）//?查找不成功時插入數據元素e到開放定址哈希表H中，并返回OK；
{?int?cp;
???c=0;
???if（SearchHash（He.keypc））?//?表中已有與e有相同關鍵字的元素
?????return?DUPLICATE;
???else?if（c???{?//?插入e
?????H.elem[p]=e;
?????++H.count;
?????return?OK;
???}
???else
?????RecreateHashTable（H）;?//?重建哈希表
???return?ERROR;
}

void?TraverseHash（HashTable?Hvoid（*Vi）（intElemType））//?按哈希地址的順序遍歷哈希表
{?
???printf（“哈希地址0～%d\n“m-1）;

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????901??2009-03-04?17:30??哈希表設計.plg

?????文件??????12878??2009-03-04?17:30??Debug\main.obj

?????文件??????41984??2009-03-04?17:30??Debug\vc60.idb

?????文件??????53248??2008-11-20?12:25??Debug\vc60.pdb

?????文件?????184388??2009-03-04?17:30??Debug\哈希表設計.exe

?????文件?????190624??2009-03-04?17:30??Debug\哈希表設計.ilk

?????文件?????248132??2008-11-20?12:25??Debug\哈希表設計.pch

?????文件?????451584??2008-11-20?12:25??Debug\哈希表設計.pdb

?????文件???????5193??2008-11-19?22:06??main.cpp

?????文件???????4326??2008-11-19?12:37??哈希表設計.dsp

?????文件????????528??2008-11-19?12:36??哈希表設計.dsw

?????文件??????41984??2009-03-04?17:30??哈希表設計.ncb

?????文件??????48640??2009-03-04?17:30??哈希表設計.opt

?????目錄??????????0??2008-11-20?12:25??Debug

-----------?---------??----------?-----??----

??????????????1284410????????????????????14