C数据结构与算法——哈希表/散列表创建过程中的冲突与聚集(哈希查找) 应用

实验任务

(1) 掌握散列算法（散列函数、散列存储、散列查找）的实现；
(2) 掌握常用的冲突解决方法。

实验内容

(1) 选散列函数 H(key) = key % p，取散列表长 m 为 10000，p 取小于 m 的最大素数；
(2) 测试 α 对于散列算法效率的影响；
分别测试将随机生成的5000个、7500个以及 p 个不重复的随机数序列放入该表中，采用线性探测法作为解决冲突方法时，各自的冲突总次数和聚集总次数
(3) 测试不同冲突解决方法对于散列算法效率的影响：
分别测试随机生成的5000个不重复的随机数序列放入该表中时，采用线性探测法和二次探测法各自的冲突总次数和聚集总次数。
(4) 自行设计实验输出，应使结果尽可能清晰地被展示。

实验源码

#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>#define HASHSIZE 10000 // 散列表长度
#define NULLKEY 0 // 空值标记int conflictCount; // 冲突次数
int gatherCount; // 聚集次数typedef struct {int key;int gather;
} ElemType;// 散列表
typedef struct {ElemType *elem;int count;
} HashTable;int InitHashTable(HashTable *table); // 初始化散列表
int Hash(int key); // 除留余数法
void CreateRandomTable(int arr[], int randMinNum, int randLength); // 生成哈希表数据，用数组存放
void knuthShuffle(int arr[], int length); // 洗牌算法
void swapInt(int *card_1, int *card_2); // 交换函数
void InsertHashByLD(HashTable *table, int key); // 线性探测-插入关键字到散列表
void InsertHashBySD(HashTable *table, int key); // 二次探测-插入关键字到散列表
void HashTableDestroy(HashTable *table); // 销毁哈希表/*** <h2>哈希表/散列表的查找 实验二</h2>*/
int main() {// 业务逻辑printf("~~~~~~~~~~ 实现散列算法并对不同α和不同冲突解决方法进行对比 ~~~~~~~~~~\n");printf("\t\t====================================\n");printf("\t\t 1  线性探测-自定义生成随机数序列\n");printf("\t\t 2  线性探测-系统随机生成随机数序列\n");printf("\t\t 3  二次探测-自定义生成随机数序列\n");printf("\t\t 4  二次探测-系统随机生成随机数序列\n");printf("\t\t 5  退出\n");printf("\t\t 6  清屏\n");printf("\t\t====================================\n");int change = 1;while (1) {// 创建随机数种子srand(time(NULL));// 创建哈希表HashTable table;// 初始化哈希表if (InitHashTable(&table) == -1) {printf("申请地址失败");return 0;}// 生成扑克+洗牌算法（可指定随机数范围，且不会重复）int randMinNum = 1;int randMaxNum = 500000;int arr[randMaxNum - randMinNum];CreateRandomTable(arr, randMinNum, (randMaxNum - randMinNum));printf("请选择：");scanf("%d", &change);if (change == 1) {// 从洗好的牌中连续抽前arrLength张出来int arrLength = 5000;printf("线性探测-请输入自定义随机数个数：");scanf("%d", &arrLength);for (int i = 0; i < arrLength; i++) {InsertHashByLD(&table, arr[i]);}} else if (change == 2) {// 从洗好的牌中连续抽前随机张出来int arrLength = randMinNum + (rand() % HASHSIZE + 1);for (int i = randMinNum; i <= arrLength; i++) {InsertHashByLD(&table, arr[i]);}} else if (change == 3) {// 从洗好的牌中连续抽前arrLength张出来int arrLength = 5000;printf("二次探测-请输入自定义随机数个数：");scanf("%d", &arrLength);for (int i = randMinNum; i <= (randMinNum + arrLength); i++) {InsertHashBySD(&table, arr[i]);}} else if (change == 4) {// 从洗好的牌中连续抽前随机张出来int arrLength = randMinNum + (rand() % HASHSIZE + 1);for (int i = randMinNum; i <= arrLength; i++) {InsertHashBySD(&table, arr[i]);}} else if (change == 5) {break;} else if (change == 6) {system("cls"); // 清屏printf("~~~~~~~~~~ 实现散列算法并对不同α和不同冲突解决方法进行对比 ~~~~~~~~~~\n");printf("\t\t====================================\n");printf("\t\t 1  线性探测-自定义生成随机数序列\n");printf("\t\t 2  线性探测-系统随机生成随机数序列\n");printf("\t\t 3  二次探测-自定义生成随机数序列\n");printf("\t\t 4  二次探测-系统随机生成随机数序列\n");printf("\t\t 5  退出\n");printf("\t\t 6  清屏\n");printf("\t\t====================================\n");} else {printf("你的输入有误！！！\n");}if (change == 1 || change == 2 || change == 3 || change == 4) {printf("冲突次数 %d\n", conflictCount);printf("聚集次数 %d\n", gatherCount);printf("\n");}conflictCount = 0;gatherCount = 0;// 销毁哈希表HashTableDestroy(&table);}return 0;
}// 初始化
int InitHashTable(HashTable *table) {if (!table) {return -1;}table->count = HASHSIZE; // 表长table->elem = (ElemType *) malloc(sizeof(ElemType) * HASHSIZE); // 表空间if (!table->elem) {return -1; // 如果没有申请到地址，退出}for (int i = 0; i < HASHSIZE; i++) {table->elem[i].key = NULLKEY; // 所有单元全部初始化为空}return 0; // 初始化成功
}// 使用除留余数法创建哈希表
int Hash(int key) {// 求出最大素数for (int i = HASHSIZE; i > 0; i--) {int j = 2;for (; j <= i; j++) {if (i % j == 0) {break;}}if (i == j) {return key % i;}}return -999; // 抛出一个错误
}void CreateRandomTable(int arr[], int randMinNum, int randLength) {if (randMinNum == 0) {printf("生成的随机数不能包含哈希表空值标记 ( 0 ) \n");return;}for (int i = randMinNum; i <= randLength; i++) {arr[i] = i;}knuthShuffle(arr, randLength);
}void knuthShuffle(int arr[], int length) {for (int i = length - 1; i >= 1; i--) {swapInt(&arr[i], &arr[rand() % (i + 1)]);}
}void swapInt(int *card_1, int *card_2) {int tCard;tCard = *card_1;*card_1 = *card_2;*card_2 = tCard;
}// 线性探测法创建哈希表（这里保证散列表有足够的空间）
void InsertHashByLD(HashTable *table, int key) {int hashIndex = Hash(key); // 除留取余的方式给新插入的值分配散列位置while (table->elem[hashIndex].key != NULLKEY) { // 在插入的时候如果出现不等于空的位置，则说明遇到冲突if (table->elem[hashIndex].gather == -1) {gatherCount++; // 聚集} else {table->elem[hashIndex].gather = -1;conflictCount++; // 冲突}hashIndex = (hashIndex + 1) % HASHSIZE; // 线性探测}table->elem[hashIndex].key = key; // 放入哈希表
}// 二次探测法创建哈希表（这里保证散列表有足够的空间）
void InsertHashBySD(HashTable *table, int key) {int count = 0;int hashIndex = Hash(key); // 除留取余的方式给新插入的值分配散列位置int pos = hashIndex;while (table->elem[hashIndex].key != NULLKEY) { // 在插入的时候如果出现不等于空的位置，则说明遇到冲突count++;if (table->elem[hashIndex].gather == -1) {gatherCount++; // 聚集} else {table->elem[hashIndex].gather = -1;conflictCount++; // 冲突}hashIndex = (pos + count * count) % (HASHSIZE / 2); // 二次探测}table->elem[hashIndex].key = key; // 放入哈希表
}void HashTableDestroy(HashTable *table) {if (table->elem != NULL) {free(table->elem);table->elem = NULL;table->count = 0;}
}