C++ 模拟散列表 || 哈希表存储与查询,模版题(拉链法)

2024-01-09 13:36

本文主要是介绍C++ 模拟散列表 || 哈希表存储与查询,模版题(拉链法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

维护一个集合,支持如下几种操作:

I x,插入一个整数 x

Q x,询问整数 x
是否在集合中出现过;
现在要进行 N
次操作,对于每个询问操作输出对应的结果。

输入格式
第一行包含整数 N
,表示操作数量。

接下来 N
行,每行包含一个操作指令,操作指令为 I x,Q x 中的一种。

输出格式
对于每个询问指令 Q x,输出一个询问结果,如果 x
在集合中出现过,则输出 Yes,否则输出 No。

每个结果占一行。

数据范围
1≤N≤105

−109≤x≤109
输入样例:
5
I 1
I 2
I 3
Q 2
Q 5

#include <iostream>
#include <cstring>using namespace std;const int N = 100003;int n;
int h[N], e[N], ne[N], idx; 
//h是哈希表(头结点数组)、e是元素数组、ne是链表中下一个元素的索引
/*h 数组是哈希表的数组,每个元素表示一个桶。
h[k] 存储的是第 k 个桶的头结点,即链表中第一个元素的索引。(存的拉链的头结点的下标)
e 数组存储具体的元素值,每个元素值对应一个索引。
ne 数组存储链表中每个元素的下一个元素的索引。
idx 是当前要插入的元素的索引。*/void insert(int x)
{// 计算哈希值,使用取模运算防止越界int k = (x % N + N) % N; // x % N x是负数的话保证这个哈希函数映射一定是正数// 插入到哈希表中,使用链地址法处理哈希冲突e[idx] = x;ne[idx] = h[k];h[k] = idx ++;
}bool find(int x)
{int k = (x % N + N) % N;for(int i = h[k]; i != -1; i = ne[i] ){if(e[i] == x) return true;}return false;
}int main()
{scanf("%d", &n);memset(h, -1, sizeof h);// 初始化哈希表的头结点为 -1,表示空链表while(n -- ){char op[2];int x;scanf("%s%d", op, &x);if(op[0] == 'I'){insert(x);}else{if(find(x)) printf("Yes\n");else printf("No\n");}}return 0;
}

这篇关于C++ 模拟散列表 || 哈希表存储与查询,模版题(拉链法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/587293

相关文章

Oracle查询表结构建表语句索引等方式

《Oracle查询表结构建表语句索引等方式》使用USER_TAB_COLUMNS查询表结构可避免系统隐藏字段(如LISTUSER的CLOB与VARCHAR2同名字段),这些字段可能为dbms_lob.... 目录oracle查询表结构建表语句索引1.用“USER_TAB_COLUMNS”查询表结构2.用“a

java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)

《java中pdf模版填充表单踩坑实战记录(itextPdf、openPdf、pdfbox)》:本文主要介绍java中pdf模版填充表单踩坑的相关资料,OpenPDF、iText、PDFBox是三... 目录准备Pdf模版方法1:itextpdf7填充表单(1)加入依赖(2)代码(3)遇到的问题方法2:pd

python中列表应用和扩展性实用详解

《python中列表应用和扩展性实用详解》文章介绍了Python列表的核心特性:有序数据集合,用[]定义,元素类型可不同,支持迭代、循环、切片,可执行增删改查、排序、推导式及嵌套操作,是常用的数据处理... 目录1、列表定义2、格式3、列表是可迭代对象4、列表的常见操作总结1、列表定义是处理一组有序项目的

python运用requests模拟浏览器发送请求过程

《python运用requests模拟浏览器发送请求过程》模拟浏览器请求可选用requests处理静态内容,selenium应对动态页面,playwright支持高级自动化,设置代理和超时参数,根据需... 目录使用requests库模拟浏览器请求使用selenium自动化浏览器操作使用playwright

C++11范围for初始化列表auto decltype详解

《C++11范围for初始化列表autodecltype详解》C++11引入auto类型推导、decltype类型推断、统一列表初始化、范围for循环及智能指针,提升代码简洁性、类型安全与资源管理效... 目录C++11新特性1. 自动类型推导auto1.1 基本语法2. decltype3. 列表初始化3

解密SQL查询语句执行的过程

《解密SQL查询语句执行的过程》文章讲解了SQL语句的执行流程,涵盖解析、优化、执行三个核心阶段,并介绍执行计划查看方法EXPLAIN,同时提出性能优化技巧如合理使用索引、避免SELECT*、JOIN... 目录1. SQL语句的基本结构2. SQL语句的执行过程3. SQL语句的执行计划4. 常见的性能优

C++11右值引用与Lambda表达式的使用

《C++11右值引用与Lambda表达式的使用》C++11引入右值引用,实现移动语义提升性能,支持资源转移与完美转发;同时引入Lambda表达式,简化匿名函数定义,通过捕获列表和参数列表灵活处理变量... 目录C++11新特性右值引用和移动语义左值 / 右值常见的左值和右值移动语义移动构造函数移动复制运算符

Linux系统中查询JDK安装目录的几种常用方法

《Linux系统中查询JDK安装目录的几种常用方法》:本文主要介绍Linux系统中查询JDK安装目录的几种常用方法,方法分别是通过update-alternatives、Java命令、环境变量及目... 目录方法 1:通过update-alternatives查询(推荐)方法 2:检查所有已安装的 JDK方

C++中detach的作用、使用场景及注意事项

《C++中detach的作用、使用场景及注意事项》关于C++中的detach,它主要涉及多线程编程中的线程管理,理解detach的作用、使用场景以及注意事项,对于写出高效、安全的多线程程序至关重要,下... 目录一、什么是join()?它的作用是什么?类比一下:二、join()的作用总结三、join()怎么

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口