用c写一个用线性构造散列表，测量不同规模散列表的平均查找长度的代码

下面是用C语言编写的使用线性构造散列表测量不同规模散列表平均查找长度的代码：

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

#define MAX_SIZE 10000 // 散列表的最大容量

// 散列表节点
typedef struct {
    int key;
    int value;
} HashNode;

// 散列表
typedef struct {
    HashNode *nodes; // 散列表节点数组
    int capacity; // 散列表的容量
    int size; // 散列表中已有节点的个数
} HashTable;

// 创建散列表
HashTable *createHashTable(int capacity) {
    HashTable *hashTable = (HashTable *) malloc(sizeof(HashTable));
    hashTable->nodes = (HashNode *) malloc(sizeof(HashNode) * capacity);
    hashTable->capacity = capacity;
    hashTable->size = 0;
    for (int i = 0; i < capacity; i++) {
        hashTable->nodes[i].key = -1; // 将散列表节点的键初始化为-1（表示空节点）
    }
    return hashTable;
}

// 计算散列值
int hash(int key, int capacity) {
    return key % capacity;
}

// 向散列表中插入节点
void insert(HashTable *hashTable, int key, int value) {
    int index = hash(key, hashTable->capacity);
    while (hashTable->nodes[index].key != -1) { // 线性探测法解决冲突
        index = (index + 1) % hashTable->capacity;
    }
    hashTable->nodes[index].key = key;
    hashTable->nodes[index].value = value;
    hashTable->size++;
}

// 从散列表中查找节点
int find(HashTable *hashTable, int key) {
    int index = hash(key, hashTable->capacity);
    int count = 0;
    while (hashTable->nodes[index].key != key && count < hashTable->capacity) { // 线性探测法解决冲突
        index = (index + 1) % hashTable->capacity;
        count++;
    }
    if (count == hashTable->capacity) { // 未找到指定键的节点
        return -1;
    } else {
        return index;
    }
}

// 计算散列表的平均查找长度
float averageSearchLength(HashTable *hashTable) {
    int total = 0;
    for (int i = 0; i < hashTable->capacity; i++) {
        if (hashTable->nodes[i].key != -1) { // 计算散列表中每个非空节点的查找长度
            total += find(hashTable, hashTable->nodes[i].key) + 1;
        }
    }
    return (float) total / hashTable->size;
}

int main() {
    // 测试不同规模散列表的平均查找长度
    for (int capacity = 10; capacity <= MAX_SIZE; capacity *= 10) {
        HashTable *hashTable = createHashTable(capacity);
        for (int i = 0; i < capacity; i++) {
            insert(hashTable, i, i * i); // 向散列表中插入节点，键为i，值为i的平方
        }
        printf("散列表容量：%d，平均查找长度：%.2f\n", capacity, averageSearchLength(hashTable));
        free(hashTable->nodes);
        free(hashTable);
    }
    return 0;
}

在上面的代码中，我们使用了线性探测法来解决散列表中的冲突。具体来说，当插入节点时，如果散列表中的某个位置已经被占用，我们就线性地向后查找，直到找到一个空位置为止。在查找节点时，也是从散列值对应的位置开始线性探测，直到找到指定键的节点为止。

为了测试不同规模散列表的平均查找长度，我们在main函数中使用了一个循环，从10开始依次测试容量为10、100、1000、10000的散列表。每次测试时，我们先创建一个指定容量的散列表，并向其中插入一定数量的节点（这里我们是以键的值为平方来作为节点的值，这样就能够保证节点的键是唯一的）。然后计算出散列表的平均查找长度，并输出到控制台上。最后，我们释放散列表的内存，以免出现内存泄漏。

注意，由于散列表的平均查找长度是一个浮点数，我们需要使用%f来格式化输出。同时，为了让输出结果更加美观，我们使用了%.2f来限制小数位数为2位。