用c语言探究冲突处理方法对散列函数平均查找长度的影响规律，给出相应代码及测试数据用例和预期实验结果

散列表是一种用于快速访问数据的数据结构，它通过将数据映射到一个固定范围的索引位置来实现快速访问。散列函数是将数据映射到索引位置的算法，但是当多个数据映射到同一个索引位置时，就会产生冲突。因此，散列函数的冲突处理方法对散列表的性能有很大影响。

常见的冲突处理方法有开放定址法、链地址法和再散列法。开放定址法是在冲突发生时，以一定的步长在散列表中寻找下一个空闲位置。链地址法是将散列到同一位置的数据存储在同一个链表中。再散列法是在冲突发生时，使用另一个散列函数重新计算索引位置。

下面是一份用C语言实现散列表并比较不同冲突处理方法对平均查找长度的影响的代码：

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

#define TABLE_SIZE 100
#define MAX_LENGTH 20

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

typedef struct hash_table {
    Node **table;
    int size;
} HashTable;

unsigned int hash(char *str) {
    unsigned int hash = 5381;
    int c;

    while ((c = *str++))
        hash = ((hash << 5) + hash) + c;

    return hash;
}

Node *create_node(char *key, int value) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

HashTable *create_table(int size) {
    HashTable *table = (HashTable *) malloc(sizeof(HashTable));
    table->table = (Node **) malloc(sizeof(Node *) * size);
    table->size = size;

    for (int i = 0; i < size; i++)
        table->table[i] = NULL;

    return table;
}

void set(HashTable *table, char *key, int value, int method) {
    unsigned int index = hash(key) % table->size;
    Node *node = table->table[index];

    if (node == NULL) {
        table->table[index] = create_node(key, value);
        return;
    }

    while (node->next != NULL && strcmp(node->key, key) != 0)
        node = node->next;

    if (strcmp(node->key, key) == 0) {
        node->value = value;
        return;
    }

    Node *new_node = create_node(key, value);

    if (method == 1) { // 开放定址法
        int i = 1;

        while (node->next != NULL) {
            index = (hash(key) + i) % table->size;
            node = table->table[index];
            i++;
        }

        table->table[index] = new_node;
    } else if (method == 2) { // 链地址法
        node->next = new_node;
    } else { // 再散列法
        unsigned int new_index = (hash(key) * 2 + 1) % table->size;
        table->table[new_index] = new_node;
    }
}

int get(HashTable *table, char *key) {
    unsigned int index = hash(key) % table->size;
    Node *node = table->table[index];

    while (node != NULL) {
        if (strcmp(node->key, key) == 0)
            return node->value;

        node = node->next;
    }

    return -1;
}

int main() {
    HashTable *table;
    char keys[10][MAX_LENGTH] = {"hello", "world", "apple", "banana", "orange", "pear", "watermelon", "grape", "lemon", "peach"};

    // 开放定址法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 1);

    int sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("开放定址法平均查找长度：%f\n", (double) sum / 10);

    // 链地址法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 2);

    sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("链地址法平均查找长度：%f\n", (double) sum / 10);

    // 再散列法
    table = create_table(TABLE_SIZE);
    for (int i = 0; i < 10; i++)
        set(table, keys[i], i, 3);

    sum = 0;
    for (int i = 0; i < 10; i++)
        sum += get(table, keys[i]);

    printf("再散列法平均查找长度：%f\n", (double) sum / 10);

    return 0;
}

其中，`set`函数用于插入数据，`get`函数用于查找数据。`method`参数指定了冲突处理方法，1表示开放定址法，2表示链地址法，3表示再散列法。`main`函数测试了三种不同的冲突处理方法，并输出了平均查找长度。

这里给出一个测试数据例子：

hello 0
world 1
apple 2
banana 3
orange 4
pear 5
watermelon 6
grape 7
lemon 8
peach 9

预期实验结果是，开放定址法的平均查找长度应该最小，再散列法的平均查找长度应该略小于链地址法的平均查找长度。但是，这个结果可能会因为数据分布的不同而有所不同。