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

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

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

#define MAX_SIZE 100000 //散列表的最大长度
#define PRIME 99991 //散列表长度应为质数

typedef struct node {
    int data;
    struct node *next;
} Node;

Node *hashTable[MAX_SIZE]; //散列表

//散列函数，采用除留余数法
int hash(int key) {
    return key % PRIME;
}

//插入元素
void insert(int key) {
    int index = hash(key);
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = key;
    p->next = hashTable[index];
    hashTable[index] = p;
}

//查找元素
int search(int key) {
    int index = hash(key);
    Node *p = hashTable[index];
    int count = 0;
    while (p != NULL) {
        count++;
        if (p->data == key) {
            return count;
        }
        p = p->next;
    }
    return -1;
}

int main() {
    //生成包含数百、数千、数万正整数的若干中正整数集合
    int n;
    printf("请输入元素个数：");
    scanf("%d", &n);
    printf("请输入元素：\n");
    for (int i = 0; i < n; i++) {
        int key;
        scanf("%d", &key);
        insert(key);
    }

    //测量不同规模散列表的平均查找长度
    int testSize;
    printf("请输入测试集合大小：");
    scanf("%d", &testSize);
    printf("请输入测试集合：\n");
    int total = 0;
    for (int i = 0; i < testSize; i++) {
        int key;
        scanf("%d", &key);
        int count = search(key);
        if (count != -1) {
            total += count;
        }
    }
    double avgLength = (double)total / testSize;
    printf("平均查找长度为：%f\n", avgLength);

    return 0;
}

### 回答2：

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

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

#define SIZE 100 // 散列表大小

// 插入链表节点
void insert(Node* table[], int value) {
    // 创建新节点
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = value;
    newNode->next = NULL;

    // 计算散列值
    int index = value % SIZE;

    // 在散列表中插入新节点
    if (table[index] == NULL) {
        table[index] = newNode;
    } else {
        Node* temp = table[index];
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

// 查找链表节点
int search(Node* table[], int value) {
    // 计算散列值
    int index = value % SIZE;

    // 在散列表中查找节点
    Node* temp = table[index];
    while (temp != NULL) {
        if (temp->key == value) {
            return index;
        }
        temp = temp->next;
    }

    return -1; // 节点未找到
}

int main() {
    Node* table[SIZE]; // 散列表
    for (int i = 0; i < SIZE; i++) {
        table[i] = NULL; // 初始化散列表
    }

    // 构造散列表
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int size = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < size; i++) {
        insert(table, arr[i]);
    }

    // 测试查找
    int key = 5;
    int result = search(table, key);
    if (result != -1) {
        printf("散列表中找到节点 %d\n", key);
    } else {
        printf("散列表中未找到节点 %d\n", key);
    }

    return 0;
}

这段代码实现了采用除留余数法作为散列函数，采用链地址法处理冲突的散列查找算法。首先，定义了一个链表节点结构体，包含键值和指向下一个节点的指针。然后，定义了散列表的大小和散列表数组。在主函数中，首先初始化散列表数组，然后通过调用insert函数将一组正整数插入散列表中。最后，调用search函数可以根据给定的键值在散列表中进行查找，找到则返回索引，未找到则返回-1。

### 回答3：
散列表是一种通过散列函数将关键字映射成地址的数据结构。基于散列表的工作原理是根据关键字通过散列函数计算出对应的散列地址，然后将关键字存储在对应地址的链表上。

在该问题中，采用除留余数法作为散列函数，即H(key) = key % p，其中p为小于散列表大小m的质数。采用链地址法处理冲突，即将散列到同一地址的关键字以链表的形式连接起来。

下面是一个完整的C语言代码实现：

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

// 定义链表节点结构
typedef struct Node {
  int data;
  struct Node* next;
} Node;

// 初始化链表
void initList(Node** head) {
  *head = NULL;
}

// 在链表头插入节点
void insertNode(Node** head, int value) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = value;
  newNode->next = *head;
  *head = newNode;
}

// 销毁链表
void destroyList(Node* head) {
  Node* cur = head;
  while (cur != NULL) {
    Node* next = cur->next;
    free(cur);
    cur = next;
  }
}

// 计算散列地址
int hash(int key, int p) {
  return key % p;
}

// 散列查找
int search(Node** hashTable, int key, int p) {
  int hashAddr = hash(key, p);
  Node* cur = hashTable[hashAddr];
  int count = 0;

  while (cur != NULL) {
    if (cur->data == key) {
      return count;  // 返回查找次数
    }
    cur = cur->next;
    count++;
  }

  return -1;  // 未找到返回-1
}

int main() {
  int m = 1000;  // 散列表大小
  int p = 997;   // 较小的质数
  int n = 10000; // 正整数集合大小

  Node** hashTable = (Node**)malloc(m * sizeof(Node*));
  for (int i = 0; i < m; i++) {
    initList(&hashTable[i]);
  }

  // 生成包含n个数的正整数集合
  int* data = (int*)malloc(n * sizeof(int));
  for (int i = 0; i < n; i++) {
    data[i] = rand() % 100000;
  }

  // 构造散列表
  for (int i = 0; i < n; i++) {
    int hashAddr = hash(data[i], p);
    insertNode(&hashTable[hashAddr], data[i]);
  }

  // 测量不同规模散列表的平均查找长度
  int searchCount = 0;
  for (int i = 0; i < n; i++) {
    searchCount += search(hashTable, data[i], p);
  }
  float averageLength = (float)searchCount / n;

  printf("Average length of hashtable with size %d: %.2f\n", m, averageLength);

  // 释放内存
  for (int i = 0; i < m; i++) {
    destroyList(hashTable[i]);
  }
  free(hashTable);
  free(data);

  return 0;
}

以上代码包括了散列表的初始化、插入、查找等操作，通过测量不同规模散列表的平均查找长度来评估散列表的性能。不同规模的散列表可以通过修改变量m的值来实现。