分离链接法删除操作如何实现长尾词的疑问？

本文共计4601个文字，预计阅读时间需要19分钟。

实现分离链接法删除操作，并测试实现。函数接口定义：bool Delete(HashTable H, ElementType Key); 其中HashTable是分离链接法散列表，定义如下：1 2 3 4 5

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 KEYLENGTH15 /* 关键词字符串的最大长度 */

typedefchar ElementType[KEYLENGTH+1];/* 关键词类型用字符串 */

typedefint Index;/* 散列地址类型 */

typedefenum {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;

}