《数据结构》读书笔记
2021-07-21 18:56:21 0 举报AI智能生成
考研408计算机综合数据结构部分知识框架、思维导图
作者其他创作
大纲/内容
第1章 绪论
1.1 数据结构的基本概念
1.2 算法和算法评价
第2章 线性表
2.1 线性表的定义和基本操作
2.2 线性表的顺序表示
2.3 线性表的链式表示
第3章 栈和队列<br>
3.1 栈(Stack)
特性：LIFO(Last In First Out)<br>入栈和出栈顺序相反<br>
存储结构
链式存储
链栈
所有操作都在<b>单链表表头</b>执行<br>
便于多个栈共享存储空间提高效率<br>
不存在栈满上溢的情况<br>
顺数存储
顺序栈(top指向栈顶元素)
进栈操作：<br>S.data[++S.top]=x;
出栈操作：<br>x=S.data[S.top--];<br>
<b>判断栈空条件：</b><br>S.top==-1
共享栈<br>
<b>定义：</b>两个顺序栈共享一个一维数组空间，将两个栈的栈底<br>分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸<br>
优点：<br>节省存储空间，降低<b>上溢</b>风险
判断栈满条件：<br><span class="equation-text" contenteditable="false" data-index="0" data-equation="top1-top0=1"><span></span><span></span></span><br>
相关考点
出栈序列
判断合法的出栈顺序
n个不同元素的出栈序列个数：<br><b>卡特兰数(Catalan数)</b><span class="equation-text" contenteditable="false" data-index="0" data-equation="=\frac{1}{n+1}C_{2n}^{n}"><span></span><span></span></span><br>
穷举法
<b>上溢：</b>栈顶指针超出了最大范围<br>因为栈的增删都是在栈顶进行的
<b>C语言标识符：<br></b>只能以字母、下划线开头，不能以数字开头
栈的应用
括号匹配
表达式求值
前缀表达式(波兰表达式)：+ab
中缀表达式(普通表达式)：a+b
后缀表达式(逆波兰表达式)：ab+<br>
“左右先”原则
习题1
习题2
中缀表达式转后缀表达式(机算)<br>
<b>机算步骤/算法：<br>1.操作数</b>，直接加入后缀表达式<br><b>2.界限符</b>，'('直接入栈，')'则依次弹出栈元素直到弹出'('<br><b>3.运算符</b>，依次弹出栈内优先级≥当前运算符的元素并加入后缀表达式，<br>直到'('或栈空。之后再入栈当前运算符
递归
递归工作栈<br>
<b>工作原理：</b><br>每进入一层递归，就将递归调用所需的信息(返回点、局部变量、传入实参)压入栈顶<br>每退出一层递归，就从栈顶弹出相应信息<br>
<b>缺点：</b>多层递归可能导致栈溢出
递归算法：斐波那契数列
进制转换、迷宫求解等
3.2 队列(Queue)
特性：FIFO(First In First Out)<br>入队和出队顺序一致
存储结构
顺序存储(循环队列)
<b>入队操作：(确定maxSize!!!)</b><br>rear=(rear+1)%maxSize;<br>A[rear]=x;<br>
<b>出队操作：</b><br><br>
<b>队列长度(size/length)：</b><br>=(rear-front+maxSize)%maxSize
<b>判断队满条件：</b><br>1.(Q.rear+1)%MaxSize==Q.front<br>2.size==MaxSize(size记录队列长度)<br>3.front==rear&&tag==1(tag记录最后一次操作类型)
<b>判断队空条件：</b><br>1.Q.rear==Q.front<br>2.size=0(size记录队列长度)<br>3.front==rear&&tag==0(最后执行了删除操作)<br>
链式存储
带头结点
<b>判断队空条件：<br></b>1.Q.front->next==null<br>2.Q.front==Q.rear
不带头结点<br>
<b>判断队空条件：<br></b>1.Q.front==null<br>2.Q.rear==null
双端队列
<b>定义：</b>允许两端进行增删的队列<br>
变种
输入受限的双端队列
输出受限的双端队列
<b>考点：</b>对输出序列合法性的判断<br>
队列的应用
树的层次遍历
图的广度优先遍历
操作系统中的应用<br>
<b>就绪队列</b><br>解决多用户的资源竞争问题<br>
<b>缓冲区</b><br>解决主机与外部设备间速度不匹配问题<br>
3.3 栈和队列的应用
3.4 特殊矩阵的压缩存储
对称矩阵
策略：只存储主对角线+下三角区<br>
按行优先原则，数组B[]下标从0开始<br><span class="equation-text" data-index="0" data-equation="a_{ij}" contenteditable="false"><span></span><span></span></span>(i≥j)是第<span class="equation-text" data-index="1" data-equation="\frac{i(i-1)}{2}+j" contenteditable="false"><span></span><span></span></span>个元素<br><span class="equation-text" contenteditable="false" data-index="2" data-equation="k=\frac{i(i-1)}{2}+j-1"><span></span><span></span></span>==>B[K]
考虑上三角？ 列优先？数组下标从1开始？i<j?的情况
三角矩阵<br>
下三角矩阵：除了对角线核下三角区，其余的元素都相同的矩阵<br>
策略：行优先存储下三角区，并在最后一个位置存储常量C<br>
三对角矩阵(带状矩阵)<br>
定义：当|i-j|>1时，有<span class="equation-text" contenteditable="false" data-index="0" data-equation="a_{ij}=0"><span></span><span></span></span>(1≤i,j≤n)<br>数组长度=3n-2
策略：行优先\列优先原则，只存储带状部分
行优先，数组下标从0开始时：<br><span class="equation-text" data-index="0" data-equation="a_{ij}" contenteditable="false"><span></span><span></span></span>->B[k]，k=2i+j-3，<span class="equation-text" data-index="1" data-equation="a_{ij}" contenteditable="false"><span></span><span></span></span>是第k+1个元素<br>B[k]-><span class="equation-text" data-index="2" data-equation="a_{ij}" contenteditable="false"><span></span><span></span></span>，<span class="equation-text" contenteditable="false" data-index="3" data-equation="i=\lceil(k+2)/3\rceil"><span></span><span></span></span>，j=k-2i+3
稀疏矩阵
定义：非零元素远远少于零元素的个数
<b>策略：</b><br>1.顺序存储——三元组<行，列，值><br>2.链式存储——十字链表法<br>
第4章 串(String)
4.1 串的定义和实现
定义：由一个或多个字符组成的有限序列<br>一般记为<span class="equation-text" data-index="0" data-equation="S='a_1a_2···a_n'(n≥0)" contenteditable="false"><span></span><span></span></span>，空串用<span class="equation-text" data-index="1" data-equation="\emptyset" contenteditable="false"><span></span><span></span></span>表示<br>
字符集：<br>英文字符——ASCII字符集<br>中英文 ——Unicode字符集
存储结构
<b>定长顺序存储</b>(静态数组实现)
<b>堆分配存储</b>(动态数组实现)
<b>块链存储<br></b>每个节点存多个字符，没有字符的位置用'#'或'\0'补足<br>
4.2 串的模式匹配<br>(主串n>>模式串m)<br>
朴素模式匹配算法<br>
思想：将主串中所有长度为m的子串与模式串比较<br>
时间复杂度:最坏O(nm)，最好O(n)
<b>KMP算法</b><br>由D.E.<b>K</b>nuth,J.H.<b>M</b>orris和V.R.<b>P</b>ratt提出
时间复杂度：O(m+n)<br>求next数组时间复杂度O(m)<br>模式匹配过程最坏时间复杂度O(n)
第5章 树与二叉树<br>
5.1 树的基本概念
基本术语
树的路径长度：树根到每个结点的路径长度的总和
树的性质
节点数=总度数+1
度为m的树中第i层上至多有<span class="equation-text" contenteditable="false" data-index="0" data-equation="m_{i-1}"><span></span><span></span></span>个节点(i≥1)
高度为h的m叉树至多有<span class="equation-text" contenteditable="false" data-index="0" data-equation="\frac{m^h-1}{m-1}"><span></span><span></span></span>个节点(等比数列求和)，至少有h个节点<br>高度为h，度为m的树至少有h+m-1个节点<br>
具有n个节点的m叉树的最小高度为<span class="equation-text" contenteditable="false" data-index="0" data-equation="\lceil log_m(n(m-1)+1)\rceil"><span></span><span></span></span><br>
5.2 二叉树的概念<br>
定义：每个结点至多只有两棵子树并且有左右之分，次序不能任意颠倒
特殊的二叉树
满二叉树
<b>定义：</b>高度为h，且含有<span class="equation-text" contenteditable="false" data-index="0" data-equation="2^h-1"><span></span><span></span></span>个节点的二叉树
<b>特点：</b><br>1.只有最后一层有叶子结点<br>2.不存在度为1的结点<br>3.节点i的左孩子为2i，右孩子为2i+1，父节点为<span class="equation-text" contenteditable="false" data-index="0" data-equation="\lfloor i/2\rfloor" style="font-weight: bold;"><span></span><span></span></span>
※完全二叉树
<b>定义：</b>每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应
<b>特点：</b><br>1.只有最后两层可能有叶子结点<br>2.最多只有一个度为1的结点<br>3.节点i的左孩子为2i，右孩子为2i+1，父节点为<span class="equation-text" data-index="0" data-equation="\lfloor i/2\rfloor" style="font-weight: bold;" contenteditable="false"><span></span><span></span></span><br>4.<span class="equation-text" contenteditable="false" data-index="1" data-equation="i≤\lfloor n/2\rfloor"><span></span><span></span></span>为分支结点，<span class="equation-text" data-index="2" data-equation="i>\lfloor n/2\rfloor" contenteditable="false"><span></span><span></span></span>为叶子结点
二叉排序树
定义：<br><br>
平衡二叉树
定义：<br><br>
二叉树的性质
性质1：叶子结点比二分支结点多一个 <span class="equation-text" contenteditable="false" data-index="0" data-equation="n_0=n_2+1"><span></span><span></span></span><br>
性质2：非空二叉树第k层至多有<span class="equation-text" contenteditable="false" data-index="0" data-equation="2^{k-1}"><span></span><span></span></span>个结点
性质3：高度为h的二叉树至多有<span class="equation-text" contenteditable="false" data-index="0" data-equation="2^k-1"><span></span><span></span></span>个结点
性质4：对完全二叉树<br>①当i>1时，结点i的双亲编号为<span class="equation-text" data-index="0" data-equation="\lfloor i/2\rfloor" contenteditable="false"><span></span><span></span></span><br>②当2i≤n时，结点i的左孩子编号为2i，否则无左孩子<br>③当2i+1≤n时，结点i的右孩子编号为2i+1，否则无右孩子<br>④结点i所在层次(深度)为<span class="equation-text" contenteditable="false" data-index="1" data-equation="\lfloor \log_2i\rfloor+1"><span></span><span></span></span>
性质5：具有n个结点的完全二叉树的高度为<span class="equation-text" contenteditable="false" data-index="0" data-equation="\lceil \log_2(n+1)\rceil"><span></span><span></span></span>或<span class="equation-text" data-index="1" data-equation="\lfloor \log_2i\rfloor+1" contenteditable="false"><span></span><span></span></span>
存储结构
顺序存储
为满足二叉树的任意性，深度为h的二叉树要申请<span class="equation-text" contenteditable="false" data-index="0" data-equation="2^h-1"><span></span><span></span></span>大小的数组
完全二叉树和满二叉树适合顺序存储
链式存储
n个结点的二叉链表有n+1个空链域<br>
5.3 二叉树的遍历和线索二叉树<br>
<b>二叉树(逻辑结构)</b>的遍历<br>
遍历序列
先序遍历
中序遍历
后序遍历
层次遍历
由遍历序列构造二叉树
前序+<b>中序遍历序列</b>
后续+<b>中序遍历序列</b>
层次+<b>中序遍历序列</b>
递归算法和非递归算法的转换
<b>线索二叉树(物理结构)</b>
相关概念
作用：方便找到某个结点的<b>前驱</b>和<b>后继，</b>方便遍历
线索：指向<b>前驱/后继</b>的<b>指针</b>称为线索
先序前驱/先序后继；中序前驱/中序后继；后序前驱/后序后继；
分类
先序线索二叉树<br>
中序线索二叉树
后序线索二叉树
不能有效解决后序线索二叉树中求后序后继的问题
后序线索二叉树的遍历仍需要栈的支持
<b>存储结构：</b><br>在二叉树链式存储结构的基础上增加两个标志位 ltag 和 rtag<br>ltag/rtag 为 1 时表示 lchild/rchild 指向前驱/后继<br>ltag/rtag 为 0 时表示 lchild/rchild 指向左孩子/右孩子<br>
手画线索二叉树<br>
二叉树线索化
视频5.3.5
5.4 树、森林<br>√
树的存储结构
双亲表示法
顺序存储结点数据，节点中保存父节点在数组中的下标，根节点为-1
<b>优点：</b>找父节点方便；<b>缺点：</b>找孩子不方便
孩子表示法
顺序存储节点数据，结点中保存孩子链表头指针<b>(顺序+链式存储)</b>
<b>优点：</b>找孩子方便；<b>缺点：</b>找父节点不方便
<b>※孩子兄弟表示法</b>
用二叉链表存储树——<b>左孩子右兄弟</b>
从存储视角来看形态上和二叉树类似
考点：<br>1.树与二叉树的相互转换，本质就是用孩子兄弟表示法存储树<br>2.已知树、森林的非终端节点个数，求对应二叉树的右指针为空的节点个数
树、森林与二叉树的转换
本质：用孩子兄弟表示法——二叉链表存储森林<br>
森林中各个根结点之间视为兄弟关系
树和森林的遍历<br>
树的遍历
先根遍历
后根遍历
层序遍历
森林的遍历
先序遍历
中序遍历
树、森林遍历和二叉树遍历的对应关系
5.5 树与二叉树的应用<br>√
二叉排序树(BST)
<b>定义：</b><br>左子树结点值<根节点值<右子树结点值，默认不允许两个结点的关键字相同
<b>二叉排序树的查找：</b><br>从根结点开始，目标更小向左找，目标更大向右找
<b>二叉排序树的插入：</b><br>找到插入位置(一定是叶子结点)，修改其父节点的指针
<b>二叉排序树的删除：</b>
被删为叶子节点，直接删除
被删结点只有左子树或只有右子树，其子树顶替其位置
被删结点左右子树都存在
<b>后继结点</b>(右子树中最左下结点)顶替并删除
<b>前驱结点</b>(左子树中最右下结点)顶替并删除
查找效率分析
取决于树的高度，最好O(log n)，最坏O(n)
平均查找长度的计算
查找成功的情况
查找失败的情况(需补充失败结点)
平衡二叉树(AVL)
<b>定义：</b>树上任一结点的左子树和右子树的高度之差不超过1<br>结点的<b>平衡因子</b>=左子树高-右子树高
平衡二叉树的插入<br>
和二叉排序树相同，找到合适的位置插入，但新插入的结点可能导致查找路径上的某个结点不再平衡
"不平衡"调整的四种规律
找到<b>最小不平衡子树</b>进行调整，记最小不平衡子树的根为A
<b>LL平衡旋转(右单旋转)：</b><br>在A的左孩子的左子树插入导致A失衡，将A的左孩子右上旋
<b>RR平衡旋转(左单旋转)：</b><br>在A的右孩子的右子树插入导致A失衡，将A的右孩子左上旋
<b>LR平衡旋转(先左后右双旋转)：</b><br>在A的左孩子的右子树插入导致A失衡，将A的左孩子的右孩子，先左上旋再右上旋
<b>RL平衡旋转(先右后左双旋转)：<br></b>在A的右孩子的左子树插入导致A失衡，将A的右孩子的左孩子，先右上旋再左上旋
平衡二叉树的查找
考点：高为h的平衡二叉树最少有几个节点——递推求解<br><span class="equation-text" contenteditable="false" data-index="0" data-equation="n_h=n_{h-1}+n_{h-2}+1"><span></span><span></span></span><br>
平衡二叉树最大深度为O(log n)，平均查找长度/查找的时间复杂度为 O(log n)
哈夫曼树和哈夫曼编码
定义
<b>哈夫曼树(最优二叉树)：</b>在含有给定的n个带权叶节点的二叉树中，WPL最小的二叉树
结点的权：某种特定含义的数值
<b>结点的带权路径长度</b>=根到结点的路径长度*结点的权值
<b>树的带权路径长度(WPL)</b>=树中所有叶子结点的带权路径长度之和
哈夫曼树的构造
每次选两个根节点权值最小的树合并，并将两者权值之和作为新的根结点的权值
哈夫曼树不唯一，但WPL必然都是最小值
<b>※哈夫曼编码</b>
将字符频次作为字符结点权值，构造哈夫曼树即可得哈夫曼编码，可用于<b>数据压缩</b>
前缀编码——没有一个编码是另一个编码的前缀
固定长度编码——每个字符用相等长度的二进制位表示
可变长度编码——允许对不同字符用不等长的二进制表示
KMP求next数组例子
第6章 图
6.1 图的基本概念<br>√√
定义：G=(V,E)，顶点集V，边集E
边的权和网(带权图)
点到点的关系
<b>连通：</b>在无向图中，存在顶点u到顶点v的路径，则称u和v是连通的<br><b>连通图：</b>若图G中任意两个顶点是连通的，则称图G为<b>连通图</b>，否则称为<b>非连通图</b><br><b>连通分量：</b>无向图中的<b>极大连通子图</b>称为<b>连通分量(</b>若n个顶点的图边数小于n-1，那么必是非连通图<b>)</b>
<b>强连通：</b>有向图中，顶点u，v之间双向均存在路径，则称u，v是强连通的<br><b>强连通图：</b>若图中任意一对顶点都是强连通的，则称为<b>强连通图</b><br><b>强连通分量：</b>有向图中的<b>极大强连通子图</b>称为有向图的<b>强连通分量</b>
<b>路径：</b>顶点<span class="equation-text" data-index="0" data-equation="V_p" contenteditable="false"><span></span><span></span></span>到顶点<span class="equation-text" contenteditable="false" data-index="1" data-equation="V_q"><span></span><span></span></span>之间的一条路径是指顶点序列(或边序列)<span class="equation-text" data-index="2" data-equation="V_p,V_{l1},V_{l2},...,,V_{lm},V_{q}" contenteditable="false"><span></span><span></span></span><br><b>路径长度：</b>指路径上边的数目<br><b>回路(环)：</b>第一个顶点和最后一个顶点相同的路径
<b>简单路径：</b>路径序列中顶点不重复出现的路径<br><b>简单回路：</b>除第一个和最后一个顶点，其余顶点不重复出现的回路
<b>距离：</b>u到v的最短路径长度，若不存在记该距离为无穷<span class="equation-text" contenteditable="false" data-index="0" data-equation="(\infin)"><span></span><span></span></span><br>
图的局部
<b>子图：</b><br>
极大连通子图：<br>极大强连通子图：
<b>生成树</b>：连通图中包含全部顶点的<b>极小连通子图</b><br><b>生成森林：</b>非连通图中各连通分量的生成树构成了非连通图的生成森林<br>
几种特殊形态的图
<b>简单图：</b>如果图G满足：①不存在重复的边；②不存在顶点到自身的边，那么成图G为简单图<br>多重图：<br>
<b>完全图(简单完全图)<br>无向完全图：</b>有n(n-1)/2条边的无向图称为无向完全图，任意两个顶点之间都存在边<br><b>有向完全图：</b>有n(n-1)条边的有向图称为有向完全图，任意两个顶点之间都存在两条方向相反的弧
<b>稠密图与稀疏图：</b>边数很少的图称为稀疏图，反之称为稠密图。一般当图G满足<span class="equation-text" contenteditable="false" data-index="0" data-equation="|E|<|V|\log|V|"><span></span><span></span></span>时视为稀疏图
<b>有向树：</b>一个顶点入度为0，其余顶点入度为1的有向图称为有向树<br>
6.2 图的存储及基本操作<br>√√
图的存储
邻接矩阵法
邻接表法
十字链表
邻接多重表
图的基本操作
6.3 图的遍历<br>√
广度优先搜索
类似于树的层序遍历
BFS算法的性能分析
无论是邻接表还是邻接矩阵，都需要辅助队列Q，<b>空间复杂度<span class="equation-text" contenteditable="false" data-index="0" data-equation="O(|V|)"><span></span><span></span></span></b>
<b>时间复杂度：</b><br><b>邻接表</b>存储图时，每个顶点需入队一次，每条边至少访问一次，<b>时间复杂度</b><span class="equation-text" contenteditable="false" data-index="0" data-equation="O(|V|+|E|)"><span></span><span></span></span><br><b>邻接矩阵</b>存储图时，查找每个顶点的邻接点所需时间O(|V|)，故<b>时间复杂度</b><span class="equation-text" data-index="1" data-equation="O(|V|^2)" contenteditable="false"><span></span><span></span></span>
BFS算法求解单源最短路径问题
广度优先的生成树和生成森林
由广度优先遍历确定的树
邻接表存储的图表示方式不唯一，遍历序列，生成树也不唯一
遍历非连通图可得广度优先生成森林
深度优先搜索
类似于树的先序遍历
DFS算法的性能分析
DFS算法是递归算法，需要借助递归工作栈，故<b>空间复杂度</b><span class="equation-text" contenteditable="false" data-index="0" data-equation="O(|V|)"><span></span><span></span></span>
<b>时间复杂度：</b><br>DFS遍历图的过程实际上是对每个顶点查找其邻接点的过程<br><b>邻接表</b>存储图时，访问顶点所需<span class="equation-text" data-index="0" data-equation="O(|V|)" contenteditable="false"><span></span><span></span></span>，查找所有顶点的邻接点所需<span class="equation-text" data-index="1" data-equation="O(|E|)" contenteditable="false"><span></span><span></span></span>，故总<b>时间复杂度</b><span class="equation-text" contenteditable="false" data-index="2" data-equation="O(|V|+|E|)"><span></span><span></span></span><br><b>邻接矩阵</b>存储图时，查找每个顶点的邻接点所需时间<span class="equation-text" data-index="3" data-equation="O(|V|)" contenteditable="false"><span></span><span></span></span>，故总的<b>时间复杂度</b><span class="equation-text" data-index="4" data-equation="O(|V|^2)" contenteditable="false"><span></span><span></span></span>
深度优先的生成树和生成森林
由深度优先遍历确定的树
邻接表存储图的表示方式不唯一，遍历序列，生成树也不唯一
遍历非连通图可得深度优先生成森林
图的遍历与图的连通性
无向图
DFS/BFS调用次数=连通分量数
有向图
若从起始顶点到其他顶点都有路径，则只需调用一次DFS/BFS函数
对于强连通图，从任意顶点出发都只需调用一次DFS/BFS函数
6.4 图的应用
最小生成树
Prim算法
Kruskal算法
最短路径
Dijkstra算法求单源最短路径问题
Floyd算法求各顶点之间的最短路径问题
有向无环图描述表达式
拓扑排序
关键路径
第7章 查找
7.1 查找的基本概念
7.2 顺序查找和折半查找
7.3 B树和B+树
7.4 散列表
第8章 排序
8.1 排序的基本概念
8.2 插入排序
8.3 交换排序
8.4 选择排序
8.5 归并排序和基数排序
8.6 各种内部排序算法的比较及应用
0 条评论
下一页
