2.基于散列表的工作原理，采用除留余数法H(key) = key % p (p<m) 作为散列函数，采用线性探测法处理冲突，实现散列查找算法，自动生成包含数百、数千、数万的正整数集合构造散列表，测量不同规模散列表的平均查找长度； C语言完整代码

以下是基于散列表的查找算法的C语言完整代码：

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

#define MAX_SIZE 100000 // 散列表的最大容量
#define PRIME 99991     // 散列表容量的质数

// 定义散列表节点结构体
typedef struct {
    int key;
} Node;

// 定义散列表结构体
typedef struct {
    Node data[MAX_SIZE];
    int count;
} HashTable;

// 初始化散列表
void init(HashTable *hashTable) {
    hashTable->count = 0;
    for (int i = 0; i < MAX_SIZE; i++) {
        hashTable->data[i].key = 0;
    }
}

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

// 插入元素
void insert(HashTable *hashTable, int key) {
    if (hashTable->count >= MAX_SIZE) {
        printf("Hash table is full\n");
        return;
    }

    int pos = hash(key);
    while (hashTable->data[pos].key != 0) {
        pos = (pos + 1) % MAX_SIZE;
    }

    hashTable->data[pos].key = key;
    hashTable->count++;
}

// 查找元素
int search(HashTable *hashTable, int key) {
    int pos = hash(key);
    while (hashTable->data[pos].key != key) {
        pos = (pos + 1) % MAX_SIZE;
        if (hashTable->data[pos].key == 0 || pos == hash(key)) {
            return -1;
        }
    }
    return pos;
}

// 生成指定数量的随机数
void generateRandomNumbers(int *arr, int n) {
    srand(time(NULL));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % MAX_SIZE + 1;
    }
}

int main() {
    HashTable hashTable;
    init(&hashTable);

    int n;
    printf("Enter the number of random numbers to generate: ");
    scanf("%d", &n);

    int arr[n];
    generateRandomNumbers(arr, n);

    // 插入元素
    for (int i = 0; i < n; i++) {
        insert(&hashTable, arr[i]);
    }

    // 测量平均查找长度
    int totalLength = 0;
    for (int i = 0; i < n; i++) {
        int pos = search(&hashTable, arr[i]);
        if (pos != -1) {
            totalLength += (pos + 1);
        }
    }
    float avgLength = (float)totalLength / n;
    printf("Average search length: %.2f\n", avgLength);

    return 0;
}

运行该程序，可以输入要生成的随机数的数量，然后程序会自动插入这些数到散列表中，并测量不同规模散列表的平均查找长度。