泉州暑假集训Day 2

PS: This is a note.

栈

数据结构(DS)

高效的组织数据的一种方式

数组

最简单的数据结构是数组(array): int n[101];

数组属于数据结构中的用顺序结构实现的线性表

注: 线性表是一维的，可以用顺序结构和链式结构实现

栈的使用

栈是一种基本的顺序结构，属于特殊的线性表(操作受限，特性: 后进先出————只能在一端插入和删除)

我们通常把元素插入栈叫做进栈(PUSH),删除栈内元素叫出栈(POP)

• 栈中可以插入和删除的一段叫栈顶
• 另一端叫做栈底
• 用一个指针TOP指向栈顶，若TOP=0，表示栈空，TOP=N时栈满，进栈时TOP加1，退栈时TOP减1。栈指针在运算中永远指向栈顶

实现栈的常用方法

数组模拟栈

STL模拟栈

栈例题

e.g. 后缀表达式求值(洛谷P1449)

#include <bits/stdc++.h>
using namespace std;
stack<int> sta;
//运用STL中的栈可能超时，当遇到过大的元素时应用数组
string s;
int main()
{
	int temp=0,x,y;
	cin>>s;
	for(int i=0; i<s.size(); i++) {
		if(s[i]>='0'&&s[i]<='9') {
			temp=temp*10+s[i]-'0';
		}
		if(s[i]=='@')
		{
			break;
		}
		else if(s[i]=='.') {
			sta.push(temp),temp=0;
		}
		if(s[i]=='+') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y+x);
		}
		if(s[i]=='-') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y-x);
		}
		if(s[i]=='*') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y*x);
		}
		if(s[i]=='/') {
			x=sta.top();
			sta.pop();
			y=sta.top();
			sta.pop();
			sta.push(y/x);
		}
	}
	cout<<sta.top();
	return 0;
}

e.g. 中缀表达式转后缀表达式

解法: 稀土掘金

队列(queue)

队列是一种线性表

队列例题

e.g. Blah数集(信息学奥赛一本通（C++版）在线评测系统 题号1333)

解法: CSDN

树与二叉树

树的定义:

• 树是一种非线性的数据结构
• 树是若干结点的集合，是由唯一的根和若干子树组成
• 树的定义本身就是递归的

树的基本概念

度

1. 结点的度: 结点拥有的字数个数
2. 树的度: 一棵树中，最大的结点的度

结点

1. 叶结点或终端结点: 度为零的节点
2. 父亲结点或父结点: 若一个节点含有子结点，则这个结点称为其子结点的父结点
3. 孩子结点或子结点: 一个结点含有的子树的根结点
4. 兄弟结点: 具有相同父结点的节点互称为兄弟结点
5. 结点的层次: 根开始定义起，根为第1层，根的子结点为第2层，以此类推
6. 堂兄弟结点：父结点在同一层的结点互为堂兄弟
7. 结点的祖先：从根到该结点所经分支上的所有结点

高度或和深度

1. 树的高度或深度: 树中结点的最大层次称为树的深度
2. 深度较为常用

有序树和无序树

1. 有序树: 树中结点的子树从左到右是有次序的，不能交换
2. 无序树: 树中结点的子树没有顺序，可以任意交换

详细可以看这篇博客

注: 结点和节点都是正确的

二叉树的定义

在一般的树上加上如下两个限制条件就得到了二叉树

• 每个结点最多只有两棵子树，即二叉树中的结点的度只能为0，1，2
• 子树有左右之分，不能颠倒
• 根据二叉树的定义共有5种基本形态:”空二叉树”、”只有根节点”、”只有左子树，右子树为空”、”只有右子树,左子树为空”、”既有左子树，又有右子树”

满二叉树(所有分支结点都有子结点)的定义

• 在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树称为满二叉树

完全二叉树的定义

• 如果对一棵深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，那么这棵二叉树就是一棵完全二叉树

⭐二叉树的主要性质