数据结构
2021-09-02 00:14:02 219 举报AI智能生成
含有对应代码注解,考研和面试均可使用
作者其他创作
大纲/内容
树<br>
基本概念
高度
结点高度<br>
树的高度<br>
层数/深度
结点深度
树的深度<br>
祖先、子孙、兄弟、双亲；堂兄弟<br>
度
结点的度<br>
树的度<br>
结点
分支结点<br>
叶子结点<br>
有序树与无序树
路径和路径长度
路径
路径长度
森林
性质
结点与度数<br>
结点数(m)=非叶子结点数+叶子节点数
结点数 = Σ 度 x 个数 + 1【根】<br><span class="equation-text" data-index="0" data-equation="结点数m=\sum_{x=1}^n num_x*x +1" contenteditable="false"><span></span><span></span></span><br>
<span class="equation-text" data-index="0" data-equation="度 = 边 = \sum 直接子孩子个数" contenteditable="false"><span></span><span></span></span><br>
结点个数
<br><span class="equation-text" data-index="0" data-equation="度为m的第i层至多m^{i-1}个结点" contenteditable="false"><span></span><span></span></span>
高度为 h 的 m 叉树<font color="#B71C1C">至(最)多</font>结点数<br> <span class="equation-text" data-index="0" data-equation="\frac{m^h-1}{m-1}=1+m+...+m^{h-1}" contenteditable="false"><span></span><span></span></span>
sp: 高 h 的<b>二叉树</b>结点至多为 <span class="equation-text" data-index="0" data-equation="2^h-1" contenteditable="false"><span></span><span></span></span>
<b>偶数个结点</b>的二叉树，其 <b>度数为1</b> 的结点<b>个数</b>必然<b>为奇</b>数<br>
最小高度<br>
n 个结点的 <font color="#B71C1C">m阶树/m叉树/完全 m</font> 叉树 的高度 【必背】<br><span class="equation-text" data-index="0" data-equation="\left \lceil \log_m[n(m-1)+1] \right \rceil 或 \lfloor \log_m[n(m-1)]\rfloor+1" contenteditable="false"><span></span><span></span></span>
最大高度
n个结点，度为m的树最大高度<br><span class="equation-text" data-index="0" data-equation="h = n - m + 1" contenteditable="false"><span></span><span></span></span><br>
类型<br>
二叉树<br>
定义<br>
如果某结点只有一个子结点，则必为左孩子<br>
结点个数 <span class="equation-text" contenteditable="false" data-index="0" data-equation="n\geq 0"><span></span><span></span></span>,含有左右子树的有序树<br>
性质<br>
个数相关
叶子结点个数<br><span class="equation-text" contenteditable="false" data-index="0" data-equation="n_0=n_2+1"><span></span><span></span></span><br>
第k层最多结点数<br><span class="equation-text" data-index="0" data-equation="2^{k-1}" contenteditable="false"><span></span><span></span></span><br>
高度为h至多结点个数<br><span class="equation-text" data-index="0" data-equation="2^h-1" contenteditable="false"><span></span><span></span></span><br>
下标相关<br>
左右孩子<br>
i 结点的左孩子编号 = 2i
i 结点的右孩子编号 = 2i+1<br>
深度相关
结点所在深度<br>
<br><span class="equation-text" data-index="0" data-equation="\lfloor \log_2i\rfloor +1" contenteditable="false"><span></span><span></span></span>
完全二叉树】深度<br>
<br><span class="equation-text" data-index="0" data-equation="\lfloor \log_2n\rfloor +1" contenteditable="false"><span></span><span></span></span>
严格二叉树的最大深度
(n+1)/2
指针个数
n个节点的二叉链存储节点空指针个数为 n+1
遍历访问序
次序合法性
访问序确定二叉树形状
左必在右的前面被访问
前中后序的访问序列，叶子结点序列不变<br>
高度等于其结点数时，先序和后序遍历序列相反<br>
类型
满二叉树
定义<br><span class="equation-text" data-index="0" data-equation="高度为h,且含有2^h-1个结点的二叉树" contenteditable="false"><span></span><span></span></span>
完全二叉树<br>
定义<br>
<span class="equation-text" data-index="0" data-equation="i-1" contenteditable="false"><span></span><span></span></span> 层都是满的，同时第 <span class="equation-text" data-index="1" data-equation="i" contenteditable="false"><span></span><span></span></span> 层按照从左往右顺序填结点
每个结点都与高为 <span class="equation-text" data-index="0" data-equation="h" contenteditable="false"><span></span><span></span></span> 的满二叉树编号为 <span class="equation-text" data-index="1" data-equation="1\sim n" contenteditable="false"><span></span><span></span></span> 的结点位置一一对应<br>
性质
若一个结点没有左孩子，则其必然是叶结点<br>
叶子结点的双亲的左兄弟（若存在）则必然不是叶子结点<br>
高度为 h 的完全二叉树，节点个数最小为 <span class="equation-text" data-index="0" data-equation=" 2^{h-1}" contenteditable="false"><span></span><span></span></span><br>
最后一个分支 (非叶) 结点序号为<span class="equation-text" data-index="0" data-equation=" \lfloor x/2 \rfloor" contenteditable="false"><span></span><span></span></span><br>
若某完全二叉树有 <span class="equation-text" data-index="0" data-equation="x" contenteditable="false"><span></span><span></span></span> 个结点，则其叶子节点个数为 <span class="equation-text" data-index="1" data-equation="x - \lfloor x/2 \rfloor" contenteditable="false"><span></span><span></span></span>
计算<br>
第 x 层有 k 个叶子结点，<br>求结点个数max/min情况<br>
结点个数最少为：<span class="equation-text" data-index="0" data-equation="2^{x-1}+k" contenteditable="false"><span></span><span></span></span><br>结点个数最多为：<span class="equation-text" data-index="1" data-equation="2^{x+1}-1-2k" contenteditable="false"><span></span><span></span></span>
存储结构<br>
顺序存储<br>
链式存储
遍历
先/前序(NLR)
中序(LNR)
后序(LRN)<br>
树和森林
定义
度为m的树<span class="equation-text" contenteditable="false" data-index="0" data-equation="\neq"><span></span><span></span></span> m叉树
森林
存储结构<br>
双亲表示法<br>
顺序存储；存储地址=逻辑地址
孩子表示法<br>
邻接表存储；有向图存储结构
孩子兄弟/二叉树表示法
森林结点数
已知森林边和结点数，求森林中包含的树的个数<br>
森林和二叉树关系<br>
右孩子指针为空的结点个数
森林左子树结点数=森林第一棵树结点树
遍历以及有序树<br>
树：先根<br>
森林：先序<br>
二叉树：先序<br>
树：后根<br>
森林：后序
二叉树：中序<br>
树、森林和二叉树转换<br>
<br><span class="equation-text" data-index="0" data-equation="树 \leftrightarrow 二叉树" contenteditable="false"><span></span><span></span></span>
<br><span class="equation-text" data-index="0" data-equation="森林 \leftrightarrow 二叉树" contenteditable="false"><span></span><span></span></span>
遍历<br>
BFS广度优先搜索<br>
复杂度分析
生成树与生成森林
DFS深度优先搜索
遍历与连通性
递归与非递规转换
递归 = 栈<br>
层次遍历
辅助队列<br>
遍历序列构造二叉树
中序(必须)+先序/后续<br>
线索树遍历需要栈<br>
后序遍历<br>
求祖先到子孙的路径可以使用先/中序遍历<br>
已知次序求二叉树异构个数
应用<br>
哈夫曼树<br>
带权路径长度
<br><span class="equation-text" data-index="0" data-equation="WPL=\sum_{i=1}^n w_il_i" contenteditable="false"><span></span><span></span></span>
定义<br>
带权路径长度(WPL)最小的二叉树；也称最优二叉树<br>
度为 m 的哈夫曼树，为严格的 m 叉树<br>
构造
贪心，每次取两个权值最小的结点作为新结点的左右子树<br>新结点权值为左右子树和，并放入到可选择的结点集合中<br>
性质
<b>初始</b>结点<b>均为叶子</b>结点<br>
权值越小到根节点路径越长<br>
新建了n-1个结点，结点<b> 总数</b> 为 <b>2n-1</b>
度为m的哈夫曼树中，叶子结点为n，则其非叶子节点个数为 <span class="equation-text" data-index="0" data-equation="\lceil (n-1)/(m-1) \rceil" contenteditable="false"><span></span><span></span></span><br>
叶子结点个数即为不同符号的编码数
哈夫曼编码<br>
固定长度编码
每个字符用相等长度二进制位表示
前缀编码
没有一个编码是另一个编码的前缀
线索二叉树<br>
物理/存储结构<br>
标志域含义<br>
<span class="equation-text" contenteditable="false" data-index="0" data-equation="ltag=\begin{cases}0, lchild域指示左孩子\\1,lchild域指示前驱\end{cases}\\rtag=\begin{cases}0, rchild域指示右孩子\\1,rchild域指示后继\end{cases}"><span></span><span></span></span>
概念
线索<br>
线索化
相关问题
线索化后的空链个数
仍需要<b>栈支持</b>的<b>遍历</b>为<b> 后序线索树</b>
不是每个结点都能通过线索查找其前驱后继
已知后序线索二叉树，求<b>后序后继</b>仍不能完全求解<br>
二叉搜索树 BST<br>
定义
操作
插入
查找
递归实现
非递归实现<br>
删除
叶结点<br>直接删除<br>
x 只有一个左/右子树<br>子结点接上其父节点<br>
x 有左右两棵子树<br>补前驱后继<br>
构造<br>
性质
删除某节点后将其插入，则前后排序树有可能不同<br>
题目计算
ASL(平均查找长度）
成功查找长度<br>
失败查找长度
递增序列遍历=中序遍历
非法查找路径序列
平衡二叉树AVL
平衡机制
平衡因子
操作原理
插入/删除
旋转
旋转要点
调整<font color="#B71C1C">最小不平衡子树</font>
LL,RR 旋一次，LR,RL 旋两次（先内后外）<br>
左重顺旋减轻左深，右重逆旋减轻右深<br>
根连前驱后继【按照数值大小比较连接】<br>
旋转方式<br>
LL(左孩子左子树)<br>
左子树旋转，降低一层就平衡<br>
RR(右孩子右子树)
LR(左孩子右子树)<br>
<br>
RL(右孩子左子树)
计算<br>
构造一棵高为 h 的 AVL 所需要的最少结点数
已知共有 n 个结点的 AVL，求其最大深度
已知AVL的高度为 n,且所有非叶子结点的平衡因子为 1,求结点总数 <br><span class="equation-text" data-index="0" data-equation="n_0 = 0, n_1 = 1,n_2 = 2 , n_h = 1+n_{h-1}+n_{h-2}" contenteditable="false"><span></span><span></span></span><br>
并查集
操作<br>
合并 Union<br>
寻找祖先 Find(S,x)<br>
初始化 Init(S)<br>
图
相关概念
有向图
弧头(顶点)
弧尾(顶点)
无向图
简单图、多重图
简单图：无自环，无重复边<br>
多重图：有自环，重复边<br>
完全图
简单图的边数达到上限<br>
子图
边和顶点均为子集且能够形成一张图<br>
连通、连通图和连通分量<br>
<b>连通</b>：u,v之间存在路径<br>
<b>连通图</b>：图中任意两点均连通<br>
<b>连通分量：</b>无向图中<b>极大连通子图</b><br>
<br><span class="equation-text" data-index="0" data-equation="无向图任意连通的最少边数=\frac{(n-1)*(n-2)}{2}+1" contenteditable="false"><span></span><span></span></span>
强连通、强连通分量<br>
<b>强连通</b>:有向图中的u,v互相可达
<b>强连通图：</b>有向图中任意两点互相可达<br>
<b>强连通分量：</b>有向图中极大墙连通子图<br>
生成树、生成森林
<b>生成树</b>：包含图中全部顶点的一个<b>极小连通子图</b><br>
<b>生成森林</b>：非连通图中连通分量的生成树构成了生成森林
极小连通子图：保持图的联通性，又使得边数尽可能少<br>
顶点度，入度和出度
<b>顶点度</b>：无向图中顶点所连边数
边的权和网
网：带权图<br>
稠密图、稀疏图
路径、路径长度和回路
路径：顶点序列【由顶点和相邻顶点序偶构成的边所形成的序列】<br>
回路/环：路径中第一个和最后一个顶点相同
简单路径、简单回路
距离<br>
有向树
无向图森林
n个顶点，e条边的无向图森林树的个数<br>
存储结构
稀疏矩阵<br>
十字链表
邻接表法
邻接多重表
稠密矩阵<br>
邻接矩阵
有向图
无向图
性质
<br><span class="equation-text" data-index="0" data-equation="A^n[i][j] 表示顶点i到j路径长度为n的数目;\\ A^n表示邻接矩阵次幂运算结果" contenteditable="false"><span></span><span></span></span>
遍历<br>
广搜bfs<br>
深搜dfs
应用
最小生成树
Prim算法<br>
Kruskal算法<br>
最短路径
Dijkstra<br>
Floyd
有向无环图表达式
拓扑排序
AOV网
有序序列个数
关键路径
AOE网
事件最早发生时间
事件最迟发生时间
活动最早开始事件
活动最晚开始时间
时间余量<br>
排序
基本概念
关键字有序过程
稳定性
具体<b>元素未知</b>，<b>至少</b>比较次数
趟
排序过程中，对尚未确定最终位置的所有元素进行一遍处理<br>
内部排序<br>
常见类型<br>
插入排序<br>
直接插入
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n^2)【平均】 O(n^2)【最坏】 O(n)【最好】" contenteditable="false"><span></span><span></span></span>
稳定排序
特点<br>
每一次排序完后，前i位有序，i位以后也可能存在使得原i位发生改变的值
折半插入
对已排好序列查找部分使用折半搜索<br>
顺序存储<br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n^2)" contenteditable="false"><span></span><span></span></span>
稳定排序
希尔排序<br>
算法描述<br>选定增量d，将原序列分成几个部分，然后对每个部分进行插入排序<br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n^2)" contenteditable="false"><span></span><span></span></span>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(1)" contenteditable="false"><span></span><span></span></span>
不稳定排序【分组原因】
交换排序
冒泡排序
算法描述【最大泡泡冒起来】<br><b>每一次</b>排序将最小/<b>最大</b>的元素，通过依次遍历比较交换，<b>放到</b>序列<b>末尾/队首最终位置</b><br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="\frac{n(n-1)}{n}= O(n^2)【平均】 O(n^2)【最坏】 O(n)【最好】" contenteditable="false"><span></span><span></span></span><br>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(1)" contenteditable="false"><span></span><span></span></span><br>
稳定排序<br>
特点<br>
前i位或者后i位(根据顺序或逆序)为最终有序排序
快速排序
基于分治思想【二分】<br>
时间复杂度【与递归栈的深度有关】<br><span class="equation-text" data-index="0" data-equation="O(n\log_2 n)【平均】；O(n^2)【最坏】" contenteditable="false"><span></span><span></span></span><br>
空间复杂度【栈深】<br><span class="equation-text" data-index="0" data-equation="O(\log_2n)【平均】O(n)【最坏】" contenteditable="false"><span></span><span></span></span><br>
特点<br>
某个值的左边均为小于它的值，右边均为大于它的值
当序列基本有序或者逆序情况下，效率最低：受不平衡划分影响
真题<br>
2014) 对 15 个元素进行快排，则比较元素次数最少是<br>
选择排序
简单选择<br>
算法描述<br>每趟找到后n-i个元素中，关键字最小的元素，并与第i个元素进行交换<br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n^2)【平均】 O(n^2)【最坏】 O(n^2)【最好】" contenteditable="false"><span></span><span></span></span><br>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(1)" contenteditable="false"><span></span><span></span></span><br>
不稳定排序【多个最小取最后遍历位置】<br>
特点
前i位或者后i位(根据顺序或逆序)为最终有序排序
堆排序
算法描述<br>二叉堆：完全二叉树，左右子树<br>均小于/大于根结点【小/大顶堆】<br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n\log_2 n)【平均/最坏/最好排序】;\\O(h)【调整】;O(n)【建堆】" contenteditable="false"><span></span><span></span></span><br>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(1)" contenteditable="false"><span></span><span></span></span><br>
建堆时间【计算补充】<br><span class="equation-text" data-index="0" data-equation="s = 1 * 2^{(H-1)} + 2 * 2^{(H-2)}+ ... + {(H-1)} * 2^1 + H * 2^0=2N - 2 - log2(N)=O(N)" contenteditable="false"><span></span><span></span></span><br>
特点<br>
最后一个非叶子结点位置为len/2【根结点下标为1】<br>
不稳定排序【调整时可能调节后面位置到根】<br>
归并排序
算法描述<br>二路归并算法：初始每个子表长度为1，然后不断两两合并排序，最终合并成长为n的有序序列<br>
时间复杂度 【与序列初始状态无关】<br><span class="equation-text" data-index="0" data-equation="O(n\log_2n)【二路归并】O(Nlog_kN)【k路归并】" contenteditable="false"><span></span><span></span></span><br>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(n)" contenteditable="false"><span></span><span></span></span><br>
稳定排序
特点<br>
当有足够大到内存装不下的文件进行排序时，采用分治的归并排序<br>
基数排序
算法描述<br>基于关键字位上数字大小进行逐一排序<br>
时间复杂度<br><span class="equation-text" data-index="0" data-equation="O(d(n+r))【分配为n】收集为【r】" contenteditable="false"><span></span><span></span></span>
空间复杂度<br><span class="equation-text" data-index="0" data-equation="O(r)" contenteditable="false"><span></span><span></span></span>
常见关键字排序<br>
最高位优先 MSD<br>
最低位优先 LSD<br>
稳定排序<br>
排序比较
时间复杂度<br>
有序情况下<br>
直接插入、冒泡排序<br><span class="equation-text" data-index="0" data-equation="O(n)" contenteditable="false"><span></span><span></span></span><br>
快排<br><span class="equation-text" data-index="0" data-equation="O(n^2)" contenteditable="false"><span></span><span></span></span><br>
无序情况下【平均】<br>
简单选择、直接插入、冒泡排序<br><span class="equation-text" data-index="0" data-equation="O(n^2)" contenteditable="false"><span></span><span></span></span>
堆排，快排、归并<br><span class="equation-text" data-index="0" data-equation="O(n\log n)" contenteditable="false"><span></span><span></span></span><br>
空间复杂度
简单选择、插入、冒泡、希尔、堆排 <span class="equation-text" data-index="0" data-equation="O(1)" contenteditable="false"><span></span><span></span></span><br>
快排<br><span class="equation-text" data-index="0" data-equation="O(\log_2n)【平均】O(n)【最坏】" contenteditable="false"><span></span><span></span></span><br>
归并<br><span class="equation-text" data-index="0" data-equation="O(n)" contenteditable="false"><span></span><span></span></span><br>
算法稳定性
稳定排序
不稳定排序
存储结构影响<br>
顺序存储<br>
链式存储
算法过程特征
【<b>每趟</b>排序能够得到<b>至少一个</b><font color="#B71C1C">最终有序序</font>】
堆排序，快速排序、简单选择、冒泡排序
【比较次数与初始序列】<br>
无关<br>二路归并排序、简单选择排序、基数排序
有关<br>快速排序、直接插入排序、冒泡排序、堆排序、希尔排序
【排序趟数与初始序列】<br>
无关<br>直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序
有关<br>冒泡排序、快速排序
外部排序
基本概念<br>
一般方法<br>归并排序法<br>
外部排序总时间 = 内存排序时间 + 外存信息读写时间 + 内部归并所需时间<br>
归并躺数 = 树的高度 = <span class="equation-text" data-index="0" data-equation="\lfloor \log_kr \rfloor" contenteditable="false"><span></span><span></span></span><br>
归并总比较次数 =<span class="equation-text" data-index="0" data-equation=" \sum 每趟次数" contenteditable="false"><span></span><span></span></span><br><span class="equation-text" data-index="1" data-equation=" S(n-1)(k-1) " contenteditable="false"><span></span><span></span></span>= <span class="equation-text" data-index="2" data-equation="\lfloor \log_kr \rfloor(n-1)(k-1)=[\lfloor \log_2r \rfloor/\lfloor \log_2k \rfloor](n-1)(k-1)" contenteditable="false"><span></span><span></span></span><br>
I/O 操作次数<br>读入归并段，写入归并段（以块为单位）<br>
图解
初始序列为12个无序数据<br>
把内存数据划分为多个块，首先对块内进行排序，形成有序字串
将两个已经排序好的子块进行归并成一个更大的块【二路归并】
继续将小的归并段合并为更大的归并段<br>
多路平衡归并与败者树<br>
k 路平衡归并<br>
最多只能有 k 个段归并为一个
每一趟中，若有m个块进行归并，则一趟处理得到<span class="equation-text" data-index="0" data-equation=" \lceil m/k \rceil " contenteditable="false"><span></span><span></span></span>个块<br>
胜者树/败者树<br>
胜者树
败者树
利用败者树加快排序
置换-选择排序<br>
原理<br>
初始段建立图解<br>
每组划分6个元素，则初始组数至少划分4组<br>
选择出第一个 MINIMAX 29<br>
选择比初始段中更大的 MINIMAX 38<br>
同理
直到无 MINIMAX 选出，此时认为初始段已经完成<br>
败者树利用
最佳归并树<br>
原理
附加虚短的最佳归并树
额外补充虚断数<br><span class="equation-text" data-index="0" data-equation="k-(m-1)\%(k-1)-1" contenteditable="false"><span></span><span></span></span><br>
C11语法
typedef 关键字<br>
struct 结构体<br>
语法
不带 typedef 标签
带 typedef 标签
错误语法
结构体嵌套
自引用<br>
相互引用
C与C++中 struct 区别
指针 T *t<br>
地址与值<br>
& 取地址/引用(别名)
绪论<br>
算法<br>
算法定义<br>
问题求解步骤描述<br>
五个特性
有穷性<br>
确定性<br>
可行性
输入
输出
复杂度计算<br>
时间复杂度
加法规则<br><span class="equation-text" data-index="0" data-equation="T(n)=T_1(n)+T_2(n)=O(f(x)+g(x))=O(max(f(n),g(n))" contenteditable="false"><span></span><span></span></span>
乘法规则<br><span class="equation-text" data-index="0" data-equation="T(n)=O(f(n)\times g(n))" contenteditable="false"><span></span><span></span></span>
常见渐进时间复杂度<br><span class="equation-text" data-index="0" data-equation="1<\log_2n【即\log n】<n<n\log n<n^2<n^3<2^n<n!<n^n" contenteditable="false"><span></span><span></span></span>
等差等比公式<br>
空间复杂度<br>
定义<br>辅助空间大小与原数据量之间的关系
原地工作<br><span class="equation-text" data-index="0" data-equation="O(1)： 所需辅助空间是固定的值(常量)" contenteditable="false"><span></span><span></span></span><br>
求解问题<br>
递归算法<br>
递推公式<br>
递归调用
递归公出口<br>
列方程法<br>
数据
数据对象<br>
数据元素
(个体)基本单位
数据项<br>
(个体)属性<br>
数据类型<br>
原子类型
结构类型<br>
抽象数据类型(ADT)<br>
数据结构
三要素
逻辑结构
线性结构<br>
一般线性表<br>
受限线性表
栈
队列
串
线性表推广
数组<br>
非线性结构<br>
树
二叉树<br>
多叉树<br>
森林<br>
图/网
有向图
无向图
集合<br>
存储结构<br>
顺序存储<br>
链式存储<br>
索引存储<br>
散列存储/哈希存储
数据运算(操作)<br>
Linear List<br>线性表<br>
定义/概念<br>
<b>有限个</b>数据元素<b>，相同</b>数据类型<b>，且有序</b><br>
存储空间大小相同<br>
表头元素；表尾元素；位序； 前驱；后继<br>
操作<br>
创建/销毁
静态分配<br>
动态分配
C/C++<br>malloc , new[]<br>
增删改查<br>
属性获取<br>
存储结构<br>
sequential mapping<br>顺序存储<br>
SqList<br>顺序表<br>
特性<br>
<b>随机存取</b>[物理顺序和逻辑顺序相同]<br>
删除和插入时间复杂度高<br>
分配方式
静态
C语言数组方式分配<br>
动态
C语言指针方式分配<br><span class="equation-text" data-index="0" data-equation="(*Elem)malloc(Length*sizeof(Elem))" contenteditable="false"><span></span><span></span></span>
操作<br>
初始化<br>
插入
实现逻辑<br>
健壮性判断<br>
移动<br>
属性修改<br>
返回函数状态
时间复杂度<br>
最好<br>O(1)<br>
最坏<br>O(n)<br>
平均 = 概率 <span class="equation-text" data-index="0" data-equation="\times" contenteditable="false"><span></span><span></span></span> 移动次数 = 期望<br><span class="equation-text" data-index="1" data-equation=" \sum_{i=1}^{n+1} \frac{1}{n+1}(n-i+1)=\frac{n}{2}= O(n)" contenteditable="false"><span></span><span></span></span>
删除
实现逻辑
健壮性<br>
移动<br>
属性修改
返回函数状态
时间复杂度
最好<br>O(1)<br>
最坏<br>O(n)<br>
平均<br><span class="equation-text" data-index="0" data-equation=" \sum_{i=1}^{n} \frac{1}{n}(n-i)=\frac{n-1}{2}= O(n)" contenteditable="false"><span></span><span></span></span><br>
按值查找<br>
实现逻辑
顺序寻找<br>
返回位序<br>
时间复杂度
最好<br>O(1)<br>
最坏<br>O(n)<br>
平均<br><span class="equation-text" data-index="0" data-equation=" \sum_{i=1}^{n} \frac{1}{n}\times i=\frac{n+1}{2}= O(n)" contenteditable="false"><span></span><span></span></span>
合并
真题<br>
2010】408<br>整数数组循环左移<br>
2011】408<br>找出两个等长升序序列的中位数<br>
2013】408<br>找出序列中的主元素<br>主元素：个数 > 序列总个数/2<br>
2018】408<br>求最小未出现整数<br>
2020】408<br>求三元组最小距离<br>
链式存储<br>
单链表<br>
定义<br>
操作<br>
插入<br>
头插法<br>
尾插法
时间复杂度<br>O(n)<br>
删除
按值查找<br>
判空
双链表<br>
定义<br>
操作<br>
插入
实现逻辑<br>
时间复杂度<br>
删除
循环链表<br>
单向循环链表
双向循环链表
静态链表
跳跃表
相关概念
头结点<br>
头指针<br>
链表头
首元结点
尾指针<br>
真题
2009】408<br>查找只含头结点的单链表中倒数第k位置的结点值<br>
2012】408<br>求出某两个链表共同后缀起始位置<br>
2015】408<br>单链表中保留所有绝对值相等节点中, 第一个出现位置的结点<br>
2019】408<br>对单链表进行重排<br>
优缺点<br>
顺序<br>
随机访问，链式则只能顺序访问<br>
链式<br>
分配灵活，无需占用连续空间，插入删除时间复杂度低<br>
逻辑结构<br>
栈(Stack)<br>
定义
栈顶(top)<br>
栈低(Bottom)<br>
空栈(Empty)<br>
特性<br>LIFO 后进先出<br>
数学性质 [ 卡特兰数 ]<br>n 个不同元素进栈，出栈元素不同的排列个数为<span class="equation-text" data-index="0" data-equation="\frac{1}{n+1}C_{2n}^n" contenteditable="false"><span></span><span></span></span><br>
操作<br>
初始化<br>Init (&S)
销毁<br>Destroy(&S)
进栈(Push)<br>Push(&S,&e)
出栈<br>Pop(&S,&e)
读取栈顶<br>GetTop(S,&e)
判空<br>IsEmpty<br>
存储结构<br>
顺序
顺序栈<br>
共享栈
链式
链栈<br>
操作
属性
表头结点
表尾结点
应用题型
括号匹配
表达式求值<br>
前缀/波兰表达式
中缀<br>
后缀/逆波兰表达式<br>
转换方法<br>
计算方法
表达式树<br>
递归调用<br>
时间复杂度计算
dfs广搜
出栈序列
不可能序列<br>
序列种类数<br>
卡特兰数: <span class="equation-text" data-index="0" data-equation="\frac{1}{n+1}C_{2n}^n" contenteditable="false"><span></span><span></span></span>
可能序列
数值转换<br>
栈的最小深度
函数局部变量存储<br>
队列/Queue<br>
基本操作
FIFO<br>
初始化<br>
销毁
判空<br>
入队<br>
出队
读取队头元素<br>
概念<br>
队头指针<br>
队尾指针
头结点<br>
存储结构<br>
顺序<br>
循环队列<br>
顺序存储
链式<br>
双端队列
链式存储
定义
操作
逻辑结构<br>
应用<br>
二叉树层次遍历<br>
出队序列计算<br>
做题时可标注左右进入的序列<br><span class="equation-text" data-index="0" data-equation="\overrightarrow{4}\overrightarrow{2}\overrightarrow{1}\overleftarrow{3}\overleftarrow{5}【由单项出队可得固定序列】" contenteditable="false"><span></span><span></span></span><br>
FIFO性质
OS缓冲区<br>
CPU资源分配<br>
页面替换算法
数组矩阵<br>
数组<br>
定义
存储结构<br>
行优先
列优先
特殊矩阵
对称矩阵<br>
下标转换公式<br><span class="equation-text" data-index="0" data-equation="k=\begin{cases}\frac{i(i-1)}{2}+j-1, i\geq j(下三角+主对角)\\\frac{j(j-1)}{2}+i-1, j\geq i ,a(i,j)=a(j,i)\end{cases}" contenteditable="false"><span></span><span></span></span><br>
三角矩阵<br>
下标转换<br><span class="equation-text" data-index="0" data-equation="k=\begin{cases}\frac{i(i-1)}{2}+j-1, i\geq j(下三角+主对角)\\\frac{n(n+1)}{2},值为c\end{cases}" contenteditable="false"><span></span><span></span></span><br>
三对角矩阵<br>
下标转换<br><span class="equation-text" data-index="0" data-equation="k=2i+j-3 (下标从0开始)" contenteditable="false"><span></span><span></span></span><br>
稀疏矩阵<br>
三元组
十字链表<br>
疏密矩阵
邻接矩阵
真题
矩阵元素下表与一位数组下标换算<br>
地址求行长<br>
串<br>
基本概念<br>
子串
主串<br>
位置<br>
存储结构<br>
定长顺序存储
堆分配存储
块链存储<br>
相关运算
模式匹配
暴力匹配<br>
KMP算法
next数组
next手工算法
相等判断
求子串
连接
长度
查找<br>
效率指标
平均查找长度<br>
查找成功
查找失败
概念
查找表/查找结构
操作<br>
查找特定元素<br>
检查满足条件元素属性<br>
插入元素<br>
删除元素<br>
静态查找表
顺序<br>
折半
散列
动态查找表
二叉排序树<br>
AVL平衡二叉树
B树
平均查找长度
<br><span class="equation-text" data-index="0" data-equation="ASL=\sum_{i=1}^nP_iC_i" contenteditable="false"><span></span><span></span></span>
冲突/碰撞
同义词之间冲突
不可能避免<br>
聚集/堆积
同义词与非同义词发生冲突
主要与冲突探测方法有关<br>
散列结构
散列函数<br>
直接定址法
<br><span class="equation-text" data-index="0" data-equation="H(key)=a*key+b" contenteditable="false"><span></span><span></span></span>
除留余数法<br>
<br><span class="equation-text" data-index="0" data-equation="H(key)=key%p" contenteditable="false"><span></span><span></span></span>
数字分析法
平方取中法
冲突处理
开放定址法<br>
线性探测再散列
二次探测再散列
伪随机探测再散列<br>
链地址法/拉链法<br>
再哈希(散列)法<br>
平均查找长度
查找成功<br>
查找失败<br>
装填因子<br>
a= 表中记录数/散列表长度
线性结构<br>
顺序查找(链式限制)
一般顺序表查找
有序表顺序查找<br>
折半(二分)查找<br>
适用于有序顺序存储结构
折半查找<b>判定树</b><br>
类型：平衡二叉树
n 个元素时的树高 h<br><span class="equation-text" data-index="0" data-equation="h=\left \lceil \log_2^{(n+1)} \right \rceil" contenteditable="false"><span></span><span></span></span><br>
判定树是否复合规则判断<br>
最多查找次数<br>
最少查找次数
<span class="equation-text" data-index="0" data-equation="ASL=\log_2^{(n+1)}-1" contenteditable="false"><span></span><span></span></span>
分块(索引顺序)查找
理想块长
<br><span class="equation-text" data-index="0" data-equation="\sqrt n" contenteditable="false"><span></span><span></span></span>
顺序分块查找<br>
<br><span class="equation-text" data-index="0" data-equation="ASL =(b+1)/2+(s+1)/2=(s^2+2s+n)/2s" contenteditable="false"><span></span><span></span></span>
最优优化<br>
<br><span class="equation-text" data-index="0" data-equation="ASL=\log_2^{(b+1)}+(s+1)/2" contenteditable="false"><span></span><span></span></span>
索引结构/树表<br>
B树<br>
属性<br>
B树的阶<br>
非叶结点结构
<br><span class="equation-text" data-index="0" data-equation="(n,P_0,K_1,P_1,...,K_n,P_n)" contenteditable="false"><span></span><span></span></span>
所有结点平衡因子为 0 【高度平衡】<br>
高度<br>
最高<br>
<br><span class="equation-text" data-index="0" data-equation="H \leq \log_{\lceil m/2 \rceil}^{(n+1)/2}+1" contenteditable="false"><span></span><span></span></span>
最低
<br><span class="equation-text" data-index="0" data-equation="h\geq \log_m^{(n+1)}" contenteditable="false"><span></span><span></span></span>
关键字数<br>
最多
<span class="equation-text" data-index="0" data-equation="n\leq m^{h}-1" contenteditable="false"><span></span><span></span></span>
最少
<br><span class="equation-text" data-index="0" data-equation="n \geq \lfloor n/2 \rfloor^{h-1}" contenteditable="false"><span></span><span></span></span>
性质
非根结点关键字个数<br><span class="equation-text" data-index="0" data-equation="(\left \lceil m/2 \right \rceil-1\leq n \leq m-1)" contenteditable="false"><span></span><span></span></span>
非根结点子树个数<br><span class="equation-text" data-index="0" data-equation="(\left \lceil m/2 \right \rceil\leq n \leq m)" contenteditable="false"><span></span><span></span></span><br>
根节点为非终端结点时，至少有两个孩子.
严格平衡查找树，所有节点子树高度一致<br>叶子处于同一层且用NULL表示<br>
非叶结点的结构<br><span class="equation-text" data-index="0" data-equation="|n【子结点个数】|P_0|K_1|P_1|...|K_n|P_n|" contenteditable="false"><span></span><span></span></span>
操作
查找
插入
分裂
<br>
删除
合并
<br>
图示<br>
<br>
计算<br>
已知阶、层数、某层关键字数，求最多结点数<br>
B+树<br>
图示
<br>
B与B+树区别<br>
红黑树
定义
性质
应用<br>
基本操作
变色<br>
旋转
插入<br>
插入调整<br>
删除
删除调整
935考纲对比<br>
2022】<br>一、线性表<br> (一) 线性表的定义和基本操作<br> (二) 线性表的实现<br> 1. 顺序存储结构<br> 2. 链式存储结构<br> 3. 线性表的应用<br> 二、栈、队列和数组<br> (一) 栈和队列的基本概念<br> (二) 栈和队列的顺序存储结构<br> (三) 栈和队列的链式存储结构<br> (四) 栈和队列的应用<br> (五) 【<b>多维数组的存储</b>】和特殊矩阵的压缩存储<br> 三、树与二叉树<br> (一) 树的基本概念<br> (二) 二叉树<br> 1. 二叉树的定义及其主要特征<br> 2. 二叉树的顺序存储结构和链式存储结构<br> 3. 二叉树的遍历<br> 4. 线索二叉树的基本概念和构造<br> (三) 树、森林<br> 1. 树的存储结构<br> 2. 森林与二叉树的转换<br> 3. 树和森林的遍历<br>(四) 树和二叉树的应用<br>1. 二叉搜索树<br> 2. 平衡二叉树<br>3. 哈夫曼(Huffman)树和哈夫曼编码<br>4. 【<b>并查集</b>】<br> 三、图<br> (一) 图的概念<br> (二) 图的存储及基本操作<br> 1. 邻接矩阵法<br> 2. 邻接表法<br> (三) 图的遍历<br> 1. 深度优先搜索<br> 2. 广度优先搜索<br>(四) 图的基本应用<br> 1. 最小(代价)生成树<br> 2. 最短路径<br> 3. 拓扑排序<br> 4. 关键路径<br> 四、查找<br> (一) 查找的基本概念<br> (二) 顺序查找法<br>(三) 【<b>分块查找法</b>】<br>(四) 折半查找法<br> (五) B-树及其基本操作、B+树的基本概念<br>(六) 散列(Hash)表<br> (七) 查找算法的分析及应用<br> 五、排序<br> (一) 排序的基本概念<br> (二) 插入排序<br> 1. 直接插入排序<br> 2. 折半插入排序<br> (三) 冒泡排序(bubble sort)<br> (四) 简单选择排序<br> (五) 希尔排序(shell sort)<br> (六) 快速排序<br> (七) 堆排序<br> (八) 二路归并排序(merge sort)<br>(九) 基数排序<br>(十) 【<b>外部排序</b>】<br> (十一) 各种排序算法的比较<br> (十二) 排序算法的应用<br>
2021】<br>一、线性表<br> (一) 线性表的定义和基本操作<br> (二) 线性表的实现<br> 1. 顺序存储结构<br> 2. 链式存储结构<br> 3. 线性表的应用<br> 二、栈、队列和数组<br> (一) 栈和队列的基本概念<br> (二) 栈和队列的顺序存储结构<br> (三) 栈和队列的链式存储结构<br> (四) 栈和队列的应用<br> (五) 特殊矩阵的压缩存储<br> 三、树与二叉树<br> (一) 树的基本概念<br> (二) 二叉树<br> 1. 二叉树的定义及其主要特征<br> 2. 二叉树的顺序存储结构和链式存储结构<br> 3. 二叉树的遍历<br> 4. 线索二叉树的基本概念和构造<br> (三) 树、森林<br> 1. 树的存储结构<br> 2. 森林与二叉树的转换<br> 3. 树和森林的遍历<br>(四) 树和二叉树的应用<br>1. 二叉排序树<br> 2. 平衡二叉树<br> 3. 哈夫曼(Huffman)树和哈夫曼编码<br> 三、图<br> (一) 图的概念<br> (二) 图的存储及基本操作<br> 1. 邻接矩阵法<br> 2. 邻接表法<br> (三) 图的遍历<br> 1. 深度优先搜索<br> 2. 广度优先搜索<br>(四) 图的基本应用<br> 1. 最小(代价)生成树<br> 2. 最短路径<br> 3. 拓扑排序<br> 4. 关键路径<br> 四、查找<br> (一) 查找的基本概念<br> (二) 顺序查找法<br> (三) 折半查找法<br> (四) B-树及其基本操作、B+树的基本概念<br>(五) 散列(Hash)表<br> (六) 查找算法的分析及应用<br> 五、内部排序<br> (一) 排序的基本概念<br> (二) 插入排序<br> 1. 直接插入排序<br> 2. 折半插入排序<br> (三) 冒泡排序(bubble sort)<br> (四) 简单选择排序<br> (五) 希尔排序(shell sort)<br> (六) 快速排序<br> (七) 堆排序<br> (八) 二路归并排序(merge sort)<br> (九) 基数排序<br> (十) 各种内部排序算法的比较<br> (十一) 内部排序算法的应用<br>
0 条评论
下一页
