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");
}

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