分离链接法的删除操作函数

时间:2022-02-28 20:38:10

试实现分离链接法的删除操作函数。

函数接口定义:

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是传入的被删除的关键词,iKey所在的链表的编

号;最后返回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;
}