2.栈和队列

2.1 堆栈

2.1.1 顺序栈

​ 1.栈的概念

  • ​ 栈（Stack）是操作受限的线性表，插入和删除数据元素的操作只能在线性表的一端进行。

    2.栈的主要操作

  • 入栈(Push)

  • 出栈(Pop)

栈的操作特性：后进先出（Last In First Out, LIFO ）

  • 顺序栈———栈的顺序存储结构

确定栈底：设top为栈顶元素索引（下标）

  • 栈的顺序存储结构及实现

进栈：top先 + 1，然后在top指向的位置压入数据。

出栈：先top所指向的元素弹出，然后top - 1。

栈空：top = -1；

栈满：top = MAX_SIZE - 1; PS：MAX_SIZE———栈的最大容量

上溢：栈顶指针或栈顶元素下标指出栈的外面。——-Push 时要先判断是否上溢

下溢：表示栈为空栈，却仍要执行弹栈操作。———–pop时要先判断是否下溢

示例：

字符类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>

using namespace std;

const int MAX_SIZE = 100;

/**
* 定义栈类
*/
class Stack
{
private:
	char* data;            //保存栈数组的首地址
	int size;
	int top;

public:

	Stack();

	Stack(int s);

	~Stack();

	void push(char ch);  //入栈
	char Pop();              //出栈，并返回栈顶元素
	char getTop();         //获得栈顶元素，不出栈
	bool isEmpty();       //判断栈是否为空
	bool isFull();           //判断栈是否满了
	void setNull();        //设置栈为空
};

Stack::Stack()
{
	size = MAX_SIZE;
	top = -1;
	data = new char[MAX_SIZE];
}

Stack::Stack(int s)
{
	size = s;
	top = -1;
	data = new char[size];
}

Stack::~Stack()
{
	delete[] data;
}

void Stack::setNull()
{
	top = -1;
}

void Stack::push(char ch)
{
	if (!isFull())
	{
		top++;
		data[top] = ch;
	}
	
}

char Stack::Pop()
{
	if (!isEmpty())
	{
		return data[top--];
	}
}

char Stack::getTop()
{
	if (!isEmpty())
	return data[top];
}

bool Stack::isEmpty()
{
	if (top == -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Stack::isFull()
{
	if (top + 1 == size)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main(void)
{
	//测试代码：
	Stack s1(2);

	s1.push('a');
	s1.push('b');

	cout << s1.isFull() << endl;
	cout << s1.getTop ()<< endl;
	cout << s1.Pop() << endl;
	cout << s1.Pop()<< endl;
	cout << s1.isEmpty() << endl;

	return 0;
}

2.1.2 异常捕获优化顺序栈

C++异常处理

  • try…catch语句语法如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //try块包含可能抛出异常的语句
    try
       {
    	语句1;
    	语句2;
    	语句3;
    	...
    }
    //catch块捕获异常，但可以有多个，但至少有一个
    catch(异常类型)
    {
    	异常处理代码
    }
    ...
    catch(异常类型)
    {
    	异常处理代码
    }
    • （1）try块语句在执行过程中没有抛出异常

    语句1,2,3均正常，则执行最后一个catch块后面的语句，所有catch块中的语句都不被执行。

    • （2）try块执行的过程中抛出了异常（被捕获）

    如果语句2发生异常，那么抛出异常后立即跳转到第一个异常类型和抛出的异常类型匹配的catch块中执行。

    语句3和try块中位于语句2下面的其他语句将会被跳过，不再执行。

    • try块执行的过程中抛出了异常（未捕获）

    假设语句2发生异常，那么抛出异常，跳出try块，假设没有catch块可以捕获此错误，跳转到最后一个catch块后面的语句，造成程序终止。

什么时候会出现异常？

  • 程序有错误会产生异常，eg：

    • 除法中分母是0；
    • 用new运算动态分配内存空间时，空间不够导致无法分配；
    • 访问数组元素，下标越界；
    • 打开文件读取时，文件不存在。

  • 程序主动抛出异常，eg：

    • 用throw语句抛出异常，throw“栈空”

自定义异常类的使用

  • 定义异常内部类（在类的声明部分定义）

    1
    class Empty{};	//在Stack类内部定义空类，大括号里面什么都没有

  • 抛出异常类（在pop函数遇到空栈时的语句）

    1
    throw Empty();   //注意这里是小括号

  • 捕获异常类（在调用pop函数时，用try/catch捕获）

    1
    2
    3
    4
    5
    6
    7
    8
    try
    {
    	stack.pop();   //如果pop抛出来的类型是Empty类这个类型
    }
    catch(Stack::Empty) //输出提示语句
    {
    	cout<<"Stack Empty!!"<<endl;
    }

优化顺序栈后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>

using namespace std;

const int MAX_SIZE = 100;

/**
* 定义栈类
*/
class Stack
{
private:
	char* data;          //保存栈数组的首地址
	int size;
	int top;

public:

	Stack();

	Stack(int s);

	~Stack();

	void push(char ch);//入栈
	char Pop();        //出栈，并返回栈顶元素
	char getTop();     //获得栈顶元素，不出栈
	bool isEmpty();    //判断栈是否为空
	bool isFull();     //判断栈是否满了
	void setNull();    //设置栈为空
	class Full{};	   //声明异常对象Full类
	class Empty{};     //声明异常对象Class类
};

Stack::Stack()
{
	size = MAX_SIZE;
	top = -1;
	data = new char[MAX_SIZE];
}

Stack::Stack(int s)
{
	size = s;
	top = -1;
	data = new char[size];
}

Stack::~Stack()
{
	delete[] data;
}

void Stack::setNull()
{
	top = -1;
}

void Stack::push(char ch)
{
	if (isFull())   //当栈满时，创建异常对象，并抛出
	{
		throw Full();
	}
	else
	{
		data[++top] = ch;
	}
	
}

char Stack::Pop()
{
	if (isEmpty())  //当栈空时，创建异常对象，并抛出
	{
		throw Empty();
	}
	else
	{
		return data[top--];
	}
}

char Stack::getTop()
{
	if (!isEmpty())
	return data[top];
}

bool Stack::isEmpty()
{
	if (top == -1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool Stack::isFull()
{
	if (top + 1 == size)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main(void)
{
	//测试代码：
	Stack s1(2);
	char ch;

	try
	{
		s1.push('a');
		s1.push('b');
		s1.push('c');
	}
	catch (Stack::Full)
	{
		cout << "Stack Full!!!" << endl;
	}

	try
	{
		ch = s1.Pop();
		cout << ch << endl;

		ch = s1.Pop();
		cout << ch << endl;

		ch = s1.Pop();
		cout << ch << endl;
	}
	catch (Stack::Empty)
	{
		cout << "Stack Empty!!!" << endl;
	}

	return 0;
}

输出结果：

Stack Full!!!
b
a
Stack Empty!!!

分析：数组只定义了2个长度，却压入三个数据，当压入第三个数据时，执行创建Full类并抛出，被catch捕获，因此输出”Stack Full!!!”，结束执行pop函数，当弹出第2个元素以后，栈已经空了，但main函数中仍要弹出第三个数据，因此执行创建Empty类并抛出，被catch捕获输出“Stack Empty!!!”。

2.1.3 用类模板实现顺序栈

  • 类模板是用于设计结构和成员函数完全相同，但所处理的数据类型不同的通用类。

    类模板定义形式：

    1
    2
    3
    4
    5
    template<class T1,class T2,...>
    class 类名
    {
    	...
    };

编写通用的栈类

将上面的代码声明部分改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class DataType>
class Stack
{
private:
	DataType* data;          //保存栈数组的首地址
	int size;
	int top;

public:

	Stack();

	Stack(int s);

	~Stack();

	void push(DataType e);//入栈
	DataType Pop();        //出栈，并返回栈顶元素
	DataType getTop();     //获得栈顶元素，不出栈
	...
};

成员函数每一项前加上 **template<class DataType>**，并把字符类型改为DataType，eg：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//析构函数
template<class DataType>
Stack<DataType>::~Stack()
{
	delete[] data;
}

//入栈
template<class DataType>
void Stack<DataType>::push(DataType ch)
{
	if (isFull())   //当栈满时，创建异常对象，并抛出
	{
		throw Full();
	}
	else
	{
		data[++top] = ch;
	}
	
}

  • 类模板

    为了使用类模板对象，必须显示地指定模板参数，eg：

    1
    2
    Stack<char> charStack;
    Stack<int> intStack;

    分别创建了charStack和intStack的堆栈对象。这两个堆栈对象分别可以处理字符类型和整数类型的数据。

树

树的定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。

树具有的特点有：

（1）每个结点有零个或多个子结点

（2）没有父节点的结点称为根节点

（3）每一个非根结点有且只有一个父节点

（4）除了根结点外，每个子结点可以分为多个互不相交的子树。

树的基本术语

结点的度：结点所拥有的子树的个数。

树的度：树中个结点度的最大值。

叶子结点：度为0的点，也叫终端结点。

分支结点：度不为0的结点，也称为非终端结点。

孩子、双亲：略。

兄弟：略。

树的遍历操作

从根结点出发，按照某种次序访问树中所有结点，使每个结点被访问一次且仅被访问一次

遍历的类型：

  • 前序遍历（根结点最先被遍历）

    若树为空，则空操作返回

    否则：

    访问根结点，按照从左到右的顺序前序遍历根结点的每一颗子树。

    image-20210711195507408

前序遍历：ABDEHIFCG

  • 后序遍历

    若树为空，则空操作返回。

    否则：

    按照从左到右的顺序遍历根节点的每一棵子树

    访问根结点

    后序遍历：DHIEFBGCA

  • 层序遍历：

    从第一层（即从根结点开始），自上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

    ABCDEFGHI

image-20210711201216230

前序：ABEFCDGHIJK

后序：EFBCIJKHGDA

层序：ABCDEFGHIJK

树的存储结构

双亲孩子表示法

image-20210711204624833

孩子兄弟表示法

image-20210711205242337

二叉树：

基本性质：

  • 叶子结点数等于度为2的结点数+1（n0=n2+1）

  • 二叉树第i层上最多有2^(i-1)个结点（i>=1）

  • 一棵深度为K的二叉树中，最多有2^k-1个结点（已知深度，可以知道要为二叉树分配多少内存空间），最少有k个结点（斜树）

  • 假设具有n个结点的完全二叉树的深度为k，k=[log2n]+1(不大于log2n的整数加1)

  • 对n个结点的完全二叉树从1开始按层序编号，则

    • 结点i的双亲结点为i/2
    • 结点i的为2i
    • 结点i的右孩子为2i+1

    img

二叉树的存储结构：

  • 数组

二叉树的顺序存储结构一般仅存储完全二叉树，否则会造成很大的浪费

  • 二叉链表

结点结构：

二叉链表结构

具有n个结点的二叉链表中，有2n-n-1=n+1个空指针。

img

但是二叉链表有个缺点就是没有办法找到双亲。因此我们引入三叉链表、

  • 三叉链表

image-20210717160859544

可以用指针表示，也可以用数组表示。

三叉链表的静态链表可以用数组存储，有点是存储方便，搜索快捷，但是它适用 于频发删除和插入的场合。最好是一个变化很少的树。

二叉树的遍历 方式：

  • 前序遍历
  • 中序遍历（树的遍历没有中序）
  • 后序遍历
  • 层序遍历

树状数组

前置知识：

lowbit：

lowbit(n)=n&(~n+1)

因为~n+1=-n，

所以lowbit(n)=n&(~n+1)=n&-n

观察可知，

  • t[x]结点覆盖的长度等于lowbit(x),
  • t[x]的父结点等于t[x+它自己的长度],即t[x+lowbit(x)],
  • 整棵树的深度为logn+1.

单点修改操作：

（以加k为例）

找到要修改的点对应的下标，加k，并一层一层地往上找到它的父结点，让它的父结点加上k。代码如下：

1
2
3
4
//单点修改
void add(int x,int k){
	for(;x<=n;x+=x&-x)t[x]+=k;//从要修改的那个点开始，一直往上找父结点，都要加上k 
}

查询操作：ask(7)从t[7]这个结点往左上走找到上一层结点，这个结点值等于x-lowbit(x)，即x-=x&-x

1
2
3
4
5
6
//查询前缀和
int ask(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=t[x];
	return ans;
}

其他一些操作：

1
2
3
4
5
6
7
8
9
//单点修改//单点查询
	add(x,k);
	ask(x)-ask(x-1); 
	//单点修改，区间查询
	add(x,k);
	ask(r)-ask(l-1);
	//区间修改，单点查询
	add(l,d);add(r+1,-d);
	a[x]+ask(x);//ask[x]是a[x]的增量

下面来看一下模板题

题目链接：https://vjudge.net/problem/HDU-1166

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
using namespace std;
int a[50005],t[50005];//分别对应原数组和树状数组 
int n;
//单点修改
void add(int x,int k){
	for(;x<=n;x+=x&-x)t[x]+=k;//从要修改的那个点开始，一直往上找父结点，都要加上k 
} 
//查询前缀和
int ask(int x){
	int ans=0;
	for(;x;x-=x&-x)ans+=t[x];//循环退出条件是x>=1,因为数组下标是从1开始的 
	return ans;
} 
int main(){
	int test;
	cin>>test;
	for(int i=1;i<=test;i++){
        memset(a,0,sizeof(a));
        memset(t,0,sizeof(t));
		cout<<"Case "<<i<<":"<<endl; 
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			add(i,a[i]);
		}
		string s;
		int x,y;
		while(cin>>s&&s[0]!='E'){
			cin>>x>>y;
			if(s[0]=='Q'){
				int sum=ask(y)-ask(x-1);
				cout<<sum<<endl;
			}
			else if(s[0]=='A'){
				add(x,y);
			}
			else if(s[0]=='S'){//减去y相当于+y的相反数 
				add(x,-y);
			}
		}
	} 
	return 0;
}

线段树

同样的模板题，这是线段树的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstdio>
#include<string>
using namespace std;

struct node{
	int l,r;
	int v;
}tr[200020];
int a[200020];

void pushup(int u){
	tr[u].v=tr[u<<1].v+tr[u<<1|1].v;
}

void build(int u,int l,int r){
	if(l==r){
		tr[u]={l,r,a[r]};
	}
	else{
		tr[u].l=l;
		tr[u].r=r;
		int mid = (r+l) >>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

void modify_add(int u,int x,int v){
	if(tr[u].l==x&&tr[u].r==x)tr[u].v+=v;
	else{
		int mid=(tr[u].l+tr[u].r)>>1;
		if(x<=mid)modify_add(u<<1,x,v);
		else modify_add(u<<1|1,x,v);
		pushup(u);
	}
}
void modify_sub(int u,int x,int v)
{
	if(tr[u].l==x&&tr[u].r==x)tr[u].v-=v;
	else{
		int mid=(tr[u].l+tr[u].r)>>1;
		if(x<=mid)modify_sub(u<<1,x,v);
		else modify_sub(u<<1|1,x,v);
		pushup(u);
	}
}

int query(int u,int l,int r){
	if(l<=tr[u].l&&r>=tr[u].r)return tr[u].v;
	else{
		int mid=(tr[u].l+tr[u].r)>>1;
		if(r<=mid)return query(u<<1,l,r);
		else if(l>mid)return query(u<<1|1,l,r);
		else{
			int v=0;
			v+=query(u<<1,l,r);
			v+=query(u<<1|1,l,r);
			return v;
		}
	}
}
int main()
{
    string op;
    int l,r;
    int p=1;
    int n,len;
    cin>>n;
    while(n--)
    {
    	cin>>len;
    	for(int i=1;i<=len;i++)//结点是从1开始的 
		{
			cin>>a[i];
		} 
		build(1,1,len);
		
		printf("Case %d:\n",p++);
		while(cin>>op&&op[0]!='E')
		{
			cin>>l>>r;
			if(op[0]=='A')modify_add(1,l,r);
			else if(op[0]=='S')modify_sub(1,l,r);
			else printf("%d\n",query(1,l,r));
		}
	}
}

图

前置理论知识

无向完全图的边：n×(n-1)/2

有向完全图的边：n×(n-1)

TD：度

无向图度和边数之和的关系：

∑ ^n^ TD(vi)=2e

i=1

有向各顶点入度出度之和与边的关系：

入度和=出度和=边数

简单路径：序列中顶点不重复出现的路径

简单回路：除了第一个顶点和最后一个顶点外，，其余顶点不重复出现的回路。

连通图：无向图中，如果任意两个顶点都是连通的，则称该图为连通图

连通分量：无向图中，非连通图的极大连通子图

强连通图：有向图中，……

强连通分量：有向图中，……

生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图

极小连通子图：含有n-1条边（多：构成回路；少：不连通）

生成森林：在非连通图中，由每个连通分量都可以得到一颗生成树，这些连通分量的生成树就组成了非连通图的生成森林。

图的存储方式

邻接矩阵

基本思想：一维数组存储途中顶点的信息

二维数组（邻接数组）存储各顶点的邻接关系

arc[i] [j]=1有边

​ =0无边

无向图邻接矩阵

对称

速建版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn=200;
int Nv,Ne;
int G[maxn][maxn];
void buildGraph(){
	int v1,v2,w;
	cin>>Nv;
	//建图
	for(int i=0;i<Nv;i++){
		for(int j=0;j<Nv;j++) G[i][j]=0x3f3f3f;//初始化为无穷大 
	} 
	cin>>Ne;
	//插入边 
	for(int i=0;i<Ne;i++){
		cin>>v1>>v2>>w;
		G[v1][v2]=w;
		G[v2][v1]=w;
	}
}
有向图邻接矩阵

某顶点的出度：此行元素和

某顶点的入度：此列元素和

邻接表

基本思想：对于图的每个顶点vi，将所有邻接与vi的顶点连成一个单链表，称为顶点vo的边表（有向图称为：出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

无向图的邻接表

待补……

有向图的邻接表

顶点i的出度：第i行的边表结点个数

顶点i的入度：找到终点为i的边表，则度+1

求顶点i的所有邻接点：第i行的边表结点个数

速建版：

1
2
3
4
5
6
7
8
9
int a[maxn];
int head[maxn],ne[maxn],ver[maxn],edge[maxn],tot=0;
void add(int x,int y)//,int z)//把边长为z的y结点插入到x原来指向的地方
{
	ver[++tot]=y;
	//edge[tot]=z;
	ne[tot]=head[x];//新结点的下一个指向head的地x编号指向的地方 
	head[x]=tot;//head存的是顶点编号 
}

图的存储结构的比较

空间性能 时间性能 适用范围 唯一性
邻接矩阵 O(n^2^) O(n^2^) 稠密图 唯一
邻接表 O(n+e) O(n+e) 稀疏图 不唯一

图的遍历

关键问题：

图中可能存在回路，如何避免不重复访问同一个结点？
解决方案：附设访问标志数组visited[n]

dfs-深度优先遍历

基本思想：

  1. 访问顶点v；
  2. 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历
  3. 重复上述两步，直至所有和v有路径相通的顶点都被访问到。

伪代码：

1
2
3
4
5
6
7
8
void DFS (int v){
	visited[v]=true;
	for(v的每个邻接点w){
		if(!visited[w]){
			DFS(w);
		}
	} 
}

是树的先序遍历的推广

bfs-广度优先搜索

借助队列来实现，伪代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
void BFS(int v){
	visited[v]=true;
	Enqueue(v,Q);
	while(!Isempty(Q)){
		v=Dequeue(Q);
		for(v的每个邻接点w){
			if(!visited[w]){
				visited[w]=true;
				Enqueue(w,Q);
			}
		}
	}
}