使用数组模拟有序(升序)链表的创建、插入和删除,题目保证没有重复元素插入链表。

时间: 2023-11-09 11:07:58 浏览: 35
可以使用数组来模拟有序(升序)链表,使用一个变量 `head` 记录链表的头节点在数组中的索引位置,初始值为 -1 表示空链表。 创建链表:可以通过依次输入有序的元素,并按照升序插入到数组中。 插入元素:假设要插入元素 `x`,从头节点开始遍历链表,找到第一个比 `x` 大的元素的位置 `pos`,然后将元素 `x` 插入到 `pos` 前面即可。如果 `x` 大于链表中所有元素,则将 `x` 插入到链表末尾。 删除元素:假设要删除元素 `x`,从头节点开始遍历链表,找到第一个值等于 `x` 的元素的位置 `pos`,然后将元素 `pos` 删除即可。 具体实现可以参考下面的代码示例: ```c++ #include <iostream> using namespace std; const int N = 100010; int e[N], ne[N], idx; int head = -1; // 在链表的第k个节点后插入元素x void insert(int k, int x) { e[idx] = x; ne[idx] = ne[k]; ne[k] = idx++; } // 遍历链表 void traverse() { for (int i = head; i != -1; i = ne[i]) cout << e[i] << " "; cout << endl; } // 插入元素x void insert(int x) { if (head == -1 || e[head] > x) { insert(-1, x); head = idx - 1; return; } int i; for (i = head; ne[i] != -1 && e[ne[i]] <= x; i = ne[i]); insert(i, x); } // 删除元素x void remove(int x) { if (head == -1) return; if (e[head] == x) { head = ne[head]; return; } int i; for (i = head; ne[i] != -1 && e[ne[i]] != x; i = ne[i]); if (ne[i] != -1) ne[i] = ne[ne[i]]; } int main() { int n; cin >> n; while (n--) { int x; cin >> x; insert(x); } traverse(); int m; cin >> m; while (m--) { int x; cin >> x; remove(x); } traverse(); return 0; } ```

相关推荐

最新推荐

recommend-type

C语言实现带头结点的链表的创建、查找、插入、删除操作

主要介绍了C语言实现带头结点的链表的创建、查找、插入、删除操作方法,对于了解数据结构中链表的各项操作有很好的借鉴价值,需要的朋友可以参考下
recommend-type

C语言链表题目(附答案).docx

大一初学C语言时的期末作业,涉及到链表的建立和功能的实现,涉及指针、函数、动态结构建立等方面的知识,初学者可以参考参考尝试尝试哟!!!
recommend-type

PTA1025 反转数组(启发式思路)

解题思路:构建结构体数组存储数据(足够大的数组),利用数组本身的连续性将节点串接(此时非有序),然后遍历数组,按照数字地址确定链表节点的先后顺序,按先后顺序将链表节点的地址依次存入另一数组之中(此时...
recommend-type

需要系数法负荷计算软件.zip

需要系数法负荷计算软件
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

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

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

用matlab绘制高斯色噪声情况下的频率估计CRLB,其中w(n)是零均值高斯色噪声,w(n)=0.8*w(n-1)+e(n),e(n)服从零均值方差为se的高斯分布

以下是用matlab绘制高斯色噪声情况下频率估计CRLB的代码: ```matlab % 参数设置 N = 100; % 信号长度 se = 0.5; % 噪声方差 w = zeros(N,1); % 高斯色噪声 w(1) = randn(1)*sqrt(se); for n = 2:N w(n) = 0.8*w(n-1) + randn(1)*sqrt(se); end % 计算频率估计CRLB fs = 1; % 采样频率 df = 0.01; % 频率分辨率 f = 0:df:fs/2; % 频率范围 M = length(f); CRLB = zeros(M,1); for
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。
recommend-type

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依