Anyview数据结构-4

-广工Anyview题解
-数据结构部分-4

/**
【题目】已知某哈希表的装载因子小于1，哈希函数H(key)
为关键字(标识符)的第一个字母在字母表中的序号，处理
冲突的方法为线性探测开放定址法。试编写一个按第一个
字母的顺序输出哈希表中所有关键字的算法。
哈希表的类型HashTable定义如下：

#define SUCCESS 1

#define UNSUCCESS 0

#define DUPLICATE -1
typedef char StrKeyType[4];
typedef struct {
StrKeyType key; // 关键字项
int tag; // 标记 0:空；1:有效; -1:已删除
void any; // 其他信息
} RcdType;
typedef struct {
RcdType rcd; // 存储空间基址
int size; // 哈希表容量
int count; // 表中当前记录个数
} HashTable;
**/

void PrintKeys(HashTable ht, void(*print)(StrKeyType))
/* 依题意用print输出关键字 */
{
    int n,i,size;
    char c;
    for(c='A';c<='Z';c++){
        for(i=0;i<ht.size;i++){
            if(ht.rcd[i].tag==-1) 
                continue;
            if(ht.rcd[i].key[0]==c)
                print(ht.rcd[i].key);
            }
      }
}

---

/**
【题目】假设哈希表长为m，哈希函数为H(x)，用链地址法
处理冲突。试编写输入一组关键字并建造哈希表的算法。
哈希表的类型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 rcd; // 指针存储基址，动态分配数组
int count; // 当前表中含有的记录个数
int size; // 哈希表的当前容量
}ChainHashTab; // 链地址哈希表
int Hash(ChainHashTab H, HKeyType k) { // 哈希函数
return k % H.size;
}
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);  */
{
    int i,k,j;
    HLink p,q,p1;
    H.rcd = (HLink*)malloc(7*sizeof(HLink));
    H.size = 7;
    H.count = 0;
    for(i = 0;es[i] >= 'A';i++){
        p = (HNode*)malloc(sizeof(HNode));
        p->next = NULL;
        p->data = es[i];
        k = Hash( H, p->data) ;
        if(NULL !=H.rcd[k]){  // 判断其中是否有相同的HKeyType
            p1 =  H.rcd[k];
            while(NULL != p1){  //用j作为标记，如果j = 0表示没有相同的，插入p
                if(p1->data == p->data)
                    j = 1;
                p1 = p1->next;
            }
            if(j == 0){
                q =  H.rcd[k];
                p->next = q;
                H.rcd[k] = p;
            }
           j = 0;
        }         
        else   
            H.rcd[k] = p; //为什么H.rcd[k]->next = p;不会报错
    H.count++;
    }
}