CCE13.【C++ Cont】练习题组13 静态链表专题

目录

1.B3630 排队顺序

题目

分析

代码

提交结果

2.B3631 单向链表

题目

分析

前置知识:map数组加快访问速度(简单的哈希表优化)

使用map数组的重要提醒

代码

提交结果

3.★P1160 队列安排

题目

分析

方法1:带头不循环双向链表的设计

方法2:带头循环的双向链表设计

删除元素操作

带头不循环双向链表代码

提交结果

带头循环的双向链表代码

提交结果

---

1.B3630 排队顺序

题目

https://www.luogu.com.cn/problem/B3630

题目描述

有 n(2≤n≤10^6) 个小朋友，他们的编号分别从 1 到 n。现在他们排成了一个队伍，每个小朋友只知道他后面一位小朋友的编号。现在每个小朋友把他后面是谁告诉你了，同时你还知道排在队首的是哪位小朋友，请你从前到后输出队列中每个小朋友的编号。

输入格式

第一行一个整数 n，表示小朋友的人数。

第二行 n 个整数，其中第 i 个数表示编号为 i 的小朋友后面的人的编号。如果这个数是 0，则说明这个小朋友排在最后一个。

第三行一个整数 h，表示排在第一个的小朋友的编号。

输出格式

一行 n 个整数，表示这个队伍从前到后所有小朋友的编号，用空格隔开。

输入输出样例

输入 #1

6
4 6 0 2 3 5
1

输出 #1

1 4 2 6 5 3

分析

线索:"只知道他后面一位小朋友的编号","后面"体现单向链表

本题较好考察了单链表的概念,本题没有必要创造单链表,而是直接按静态单链表去访问

代码

#include <iostream>
#include <vector>
#define endl "\n"//提高换行的运行速度 
const int N=1e6+10;
using namespace std;
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n, first, index;vector<int> arr(N);cin >> n;for (int i = 1; i <= n; i++){cin >> arr[i];}cin >> first;index = first;cout << first << " ";while (arr[index] != 0){cout<<arr[index]<<" ";index = arr[index];}return 0;
}

其实可以借用 文章的print函数

#include <iostream>
#include <vector>
using namespace std;
const int N=1e3+10;
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n,head;vector<int> next(N);cin >> n;for (int i = 1; i <= n; i++){cin >> next[i];}cin >> head;for (int i=head;i;i=next[i]){cout<<i<<" ";	} return 0;
}

提交结果

2.B3631 单向链表

题目

https://www.luogu.com.cn/problem/B3631

题目描述

实现一个数据结构，维护一张表（最初只有一个元素 1）。需要支持下面的操作，其中 x 和 yy 都是 1 到 10^6 范围内的正整数，且保证任何时间表中所有数字均不相同，操作数量不多于 10^5：

• 1 x y ：将元素 y 插入到 x 后面；
• 2 x ：询问 xx 后面的元素是什么。如果 x 是最后一个元素，则输出 0；
• 3 x：从表中删除元素 x 后面的那个元素，不改变其他元素的先后顺序。

输入格式

第一行一个整数 q 表示操作次数。

接下来 q 行，每行表示一次操作，操作具体见题目描述。

输出格式

对于每个操作 2，输出一个数字，用换行隔开。

输入输出样例

输入 #1

6
1 1 99
1 99 50
1 99 75
2 99
3 75
2 1

输出 #1

75
99

分析

这道题用单链表或顺序表都能做,但是顺序表的任意位置插入和删除时间复杂度都是,运行速度慢,而借助map数组(题目提示:且保证任何时间表中所有数字均不相同)的单链表时间复杂度为,很快!

前置知识:map数组加快访问速度(简单的哈希表优化)

一般查找链表的某个元素通常使用循环,即遍历链表,时间复杂度为,而如果借助map数组,直接访问其元素map[i],时间复杂度为,即用空间换时间

map[i]用来标记i这个元素在链表的什么位置

例如:

map数组将e数组和对应的下标建立联系

上方链表的map数组为

map[i]==-1为链表中删除的元素,其map[i]为无效值

使用map数组的重要提醒

1.存储的数值不能过大; 2.链表中不能有相同的元素;

代码

#include <iostream>
#include <vector>
#define endl "\n"
using namespace std;
const int N=1e6+10;
class List
{public:int val[N];int next[N];int map[N];//map数组加快访问速度,map[i]用来标记i这个元素在什么位置int head;int id;List(){next[0]=1;val[1]=1;next[1]=-1;head=0;id=1;map[1]=1; }void insert(int x,int y){int pos=map[x];val[++id]=y;map[y]=id;if (next[pos]==-1){//尾插next[pos]=id;next[id]=-1;}else{//头插或者中间插入next[id]=next[pos];next[pos]=id; }}void search(int x){int pos=map[x];if (next[pos]==-1)//为尾部元素 {cout<<"0"<<endl;return;}if (map[x]!=-2)cout<<val[next[pos]]<<endl;}void erase(int x){int pos=map[x];if (next[pos]!=-1){map[val[next[pos]]]=-2;next[pos]=next[next[pos]];//非尾删}}
};int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);List list;int q,op,x,y;cin>>q;while(q--){cin>>op;if (op==1){cin>>x>>y;list.insert(x,y);	}	else if (op==2){cin>>x;list.search(x);}else //op==3{cin>>x;list.erase(x);}}return 0;
}

提醒:const int N=1e6+10;如果N小了会报段错误,如下图

提交结果

3.★P1160 队列安排

题目

https://www.luogu.com.cn/problem/P1160

题目描述

一个学校里老师要将班上 N 个同学排成一列，同学被编号为 1∼N，他采取如下的方法：

1. 先将 1 号同学安排进队列，这时队列中只有他一个人；

2. 2∼N 号同学依次入列，编号为 i 的同学入列方式为：老师指定编号为 i 的同学站在编号为 1∼(i−1) 中某位同学（即之前已经入列的同学）的左边或右边；

3. 从队列中去掉 M 个同学，其他同学位置顺序不变。

在所有同学按照上述方法队列排列完毕后，老师想知道从左到右所有同学的编号。

输入格式

第一行一个整数 N，表示了有 N 个同学。

第 2∼N 行，第 i 行包含两个整数 k,p，其中 k 为小于 i 的正整数，p 为 0 或者 1。若 p 为 0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边。

第 N+1 行为一个整数 M，表示去掉的同学数目。

接下来 M 行，每行一个正整数 x，表示将 x 号同学从队列中移去，如果 x 号同学已经不在队列中则忽略这一条指令。

输出格式

一行，包含最多 N 个空格隔开的整数，表示了队列从左到右所有同学的编号。

输入输出样例

输入 #1

4
1 0
2 1
1 0
2
3
3

输出 #1

2 4 1

说明/提示

【样例解释】

将同学 2 插入至同学 1 左边，此时队列为：

2 1

将同学 3 插入至同学 2 右边，此时队列为：

2 3 1

将同学 4 插入至同学 1 左边，此时队列为：

2 3 4 1

将同学 3 从队列中移出，此时队列为：

2 4 1

同学 3 已经不在队列中，忽略最后一条指令

最终队列：

2 4 1

【数据范围】

对于 20% 的数据，1≤N≤10。

对于 40% 的数据，1≤N≤1000。

对于 100% 的数据，1<M≤N≤10^5。

分析

不要被题目迷惑,以为同学入队和出队就要使用队列,其实不然,用队列或者顺序表解的时间复杂度都为,没有链表快

其次本题要求"若 p 为 0，则表示将 i 号同学插入到 k 号同学的左边，p 为 1 则表示插入到右边",有左有右一定用双向链表(循环或不循环)

方法1:带头不循环双向链表的设计

由于学生入队的顺序是固定的,而且从2~N,显然不用专门开数组val[]来存储学生的编号,更不需要遍历指针id,从而简化代码,只需要next[]和prev[]数组和头指针head

 一开始链表只存储哨兵位和编号为1的学生

逻辑结构

(-1代表无效下标)

物理结构

上面这个表有两种看法

看法1:竖着看,相当于逻辑结构的每个节点(下标充当val数组,即节点的数据域)

看法2:横着看,为物理存储方式

方法2:带头循环的双向链表设计

删除元素操作

注意:删除某个元素x时需要用一个状态数组is_erase来看

is_erase[x]==0说明没有删除过,可以删除;删除过x后is_erase[x]==1,确保下次不再删除x

带头不循环双向链表代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n,k,p,m,x;cin>>n;vector<int> next(n+1,-1);vector<int> prev(n+1,-1);vector<int> is_erase(n+1,0);//处理头结点和编号为1的学生 next[0]=1;prev[1]=0;prev[0]=-1;next[1]=-1; for (int i=2;i<=n;i++)//i既为下标又为学生的编号 {cin>>k>>p;if (p==0)//i放在k的左边 {next[i]=k;prev[i]=prev[k];next[prev[k]]=i;prev[k]=i;	//因为一开始要访问到prev[k],所以最后修改prev[k] }	else //p==1{if (next[k]==-1){next[k]=i;//尾插单独写prev[i]=k;}else{next[i]=next[k];prev[i]=k;prev[next[k]]=i;next[k]=i;//因为一开始要访问到next[k],所以最后修改next[k] }}}cin>>m;while(m--){cin>>x;//is_erase数组用于检查x是否被删过一次了 if (!is_erase[x]){if (next[x]==-1){//尾删单独写 next[prev[x]]=-1;}else{next[prev[x]]=next[x];prev[next[x]]=prev[x];is_erase[x]=1;} }}for (int i=next[0];i!=-1;i=next[i]){cout<<i<<" ";}return 0;
}

提交结果

带头循环的双向链表代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int n, k, p, m, x;cin >> n;vector<int> next(n + 1, -1);vector<int> prev(n + 1, -1);vector<int> is_erase(n + 1, 0);next[0] = 1;prev[1] = 0;prev[0] = 1;next[1] = 0;for (int i = 2; i <= n; i++)//i既为下标又为学生的编号 {cin >> k >> p;if (p == 0)//i放在k的左边 {next[i] = k;prev[i] = prev[k];next[prev[k]] = i;prev[k] = i;	//因为一开始要访问到prev[k],所以最后修改prev[k] }else //p==1{prev[i] = k;next[i] = next[k];prev[next[k]] = i; //因为一开始要访问到next[k],所以最后修改next[k] next[k] = i; }}cin >> m;while (m--){cin >> x;//is_erase数组用于检查x是否被删过一次了 if (!is_erase[x]){//中间删next[prev[x]] = next[x];prev[next[x]] = prev[x];is_erase[x] = 1;}}for (int i = next[0]; i != 0; i = next[i]){cout << i << " ";}return 0;
}

p==0和p==1都可以等价为中间插入,头插和尾插不用区分

提交结果

可以看到两种方法明显方法2代码量较少,特殊情况不用单独判断