用C语言写一个哈希函数用除留余数法构造，用线性探测再散列处理冲突，并且能够实现显示、插入、查找、删除数据的哈希表程序

Hi，您好！感谢您使用ChitGPT与我进行交流。根据您的需求，我可以提供一个用C语言编写的哈希表程序，该程序采用了除留余数法构造哈希函数，并结合了线性探测再散列处理冲突。该程序可以实现数据的插入、查找、删除和显示等操作，具体代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_KEY_LEN 20     // 关键字最大长度为20
#define MAX_DATA_LEN 40    // 数据最大长度为40
#define MAX_TABLE_SIZE 100 // 哈希表大小为100

typedef struct {
    char key[MAX_KEY_LEN];
    char data[MAX_DATA_LEN];
} Item;

Item NULL_ITEM = {"", ""};

typedef struct {
    Item item;
    int status; // 0: 空元素，1: 有元素，-1: 删除元素
} Slot;

Slot hash_table[MAX_TABLE_SIZE];

// 计算字符串的哈希值，采用除留余数法
unsigned int hash(char *key)
{
    unsigned int hash_value = 0;

    while (*key != '\0') {
        hash_value = (hash_value * 31 + *key) % MAX_TABLE_SIZE;
        key++;
    }

    return hash_value;
}

// 进行线性探测再散列
int rehash(int hash_value)
{
    return (hash_value + 1) % MAX_TABLE_SIZE;
}

// 查找元素
Item *find(char *key)
{
    int hash_value = hash(key);
    int i = hash_value;

    while (hash_table[i].status != 0) {
        if (hash_table[i].status == 1 && strcmp(hash_table[i].item.key, key) == 0) {
            return &hash_table[i].item;
        }

        i = rehash(i);
        if (i == hash_value) {
            break;
        }
    }

    return NULL;
}

// 插入元素
void insert(Item item)
{
    if (find(item.key) != NULL) {
        printf("Error: Key already exists.\n");
        return;
    }

    int hash_value = hash(item.key);
    int i = hash_value;

    while (hash_table[i].status == 1) {
        i = rehash(i);
        if (i == hash_value) {
            printf("Error: Hash table is full.\n");
            return;
        }
    }

    hash_table[i].item = item;
    hash_table[i].status = 1;
}

// 删除元素
void delete(char *key)
{
    Item *item = find(key);
    if (item == NULL) {
        printf("Error: Key does not exist.\n");
        return;
    }

    int i = hash(key);
    while (strcmp(hash_table[i].item.key, key) != 0) {
        i = rehash(i);
    }

    hash_table[i].status = -1;
    printf("Item deleted.\n");
}

// 显示哈希表
void display()
{
    for (int i = 0; i < MAX_TABLE_SIZE; i++) {
        if (hash_table[i].status == 1) {
            printf("Key: %s, Data: %s\n", hash_table[i].item.key, hash_table[i].item.data);
        }
    }
}

int main()
{
    memset(hash_table, 0, sizeof(hash_table));

    // 插入示例数据
    insert((Item){"apple", "red fruit"});
    insert((Item){"banana", "yellow fruit"});
    insert((Item){"cherry", "red fruit"});
    insert((Item){"orange", "orange fruit"});

    // 显示哈希表
    display();

    // 删除元素
    delete("cherry");

    // 显示哈希表
    display();

    return 0;
}

该程序中，哈希表采用数组实现，每个元素为一个`Slot`结构体，其中包含了一个`Item`结构体和一个`status`变量，`Item`结构体中包含了关键字和数据，`status`变量表示该元素的状态，0表示空元素，1表示有元素，-1表示删除元素。该程序中实现的哈希函数采用了除留余数法，探测方法采用了线性探测再散列。该程序中实现了插入、查找、删除和显示等操作。在删除元素时，将该元素的状态标记为-1，而不是直接将该元素从哈希表中删除，这是因为在线性探测再散列的过程中，如果当前元素被删除了，后续元素的探测路径将不够连续，导致查找失败。因此，将元素的状态标记为-1可以在探测过程中跳过已删除的元素，而不会影响后续元素的探测路径。