试实现分离链接法的删除操作函数。
函数接口定义:
bool Delete( HashTable H, ElementType Key );
其中HashTable
是分离链接散列表,定义如下:
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。
裁判测试程序样例:
#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
测试输入样本(不包括要删除的结点)
key
able
zero
bye
very
day
如果要删除某条信息请按Ctrl+Z后下一行输入待删除信息
#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() { HashTable T = (HashTable)malloc(sizeof(struct TblNode)); T->Heads = (PtrToLNode)malloc(sizeof(struct LNode) * 5); T->TableSize = 5; //根据题干所给图可知 char key[16]; int i; for(i = 0; i < T->TableSize; ++i) { T->Heads[i].Next = NULL; } while(~scanf("%s", key)) { int pos = Hash(key, T->TableSize); PtrToLNode ins = (PtrToLNode)malloc(sizeof(struct LNode)); strcpy(ins->Data, key); ins->Next = T->Heads[pos].Next; T->Heads[pos].Next = ins; } return T; } bool Delete( HashTable H, ElementType Key ) { int hvalue = Hash(Key, H->TableSize); PtrToLNode del, pre; pre = H->Heads + hvalue; del = H->Heads[hvalue].Next; while(del != NULL) { if(strcmp(del->Data, Key) == 0) { pre->Next = del->Next; free(del); del = NULL; printf("%s is deleted from list Heads[%d]\n", Key, hvalue); return true; } else { pre = del; del = del->Next; } } return false; } int main() { HashTable H; ElementType Key; H = BuildTable(); //略作修改, 用于测试 while(~scanf("%s", Key)){ if (Delete(H, Key) == 0) printf("ERROR: %s is not found\n", Key); if (Delete(H, Key) == 1) printf("Are you kidding me?\n"); } return 0; }