为班级30个人的姓名设计一个哈希表，平均查找长度的上限为2，完成相应的建表和查表。用除留余数法和线性探测再散列法C语言

好的，这里是使用除留余数法和线性探测再散列法建立哈希表的C语言代码：

1. 除留余数法

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

#define MAX_SIZE 15

typedef struct {
    int key;
    char name[20];
} Item;

typedef struct {
    Item items[MAX_SIZE];
} HashTable;

int hash(int key)
{
    return key % MAX_SIZE;
}

void insert(HashTable *table, int key, char *name)
{
    int index = hash(key);
    if (table->items[index].key == -1) {
        table->items[index].key = key;
        strcpy(table->items[index].name, name);
    } else {
        int i = (index + 1) % MAX_SIZE;
        while (i != index) {
            if (table->items[i].key == -1) {
                table->items[i].key = key;
                strcpy(table->items[i].name, name);
                break;
            }
            i = (i + 1) % MAX_SIZE;
        }
    }
}

char *search(HashTable *table, int key)
{
    int index = hash(key);
    if (table->items[index].key == -1) {
        return NULL;
    } else if (table->items[index].key == key) {
        return table->items[index].name;
    } else {
        int i = (index + 1) % MAX_SIZE;
        while (i != index) {
            if (table->items[i].key == -1) {
                return NULL;
            } else if (table->items[i].key == key) {
                return table->items[i].name;
            }
            i = (i + 1) % MAX_SIZE;
        }
        return NULL;
    }
}

int main()
{
    HashTable table = {0};
    for (int i = 0; i < MAX_SIZE; i++) {
        table.items[i].key = -1;
    }

    char *names[] = {"Alice", "Bob", "Charlie", "David", "Emily", "Frank", "Grace", "Henry", "Isaac", "Jack", "Kate", "Lily", "Megan", "Nancy", "Oliver", "Peter", "Queen", "Rose", "Sam", "Tom", "Ursula", "Victor", "Wendy", "Xavier", "Yvonne", "Zoe", "Adam", "Ben", "Cathy"};

    for (int i = 0; i < 30; i++) {
        insert(&table, i, names[i]);
    }

    char *name = search(&table, 3);
    printf("%s\n", name);

    return 0;
}

在上面的代码中，我们定义了一个哈希表结构体，其中包含了一个Item结构体数组。在insert和search函数中，我们使用了除留余数法来计算关键字在哈希表中的位置，并使用线性探测法来解决哈希冲突。在main函数中，我们先将哈希表中所有的key初始化为-1，然后依次将30个人的姓名插入到哈希表中，并查找了关键字为3的元素。

2. 线性探测再散列法

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

#define MAX_SIZE 15

typedef struct {
    int key;
    char name[20];
} Item;

typedef struct {
    Item items[MAX_SIZE];
} HashTable;

int hash(int key)
{
    return key % MAX_SIZE;
}

int rehash(int key, int i)
{
    return (hash(key) + i) % MAX_SIZE;
}

void insert(HashTable *table, int key, char *name)
{
    int i = 0;
    while (i < MAX_SIZE) {
        int index = rehash(key, i);
        if (table->items[index].key == -1) {
            table->items[index].key = key;
            strcpy(table->items[index].name, name);
            break;
        }
        i++;
    }
}

char *search(HashTable *table, int key)
{
    int i = 0;
    while (i < MAX_SIZE) {
        int index = rehash(key, i);
        if (table->items[index].key == -1) {
            return NULL;
        } else if (table->items[index].key == key) {
            return table->items[index].name;
        }
        i++;
    }
    return NULL;
}

int main()
{
    HashTable table = {0};
    for (int i = 0; i < MAX_SIZE; i++) {
        table.items[i].key = -1;
    }

    char *names[] = {"Alice", "Bob", "Charlie", "David", "Emily", "Frank", "Grace", "Henry", "Isaac", "Jack", "Kate", "Lily", "Megan", "Nancy", "Oliver", "Peter", "Queen", "Rose", "Sam", "Tom", "Ursula", "Victor", "Wendy", "Xavier", "Yvonne", "Zoe", "Adam", "Ben", "Cathy"};

    for (int i = 0; i < 30; i++) {
        insert(&table, i, names[i]);
    }

    char *name = search(&table, 3);
    printf("%s\n", name);

    return 0;
}

在上面的代码中，我们同样定义了一个哈希表结构体和一个Item结构体，但是在insert和search函数中，我们使用了线性探测再散列法来解决哈希冲突。在main函数中，我们同样先将哈希表中所有的key初始化为-1，然后依次将30个人的姓名插入到哈希表中，并查找了关键字为3的元素。