6-23 分离链接法的删除操作函数 （20 分）
试实现分离链接法的删除操作函数。
函数接口定义：
1
bool Delete( HashTable H, ElementType Key );
其中HashTable是分离链接散列表，定义如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
List Heads; /* 指向链表头结点的数组 */
};
函数Delete应根据裁判定义的散列函数Hash( Key, H->TableSize )从散列表H中查到Key的位置并删除之，然后输出一行文字：Key is deleted from list Heads[i]，其中Key是传入的被删除的关键词，i是Key所在的链表的编号；最后返回true。如果Key不存在，则返回false。
裁判测试程序样例：
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
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <string.h>
#define KEYLENGTH 15 /* 关键词字符串的最大长度 */
typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
typedef int Index; /* 散列地址类型 */
typedef enum {false, true} bool;
typedef struct LNode *PtrToLNode;
struct LNode {
ElementType Data;
PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode { /* 散列表结点定义 */
int TableSize; /* 表的最大长度 */
List Heads; /* 指向链表头结点的数组 */
};
Index Hash( ElementType Key, int TableSize )
{
return (Key[0]-'a')%TableSize;
}
HashTable BuildTable(); /* 裁判实现，细节不表 */
bool Delete( HashTable H, ElementType Key );
int main()
{
HashTable H;
ElementType Key;
H = BuildTable();
scanf("%s", Key);
if (Delete(H, Key) == false)
printf("ERROR: %s is not found\n", Key);
if (Delete(H, Key) == true)
printf("Are you kidding me?\n");
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例1：散列表如下图
able
输出样例1：
able is deleted from list Heads[0]
输入样例2：散列表如样例1图
date
输出样例2：
ERROR: date is not found
注意：如果1次就查到删除的话，要特判
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool Delete( HashTable H, ElementType Key ) {
int p=Hash(Key,H->TableSize);
List L=H->Heads[p].Next;
List LL;
if(L&&strcmp(L->Data,Key)==0) { //第一个就是
H->Heads[p].Next=L->Next;
printf("%s is deleted from list Heads[%d]\n",Key,p);
return true;
} else {
while(L) {
if(strcmp(L->Data,Key)==0) {
LL->Next=L->Next;
printf("%s is deleted from list Heads[%d]\n",Key,p);
return true;
}
LL=L;
L=L->Next;
}
}
return false;
}