用c写一个用线性构造散列表,测量不同规模散列表的平均查找长度的代码
时间: 2023-06-16 07:05:36 浏览: 45
以下是用C语言实现的用线性构造散列表,测量不同规模散列表的平均查找长度的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_SIZE 10000 // 最大散列表长度
typedef struct {
int key;
int value;
} HashNode;
typedef struct {
HashNode* data;
int size;
} HashTable;
// 初始化散列表
void initHashTable(HashTable* hashTable) {
hashTable->data = (HashNode*)malloc(sizeof(HashNode) * MAX_SIZE);
hashTable->size = 0;
for (int i = 0; i < MAX_SIZE; i++) {
hashTable->data[i].key = -1;
}
}
// 散列函数
int hashFunction(int key) {
return key % MAX_SIZE;
}
// 插入元素
void insertElement(HashTable* hashTable, int key, int value) {
int index = hashFunction(key);
while (hashTable->data[index].key != -1) {
index = (index + 1) % MAX_SIZE;
}
hashTable->data[index].key = key;
hashTable->data[index].value = value;
hashTable->size++;
}
// 查找元素
int searchElement(HashTable* hashTable, int key) {
int index = hashFunction(key);
int count = 0;
while (hashTable->data[index].key != key && count < MAX_SIZE) {
index = (index + 1) % MAX_SIZE;
count++;
}
if (count == MAX_SIZE) {
return -1;
} else {
return count + 1;
}
}
// 生成随机数
int getRandomNumber() {
return rand() % MAX_SIZE;
}
int main() {
srand(time(NULL));
HashTable hashTable;
initHashTable(&hashTable);
int sizeArray[] = {100, 500, 1000, 5000, 10000};
int sizeArrayLength = sizeof(sizeArray) / sizeof(int);
for (int i = 0; i < sizeArrayLength; i++) {
int size = sizeArray[i];
for (int j = 0; j < size; j++) {
int key = getRandomNumber();
insertElement(&hashTable, key, key);
}
int total = 0;
for (int j = 0; j < MAX_SIZE; j++) {
if (hashTable.data[j].key != -1) {
total += searchElement(&hashTable, hashTable.data[j].key);
}
}
float average = (float)total / (float)size;
printf("散列表长度为%d时,平均查找长度为%f\n", size, average);
hashTable.size = 0;
free(hashTable.data);
initHashTable(&hashTable);
}
return 0;
}
```
以上代码先定义了两个结构体,一个是散列表的节点结构体 `HashNode`,一个是散列表的结构体 `HashTable`。在 `initHashTable` 函数中初始化散列表,并在 `hashFunction` 函数中定义散列函数。在 `insertElement` 函数中插入元素,使用线性探测法解决哈希冲突。在 `searchElement` 函数中查找元素,并返回平均查找长度。在 `main` 函数中生成随机数,并在不同规模的散列表中插入随机数,并计算平均查找长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)