查找的数据结构实验报告（哈希表）

目录

一、实验目的：

二、实验内容（实验题目与说明）

三、算法设计（核心代码或全部代码）

四、运行与测试（测试数据和实验结果分析）

五、总结与心得

一、实验目的：

(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?函数中构造哈希表并进行关键字查找。

五、总结与心得

??学习了哈希表的基本原理和实现方法。通过使用哈希函数将关键字映射到固定位置上，并采用链地址法解决冲突问题，哈希表可以实现高效的数据插入和查找操作。

?