9.45.c

部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)严蔚敏版的课后习题答案.专门提供给在anyview上运行,全部为通告代码

9.45③  假设哈希表长为m，哈希函数为H(x)，用链地址法
处理冲突。试编写输入一组关键字并建造哈希表的算法。

实现下列函数：
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]);
/* 直接调用下列函数                             */
/* 哈希函数：                                   */
/*    int Hash(ChainHashTab H, HKeyType k);     */
/* 冲突处理函数：                               */
/*    int Collision(ChainHashTab H, HLink &p);  */

哈希表的类型ChainHashTab定义如下：
#define NUM         7
#define NULLKEY    -1
#define SUCCESS     1
#define UNSUCCESS   0
#define DUPLICATE  -1

typedef char HKeyType;

typedef struct HNode {
   HKeyType  data;
   struct HNode*  next;
}*HLink;

typedef struct {
   HLink  *elem;  // 指针存储基址，动态分配数组
   int    count;  // 当前表中含有的记录个数
   int  cursize;  // 哈希表的当前容量
}ChainHashTab;    // 链地址哈希表

int Hash(ChainHashTab H, HKeyType k) {
  // 哈希函数
  return k % H.cursize;
}

Status Collision(ChainHashTab H, HLink &p) {
  // 求得下一个探查地址p 
  if (p && p->next) { 
    p = p->next;
    return SUCCESS;
  } else return UNSUCCESS;
}
int BuildHashTab(ChainHashTab &H, int n, HKeyType es[]) 
/* 直接调用下列函数                             */
/* 哈希函数：                                   */
/*    int Hash(ChainHashTab H, HKeyType k);     */
/* 冲突处理函数：                               */
/*    int Collision(ChainHashTab H, HLink &p);  */
{
 HLink p,q;
 int i,pos; 
 for(i=0;i<n;i++) H.elem[i]->next=NULL;
 for(i=0;i<n;i++)
   {
    q=(HNode*)malloc(sizeof(HNode));
    q->data=es[i];q->next=NULL;                         //建立新结点
    pos=Hash(H,es[i]);                                  //查找位置
    p=H.elem[pos];
    while(p->data!=q->data&&p->next) Collision(H,p);    //确定是否出现过
    if(p->data!=q->data)                                //新元素，插在前面
       {q->next=H.elem[pos];
        H.elem[pos]=q;}//if
    }//for         
 return OK ;
}