创建基于链地址法的hash表，并实现电话薄的管理（记录不超过20个）。电话薄中的记录包括姓名、电话号码和地址三个数据项，创建两个hash表，关键字分别为姓名和电话号码 hash函数自定，比如可以为姓名/电话号码部分字符求和之后对17取模完成记录的插入、查找、显示功能

时间: 2023-05-02 09:02:07 浏览: 97

哈希表的设计与实现

4星 · 用户满意度95%

问题描述：针对某个单位电话号码簿，设计一个哈希表，并完成相应的建表和查表程序。基本要求：设每个记录有下列数据项：电话号码、用户名、住址。从键盘输入各记录，以用户名为关键字建立哈希表，哈希函数用除留取余数法构造，采用线性探测法解决冲突。可以插入、查找、删除并显示给定用户名的记录，并计算查找长度, 哈希表保存到文件中，并能从文件中读取数据。测试数据：取某个单位电话号码簿中的30个记录。提高要求： (1)将电话号码薄以文件形式保存到盘上，能够按用户名和电话号码两种形式建立哈希表并实现插入、查找、删除表中元素的功能。 (2)对于相同的哈希函数，采用两种或两种以上的处理冲突的方法，如线性探测法和拉链法，比较不同的处理冲突的方法平均查找长度的变化。测试时，采用同一组测试数据，分别用不同的方法处理冲突，记录并输出各自的平均查找长度。 (3)设计图形用户界面 ### 哈希表的设计与实现 #### 一、背景介绍哈希表是一种非常高效的数据结构，通过哈希函数将键映射到表中的一个位置来访问记录，这使得查找记录的操作能在常数时间内完成。本项目的目标是设计并实现一个哈希表，用于存储单位电话号码簿中的信息。 #### 二、基本要求与实现 ##### 2.1 数据结构定义为了存储电话号码簿的信息，我们定义了一个`struct node`结构体，其中包含三个主要成员：电话号码（`char num[11]`）、用户名（`char name[8]`）和住址（`char address[20]`）。此外，还有一个指向下一个节点的指针（`node *next`），用于解决哈希冲突时的链式存储。 ```c struct node { char name[8], address[20]; char num[11]; node *next; }; ``` ##### 2.2 哈希函数设计哈希函数用于将电话号码和用户名映射到哈希表中的位置。这里使用了除留取余法作为哈希函数的基础，并且对电话号码采用了累加ASCII值的方式进行哈希，对用户名则是直接累加字符的ASCII值。 ```c void hash(char num[11]) { int i = 3; key = (int)num[2]; while (num[i] != '\0') { key += (int)num[i]; i++; } key %= 20; } void hash2(char name[8]) { int i = 1; key2 = (int)name[0]; while (name[i] != '\0') { key2 += (int)name[i]; i++; } key2 %= 20; } ``` ##### 2.3 冲突解决策略本项目采用了线性探测法来解决哈希冲突，即当发生冲突时，在哈希表中继续寻找下一个空位存放新的记录。 ```c void append() { node *newphone = input(); hash(newphone->num); newphone->next = phone[key]->next; phone[key]->next = newphone; return 0; } ``` ##### 2.4 插入、查找和删除操作插入操作通过调用`append()`函数实现；查找操作通过`find()`和`find2()`函数实现，分别根据电话号码和用户名查找；删除操作未在示例代码中给出，但可以通过遍历链表找到待删除的节点并调整指针实现。 ```c void find(char num[11]) { hash(num); node *q = phone[key]->next; while (q != NULL) { if (strcmp(num, q->num) == 0) { break; } q = q->next; } if (q) { printf("%s_%s_%s\n", q->name, q->address, q->num); } else { printf("Not Found\n"); } } ``` #### 三、提高要求实现 ##### 3.1 文件存储为了满足提高要求中的第一点，可以利用文件I/O操作将电话号码簿以文件的形式保存到磁盘上。具体实现包括文件的读写功能。 ##### 3.2 多种冲突解决方法本项目除了线性探测法之外，还可以实现拉链法来解决哈希冲突。拉链法使用链表存储冲突的元素，使得插入、查找和删除操作更加灵活。 ```c void hashChain(char num[11]) { // 实现拉链法下的哈希函数 } ``` ##### 3.3 平均查找长度统计通过对不同冲突解决方法的平均查找长度进行统计，可以比较各种方法的性能差异。例如，对于每种方法，都可以记录每次查找的次数，并求出所有查找次数的平均值。 ```c int averageSearchLength(node **hashTable, int size) { // 统计平均查找长度的实现 } ``` ##### 3.4 图形用户界面设计可以考虑使用图形用户界面库（如GTK+、Qt等）来提供更友好的用户交互体验。GUI可以包括添加、查找和删除记录的功能按钮，以及显示当前哈希表状态的窗口。 #### 四、总结本文介绍了如何设计并实现一个哈希表，以存储单位电话号码簿中的信息。通过对基本要求和提高要求的实现，不仅可以加深对哈希表原理的理解，还能掌握如何在实际应用中有效地使用哈希表。

这个问题的意思是，使用哈希表来实现电话号码管理，记录不超过20条电话记录。电话记录包括姓，电话号码和地址三个数据项。创建两个哈希表，关键字分别为姓和电话号码。哈希函数自定，比如可以将姓/电话号码部分分字符求和，然后取模得到哈希值。完善记录的插入、查找和显示功能。

阅读全文

相关推荐

C++实现散列表电话簿程序

哈希表实现电话号码查询系统

Hash表法实现散列以及再散列

二分查找和hash表的实现

hash_telbook.zip_telbook电话簿

MFC 哈希表 小电话簿 线性探测法 除留取余法

使用哈希表与链表实现电话号码查询系统

C语言实现哈希表：电话号码查询与冲突解决

基于springboot+Web的毕业设计选题系统源码数据库文档.zip

垃圾分类数据集：四大类垃圾，有害垃圾、可回收垃圾、厨余垃圾、其他垃圾，共四千张左右，包含小米电池等不寻常的垃圾

C#ASP.NET在线培训考试系统源码数据库 SQL2000源码类型 WebForm

最新推荐

C语言设计散列表实现电话号码查找系统

散列表的设计与实现设计散列表实现电话号码查找系统。

基于springboot+Web的毕业设计选题系统源码数据库文档.zip

垃圾分类数据集：四大类垃圾，有害垃圾、可回收垃圾、厨余垃圾、其他垃圾，共四千张左右，包含小米电池等不寻常的垃圾

C#ASP.NET在线培训考试系统源码数据库 SQL2000源码类型 WebForm

基于Python和Opencv的车牌识别系统实现

管理建模和仿真的文件

网络隔离与防火墙策略：防御网络威胁的终极指南

在密码学中，对称加密和非对称加密有哪些关键区别，它们各自适用于哪些场景？

我的代码小部件库：统计、MySQL操作与树结构功能

MFC 哈希表小电话簿线性探测法除留取余法