使用数组模拟有序(升序)链表的创建、插入和删除,题目保证没有重复元素插入链表。
时间: 2023-11-09 11:07:58 浏览: 70
C语言链表的建立、插入和删除
4星 · 用户满意度95%
可以使用数组来模拟有序(升序)链表,使用一个变量 `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;
}
```
阅读全文