查找的数据结构实验报告(哈希表)

发布时间:2024年01月07日

目录

一、实验目的:

二、实验内容(实验题目与说明)

三、算法设计(核心代码或全部代码)

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

五、总结与心得


一、实验目的:

(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;

}

?

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

c9956a76272e4a3a913ee7fd0172be5c.png

ccee2577052c45d08705e1aef1ebeb98.png?

先定义了哈希节点结构体 Node?和哈希表结构体 HashTable。然后使用 initHashTable?函数初始化哈希表,并使用 hash?函数计算哈希值。使用 insert?函数向哈希表中插入关键字,并使用 search?函数在哈希表中查找关键字。最后,我们在 main?函数中构造哈希表并进行关键字查找。

五、总结与心得

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

?

文章来源:https://blog.csdn.net/2301_76690905/article/details/135415681
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。