采用链地址法处理冲突实现散列表查找

散列表（hash table）是一种常见的数据结构，它允许根据键（key）快速查找值（value）。散列表的基本思想是将键通过一个哈希函数（hash function）映射到一个数组下标，然后在该位置存储对应的值。

当不同的键被映射到同一个数组下标时，就会发生冲突（collision）。解决冲突的方法有很多种，其中一种常见的方法是链地址法（chaining）。

链地址法的基本思想是，在每个散列表的位置上，维护一个链表。当一个键被映射到该位置时，就将它插入到链表中。这样，当发生冲突时，就可以将不同的键存储在同一个位置上，并通过链表来管理它们。

下面是使用链地址法实现散列表查找的示例代码：

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

#define HASHSIZE 5

typedef struct node {
    int key;
    int value;
    struct node *next;
} Node;

typedef struct hashtable {
    Node *table[HASHSIZE];
} HashTable;

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

Node *search(HashTable *ht, int key) {
    int index = hash(key);
    Node *p = ht->table[index];
    while (p != NULL && p->key != key) {
        p = p->next;
    }
    return p;
}

void insert(HashTable *ht, int key, int value) {
    int index = hash(key);
    Node *p = ht->table[index];
    while (p != NULL && p->key != key) {
        p = p->next;
    }
    if (p == NULL) {
        Node *new_node = (Node *)malloc(sizeof(Node));
        new_node->key = key;
        new_node->value = value;
        new_node->next = ht->table[index];
        ht->table[index] = new_node;
    } else {
        p->value = value;
    }
}

void print_table(HashTable *ht) {
    for (int i = 0; i < HASHSIZE; i++) {
        printf("%d: ", i);
        Node *p = ht->table[i];
        while (p != NULL) {
            printf("(%d, %d) ", p->key, p->value);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    HashTable ht;
    for (int i = 0; i < HASHSIZE; i++) {
        ht.table[i] = NULL;
    }
    insert(&ht, 1, 10);
    insert(&ht, 2, 20);
    insert(&ht, 3, 30);
    insert(&ht, 4, 40);
    insert(&ht, 6, 60);
    insert(&ht, 7, 70);
    printf("table after insert:\n");
    print_table(&ht);
    Node *p = search(&ht, 3);
    if (p != NULL) {
        printf("search result: (%d, %d)\n", p->key, p->value);
    } else {
        printf("not found\n");
    }
    return 0;
}

在这个示例中，我们定义了一个哈希表结构 `HashTable` 和一个节点结构 `Node`。每个节点包含一个键 `key`、一个值 `value`，以及一个指向下一个节点的指针 `next`。哈希表包含一个数组 `table`，其中每个元素都是一个指向节点链表的指针。

我们还定义了三个函数：`hash`、`search` 和 `insert`。`hash` 函数将一个键映射到一个数组下标，`search` 函数在哈希表中查找一个键，并返回对应的节点指针，`insert` 函数向哈希表中插入一个键值对。

在 `insert` 函数中，如果该位置已经有节点，则遍历链表，查找是否已经存在该键，如果存在，则更新对应的值，否则在链表头插入一个新节点。如果该位置没有节点，则直接插入一个新节点。

最后，我们定义了一个 `print_table` 函数，用于打印哈希表的内容。在 `main` 函数中，我们向哈希表中插入了几个键值对，并且通过 `search` 函数查找了一个键。