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 ",x）;
         }
         （*x）.next=&e;
          printf（"OK in "）;
         ++（*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 "）;
         --（*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 "）;
   InsertData（&h,b）;
   printf（"insert b "）;
   InsertData（&h,c）;
   printf（"insert c "）;
}注：本代码参考严蔚敏老师的《数据结构》