【洛谷】用两个数组实现静态单链表、静态双向链表，排队顺序

---

链表的静态实现

动态实现是通过 new 申请结点，然后通过 delete 释放结点的形式构造链表。这种实现⽅式最能体现链表的特性；
静态实现是利⽤两个数组配合来模拟链表。第⼀次接触可能⽐较抽象，但是它的运⾏速度很快，在算法竞赛中会经常会使⽤到，虽然空间消耗大，但是算法竞赛中时间效率更重要

单链表的模拟实现

我们要把数组同一下标的两个数据打包看成一个整体，用来存储链表的其中一个结点的信息。这个next数组的作用就是用来模拟list的指定位置O1插入删除，比如下面我们想在B、C结点之间插入一个C，如果只用elem一个数组的话就需要挪动数据，但是如果有next数组的话我们就可以将D直接尾插，然后通过修改next数组的数据达到和list一样的效果。
静态单链表的尾插、尾删、任意位置插入删除操作时间复杂度太高，我们就不实现了，因为这里实现静态单链表的目的就是看中了它效率高，所以这里我们实现一部分效率高的操作。

定义单链表

const int N = 1e5 + 10;
int e[N], ne[N], h, id;

e[N]为存放数据的数组，ne[N]为存放指针也就是指向下一数据下标的数组，若对应数据的ne[N]数组的值为零，则代表该位置为尾结点，h一直指向头结点，id跟随插入的数据而移动，它们俩的值默认为0，所以直接把它们定义在全局就不用初始化了，全局int变量定义在全局默认为0。

头插

void push_front(int x)
{id++;//放入数据e[id] = x;//修改指针ne[id] = ne[h];  //新节点指向原头结点ne[h] = id;      //哨兵位指向新头结点
}

insert

//pos后插入
void insert(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[pos];ne[pos] = id;
}

insert只能从指定位置后面插入，也就是物理结构的数组下标位置pos，不能在某个值后面插入，因为拿到某个值后也要通过这个值去找对应的下标才能实现插入操作。

erase

删除操作也很简单，把当前位置结点指向的下标改为当前位置的下一位置的结点指向的下标就行了，但是要注意当pos结点是尾结点时不能删除，因为会造成两个结点指向同一个结点，形成环形链表。
删除操作的pos也是物理结构的数组下标位置pos。

//删除pos位置之后的数据
void erase(int pos)
{//当pos位置结点不是单链表的尾结点时才能执行删除操作if(ne[pos])ne[pos] = ne[ne[pos]];
}

打印链表

void print()
{for (int i = ne[h]; i; i = ne[i]){cout << e[i] << " ";}cout << endl;
}

i从头结点开始遍历打印，当i为0即i指向哨兵位时停止循环打印。

查找

法一：

这里查找数据一定要按链表的逻辑顺序来查找，不能直接遍历e[N]数组，因为e[N]数组里有可能会存在我们已经删除了的元素。

int find(int x)
{for (int i = ne[h]; i; i = ne[i]){if (x == e[i]){return i;}}return 0;
}

法二：

首先创建一个数组mp，登记数据存储的位置到mp,方便find直接通过数据的值return它的下标,然后在每次插入数据时把值登记到mo数组，因为数组是在全局创建的，会自动把mp数组的值初始化为0，那么如果find的目标值不存在就会返回0。

int mp[N];   //把数据的值当作mp数组的下标，mp存的值为数据的下标void push_front(int x)
{id++;//放入数据e[id] = x;mp[x] = id;      //登记数据存储的位置到mp,方便直接return//修改指针ne[id] = ne[h];  //新节点指向原头结点ne[h] = id;      //哨兵位指向新头结点
}int find(int x)
{return mp[x];
}

单链表源码

using namespace std;
#include <iostream>const int N = 1e5;
int e[N], ne[N], h, id;
int mp[N];   //把数据的值当作mp数组的下标，mp存的值为数据的下标void push_front(int x)
{id++;//放入数据e[id] = x;mp[x] = id;//修改指针ne[id] = ne[h];  //新节点指向原头结点ne[h] = id;      //哨兵位指向新头结点
}void print()
{for (int i = ne[h]; i; i = ne[i]){cout << e[i] << " ";}cout << endl;
}//int find(int x)
//{
//	for (int i = ne[h]; i; i = ne[i])
//	{
//		if (x == e[i])
//		{
//			return i;
//		}
//	}
//	return 0;
//}int find(int x)
{return mp[x];
}//pos后插入
void insert(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[pos];ne[pos] = id;
}//删除pos位置之后的数据
void erase(int pos)
{//当pos位置结点不是单链表的尾结点时才能执行删除操作if (ne[pos] != 0){   //清空mp里pos下一个位置的值mp[e[ne[pos]]] = 0;ne[pos] = ne[ne[pos]];}
}int main()
{push_front(3);push_front(2);push_front(1);print();push_front(7);print();push_front(8);print();push_front(9);print();cout << find(1) << endl;cout << find(9) << endl;cout << find(4) << endl;insert(5, 100);print();insert(1, 200);print();erase(1);print();erase(5);print();//push_front(1);//push_front(2);//push_front(3);//push_front(4);//push_front(5);//print();//erase(1);//   print();//   erase(4);//   print();return 0;
}

双向链表的模拟实现

定义双向链表

const int N = 1e5;
int e[N], ne[N], pre[N], id, h;

头插

注意：指针1最后修改。

void push_front(int x)
{id++;e[id] = x;ne[id] = ne[h];pre[id] = h;pre[ne[h]] = id;ne[h] = id;
}

任意位置之后插入

这里这是在物理存储位置的下标插入。

//pos之后插入
void insert(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[pos];pre[id] = pos;pre[ne[pos]] = id;ne[pos] = id;
}

任意位置之前插入

注意插入删除都要登记mp。

//pos之前插入
void insert_back(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = pos;pre[id] = pre[pos];ne[pre[pos]] = id;pre[pos] = id;
}

erase

注意插入删除都要登记mp。

//删除任意位置元素
void erase(int pos)
{mp[e[pos]] = 0;ne[pre[pos]] = ne[pos];pre[ne[pos]] = pre[pos];
}

打印链表

void print()
{for (int i = ne[h]; i; i = ne[i]){cout << e[i] << " ";}cout << endl; 
}

find

这里为了效率更高，我们就用创建mp数组的方法了。

int mp[N];void push_front(int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[h];pre[id] = h;pre[ne[h]] = id;ne[h] = id;
}int find(int x)
{return mp[x];
}

双向链表源码

using namespace std;
#include <iostream>const int N = 1e5 + 10;
int e[N], ne[N], pre[N], id, h;
int mp[N];void push_front(int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[h];pre[id] = h;pre[ne[h]] = id;ne[h] = id;
}//pos之后插入
void insert(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = ne[pos];pre[id] = pos;pre[ne[pos]] = id;ne[pos] = id;
}//pos之前插入
void insert_back(int pos, int x)
{id++;e[id] = x;mp[x] = id;ne[id] = pos;pre[id] = pre[pos];ne[pre[pos]] = id;pre[pos] = id;
}//删除任意位置元素
void erase(int pos)
{mp[e[pos]] = 0;ne[pre[pos]] = ne[pos];pre[ne[pos]] = pre[pos];
}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(5);print();push_front(6);print();push_front(7);print();push_front(8);print();push_front(9);print();cout << find(7) << endl;cout << find(9) << endl;cout << find(10) << endl;insert(2, 100);print();insert(1, 200);print();insert(1, 500);print();insert(4, 300);print();insert_back(5, 800);print();insert_back(3, 900);print();erase(3);print();erase(5);print();return 0;
}

循环链表

我们之前的单链表最后的尾结点的指向0也就是指向哨兵位的，所以先前的单链表其实就是一个循环链表，嘻嘻，所以循环链表就不用实现啦！

排队顺序

题目描述

题目解析

这道题很好理解，我们可以用数组模拟链表实现，首先我们把第二行数据用一个vector来保存，注意从下标1开始保存，这样可以让小朋友的编号与下标对应，保存好后用一个for循环按找链表顺序输出结果就行了，i为输出的小朋友的编号，首先输出第一个小朋友的编号，这个输出的小朋友的编号就是下一个要输出小朋友编号在数组里的下标，最后当编号为0时跳出循环。

代码

using namespace std;
#include <iostream>
#include <vector>
#include <list>
const int N = 2e6 + 10;
vector<int> v(N);int main()
{	
int n, h;	
cin >> n;	
for (int i = 1; i <= n; i++)	
{		
cin >> v[i];	
}
cin >> h;		
//若i为1跳出循环	
for (int i = h; i; i = v[i])	
{		
cout << i << " ";	
}return 0;
}

以上就是小编分享的全部内容了，如果觉得不错还请留下免费的关注和收藏如果有建议欢迎通过评论区或私信留言，感谢您的大力支持。
一键三连好运连连哦~~