/* bo9-7.c 哈希函數的基本操作 */
 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;
 }

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

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

 void collision(int *p,int d) /* 線性探測再散列 */
 { /* 開放定址法處理沖突 */
   *p=(*p+d)%m;
 }

 Status SearchHash(HashTable H,KeyType K,int *p,int *c)
 { /* 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據 */
   /* 元素在表中位置,并返回SUCCESS;否則,以p指示插入位置,并返回UNSUCCESS */
   /* c用以計沖突次數，其初值置零，供建表插入時參考。算法9.17 */
   *p=Hash(K); /* 求得哈希地址 */
   while(H.elem[*p].key!=NULLKEY&&!EQ(K,H.elem[*p].key))
   { /* 該位置中填有記錄．并且關鍵字不相等 */
     (*c)++;
     if(*c<m)
       collision(p,*c); /* 求得下一探查地址p */
     else
       break;
   }
   if EQ(K,H.elem[*p].key)
     return SUCCESS; /* 查找成功，p返回待查數據元素位置 */
   else
     return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY)，p返回的是插入位置 */
 }

 Status InsertHash(HashTable *,ElemType); /* 對函數的聲明 */
 void RecreateHashTable(HashTable *H) /* 重建哈希表 */
 { /* 重建哈希表 */
   int i,count=(*H).count;
   ElemType *p,*elem=(ElemType*)malloc(count*sizeof(ElemType));
   p=elem;
   printf("重建哈希表\n");
   for(i=0;i<m;i++) /* 保存原有的數據到elem中 */
     if(((*H).elem+i)->key!=NULLKEY) /* 該單元有數據 */
       *p++=*((*H).elem+i);
   (*H).count=0;
   (*H).sizeindex++; /* 增大存儲容量 */
   m=hashsize[(*H).sizeindex];
   p=(ElemType*)realloc((*H).elem,m*sizeof(ElemType));
   if(!p)
     exit(OVERFLOW); /* 存儲分配失敗 */
   (*H).elem=p;
   for(i=0;i<m;i++)
     (*H).elem[i].key=NULLKEY; /* 未填記錄的標志(初始化) */
   for(p=elem;p<elem+count;p++) /* 將原有的數據按照新的表長插入到重建的哈希表中 */
     InsertHash(H,*p);
 }

 Status InsertHash(HashTable *H,ElemType e)
 { /* 查找不成功時插入數據元素e到開放定址哈希表H中，并返回OK； */
   /* 若沖突次數過大，則重建哈希表。算法9.18 */
   int c,p;
   c=0;
   if(SearchHash(*H,e.key,&p,&c)) /* 表中已有與e有相同關鍵字的元素 */
     return DUPLICATE;
   else if(c<hashsize[(*H).sizeindex]/2) /* 沖突次數c未達到上限,(c的閥值可調) */
   { /* 插入e */
     (*H).elem[p]=e;
     ++(*H).count;
     return OK;
   }
   else
     RecreateHashTable(H); /* 重建哈希表 */
   return ERROR;
 }

 void TraverseHash(HashTable H,void(*Vi)(int,ElemType))
 { /* 按哈希地址的順序遍歷哈希表 */
   int i;
   printf("哈希地址0～%d\n",m-1);
   for(i=0;i<m;i++)
     if(H.elem[i].key!=NULLKEY) /* 有數據 */
       Vi(i,H.elem[i]);
 }

 Status Find(HashTable H,KeyType K,int *p)
 { /* 在開放定址哈希表H中查找關鍵碼為K的元素,若查找成功,以p指示待查數據 */
   /* 元素在表中位置,并返回SUCCESS;否則,返回UNSUCCESS */
   int c=0;
   *p=Hash(K); /* 求得哈希地址 */
   while(H.elem[*p].key!=NULLKEY&&!EQ(K,H.elem[*p].key))
   { /* 該位置中填有記錄．并且關鍵字不相等 */
     c++;
     if(c<m)
       collision(p,c); /* 求得下一探查地址p */
     else
       return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY) */
   }
   if EQ(K,H.elem[*p].key)
     return SUCCESS; /* 查找成功，p返回待查數據元素位置 */
   else
     return UNSUCCESS; /* 查找不成功(H.elem[p].key==NULLKEY) */
 }