哈希表的设计与实现——线性探测再散列 问题描述 设计哈希表实现电话号码查找系统。 基本要求： （1）设每个记录有下列数据项：电话号码、用户名、地址 (2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表; (3）采用线性探测再散列的方法解决冲突; (4)查找并显示给定电话号码的记录 （5）查找并显示给定用户名的记录。用大一能理解的简单C语言数据结构写

以下是一个简单的C语言实现哈希表的例子，其中包括了电话号码和用户名两个关键字的哈希表，并采用了线性探测再散列的方法解决冲突。

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

#define MAX_SIZE 100 // 哈希表的最大大小
#define EMPTY -1     // 哈希表空位标志

typedef struct {
    char phone[12]; // 电话号码
    char name[20];  // 用户名
    char address[30]; // 地址
} Record;

typedef struct {
    Record data;    // 数据项
    int key;        // 哈希表关键字
} HashNode;

void init(HashNode hash_table[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        hash_table[i].key = EMPTY;
    }
}

int hash(char* key, int size) {
    int hash_val = 0;
    while (*key) {
        hash_val = (hash_val << 5) + *key++;
    }
    return hash_val % size;
}

int find(char* key, HashNode hash_table[], int size) {
    int hash_val = hash(key, size);
    while (hash_table[hash_val].key != EMPTY && strcmp(hash_table[hash_val].data.phone, key) != 0) {
        hash_val = (hash_val + 1) % size;
    }
    return hash_val;
}

void insert(Record data, HashNode hash_table[], int size) {
    int hash_val = find(data.phone, hash_table, size);
    hash_table[hash_val].data = data;
    hash_table[hash_val].key = hash(data.phone, size);
}

Record* search_by_phone(char* phone, HashNode hash_table[], int size) {
    int hash_val = find(phone, hash_table, size);
    if (hash_table[hash_val].key != EMPTY) {
        return &(hash_table[hash_val].data);
    }
    return NULL;
}

Record* search_by_name(char* name, HashNode hash_table[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        if (hash_table[i].key != EMPTY && strcmp(hash_table[i].data.name, name) == 0) {
            return &(hash_table[i].data);
        }
    }
    return NULL;
}

int main() {
    HashNode phone_table[MAX_SIZE], name_table[MAX_SIZE];
    Record record;
    int i, size;
    char phone[12], name[20];

    printf("Enter the size of hash table: ");
    scanf("%d", &size);

    init(phone_table, size);
    init(name_table, size);

    printf("\nEnter the phone number, name and address of the person:\n");
    for (i = 0; i < size; i++) {
        printf("Record %d:\n", i + 1);
        scanf("%s %s %s", record.phone, record.name, record.address);
        insert(record, phone_table, size);
        insert(record, name_table, size);
    }

    printf("\nEnter the phone number to search: ");
    scanf("%s", phone);
    Record* r = search_by_phone(phone, phone_table, size);
    if (r != NULL) {
        printf("Phone: %s\nName: %s\nAddress: %s\n", r->phone, r->name, r->address);
    } else {
        printf("Record not found.\n");
    }

    printf("\nEnter the name to search: ");
    scanf("%s", name);
    r = search_by_name(name, name_table, size);
    if (r != NULL) {
        printf("Phone: %s\nName: %s\nAddress: %s\n", r->phone, r->name, r->address);
    } else {
        printf("Record not found.\n");
    }

    return 0;
}

在这个例子中，我们首先定义了一个 `Record` 结构体来表示每个记录，其中包括了电话号码、用户名和地址三个数据项。然后我们定义了一个 `HashNode` 结构体来表示哈希表中的节点，其中包括了一个 `data` 成员来存储记录数据，以及一个 `key` 成员来存储哈希表关键字。

在 `init` 函数中，我们将哈希表中的每个节点的 `key` 成员初始化为 `EMPTY`，表示该节点为空。

在 `hash` 函数中，我们使用了一种简单的哈希函数，将字符串转换为整数并取模得到哈希值。

在 `find` 函数中，我们使用线性探测的方法解决哈希冲突，如果当前节点的 `key` 成员不为 `EMPTY` 且节点中的电话号码与要查找的电话号码不同，则继续搜索下一个节点，直到找到一个空节点或者关键字与要查找的电话号码相同的节点为止。

在 `insert` 函数中，我们通过调用 `find` 函数找到一个空节点或者与要插入的记录关键字相同的节点，并将该节点的 `data` 和 `key` 成员更新为要插入的记录数据和关键字。

在 `search_by_phone` 函数中，我们通过调用 `find` 函数找到与给定电话号码相同的节点，并返回该节点中的记录数据。

在 `search_by_name` 函数中，我们遍历哈希表中的所有节点，找到用户名与给定名字相同的节点，并返回该节点中的记录数据。

最后，在 `main` 函数中，我们首先从键盘输入每个记录的电话号码、用户名和地址，并将其插入到电话号码和用户名两个哈希表中。然后，我们分别通过调用 `search_by_phone` 和 `search_by_name` 函数来查找给定电话号码和用户名对应的记录，并输出该记录的电话号码、用户名和地址。