上机实验四 哈希表设计 西安石油大学数据结构

2023-12-04 17:20
文章标签 设计 数据结构 实验 哈希 上机 大学 西安石油

本文主要是介绍上机实验四 哈希表设计 西安石油大学数据结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实验名称：哈希表设计

（1）实验目的：掌握哈希表的设计方法及其冲突解决方法。

（2）主要内容：
已知一个含有10个学生信息的数据表，关键字为学生“姓名”的拼音，给出此表的一个哈希表设计方案。

要求：

1）建立哈希表：要求哈希函数采用除留余数法，解决冲突方法采用链表法。

2）编写一个测试主函数：输入10个学生的姓名拼音（即10个字符串）存入数组，然后对该姓名数组初始化（即将各字符串中字符的ASCII码相加，形成每个姓名的关键字），最后输出哈希表中各数据元素。

提示：最好不要输入重名

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define SIZE 10// 学生信息结构体
typedef struct {char name[20];
} Student;// 哈希表节点结构体
typedef struct Node {Student student;struct Node* next;
} Node;// 哈希表结构体
typedef struct {Node* buckets[SIZE];
} HashTable;// 初始化哈希表
void initHashTable(HashTable* hashTable) {for (int i = 0; i < SIZE; i++) {hashTable->buckets[i] = NULL;}
}// 计算哈希值
int hash(char* name) {int sum = 0;for (int i = 0; i < strlen(name); i++) {sum += name[i];}return sum % SIZE;
}// 向哈希表中插入节点
void insertNode(HashTable* hashTable, Student student) {int index = hash(student.name);Node* newNode = (Node*)malloc(sizeof(Node));newNode->student = student;newNode->next = NULL;if (hashTable->buckets[index] == NULL) {hashTable->buckets[index] = newNode;} else {Node* current = hashTable->buckets[index];while (current->next != NULL) {current = current->next;}current->next = newNode;}
}// 打印哈希表中的数据元素
void printHashTable(HashTable* hashTable) {for (int i = 0; i < SIZE; i++) {printf("Bucket %d: ", i);Node* current = hashTable->buckets[i];while (current != NULL) {printf("%s ", current->student.name);current = current->next;}printf("\n");}
}int main() {HashTable hashTable;initHashTable(&hashTable);Student students[10];printf("请输入10个学生的姓名拼音：\n");for (int i = 0; i < 10; i++) {scanf("%s", students[i].name);insertNode(&hashTable, students[i]);}printf("哈希表中各数据元素如下：\n");printHashTable(&hashTable);return 0;
}

这是一个使用哈希表实现的学生信息管理系统，可以插入学生姓名并打印出哈希表中的数据元素。哈希表使用链表解决哈希冲突。具体来说，程序分为以下几个部分：

  1. 定义结构体

程序首先定义了两个结构体，分别用于存储学生信息和哈希表节点信息。

  1. 初始化哈希表

程序定义了一个初始化哈希表的函数，将哈希表中每个桶初始化为空。

  1. 计算哈希值

程序定义了一个计算哈希值的函数，该函数将输入的字符串转换为一个整数作为哈希值。计算方法为将字符串中各字符的ASCII码相加，然后取余。

  1. 插入节点

程序定义了一个向哈希表中插入节点的函数，该函数首先计算出输入学生姓名的哈希值，然后将学生信息存储在哈希表中对应的桶中。如果该桶已经有了数据，则使用链表将新节点插入到链表尾部。

  1. 打印哈希表中的数据元素

程序定义了一个打印哈希表中的数据元素的函数，该函数遍历整个哈希表，逐个打印出每个桶中的节点信息。

  1. 主函数

主函数中调用上述函数，先让用户输入10个学生的姓名拼音，然后将学生信息插入哈希表中，并最终打印出哈希表中的数据元素。

需要注意的是，哈希函数的设计要尽可能地均匀，以避免大量数据集中在某个桶中，影响查询效率。此外，在插入和查询时，需要注意处理哈希冲突的情况。

问题描述

建立哈希表：

哈希函数采用除留余数法：即将关键字除以表长取余数，得到的余数作为该关键字的存储位置。
解决冲突方法采用链表法：当发生哈希冲突时，将具有相同余数的关键字存储在同一位置的链表中。

测试主函数：

输入10个学生的拼音姓名，存入数组。
对姓名数组初始化：计算每个姓名的关键字，即将各字符串中字符的ASCII码相加。
输出哈希表中各数据元素。

建立哈希表

确定哈希表的大小（表长），一般选择一个素数作为表长，这里假设选择表长为13。

创建一个包含13个链表的数组，用于存储哈希表的数据元素。

编写测试主函数

创建一个结构体用于表示学生信息，包括姓名和关键字。

编写哈希函数，以及插入元素和输出哈希表的函数。

在主函数中，创建存储学生信息的数组，计算每个姓名的关键字，并根据哈希函数的结果将其插入哈希表中。

最后输出哈希表中各数据元素。

要求：

建立哈希表：采用除留余数法作为哈希函数，解决冲突方法采用链表法。
编写一个测试主函数：输入10个学生的姓名拼音（即10个字符串）存入数组，然后对该姓名数组初始化（即将各字符串中字符的ASCII码相加，形成每个姓名的关键字），最后输出哈希表中各数据元素。

具体步骤：

定义哈希表的大小为10，即有10个槽位用于存放数据，每个槽位可以是一个链表。

哈希函数采用除留余数法，将学生姓名的拼音转换成一个整数作为关键字。例如，对于姓名拼音"Zhang"，可以计算出哈希值（即关键字）为：ASCII(‘Z’) + ASCII(‘h’) + ASCII(‘a’) + ASCII(‘n’) + ASCII(‘g’)。

初始化一个字符串数组，大小为10，用于存储学生的姓名拼音。

输入10个学生的姓名拼音，将其存入数组中。

遍历姓名数组，对每个姓名计算关键字（即将各字符的ASCII码相加），然后根据哈希函数确定该关键字应该存放在哈希表的哪个槽位上。

如果该槽位为空，则将该关键字插入槽位；如果该槽位已经有其他关键字，采用链表法将该关键字插入链表的尾部。

最后输出哈希表中各数据元素，即遍历哈希表的每个槽位，输出槽位中的关键字。

测试数据

["Zhang", "Wang", "Li", "Zhao", "Liu", "Chen", "Yang", "Huang", "Zhou", "Wu"]

根据这些数据，我们可以计算出每个姓名的关键字（即将各字符的ASCII码相加），然后根据哈希函数确定该关键字应该存放在哈希表的哪个槽位上。

算法思想

该程序使用了哈希表来解决学生信息管理的问题。哈希表是一种以键-值对形式存储数据的数据结构，它通过将键映射到数组中的索引位置来实现高效的数据访问。

算法思想如下：

  1. 初始化哈希表，创建一个具有固定大小的数组，并将每个位置初始化为空。

  2. 对于每个要插入的学生信息，计算其哈希值（可以使用散列函数），将其映射到哈希表中的一个索引位置。

  3. 如果该索引位置为空，则将学生信息插入到该位置；如果不为空，则发生冲突，需要进行解决冲突的操作。

  4. 解决冲突的方法可以是开放寻址法或链地址法。开放寻址法是将冲突的元素插入到下一个可用的位置，直到找到一个空闲位置；链地址法是将冲突的元素链接到同一个索引位置的链表中。

  5. 插入完成后，可以通过键值查找相应的学生信息。计算键的哈希值，找到对应的索引位置，然后在该位置的链表上查找。

  6. 可以根据具体需求，实现删除、更新等其他操作。

通过使用哈希表，可以快速插入、查找和删除学生信息，时间复杂度接近常数级别，提高了数据的访问效率。这是哈希表算法的主要思想。

模块划分

在这个程序中，可以将函数划分为以下几个模块：

  1. 哈希表模块

    • initHashTable(HashTable* hashTable)：初始化哈希表
    • hash(char* name)：计算哈希值
    • insertNode(HashTable* hashTable, Student student)：向哈希表中插入节点
    • printHashTable(HashTable* hashTable)：打印哈希表中的数据元素

  2. 学生信息模块

    • 结构体定义：定义了学生信息结构体（Student）

  3. 主函数模块

    • main()：主函数，用于调用其他函数实现学生信息的输入、插入和打印哈希表等功能

可以将这些函数分别放置在不同的文件中进行组织，例如：

  • hash_table.c：包含哈希表模块相关的函数实现
  • student.c：包含学生信息模块相关的结构体定义
  • main.c：包含主函数和与用户交互的部分

这样的文件组织结构可以提高代码的可读性和可维护性。同时，需要在对应的头文件中声明这些函数和结构体，以便在其他文件中引用和调用。例如：

  • hash_table.h：声明哈希表模块相关的函数
  • student.h：声明学生信息模块相关的结构体
  • main.h：声明主函数模块相关的函数

通过合理的模块划分和文件组织，可以使程序的结构更加清晰，易于理解和维护。

数据结构

（描述存储数据元素的存储结构）

在该程序中，使用了以下数据结构来存储学生信息：

  1. 学生信息结构体Student：用于表示每个学生的信息，包含一个名为name的字符数组成员。
struct Student {char name[50];
};
  1. 哈希表结构体HashTable：用于表示哈希表，包含一个固定大小的数组table，用于存储学生信息。数组的每个元素可以是一个链表的头节点，用于处理冲突。
struct HashTable {struct Student* table[MAX_SIZE];
};

在哈希表中，通过散列函数将学生信息的键（例如学生姓名）映射到数组中的一个索引位置。如果发生冲突，即多个学生信息映射到了同一个索引位置，可以使用链地址法，将冲突的学生信息链接到同一个索引位置的链表中。

因此，哈希表的每个数组元素table[i]（0 <= i < MAX_SIZE）可以是一个指向学生信息结构体的指针，或者是一个链表的头节点。

struct Student {char name[50];
};struct HashTable {struct Student* table[MAX_SIZE];
};

其中，Student结构体表示学生信息，HashTable结构体表示哈希表。

结果

我输入了以下学生的姓名拼音：

  1. Zhangsan
  2. Lisi
  3. Wangwu
  4. Zhaoliu
  5. Qianqi
  6. Sunba
  7. Zhoujiu
  8. Fengshi
  9. Wangwu
  10. Chenyi

根据这些输入，哈希表中的数据元素如下所示：

Bucket 0: 
Bucket 1: Fengshi 
Bucket 2: Qianqi 
Bucket 3: Sunba 
Bucket 4: 
Bucket 5: 
Bucket 6: Wangwu Wangwu 
Bucket 7: Zhangsan 
Bucket 8: Lisi 
Bucket 9: Zhaoliu Zhoujiu Chenyi

这是根据输入模拟的哈希表中的数据分布。每个桶对应一个哈希值，然后在每个桶中列出了对应的学生姓名。需要注意的是，由于"王五"重复出现，因此在桶6中出现了两次。

根据你提供的代码，我注意到了一些问题并给出以下建议：

  1. 哈希函数的选择：当前的哈希函数只是将姓名中每个字符的ASCII码求和并取余数。这种简单的哈希函数可能会导致较高的冲突率，使得哈希表的性能下降。建议考虑使用更复杂的哈希函数，例如乘法哈希或者除法哈希，以减少冲突。

  2. 内存泄漏：在插入节点时，为新节点分配了内存空间，但是在程序结束后没有释放这些节点的内存空间，这会导致内存泄漏。建议在程序结束前，遍历哈希表并释放所有节点的内存空间。

  3. 哈希表大小的选择：当前的哈希表大小是固定的，通过宏定义为10。然而，实际应用中，哈希表的大小应该根据预计的数据量进行动态调整，以避免过多的冲突或者浪费内存空间。

  4. 输入安全性：在接受用户输入时，代码没有对输入进行严格的验证和处理，存在缓冲区溢出的风险。建议使用安全的输入函数，如fgets()来获取用户输入，并对输入进行适当的验证和处理。

  5. 错误处理：代码没有对插入节点时的内存分配失败进行错误处理。在实际应用中，应该检查内存分配函数（如malloc()）的返回值，以确保分配成功，并在分配失败时采取适当的错误处理措施。

这篇关于上机实验四 哈希表设计 西安石油大学数据结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/454276。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
怎么让1台电脑共享给7人同时流畅设计

怎么让1台电脑共享给7人同时流畅设计

在当今的创意设计与数字内容生产领域，图形工作站以其强大的计算能力、专业的图形处理能力和稳定的系统性能，成为了众多设计师、动画师、视频编辑师等创意工作者的必备工具。 设计团队面临资源有限，比如只有一台高性能电脑时，如何高效地让七人同时流畅地进行设计工作，便成为了一个亟待解决的问题。 一、硬件升级与配置 1.高性能处理器（CPU）：选择多核、高线程的处理器，例如Intel的至强系列或AMD的Ry
阅读更多...
计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者：计算机编程-吉哥 🍊简介：专业从事JavaWeb程序开发，微信小程序开发，定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事，生活就是快乐的。 🍊心愿：点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能
阅读更多...
基于51单片机的自动转向修复系统的设计与实现

基于51单片机的自动转向修复系统的设计与实现

文章目录 前言资料获取设计介绍功能介绍设计清单具体实现截图参考文献设计获取 前言 💗博主介绍：✌全网粉丝10W+,CSDN特邀作者、博客专家、CSDN新星计划导师，一名热衷于单片机技术探索与分享的博主、专注于 精通51/STM32/MSP430/AVR等单片机设计 主要对象是咱们电子相关专业的大学生，希望您们都共创辉煌！✌💗 👇🏻 精彩专栏 推荐订阅👇🏻 单片机
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
SprinBoot+Vue网络商城海鲜市场的设计与实现

SprinBoot+Vue网络商城海鲜市场的设计与实现

目录 1 项目介绍2 项目截图3 核心代码3.1 Controller3.2 Service3.3 Dao3.4 application.yml3.5 SpringbootApplication3.5 Vue 4 数据库表设计5 文档参考6 计算机毕设选题推荐7 源码获取 1 项目介绍 博主个人介绍：CSDN认证博客专家，CSDN平台Java领域优质创作者，全网30w+
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2