目录
(1)理解查找表的基本概念,定义、 分类和各类的特点;
(2)掌握哈希表的构造方法以及解冲突的方法;
(3)掌握哈希存储和哈希查找的基本思想及有关方法。
使用哈希函数:H(K)=3K MOD 11
并采用链地址法处理冲突。试对关键字序列(22,41,53,46,30,13,01,67)构造哈希表,设计构造哈希表的完整算法去。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 11
typedef struct Node {
????int key;
????struct Node* next;
} Node;
?
typedef struct HashTable {
????Node** data;
????int size;
} HashTable;
?
HashTable* initHashTable(int size) {
????HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable));
????hashTable->size = size;
????hashTable->data = (Node**)malloc(sizeof(Node*) * size);
????for (int i = 0; i < size; i++) {
????????hashTable->data[i] = NULL;
????}
????return hashTable;
}
?
// 计算哈希值
int hash(int key) {
????return 3 * key % MAX_SIZE;
}
?
// 向哈希表中插入关键字
void insert(HashTable* hashTable, int key) {
????int position = hash(key); // 计算哈希值
????Node* node = (Node*)malloc(sizeof(Node)); // 创建新节点
????node->key = key;
????node->next = NULL;
?
????if (hashTable->data[position] == NULL) { // 插入新节点
????????hashTable->data[position] = node;
????} else {
????????Node* p = hashTable->data[position];
????????while (p->next != NULL) {
????????????p = p->next;
????????}
????????p->next = node;
????}
}
?
// 在哈希表中查找关键字
int search(HashTable* hashTable, int key) {
????int position = hash(key); // 计算哈希值
????Node* p = hashTable->data[position];
????while (p != NULL) { // 遍历链表
????????if (p->key == key) {
????????????return position; // 返回位置
????????}
????????p = p->next;
????}
????return -1; // 没有找到返回-1
}
?
int main() {
????int keys[] = {22, 41, 53, 46, 30, 13, 1, 67};
????int size = sizeof(keys) / sizeof(int);
?
????// 构造哈希表
????HashTable* hashTable = initHashTable(MAX_SIZE);
????for (int i = 0; i < size; i++) {
????????insert(hashTable, keys[i]);
????}
?
????// 查找关键字
????printf("输入要查找的关键字: ");
????int key;
????scanf("%d", &key);
????int position = search(hashTable, key);
????if (position == -1) {
????????printf("没有找到该关键字\n");
????} else {
????????printf("该关键字在哈希表中的位置为: %d\n", position);
????}
?
????return 0;
}
?
?
先定义了哈希节点结构体 Node?和哈希表结构体 HashTable。然后使用 initHashTable?函数初始化哈希表,并使用 hash?函数计算哈希值。使用 insert?函数向哈希表中插入关键字,并使用 search?函数在哈希表中查找关键字。最后,我们在 main?函数中构造哈希表并进行关键字查找。
??学习了哈希表的基本原理和实现方法。通过使用哈希函数将关键字映射到固定位置上,并采用链地址法解决冲突问题,哈希表可以实现高效的数据插入和查找操作。
?