蓝桥备赛（13）- 链表和 list（上）
目录
一、模拟题：
二 、 链表的概念
1.1 链表的定义
1.2 链表的分类
三、链表的模拟实现
3.1 单链表的模拟实现
3.1.1 实现方式
3.1.2 定义
3.1.3 头插
3.1.4 遍历链表
3.1.5 按值查找
3.1.6 在任意位置之后插入元素
3.1.7 删除任意位置之后的元素
3.1.8 遗留问题
2.1.9 所有测试代码
3.2 双向链表的模拟实现
3.2.1 实现方式
3.2.2 定义
3.2.3 头插
3.2.4 遍历链表
3.2.5 按值查找
3.2.6 在任意位置之后插入元素
3.2.7 在任意位置之前插入元素
3.2.8 删除任意位置的元素
2.1.9 所有测试代码
3.3 循环链表的实现
一、模拟题：
在开始之前：先来看一道提升题 --> The Blocks Problem
UVA101 The Blocks Problem - 洛谷
这道题本质上是一道模拟题 ， 模拟题目所需要的流程；
1） 看到题目我们首先就会想到 ， 用4 个 if 语句 ， 对这4个指令进行 匹配 ， 然后执行
2 ） 但是 ， 其实只有两种操作 ， 分别是 归位 和 移动
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 30;
vector<int> p[N];
int n;
PII find(int x)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < p[i].size(); j++)
{
if (p[i][j] == x)
{
return { i,j };
}
}
}
}
//归位
void clean(int x, int y)
{
//把[x , y ] 上方的木块归位
for (int j = y + 1; j < p[x].size(); j++)
{
int t = p[x][j];
p[t].push_back(t);
}
p[x].resize(y + 1);
}
//移动
void move(int x1, int y1, int x2)
{
//把 [ x1 , y1 ] 以及以上的木块放在x2上
for (int j = y1; j < p[x1].size(); j++)
{
p[x2].push_back(p[x1][j]);
}
p[x1].resize(y1);
}
int main()
{
cin >> n;
//初始化
for (int i = 0; i < n; i++)
{
p[i].push_back(i);
}
string op1, op2;
int a, b;
while (cin >> op1 >> a >> op2 >> b)
{
//查找 a 和 b 的位置
PII pa = find(a);
int x1 = pa.first, y1 = pa.second;
PII pb = find(b);
int x2 = pb.first, y2 = pb.second;
//执行
if (x1 == x2)continue; // 操作不合法
if (op1 == "move")//把 a 上方归位
{
clean(x1, y1);
}
if (op2 == "onto") //把 b 上方归位
{
clean(x2, y2);
}
//移动
move(x1, y1, x2);
}
//打印
for (int i = 0; i < n; i++)
{
cout << i << ":";
for (int j = 0; j < p[i].size(); j++)
{
cout << " " << p[i][j];
}
cout << endl;
}
return 0;
}
这道题是洛谷从UVa这个外国的OJ平台收录的题目 ，
在提交的答案的时候回显示需要到UVa 里去提交 ；
在Vitrual Judge 平台显示这个，就表示AC了
Problems - Virtual Judge
二 、 链表的概念
1.1 链表的定义
链表 : 用 链式存储 实现的线性表
1.2 链表的分类
把各种类型的链表排列组合 ， 总共有 8 种不同链表的结构：
虽然链表种类较多 ， 我们只需要掌握 单向链表 ， 双向链表 和循环链表即可 。
三、链表的模拟实现
3.1 单链表的模拟实现
3.1.1 实现方式
1） 动态实现 ： 通过 new 申请结点 ，然后通过 delete 释放结点 。 这种实现方式最能体现链表的特性 ， 代码也很清晰 。 但是频繁的调用 new 和 delete 会有很大的时间开销。
2）静态实现 ： 利用两个数组配合模拟链表 。（重点）
可能还是不怎么理解这里，那么我们看一下下面的题目：还原一下逻辑结构
3.1.2 定义
1） 两个足够大的数组 ， 一个用来存储数据 ， 一个用来存下一个结点的位置
2）变量 h ，充当头指针 ， 来表示头结点的位置
3 ） 变量 id , 为新插入结点的位置
#include <iostream>
#include <cstdio>
const int N = 1e5 + 10;
//创建数组
int e[N] , ne[N] , h , id;
int main()
{
return 0;
}3.1.3 头插
在链表的头部插入一个元素
----> 放在有效数据的前面 ， 即哨兵位的后面
时间复杂度：O（1）
//头插
void push_front(int x)
{
//把x 放在 e[N]中
id++;
e[id] = x;
//修改指针
//1.新结点指向下一个结点的位置
ne[id] = ne[h];
//2.头结点指向新结点
ne[h] = id;
}3.1.4 遍历链表
时间复杂度：O（n）
通过指针 ， 访问链表中的所有元素
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
//创建数组
int e[N] , ne[N] , h , id;
//头插
void push_front(int x)
{
//把x 放在 e[N]中
id++;
e[id] = x;
//修改指针
//1.新结点指向下一个结点的位置
ne[id] = ne[h];
//2.头结点指向新结点
ne[h] = id;
}
//遍历链表
void print()
{
//从第一个有效结点开始遍历
int i = ne[h];
//遇到空指针结束
while(i != 0)
{
cout << e[i] << " ";
//i 不断向后移动
i = ne[i];
}
cout << endl << endl;
}
int main()
{
push_front(1);
push_front(2);
push_front(3);
push_front(4);
//4 3 2 1
print();
return 0;
}3.1.5 按值查找
查询链表中是否存在元素x , 如果存在 ， 返回下标 ， 不存在 ， 返回0 或者 -1
方法一：遍历整个链表
时间复杂度：O（n)
//方法一：遍历整个链表
int find(int x)
{
for(int i = ne[h] ; i ; i= ne[i])
{
if(e[i] == x)
return i;
}
return 0;
}
方法二：标记数组法
时间复杂度：O（1）
3.1.6 在任意位置之后插入元素
在存储位置之后插入数据 ， 插入新的元素 x
时间复杂度：O（1）
1) id++ , 标记新结点的位置 ；同时存储新结点的位置
2）修改新结点的指针域 ， 让其指向 p 的下一个位置
3）最后让 p 指向 新结点
//在任意位置之后插入元素
void insert(int p , int x) //这里 p 是位置
{
id++;
e[id] = x;
ne[id] = ne[p];
ne[p] = id;
}
3.1.7 删除任意位置之后的元素
删除存储位置 p 之后的元素
时间复杂度为O（1）
1） 直接让 p 指向下一个元素的下一个元素即可
ne[p] = ne[ne[p]]
// 删除任意位置之后的元素
void erase(int p)
{
if(ne[p])
{
mp[e[ne[p]]] = 0;//将p后面的元素从 mp 中删除
ne[p] = ne[ne[p]];//指向下一个元素的下一个元素
}
} 3.1.8 遗留问题
单链表为什么不实现尾插 、 尾删 、 删除任意位置元素等操作？
1） 能实现 ， 但是没必要 ， 因为时间复杂度是O（N）级别的 ， 竞赛中不怎么用
2）使用数据结构是为了方便我们解决问题的 ， 而不是添堵的
2.1.9 所有测试代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
//创建数组
int e[N] , ne[N] , h , id;
int mp[N];
//头插
void push_front(int x)
{
//把x 放在 e[N]中
id++;
e[id] = x;
mp[x] = id;//标记x 存储的为位置
//修改指针
//1.新结点指向下一个结点的位置
ne[id] = ne[h];
//2.头结点指向新结点
ne[h] = id;
}
//遍历链表
void print()
{
//从第一个有效结点开始遍历
int i = ne[h];
//遇到空指针结束
while(i != 0)
{
cout << e[i] << " ";
//i 不断向后移动
i = ne[i];
}
cout << endl << endl;
}
//按值查找
//方法一：遍历整个链表
int find(int x)
{
// for(int i = ne[h] ; i ; i= ne[i])
// {
// if(e[i] == x)
// return i;
// }
// return 0;
return mp[x];
}
//在任意位置之后插入元素
void insert(int p , int x) //这里 p 是位置
{
id++;
e[id] = x;
ne[id] = ne[p];
ne[p] = id;
}
// 删除任意位置之后的元素
void erase(int p)
{
if(ne[p])
{
mp[e[ne[p]]] = 0;//将p后面的元素从 mp 中删除
ne[p] = ne[ne[p]];//指向下一个元素的下一个元素
}
}
int main()
{
push_front(1);
push_front(2);
push_front(3);
push_front(4);
//4 3 2 1
print();
// cout << find(4) << endl;
// cout << find(2) << endl;
// cout << find(99) << endl;
insert(1,10);
print();
//4 3 2 1 10
insert(4,99);
print();
//4 99 3 10 2 1
return 0;
}3.2 双向链表的模拟实现
3.2.1 实现方式
依旧采用静态实现的方式 。
双向链表无非就是在单链表的基础上加上一个 指向前驱的指针 ， 那就再来一个数组 充当前驱的指针域即可 。
3.2.2 定义
const int N = 1e5 + 10;
int id;
int h; // 头结点
int pre[N] , ne[N] , e[N];//前后指针域 数据域
int mp[N];
int main()
{
return 0;
}3.2.3 头插
时间复杂度为 O（1）
1） id++ , 标记新结点存储位置 ； 把 新的元素存储起来 : e[id[ = x
2) 修改新结点的前驱指针 ， 让其指向哨兵位：pre[id] = h
3) 修改新结点的后继指针 ， 让其指向哨兵位的下一个位置 : ne[id] = ne[h]
4) 修改 y 结点的前驱指针 ， 让其指向新的结点：pre[ne[h]] = id
5) 修改哨兵位的后继指针 ， 让其指向新的结点：ne[h] = id
//头插
void push_front(int x)
{
id++;
e[id] = x;
mp[x] = id; // 存一下x这个元素的位置
pre[id] = h;
ne[id] = ne[h];
pre[ne[h]] = id;
ne[h] = id;
} 3.2.4 遍历链表
同单链表的遍历方式一样
时间复杂度：O（N）
//遍历链表
void print()
{
for(int i = ne[h] ; i ; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl;
} 3.2.5 按值查找
时间复杂度：O（1）
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int id;
int h; // 头结点
int pre[N] , ne[N] , e[N];//前后指针域 数据域
int mp[N];
//头插
void push_front(int x)
{
id++;
e[id] = x;
mp[x] = id; // 存一下x这个元素的位置
pre[id] = h;
ne[id] = ne[h];
pre[ne[h]] = id;
ne[h] = id;
}
//遍历链表
void print()
{
for(int i = ne[h] ; i ; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl;
}
//按值查找
int find(int x)
{
return mp[x];
}
int main()
{
push_front(1);
push_front(2);
push_front(3);
push_front(4);
//4 3 2 1
print();
cout << find(3) << endl;
cout << find(0) << endl;
cout << find(1) << endl;
return 0;
}3.2.6 在任意位置之后插入元素
时间复杂度：O（1）
与头插操作类似 ， 只是是在 存储位置 p 之后插入元素
//在任意位置之后插入元素
void push_back(int p ,int x)
{
id++;
e[id] = x;
mp[x] = id;
//先左指向p , 右指向 p 的后继
pre[id] = p;
ne[id] = ne[p];
//再让p 的后继的左指针指向id
//p的右指针指向 id
pre[ne[p]] = id;
ne[p] = id;
} 3.2.7 在任意位置之前插入元素
时间复杂度：O（1）
//在任意位置之前插入元素
void push_front(int p,int x)
{
id++;
e[id] = x;
mp[x] = id;
pre[id] = pre[p];
ne[id] = p;
ne[pre[p]] = id;
pre[p] = id;
}3.2.8 删除任意位置的元素
时间复杂度：O（1）
//删除任意位置的元素
int rease(int p)
{
mp[e[p]] = 0;//从标记这里删除
ne[pre[p]] = ne[p];
pre[ne[p]] = pre[p];
}2.1.9 所有测试代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
int id;
int h; // 头结点
int pre[N] , ne[N] , e[N];//前后指针域 数据域
int mp[N];
//头插
void push_front(int x)
{
id++;
e[id] = x;
mp[x] = id; // 存一下x这个元素的位置
pre[id] = h;
ne[id] = ne[h];
pre[ne[h]] = id;
ne[h] = id;
}
//遍历链表
void print()
{
for(int i = ne[h] ; i ; i = ne[i])
{
cout << e[i] << " ";
}
cout << endl;
}
//按值查找
int find(int x)
{
return mp[x];
}
//在任意位置之后插入元素
void insert_back(int p ,int x)
{
id++;
e[id] = x;
mp[x] = id;
//先左指向p , 右指向 p 的后继
pre[id] = p;
ne[id] = ne[p];
//再让p 的后继的左指针指向id
//p的右指针指向 id
pre[ne[p]] = id;
ne[p] = id;
}
//在任意位置之前插入元素
void insert_front(int p,int x)
{
id++;
e[id] = x;
mp[x] = id;
pre[id] = pre[p];
ne[id] = p;
ne[pre[p]] = id;
pre[p] = id;
}
//删除任意位置的元素
int erase(int p)
{
mp[e[p]] = 0;//从标记这里删除
ne[pre[p]] = ne[p];
pre[ne[p]] = pre[p];
}
int main()
{
push_front(1);
push_front(2);
push_front(3);
push_front(4);
//4 3 2 1
print();
cout << find(3) << endl;
cout << find(0) << endl;
cout << find(1) << endl;
insert_back(2,5);
//4 3 2 5 1
print();
insert_back(0,99);
//99 4 3 2 5 1
print();
insert_front(4,55);
//99 55 4 3 2 5 1
print();
erase(4);
print();
return 0;
}3.3 循环链表的实现
回看之前实现的带头单向链表 。
定义 0 表示空指针 ， 其实哨兵位就在 0 的位置 ， 所有的结构正好成环。
循环聊表就是再原有的基础上 ， 让最后一个元素指向表头即可 。