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

 

注：本代码参考严蔚敏老师的《数据结构》

评论

1 楼 deepfuture 2010-11-28  

  unsigned Hash(KeyType K)
{ /* 一个简单的哈希函数(m为表长，全局变量) */
   return K%m;
}
有没有更复杂的