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;
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}
*
/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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++;
}
}
Thanks for your reward!