C++ 自定義HASH表實現[沖突指針鏈表法]

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函數結果狀態代碼 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
typedef int Status; /* Status是函數的類型,其值是函數結果狀態代碼，如OK等 */
typedef int Boolean;

#define NULLKEY 0 /* 0為無記錄標志 */
#define N 10 /* 數據元素個數 */
typedef int KeyType; /* 設關鍵字域為整型 */

class ElemType{
public:
KeyType key;
int ord;
ElemType *next;
ElemType(KeyType key,int ord){
this->key=key;
this->ord=ord;
this->next=NULL;
}
};

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

#define SUCCESS 1
#define UNSUCCESS 0
#define DUPLICATE -1

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<m;i++)
(*H).elem[i].key=NULLKEY; /* 未填記錄的標志 */
return OK;
}

unsigned Hash(KeyType K)
{ /* 一個簡單的哈希函數(m為表長，全局變量) */
return K%m;
}
Status InsertData(HashTable *H,ElemType e)
{
//計算HASH
int p;
ElemType *x;
p=Hash(e.key);
if ((*H).elem[p].key==NULLKEY){//若沒有數據，直接添加
(*H).elem[p]=e;
++(*H).count;
}else{
x=&(*H).elem[p];
while ((*x).next!=NULL){
x=(*x).next;
printf("&x is %d\n",x);
}
(*x).next=&e;
printf("OK in\n");
++(*H).count;
}

}
void DeletData(HashTable *H, ElemType e)
{
//計算HASH
int p;
ElemType *x;
p=Hash(e.key);
if ((*H).elem[p].ord==e.ord){//在頭位置，直接刪除
if ((*H).elem[p].next==NULL){
(*H).elem[p].key=NULLKEY;
}else{
(*H).elem[p]=(*(*H).elem[p].next);
}
--(*H).count;
printf("x is deleted");
}else{
x=&(*H).elem[p];
while ((*((*x).next)).ord!=e.ord){//找到並刪除
x=(*x).next;
if ((*x).next==NULL){
printf("沒有這個");
exit(0);
}
}
//刪除
(*x).next=(*((*x).next)).next;
printf("OK delet\n");
--(*H).count;
}

}

void DestroyHashTable(HashTable *H)
{ /* 初始條件: 哈希表H存在。操作結果: 銷毀哈希表H */
free((*H).elem);
(*H).elem=NULL;
(*H).count=0;
(*H).sizeindex=0;
}


int main(){

ElemType a(12,39);

ElemType b(2,33);

ElemType c(1,23);

HashTable h;
Status j;
KeyType k;
InitHashTable(&h);
InsertData(&h,a);
printf("insert a\n");
InsertData(&h,b);
printf("insert b\n");
InsertData(&h,c);
printf("insert c\n");
}

注：本代碼參考嚴蔚敏老師的《數據結構》