数据结构笔记
[TOC]
写在前面
寒假看看数据结构的网课当作复习吧，随便写了一些笔记
概念小结
1 | graph LR; |
逻辑结构：研究对象之间的特性和关系；
存储结构：有效组织计算机进行存储
算法五个特性：
- 有穷性：经过有穷步可以结束
- 确定性：每一条指令必须有确切的含义，没有二义性
- 可行性：可以执行的
- 输入
- 输出
算法设计要求：
- 正确性
- 可读性
- 健壮性
- 高效性
栈和队列
定义和特点
栈特点：后进先出（LIFO）
队列特点：先进先出（FIFO
使用案例
进制转换
将十进制数159转换成八进制数
短除法余数分别依次是$7，3，2$，每一次得到余数的时候放入栈中，然后将栈中元素依次弹出可以得到八进制数$237$
括号匹配
假设表达式中有[],()两种括号，括号可以嵌套，但是顺序不可以出错。比如([] ())是合法的，但是([)]不合法
按照顺序依次push进入栈中，如果和下面的匹配就弹出，如果出现交叉的情况说明不匹配。
表达式求值
算法有限算法
把表达式分为：
- 操作数： 常数，变量
- 运算符： 算术运算符，逻辑运算符，关系运算符
- 界限符： 左右括号和表达式结束符
设置两个栈，一个是算符栈，另一个是操作数栈
从左至右开始扫描表达式：
如果是数：压入操作数栈
如果是运算符：
- 优先级高于运算符栈顶的优先级，入栈并继续向后扫描
- 优先级低于运算符栈顶的优先级，从操作数栈弹出两个运算数，弹出栈顶运算符，并进行运算，并将结果压栈进入操作数栈
继续进行扫描
舞伴问题
舞会上男女各自拍成一列，开始时从队头出来配对跳舞，跳完了过后自己排到后面去。
树
- 二叉树和树是两个概念，因为树的结点的孩子不分左右
- 假设二叉树叶子节点个数为$N_0$,有两个孩子的节点个数为$N_2$,则$N_0=N_2+1$
$$
设节点数为N,两个孩子的节点数为N_2,一个的为N_1,没有的为N_0\
边数:\
N-1=N_2+N_1+N_0-1=2*N_2+N_1\
化简可得
$$
满二叉树：一个深度为$k$且有$2^k-1$个结点的二叉树
完全二叉树：深度为$k$的具有$n$个节点的二叉树，当且仅当每一个节点都与深度为$k$的满二叉树从上到下，从左到右编号1到$n$对应的时候，称作完全二叉树。其深度为$\lfloor log_2n\rfloor+1$
完全二叉树节点$ib $的父亲$\lfloor i/2\rfloor$,儿子$2i,2i+1$
先序遍历:根左右；中序遍历：左根右；后序遍历：左右根
如果二叉树各节点均不同，则三种遍历的序列都唯一
如果知道先序遍历和中序遍历，或者后序遍历和中序遍历，则可以确定唯一的二叉树。已知先序/后序，中序，确定子树的时候，通过先序/后序确定子树的根，通过中序确定左右。
线索二叉树：我选择把这篇文章贴上来#图解 数据结构：轻松搞定线索二叉树 - 知乎
树转换成二叉树：从上到下，当前节点孩子放在该节点的左子树，兄弟放在右子树
二叉树转换成树：左孩子的的右孩子连接到双亲，删除原来的右孩子的线
二叉树转换成森林：从根节点开始，顺着将和右孩子的连线抹掉，再把每一个二叉树再进行还原。
哈夫曼树：最优二叉树，带权路径长度最短的树
- 构造方法：先构造N个二叉树，每个都只有一个节点，选择权值最小的两个节点作为左右子树构成一个新的树，权值设为两个节点权值之和，然后在森林之中删除掉原来的两个节点，再把新的树放入到森林当中
- 特点：经过$N-1$次合并形成，有$2N-1$条边，且每个分支节点度都为2。
图
定义和术语
图：G=(V,E)
- V(Vertex):顶点（数据元素）的非空有穷集合
- E(Edge):边的有穷集合
根据是否每条边有方向分为有向图，无向图
任意两个点都有边叫做完全图(有向图是两个点之间有两条边)
有向图的边也叫做弧
边的数目很少($\leq nlogn$)叫做稀疏图
边较多的叫做稠密图
网：边带权的图
邻接：有边相连的两个顶点之间联系
$(v_i,v_j)表示无向边，v_i邻接v_j,<v_i,v_j>表示有v_i到v_j的一条有向边，称作v_i邻接到v_j或者v_j邻接于v_i$
关联（依附）:边和顶点的关系
顶点的度：和顶点相关联的边的数目（有向图称出度入度）
路径：连续的边构成的顶点序列
路径长度：路径上的边的权值之和
回路：第一个顶点和最后一个顶点相同的路径
简单路径：除了起点终点可以相同外，其他顶点均不相同
连通图：在图中，任意两个顶点之间存在路径成为连通图（有向图则成为强连通图）
连通分量：无向图的极大连通子图称为其的连通分量(有向图叫做强连通分量)
生成树：包含无向图所有顶点的极小连通子图
生成森林：对于非连通图，由各个连通分量的生成树的集合