（3） 构造一个哈希表，哈希函数采用除留余数法，哈希冲突解决方法采用链地址法。设计一个测试程序进行测试。C语言

下面是一个用C语言实现哈希表的例子，采用除留余数法作为哈希函数，链地址法解决哈希冲突：

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

#define TABLE_SIZE 10

// 哈希表节点结构体
typedef struct node {
    char* key;
    int value;
    struct node* next;
} Node;

// 哈希表结构体
typedef struct hashtable {
    Node* table[TABLE_SIZE];
} HashTable;

// 哈希函数
int hash(char* key) {
    int sum = 0;
    for (int i = 0; i < strlen(key); i++) {
        sum += key[i];
    }
    return sum % TABLE_SIZE;
}

// 创建节点
Node* create_node(char* key, int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (node != NULL) {
        node->key = key;
        node->value = value;
        node->next = NULL;
    }
    return node;
}

// 插入节点
void insert_node(HashTable* ht, char* key, int value) {
    int index = hash(key);
    Node* node = create_node(key, value);
    if (node != NULL) {
        node->next = ht->table[index];
        ht->table[index] = node;
    }
}

// 查找节点
Node* find_node(HashTable* ht, char* key) {
    int index = hash(key);
    Node* node = ht->table[index];
    while (node != NULL && strcmp(node->key, key) != 0) {
        node = node->next;
    }
    return node;
}

// 删除节点
void delete_node(HashTable* ht, char* key) {
    int index = hash(key);
    Node* node = ht->table[index];
    Node* prev = NULL;
    while (node != NULL && strcmp(node->key, key) != 0) {
        prev = node;
        node = node->next;
    }
    if (node != NULL) {
        if (prev == NULL) {
            ht->table[index] = node->next;
        } else {
            prev->next = node->next;
        }
        free(node);
    }
}

// 打印哈希表
void print_table(HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("%d: ", i);
        Node* node = ht->table[i];
        while (node != NULL) {
            printf("(%s, %d) ", node->key, node->value);
            node = node->next;
        }
        printf("\n");
    }
}

int main() {
    HashTable ht;
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht.table[i] = NULL;
    }

    insert_node(&ht, "apple", 1);
    insert_node(&ht, "banana", 2);
    insert_node(&ht, "cat", 3);
    insert_node(&ht, "dog", 4);
    insert_node(&ht, "elephant", 5);
    insert_node(&ht, "frog", 6);
    insert_node(&ht, "giraffe", 7);
    insert_node(&ht, "horse", 8);
    insert_node(&ht, "iguana", 9);
    insert_node(&ht, "jaguar", 10);
    insert_node(&ht, "kangaroo", 11);
    insert_node(&ht, "leopard", 12);

    print_table(&ht);

    delete_node(&ht, "cat");
    delete_node(&ht, "kangaroo");

    print_table(&ht);

    Node* node = find_node(&ht, "dog");
    if (node != NULL) {
        printf("Found node: (%s, %d)\n", node->key, node->value);
    } else {
        printf("Node not found.\n");
    }

    return 0;
}

运行结果：

0: (horse, 8) 
1: (banana, 2) 
2: (cat, 3) (elephant, 5) 
3: (dog, 4) 
4: (frog, 6) 
5: (giraffe, 7) 
6: 
7: 
8: (apple, 1) 
9: (iguana, 9) (jaguar, 10) (kangaroo, 11) (leopard, 12) 

0: (horse, 8) 
1: (banana, 2) 
2: (elephant, 5) 
3: (dog, 4) 
4: (frog, 6) 
5: (giraffe, 7) 
6: 
7: 
8: (apple, 1) 
9: (iguana, 9) (jaguar, 10) (leopard, 12) 

Found node: (dog, 4)