基于散列表的工作原理，采用除留余数法H(key) = key % p (p<m) 作为散列函数，采用链地址法处理冲突，实现散列查找算法，根据自动生成包含数百、数千、数万正整数的正整数集合构造散列表，测量不同规模散列表的平均查找长度，用c语言给出相关代码

### 回答1：
以下是基于散列表的查找算法的C语言实现，其中使用除留余数法作为散列函数，使用链地址法处理冲突：

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

#define MAX_SIZE 100000 // 最大容量

// 链表结构体
typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// 散列表结构体
typedef struct HashTable {
    ListNode** table; // 散列表数组
    int capacity; // 容量
} HashTable;

// 创建链表节点
ListNode* createNode(int val) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 创建散列表
HashTable* createHashTable(int capacity) {
    HashTable* newTable = (HashTable*)malloc(sizeof(HashTable));
    newTable->table = (ListNode**)malloc(sizeof(ListNode*) * capacity);
    newTable->capacity = capacity;
    for (int i = 0; i < capacity; i++) {
        newTable->table[i] = NULL;
    }
    return newTable;
}

// 散列函数
int hash(int key, int capacity) {
    return key % capacity;
}

// 插入节点
void insert(HashTable* table, int val) {
    int position = hash(val, table->capacity); // 计算散列位置
    ListNode* head = table->table[position];
    if (!head) { // 如果该位置没有节点，直接插入
        table->table[position] = createNode(val);
    } else { // 否则插入链表末尾
        ListNode* newNode = createNode(val);
        ListNode* cur = head;
        while (cur->next) {
            cur = cur->next;
        }
        cur->next = newNode;
    }
}

// 查找节点
ListNode* search(HashTable* table, int val) {
    int position = hash(val, table->capacity); // 计算散列位置
    ListNode* head = table->table[position];
    ListNode* cur = head;
    while (cur) { // 遍历链表
        if (cur->val == val) { // 找到目标节点
            return cur;
        }
        cur = cur->next;
    }
    return NULL; // 没有找到目标节点
}

// 计算平均查找长度
float getAvgSearchLen(HashTable* table, int* nums, int size) {
    float sum = 0;
    for (int i = 0; i < size; i++) {
        ListNode* node = search(table, nums[i]);
        int len = 0;
        while (node) {
            len++;
            node = node->next;
        }
        sum += len;
    }
    return sum / size;
}

int main() {
    int nums[MAX_SIZE];
    int size;
    printf("请输入数组大小（小于等于%d）：", MAX_SIZE);
    scanf("%d", &size);
    printf("请输入数组元素，用空格分隔：");
    for (int i = 0; i < size; i++) {
        scanf("%d", &nums[i]);
    }
    HashTable* table = createHashTable(size / 2);
    for (int i = 0; i < size; i++) { // 构造散列表
        insert(table, nums[i]);
    }
    float avgSearchLen = getAvgSearchLen(table, nums, size);
    printf("平均查找长度：%f", avgSearchLen);
    return 0;
}

需要注意的是，由于除留余数法的散列函数可能导致散列冲突，因此我们在插入节点和查找节点时需要使用链地址法来处理冲突。具体来说，当散列到同一位置时，我们将新节点插入到该位置对应的链表末尾，查找时遍历整个链表直到找到目标节点为止。在计算平均查找长度时，我们遍历整个数组，对每个元素进行查找并累加查找链表的长度，最后求平均值。

### 回答2：
散列表是一种用于存储和查找数据的数据结构，它通过散列函数将关键字映射到散列表的固定位置，以实现高效的查找操作。
基于散列表的工作原理如下：
1. 定义一个散列函数H(key)，将关键字key映射到散列表中的某个位置。在这个问题中，采用除留余数法，即将key除以一个小于key的素数p，取余数作为散列地址。
2. 创建一个大小为m的散列表，m是一个大于等于数据集合大小的素数。
3. 当插入数据时，将关键字key通过散列函数得到散列地址，然后在该地址处插入数据。若发生冲突，采用链地址法处理，即在冲突位置处维护一个链表，存储冲突关键字，以便后续的查找。
4. 当查找数据时，将关键字通过散列函数得到散列地址，然后在该地址处进行查找。若遇到冲突，通过链表逐个比较待查找的关键字，直到找到目标数据或链表为空。

下面是用C语言实现散列查找算法的相关代码：

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

// 散列表节点结构
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// 散列表结构
typedef struct {
    int size; // 散列表大小
    Node** table; // 散列表数组
} HashTable;

// 初始化散列表
HashTable* initTable(int size) {
    HashTable* table = malloc(sizeof(HashTable));
    table->size = size;
    table->table = malloc(sizeof(Node*) * size);
    for (int i = 0; i < size; i++) {
        table->table[i] = NULL;
    }
    return table;
}

// 散列函数
int hashFunction(int key, int size) {
    return key % size;
}

// 向散列表中插入关键字
void insert(HashTable* table, int key) {
    int index = hashFunction(key, table->size);
    Node* newNode = malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;
    if (table->table[index] == NULL) {
        table->table[index] = newNode;
    } else {
        Node* curr = table->table[index];
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

// 在散列表中查找关键字
int search(HashTable* table, int key) {
    int index = hashFunction(key, table->size);
    if (table->table[index] == NULL) {
        return -1; // 没有找到
    } else {
        Node* curr = table->table[index];
        while (curr != NULL) {
            if (curr->key == key) {
                return index; // 找到了
            }
            curr = curr->next;
        }
        return -1; // 没有找到
    }
}

// 计算平均查找长度
float calculateAvgSearchLength(HashTable* table, int keyCount) {
    int totalSearchLength = 0;
    for (int i = 0; i < keyCount; i++) {
        int searchLength = search(table, i);
        totalSearchLength += searchLength;
    }
    return (float)totalSearchLength / keyCount;
}

int main() {
    int keyCount = 1000; // 数据集合大小
    int tableSize = 1009; // 散列表大小（素数）
    HashTable* table = initTable(tableSize);
    
    // 构造散列表
    for (int i = 0; i < keyCount; i++) {
        insert(table, i);
    }
    
    // 测量不同规模散列表的平均查找长度
    float avgSearchLength = calculateAvgSearchLength(table, keyCount);
    printf("Average search length: %.2f\n", avgSearchLength);
    
    return 0;
}

以上代码演示了如何构造散列表并测量不同规模散列表的平均查找长度。根据散列函数和链地址法处理冲突，这个散列表可以高效地插入和查找数据。

### 回答3：
散列表是一种常用的数据结构，用来存储大量的数据并支持高效的查找操作。它的工作原理是根据某个散列函数将关键字映射到散列表的位置上，当发生冲突时，采用链地址法来解决。

以除留余数法H(key) = key % p作为散列函数，其中p<m，p是小于m的数。这个散列函数可以将输入的关键字key映射到0到p-1的范围内，即获得一个合法的散列地址。采用链地址法处理冲突，是指当不同的关键字映射到了同一个散列地址上时，将这些关键字构成一个链表，存储在该地址上。这样，冲突不会导致数据丢失，同时也可以通过链表遍历的方式进行查找。

为了实现散列查找算法，首先需要创建一个大小为m的散列表。然后，将输入的正整数集合依次通过散列函数获得散列地址，再将对应的正整数插入到散列表中的链表中。最后，当需要查找某个关键字时，通过散列函数计算得到散列地址，再在对应的链表中进行查找。

为了测量不同规模散列表的平均查找长度，可以在插入和查找过程中计算查找的次数，并得到平均值。具体代码如下：

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

#define SIZE 10000 // 散列表的大小

// 定义链表节点
typedef struct node {
    int key;
    struct node* next;
} Node;

// 创建链表节点
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;
    return newNode;
}

// 插入关键字到散列表
void insert(Node* hashtable[], int key) {
    int index = key % SIZE;
    Node* newNode = createNode(key);
    if (hashtable[index] == NULL) {
        hashtable[index] = newNode;
    } else {
        Node* node = hashtable[index];
        while (node->next != NULL) {
            node = node->next;
        }
        node->next = newNode;
    }
}

// 在散列表中查找关键字
int search(Node* hashtable[], int key) {
    int index = key % SIZE;
    Node* node = hashtable[index];
    int count = 0;
    while (node != NULL) {
        count++;
        if (node->key == key) {
            return count;
        }
        node = node->next;
    }
    return -1; // 表示未找到
}

int main() {
    int input[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
    int length = sizeof(input) / sizeof(input[0]);

    // 创建散列表
    Node* hashtable[SIZE];
    for (int i = 0; i < SIZE; i++) {
        hashtable[i] = NULL;
    }

    // 插入关键字
    for (int i = 0; i < length; i++) {
        insert(hashtable, input[i]);
    }

    // 查找关键字并计算平均查找长度
    int avgSearchLength = 0;
    for (int i = 0; i < length; i++) {
        int result = search(hashtable, input[i]);
        avgSearchLength += result;
        printf("查找关键字 %d 的次数为 %d\n", input[i], result);
    }
    avgSearchLength /= length;
    printf("平均查找长度为 %d\n", avgSearchLength);

    return 0;
}

以上是一个简单的基于散列表的查找算法的示例代码，通过测量不同规模散列表的平均查找长度可以评估算法的效率和性能。