用C语言写一个哈希函数用除留余数法构造,用线性探测再散列处理冲突,并且能够实现显示、插入、查找、删除数据的哈希表程序

时间: 2023-06-06 08:05:41 浏览: 52
Hi,您好!感谢您使用ChitGPT与我进行交流。根据您的需求,我可以提供一个用C语言编写的哈希表程序,该程序采用了除留余数法构造哈希函数,并结合了线性探测再散列处理冲突。该程序可以实现数据的插入、查找、删除和显示等操作,具体代码如下: ``` #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_KEY_LEN 20 // 关键字最大长度为20 #define MAX_DATA_LEN 40 // 数据最大长度为40 #define MAX_TABLE_SIZE 100 // 哈希表大小为100 typedef struct { char key[MAX_KEY_LEN]; char data[MAX_DATA_LEN]; } Item; Item NULL_ITEM = {"", ""}; typedef struct { Item item; int status; // 0: 空元素,1: 有元素,-1: 删除元素 } Slot; Slot hash_table[MAX_TABLE_SIZE]; // 计算字符串的哈希值,采用除留余数法 unsigned int hash(char *key) { unsigned int hash_value = 0; while (*key != '\0') { hash_value = (hash_value * 31 + *key) % MAX_TABLE_SIZE; key++; } return hash_value; } // 进行线性探测再散列 int rehash(int hash_value) { return (hash_value + 1) % MAX_TABLE_SIZE; } // 查找元素 Item *find(char *key) { int hash_value = hash(key); int i = hash_value; while (hash_table[i].status != 0) { if (hash_table[i].status == 1 && strcmp(hash_table[i].item.key, key) == 0) { return &hash_table[i].item; } i = rehash(i); if (i == hash_value) { break; } } return NULL; } // 插入元素 void insert(Item item) { if (find(item.key) != NULL) { printf("Error: Key already exists.\n"); return; } int hash_value = hash(item.key); int i = hash_value; while (hash_table[i].status == 1) { i = rehash(i); if (i == hash_value) { printf("Error: Hash table is full.\n"); return; } } hash_table[i].item = item; hash_table[i].status = 1; } // 删除元素 void delete(char *key) { Item *item = find(key); if (item == NULL) { printf("Error: Key does not exist.\n"); return; } int i = hash(key); while (strcmp(hash_table[i].item.key, key) != 0) { i = rehash(i); } hash_table[i].status = -1; printf("Item deleted.\n"); } // 显示哈希表 void display() { for (int i = 0; i < MAX_TABLE_SIZE; i++) { if (hash_table[i].status == 1) { printf("Key: %s, Data: %s\n", hash_table[i].item.key, hash_table[i].item.data); } } } int main() { memset(hash_table, 0, sizeof(hash_table)); // 插入示例数据 insert((Item){"apple", "red fruit"}); insert((Item){"banana", "yellow fruit"}); insert((Item){"cherry", "red fruit"}); insert((Item){"orange", "orange fruit"}); // 显示哈希表 display(); // 删除元素 delete("cherry"); // 显示哈希表 display(); return 0; } ``` 该程序中,哈希表采用数组实现,每个元素为一个`Slot`结构体,其中包含了一个`Item`结构体和一个`status`变量,`Item`结构体中包含了关键字和数据,`status`变量表示该元素的状态,0表示空元素,1表示有元素,-1表示删除元素。该程序中实现的哈希函数采用了除留余数法,探测方法采用了线性探测再散列。该程序中实现了插入、查找、删除和显示等操作。在删除元素时,将该元素的状态标记为-1,而不是直接将该元素从哈希表中删除,这是因为在线性探测再散列的过程中,如果当前元素被删除了,后续元素的探测路径将不够连续,导致查找失败。因此,将元素的状态标记为-1可以在探测过程中跳过已删除的元素,而不会影响后续元素的探测路径。

相关推荐

最新推荐

PA246 Earphone光感入耳检测- V2.3.pdf

PA246 Earphone光感入耳检测- V2.3.pdf GENERAL DESCRIPTION RoHS Compliant and Halogen Free ■ FEATURES Sleep Mode For ALS And PS ALS Spectral Sensitivity is Close to Human Eyes Sensitivity Smart Phone Backlight Dimming ALS with wide view angle I2C Interface Compatible Digital Camera, Digital Video Camera The PA22A00001 provides digital ambient light sensing, IR Light Source with lighting driver and proximity detector in a 2.55mm x 2.05mm 6 pin package (MSL3). For ambient light sensing, the spectral sens

AQuery-0.0.2-py3-none-any.whl.zip

AQuery-0.0.2-py3-none-any.whl.zip

aps011_sources_of_error_in_twr.pdf

aps011_sources_of_error_in_twr.pdf

mysql-libs.rar

mysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rarmysql-libs.rar

编程语言+JAVAspring+IoC容器+依赖注入

编程语言+JAVAspring+IoC容器+依赖注入**:这是一个关于JAVAspring编程语言的IoC容器的依赖注入的资源,适合有一定JAVAspring基础的开发者。它介绍了JAVAspring的IoC容器的概念、原理和作用,以及如何使用JAVAspring的IoC容器来实现依赖注入,包括设值注入和构造注入的方式,以及一些配置文件和注解的用法。

MIL_STD_1364J.537.pdf

MIL_STD_1364J.537.pdf

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire

粒子群多目标算法matlab代码【MATLAB代码实现】定义优化问题参数

# 1. 粒子群多目标算法简介 ## 1.1 什么是粒子群算法? 粒子群算法是一种基于群体智能的优化算法,灵感来源于鸟群或鱼群等生物群体的行为。每个“粒子”代表问题空间中的一个候选解,而整个粒子群代表了候选解的一个群体。粒子在解空间中搜索最优解,通过个体的经验和群体的协作来不断调整自身位置和速度,从而逐步靠近最优解。 ## 1.2 粒子群算法在多目标优化中的应用 粒子群算法最初是针对单目标优化问题提出的,但后来被扩展应用到了多目标优化领域。与单目标优化不同,多目标优化需要考虑多个冲突的目标函数,因此粒子群算法的应用在多目标优化中具有一定的挑战性。 ## 1.3 粒子群多目标算法原理解

hbase中时间戳的精确度和hbase中列族和列名的分隔符是什么

我已经回答了关于HBase中时间戳的精确度的问题,现在回答你的第二个问题: 在HBase中,列族和列名的分隔符是冒号(:)。例如,如果你有一个列族为“info”,列名为“name”的列,那么在HBase中的完整列名将是“info:name”。这个分隔符是在HBase的设计中被硬编码的,不能更改。这个分隔符在HBase的API中也得到了体现,例如在Java API中,可以使用“:`”来将列族和列名分隔开来,如下所示: ```java Get get = new Get(Bytes.toBytes("rowkey")); get.addColumn(Bytes.toBytes("info"),

spring boot应用启动原理分析.docx

spring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docxspring boot应用启动原理分析.docx