【基础数据结构】 学习笔记

数据结构是组织数据的结构，用来方便我们的操作。

数组是一种简单的数据结构（顺序存储结构的线性表）。

栈

例$1$：

大清洗期间，小明每天都要洗盘子，盘子总是堆成一堆，已知：

• 小明总是取出最顶端的盘子，拿去洗。

• 其他人总是把需要清洗的盘子放在最顶端。

问：“放进盘子$1$，放进盘子$2$，清洗，放进盘子$3$，放进盘子$4$，清洗，清洗，放进盘子$5$，清洗，清洗”这一连串动作中，盘子清洗的顺序是什么？

答案是：$2->4->3->5->1$

可以注意到，我们永远是在顶端操作。在顶端加入，在顶端拿出。他带来了一个特性：后进先出。对于所有的$a,b$都有：若$a$比$b$晚进入，那么$a$比$b$先出去。

生活中有大量遵循“后进先出”规则的结构，我们将之抽象为栈。

栈$(stack)$支持如下操作：

• 查询栈顶

• 弹出栈顶（去掉）

• 向顶部压入元素（添加）

我们可以用一个图像（代码）来表示栈内的变化：

#include<bits/stdc++.h>
using namespace std;
int s[100005],tot;
int top(){//查询栈顶
	return s[tot];
}
void push(int x){//向顶部压入元素（添加）
	tot++;
	s[tot]=x;
}
void pop(){//弹出栈顶（去掉）
	tot--;
}
void debug(){//输出每一步栈内的值，便于检查 
	cout<<"["<<tot<<"] ";
	for(int i=0;i<tot;i++){
		cout<<s[i]<<" ";
	}cout<<endl;
}
int main(){
	debug();
	push(1);//放进盘子1
	debug();
	push(2);//放进盘子2
	debug();
	pop();//清洗
	debug();
	push(3);//放进盘子3
	debug();
	push(4);//放进盘子4
	debug();
	pop();//清洗
	debug();
	pop();//清洗
	debug();
	push(5);//放进盘子5
	debug();
	pop();//清洗
	debug();
	pop();//清洗
	debug();
    return 0; 
}

输出为：

[0]
[1] 0
[2] 0 1
[1] 0
[2] 0 1
[3] 0 1 3
[2] 0 1
[1] 0
[2] 0 1
[1] 0
[0]

如果不理解的话，也可以观察一下代码，找找规律。

当然，我们用$STL$也能做，但是$STL$相当于一个有进无出的黑盒子，它只能输出$top$（栈顶）的值。

代码：

#include<bits/stdc++.h>
using namespace std;
int tot;

stack<int>s;//STL的神奇做法，stack 

int main(){
	s.push(1);cout<<"top="<<s.top()<<endl;
	s.push(2);cout<<"top="<<s.top()<<endl;
	s.pop();cout<<"top="<<s.top()<<endl;
	s.push(3);cout<<"top="<<s.top()<<endl;
	s.push(4);cout<<"top="<<s.top()<<endl;
	s.pop();cout<<"top="<<s.top()<<endl;
	s.pop();cout<<"top="<<s.top()<<endl;
	s.push(5);cout<<"top="<<s.top()<<endl;
	s.pop();cout<<"top="<<s.top()<<endl;
	s.pop();cout<<"top="<<s.top()<<endl;//每一次输出它的栈顶值
    return 0; 
}

输出为：

top=1
tpo=2
top=1
top=3
top=4
top=3
top=1
top=5
top=1

但是发现，在程序输出后，会出现问题，例如：

Dev-C++：xxx.exe已停止工作
VS:Segmentation fault

这是因为当我们执行了九次之后，第十次时，$s.top$是空的，系统因为这个而报错，所以，可以把最后一次输出去掉。

栈里面的元素越多，栈的空间就越大。

单调栈：由于上文中的栈永远单调递减，故称为“单调栈”。复杂度$O(n)$，因为栈里的每个元素最多入栈一次，出栈一次。

例$2$：P5788 【模板】单调栈

#include<bits/stdc++.h>
using namespace std;
int a[3000005],ans[3000005],n;//a是需要判断的数组（即输入的数组），ans是存储答案的数组
inline int read(){//快读
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void inp(){//输入
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
}
stack<int>s;
void work(){
	for(int i=n;i>=1;i--){
		while(!s.empty()&&a[s.top()]<=a[i]){
			s.pop();//弹出栈顶比当前数小的
		}
		if(s.empty()){
		    ans[i]=0;
	    }else{
	    	ans[i]=s.top();
    	}
		s.push(i);//压入当前元素
	}
	for(int i=1;i<=n;i++){
		printf("%d ",ans[i]);
	}
}
int main(){
	inp();
	work();
	return 0; 
}

这道题如果用$STL$写的话，运气好的可以得$90$分，运气差的只能得$60$分，但如果加上了快读，就没有什么问题啦。当然，还可以手写单调栈。

• 如果说它找到了比矮的人还高的另外一个人并且不是最后一个，那么将那个矮的人弹掉，毕竟后面也不会有人看到它了，因为如果看到它的话那么必定可以看到比它前面的还比它高的。所以我们可以从最后一个开始入单调栈。

#include<bits/stdc++.h>
using namespace std;
int n,a[3000005],q[3000005],r,f[3000005];
//定义变量，其中a数组表示输入的数，q数组表示存下标的单调栈，f数组是存结果。
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int main() {
	n=read();
	for(int i=1;i<=n;i++){
	    a[i]=read();
    }
   //上面是读入。
	for (int i=n;i>=1;i--){
		while (a[i]>=a[q[r]]&&r>0){
		    r--;	
		}
		f[i]=q[r];
		q[++r]=i;//入栈。
	}
	for(int i=1;i<=n;i++){
	    printf("%d ",f[i]);//最后正向输出
    }
	return 0;
}

经测试得出，好像不论$STL$还是手打， 都会$TLE$。所以，还是加快读保险一点。

• 到这里，我们栈的学习就先告一段落。

队列

现在有一群人排队打饭，每次加入的人都是在队尾，每次取出的人都是在队首。我们把这种队伍抽象为数据结构的队列。

先入先出：队列符合先入先出的结构，越早进入队列的，越早排完队出去。对于所有的$a,b$均有：若$a$比$b$早进入队列，那么$a$比$b$早出去。

队列提供以下操作：

• 查询队首
• 弹出队首
• 向尾部压入元素

可以定义一个数组来保存元素，用$fnt,end$分别记录头指针，尾指针。

int q[10005];
int fnt=1,end;

#define front (q[fnt])
#define pop (fnt++)
#define push(x) (q[++end]=(x))

但是，这样的话，q[fnt]之前所有的空间都被浪费了。

循环队列：在$end$超出数组大小之后，把数据溢出到数组的头部。

#define SIZE 100000//SIZE大小要估准！
int q[SIZE+5];
int fnt=1,end;

#define front (q[fnt%SIZE])
#define pop (fnt++)//fnt不取模
#define push(x) (q[(++end)%SIZE]=(x))

//队列大小：end-fnt+1,或int fnt=0;......++fnt

$STL$提供了队列，需要包含$queue$库。用法与$stack$相似，但队首用$front()$访问，$queue$也是动态空间，不会有空间被浪费掉。

#include<queue>
#include<iostream>
using namespace std;

void calc(){
	queue<int>s;//发现一个队列，存储int类型
	for(int i=1;i<=5;i++){
		s.push(i);//压入队列
	}
	while(!s.empty()){//当队列非空时
		cout<<s.front()<<endl;//队首
		s.pop();//弹出
	}
}

int main(){
	calc();
}

$front,push,pop$时间复杂度为$O(1)$，所以建议使用$STL$ $queue$。

例$1$：P1996 约瑟夫问题

• 起一个队列，初始为$[1,2,3,4…]$。
• 每轮循环：$1.$队首出队，判断是否符合，然后重新入队，执行$(m-1)$次。$2.$队首出队，输出。
• 直到队列为空为止。

代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n,m;
	queue<int>q;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		q.push(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<m;j++){
			q.push(q.front()),q.pop();
		}cout<<q.front()<<" ";q.pop();
	}
}

链表

数组是一个顺序表。相邻元素在内存上的地址是连续的，这提供了：

• 快速访问某一个元素，可以在$O(1)$的时间内找到$a[i]$。
• 无需额外信息，就可以查询前驱后继。只需要下标减一即可。

虽然有上述好处，但也有明显不足：

• 插入、删除的代价极高，为$O(n)$。
• 固定的空间占用。

为了解决数组的这两个缺陷，我们发明了链表。

链表是一种崭新的数据结构。它不以下标来寻址，而是通过相邻元素之间的联系。

通俗的讲，数组是一群人在内存上排了个队；链表不需要每个人都相邻，但是需要每个人记住自己旁边的人。

• 下面演示了以单向链表存储的$[3,1,2,4,5]$;

$3->1->2->4->5$

可见，每个元素都有一个指针，指向右端元素。

链表的存储

//指针
struct node{
  int key;
  node* rt;
};

//数组
struct node{
   int key;//关键字
   int rt;//右边元素的下标
}s[100005];

以上两种方法都可以存储链表，无优劣之分。

链表（以及很多其他的数据结构）的每个元素称为“结点”。链表分为两种：

• 单向链表：每个人记住自己右边或左边的人
• 双向链表：每个人记住自己两边的人

单向链表只能单向查找，双向链表支持双向查找。

简单的链表只需要支持以下几个任务：

• 查询$key$是否存在
• 插入$key$
• 删除$key$

一般的，每一个链表都有一个伪结点。

还有一种叫循环链表，可以“走回头路”。

例$1$：P1996 约瑟夫问题

这一次，我们用链表来解决这道题。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m,rt[105],p=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
    	rt[i]=i+1;
	}rt[n]=1;//循环单链表 
	for(int i=1;i<=n;i++) {
		for(int j=1;j<m;j++){//走m-1个 
			p=rt[p];
		}cout<<rt[p]<<" ";rt[p]=rt[rt[p]];
	}cout<<endl;
    return 0;
}

并查集

最基本的一个问题：家族问题，给你两个人，判断他们是不是同一个家族的人。

只需要判断他们的祖先是否是同一个人就可以了。

#include<bits/stdc++.h>
using namespace std;

int dad[100005];

int anc(int x){
	if(dad[x])return anc(dad[x]);
	return 0;
}

void uni(int x,int y){
	x=anc(x);
	y=anc(y);
	if(x!=y){
		dad[x]=y;
	}
}

bool ask(int x,int y){
	return anc(x)==anc(y);
}

int main(){
	//......
	return 0;
}

刚刚实现的数据结构叫做并查集，并查集是用来维护不相交集合的数据结构，支持两个操作：

• $ask(x,y)$查询x，y是否在同一个集合。
• $union(x,y)$将x，y所在的集合合并。

带路径压缩的并查集，单次操作平均复杂度接近$O(1)$。

例$1$：P1551 亲戚

#include<bits/stdc++.h>
using namespace std;

int dad[100005];

int anc(int x){
	if(dad[x]) return dad[x]=anc(dad[x]);
	return x;
}

void uni(int x,int y){
	x=anc(x);
	y=anc(y);
	if(x!=y){
		dad[x]=y;
	}
}

bool ask(int x,int y){
	return anc(x)==anc(y);
}

int n,m,p;

void work(){
	int x,y;
	cin>>n>>m>>p;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		uni(x,y);
	}
	for(int i=1;i<=p;i++){
		cin>>x>>y;
		puts(ask(x,y)?"Yes":"No");
	}
}

int main(){
	work();
	return 0;
}

例$2$：P3367 【模板】并查集

#include<bits/stdc++.h>
using namespace std;

int dad[100005];

int anc(int x){
	if(dad[x]) return dad[x]=anc(dad[x]);
	return x;
}

void uni(int x,int y){
	x=anc(x);
	y=anc(y);
	if(x!=y){
		dad[x]=y;
	}
}

bool ask(int x,int y){
	return anc(x)==anc(y);
}

int n,m;

void work(){
	int cmd,x,y;
	cin>>n>>m;
	while(m--){
	    cin>>cmd>>x>>y;
	    if(cmd==1){
	    	uni(x,y);
		}else{
			printf("%c\n","NY"[ask(x,y)]);
		}
	}
}

int main(){
	work();
	return 0;
}

• 到此为止，基础数据结构就学完啦！恭喜你！

于$2020.8.2-20:59$竣工，共$517$行。