week2

408

算法

9.栈的链表实现

可以等效于只能用头插法和头删法的单链表：

10.队列

队列是只允许在一端进行插入，在另一端删除的线性表
重要术语：对头、对尾、空队列
队列的特点：FIFO
队列的顺序实现：

入队：

循环队列初始化：

判断队空还是队满时需要看size的值

队列的链表实现：

链表实现的队列一般不会队满，除非内存不足

双端队列：只允许从两端插入、两端删除的线性表
输入受限的双端队列：只允许从一端插入、两端删除的线性表
输出受限的双端队列：只允许从两端插入、一端删除的线性表

11.栈在括号匹配中的使用

12.栈在表达式求值中的应用

逆波兰表达式：后缀表达式，波兰表达式：前缀表达式
后缀：将运算符放在两个操作数后面
前缀：将运算符放在两个操作数前面
同一式子的后缀表达式不唯一，所以有"左优先"原则：只要左边的运算符能先计算，就优先算左边的

中缀表达式转后缀表达式的具体操作：
①若遇到数字，直接加入后缀表达式
②若遇到括号，遇到"(“直接入栈，遇到”)“则依次弹出栈内运算符并加入后缀表达式，直到弹出”(“为止
③若遇到运算符，依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到”("或栈空则停止。之后再把当前运算符入栈
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式

中缀表达式的计算：

1. 初始化两个栈，操作数栈和运算符栈
2. 若扫描到操作数，压入操作数栈
3. 若扫描到运算符或界限符，则按照"中缀转后缀"相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)

13.特殊矩阵的压缩存储

行优先存储：对于二维数组，依次存储每一行的元素
列优先存储：依次存储每一列的元素

对称矩阵的存储：可以只存储主对角线+下三角区(或上三角区)

将对称矩阵存储到一维数组中：
数组大小应该是$\frac{(1+n)\ast n}{2}$
可以用一个映射函数实现矩阵下标->一维数组下标
如果按照行优先原则，$a_{i,j}$->$B[k]$的映射规则是$k=\frac{i(i-1)}{2}+j-1$，(下三角区域+主对角线)

三对角矩阵，又叫带状矩阵：

行优先规则下，k=2i+j-3

稀疏矩阵：非零元素远远少于矩阵元素的个数：

存储策略：三元组<行, 列, 值>，可以用struct来存储，并定义一个struct数组
或者用十字链表法：每个三元组有两个next指针，一个指向横向的下一个元素，另一个指向纵向的

14.串

即字符串，是由零个或多个字符组成的有限序列
串是一种特殊的线性表，数据元素之间呈线性关系
StrCompare(S, T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若返回值<0
串的顺序存储方式：

15.朴素模式匹配算法

时间复杂度：O(nm)

16.KMP算法

引入next数组，每当字符不匹配时，将j移动到next[j]的位置
next[j]是前j-1个字符最长相等的前后缀长度+1，第一位固定是0，第二位固定是1
如：

1. ababaa是011234，第三位前面是ab，没有相等的所以是1，第四位前面是aba，相等最大长度是1所以是2
2. aaaab是01234，第五位前面是aaaa，最大相等串是aaa，所以是4

时间复杂度是O(m+n)
优化思路：

若第j个字符不匹配且第j个字符与第next[j]个字符相等，则让next[j]=next[next[j]]

17.树

树是n个结点的有限集合，其中任何一个结点都有且仅有一个前驱
相关名词：子树、度数(结点有几个孩子)、父结点、祖先结点、有序树、无序树
结点之间的路径：只能从上往下

常考考点：

1. 结点数=总度数+1
2. 度为m的树–各结点的度的最大值，m叉树–每个结点最多只能有m各孩子，可以为空树
3. 度为m的树第i层最多有$m^{i-1}$个结点
4. 高度为h的m叉树最多有$\frac{m^h-1}{m-1}$个结点
5. 高度为h的m叉树最少有h个结点
6. 具有n个结点的m叉树的最小高度为$\lceil {\log }_m(n(m-1)+1)\rceil$

18.二叉树

基本概念：可为空二叉树，任意结点的度<=2，是有序树，左子树、右子树不可颠倒
满二叉树：高度为h，有2^h-1个结点
完全二叉树：在满二叉树的基础上可去掉若干个编号更大的结点
二叉排序树：左子树关键字<根结点关键字<右子树关键字
平衡二叉树：左右子树深度差不超过1