导图社区 数据结构王道细节知识点整理
包含对考研数据结构王道内习题细节的归纳与若干二级结论的思考归纳与总结，非常实用。
下图对于王道二刷的题目细节整理，包含新大纲知识点，王道选择题和大题两个模块，结合了暑期强化直播，对各个题目的细节归纳总结。
王道计网习题的若干细节总结（包括王道视频讲解的补充，课本有但王道没有且属于考试范围的内容，解题的二级结论等秒杀方法）
王道操作系统之文件系统思维导图，有助于帮助您熟悉知识要点，加强记忆。有需要的同学，可以收藏下哟。
社区模板帮助中心，点此进入>>
安全教育的重要性
个人日常活动安排思维导图
西游记主要人物性格分析
17种头脑风暴法
马克思主义原理
如何令自己更快乐
头脑风暴法四个原则
思维导图
考研数学重点考点知识总结归纳！
数据结构
数据结构王道
第一章-大纲
习题细节
时间复杂度是考虑最坏情况下的，因此O(n)永远比O(n²)快，不管n有多特殊
递归的时间复杂度要看递归的次数和每次递归干了什么
算法原地工作：算法所需的辅助空间是常量
第二章-线性表
知识细节
顺序表是随机存取的
理解存取的意思
存：改变A[i]=n
取：return A[i]
顺序表比链表交换元素快
对于链表，包括找到第i个元素的访问，自然慢
单链表删除结点的O(1)方法
交换前后元素，再指向后后
P31
循环单链表在表尾设置指针，对于操作表头和表尾都只需要O(1) 而在表头设置指针，当访问表尾的时候需要O(n)
题目辨析
经典错误
顺序存储只能存储线性结构
树和图也可
s->next=L.next L.next=s
不能倒转过来
但若L和其前驱结点是两个指针表示，就可倒过来
易混点
若要删除尾结点，应当选用带头节点的双循环链表
这里不考虑不用前驱结点的删除方式，所以默认 要找到尾结点的前驱结点，这时候若采用 带尾指针的单向链表则不行
单链表的长度为0的头节点head->next=NULL
第三章-栈和队列
出栈排列个数
卡特兰数
(Cn`2n)/（n+1）
逻辑结构分为线性和非线性
栈和队列的逻辑结构一样
都是受限线性表
栈只可能发生上溢
栈指针超出最大范围
非递归不一定要用栈
斐波那契用循环实现
循环队列
对于求元素个数
(rear+maxsize-front)%maxsize的适用情况
队头指向首元素前，且队尾指向尾元素
队头指向首元素，且队尾指向尾元素后
若队头指向首元素，且队尾指向尾元素
元素个数为(rear+maxsize-front)%maxsize+1
理解队空和队满的判断
一刷选了C，但当只有一个元素的时候，也满足C，故错误
链表队列
最优结构
带队首指针和队尾指针的循环单链表
带队尾指针的循环单链表
队头一定在链头，因为总是从队头出队
队首指向队尾
题目一般不考虑交换值的骚操作，不然无解
若队头在表尾，约定俗成队尾在表头
头指针是队列的第一个元素，队头指针不一定在第一个
栈的中缀表达式转后缀表达式 P90 T11,12
一坨 （op）一坨
分析栈的操作符 看该坨左边的符号
对于d
此时d属于（c+d）这坨
涉及到（，+
对于（c+d）
此时涉及到（（c+d）/e-f）
涉及到（
对于（（c+d）/e-f）
此时涉及到a*（（c+d）/e-f）
涉及到*
对于a*（（c+d）/e-f）
涉及到b-a*（（c+d）/e-f）
涉及到-
特殊矩阵计算
三对角
i,j从1开始算，B[k]从0开始算
2i+j-3
稀疏矩阵存储结构
三元组
行
列
值
十字链表
第四章-串
解题细节
算next和nextval数组的前两个都是0和1
算next时候有时候前两个用-1和0表示，看具体题目
算nextval的时候，如果递归一次的值仍然和原来一样，直接等于递归一次对应的nextval值，不用继续递归第二次
因为递归的值已经保证了不会再出现重复的现象
见P112 T7
第五章-树与二叉树
P123 完全二叉树有很多二级结论，但现场推即可
脑子要构建出完全二叉树的图，然后记住左边一列是1，2，4，8
构建n与高度与结点个数的关系
构建[n/2]以上都是叶子结点
左孩子偶数，右孩子奇数
用顺序存储则必须从1开始
线索二叉树
先序线索树：C找不到前驱A
后序线索树：C找不到后继A
原因都是因为C结点的左右链域都满了
rflag为0必有右孩子，rchild必不为NULL
为1的时候其rchild可能为NULL,可能指向其后继
二叉树是逻辑结构
线索二叉树是存储（物理）结构
如果给定一个先序序列abcd，相当于入栈顺序确定了，则中序序列的种类相当于出栈顺序
区分清楚二叉排序树和线索二叉树
二叉排序树（BST，二叉查找树，二叉搜索树）
删除后再插入可能跟原本不同
ASL的计算方法等同各个高度的加权平均
最差的复杂度是O（n）
所有度对应的边的个数的和（1*n1+2*n2）+1(根节点)=所有结点n
n个结点的二叉链表有n+1个空链区域
因为一个链相当于一条边，占用一个域，共有n-1条链
共有2n个区域
减一下
n0=n2+1
偶数个结点的二叉树只有奇数个n1结点
n0+n1+n2= 2*n0+n1 -1= n
n为奇数，n1=0
n为偶数，n1=1
二级结论！ n1仅由n决定，与n0，n2无关！
二叉树顺序存储需要存储对应高度下的满二叉树的个数
如高度为5，则存1+2+4+8+16=31个空间
完全二叉树的叶子结点相关题目
算完全二叉树的叶子结点
先算最深层次的结点个数
再算其父亲的个数
再算父亲那层的叶子结点
P126 T13,14
等于n-【结点个数/2】
因为完全二叉树的特性是一半以及下界（奇数的时候）都不是叶子结点
告诉第k层叶子结点个数
可能是第k层是最底层
可能还有第k+1层
此时第k层是满的
告诉全部的叶子节点
注意区分n1是否为1的情况
知道n0即知道n2=n0 - 1，再分n1的情况讨论总结点数
完全二叉树的n1只能是0或者1 二者的叶子结点个数一样，但总节点数不同
n1=0 1 2 3 4 5
n0+n2=n
2*n0=n+1
2*n2+1=n
n2=n0-1
先验条件
n1=1 1 2 3 4 5 6
n0+n1+n2=n
2*n0=n
n1+2*n2+1=n
满m叉树的特征
第i个结点的第一个孩子=(i-1)*m+2
当m为2，即二叉树的第一个孩子为2i
双亲为[(i-2)/m]+1
m叉树转二叉树原则：左孩子右兄弟
二叉树遍历
若没有左子树，先序＝中序
根（左）右=（左）根右
若先序和后序相反，说明只有一个叶子结点，且每个高度只有一个结点
n在m前的情况
中序：n在m的左边 后序：m是n的祖先
写题的时候牢记“左根右”这三个字，很多题目是其变形而来，比如少了左或者少了右，但不会少根
若要找到m到n的路径，要用后序遍历
因为先序和中序遍历其栈会存入除路径以外的右边结点
后序线索树的遍历需要栈的支持，因为根结点最后访问，而其孩子结点可能没有链域指向其中
森林和树
用二叉链表存储森林的时候
有大于一棵树，根节点的右指针不空
一棵树
根节点的右指针为空
森林中的叶子结点相当于没有孩子，在二叉树中等价于左指针为空
森林中的每一个非终端结点相当于有孩子，不管有几个孩子也不管孩子有没有孙子，这几个孩子中最右边的孩子在二叉树中右指针是空的，即一个非终端结点对应一个右指针为空的结点
同时还要看最后一棵树，因为树1->树2->树n，树n是没有指向的
因此n个非终端结点对应n+1个对应二叉树右指针为空的结点
平衡二叉树（AVL）
最小结点数 nh=nh-1 + nh-2 + 1 等价于所有非叶子结点的平衡系数为1
删除再插入同一个元素，不管该元素开始是不是叶子结点，之后的情况有可能一样也有可能不一样
哈夫曼树（最优二叉树）
不存在n1结点
有n-1个新构造的n2结点
求某种长度下的编码的数目，考虑最多的时候看拉满的情况，不考虑中间态（即本题不存在只有三个长度的情况）
第六章-图
图不能没顶点
非连通图最多边数
(n-1)*(n-2)/2
相当于n-1个结点组成完全图，此时再加入随便一条边都变成连通图
有向图强连通的最少边数为n
连接成一个环
连通分量：一个并查集
极大连通子图是讨论连通分量的,极小连通子图是讨论生成树的 极小连通子图只存在于连通图中 1.强连通图的极大强连通子图为其本身。（是唯一的） 2.非强连通图有多个极大强连通子图。（非强连通图的极大强连通子图叫做强连通分量） 极小强连通子图：不存在这个概念
生成树是连通图的极小连通子图
生成树不一定是连通分量，因为联通分量要求包括该部分所有的结点和边
连通分量=极大联通子图
路径
简单路径
没重复顶点
复杂路径
简单回路
首尾重复，其他不重复
复杂回路
首尾重复，中间也重复
其他
存在回路的图不存在拓扑序列
无向连通图不需要构成环，n-1即可构成最小连通图
邻接矩阵A中
A的k次方中，A[i][j]表示顶点i到j长度为n的路径的数目
1->2->3
1到3没有弧，只能说有路径
完全图才能说任何顶点到其他顶点都有弧
有向图邻接矩阵中，A[i][i]=0,没边的为∞
邻接矩阵的表示是唯一的
都是0表示没边，1表示有边
不要过度推测改为别的数值然后推翻为不唯一
临界表删除顶点的复杂度为O(n+e)
广度的生成树高度小于等于深度 广度只能找权值相同的单源最短路径
时空复杂度
BFS
邻接矩阵
时间复杂度
O(n²)
空间复杂度
O(N)
邻接表
O(n+e)
DFS
BFS和DFS都是一样的，其中的空间复杂度分别指其队列和栈需要的大小
迪杰斯特拉
拓扑排序
删除n个点和e条边
深度优先可以检测回路，广度优先不可以
弗洛伊德算法
可用于负权图，但要求包含负权值的边不存在回路
最小生成树
路径一定最短
可能存在多条路径，比如有环的权值相同的情况，有n-1种相同的生成树
如果每条边权值不相同，则肯定只有一种情况
此时普利姆和克鲁斯卡尔相同
检测有环
关键路径
其第一步是拓扑排序，因为不允许有环的路径进行关键路径算法
最短路径不能判断是否有环
有向无环图(DAG)
拓扑排序(AOV)
有环则不行
有环不意味着是强连通图，但是意味着存在顶点大于1的强连通分量
拓扑排序唯一不一定顶点的出入度小于等于1
拓扑序列唯一可能有多种图形状 三角矩阵的拓扑排序可能不唯一
有序的拓扑排序序列：先后是有大小关系的，比如123，不能是132
关键路径（AOE）
求ve
算最大的那条
求vl
算最小的那条
事件是点，活动是边
第七章-查找
有序表顺序查找
分块查找
若本身是有序顺序表，则找块和块内都采用二分
次数为：log2(b+1)+log2(s+1)
b是块数
s是每块内的元素
折半查找
仅仅适用于有序的顺序表
是平衡二叉树
右子树结点-左子树结点=0/1
判定树中失败结点（方形结点）是虚构的，不纳入计算树当中
寻找次数为log2(n+1)向上取整
理解为树的高度
查找失败的ASL的分母比成功的多1
查找失败的ASL的高度为其父亲高度
P263 T14
B树
B+树
n个关键字，n个分叉
根节点的关键字和分叉个数：【1，m】 非根结点：【m/2的上界，m】
散列表
除留取余法为什么取质数
拉链法的结点不算作一次查找
查找到为空地址即表示查找失败，所以开放定址法删除时候时候只作删除标记
散列函数返回的值需要确定，如函数中有random即不可
堆积（聚集）现象即产生冲突，对ASL有影响
原因是解决冲突的方法不合适
平方探测法
分清楚结点和关键字的区别
最小高度logm(n+1)取上界
最大高度
不支持顺序查找
是满树
比如高度为5的二叉b树，则第五层一定有16个结点
插入的时候分裂的位置为 m/2上界的右边那个结点作为根节点，比如四叉树则第二叉的右边的结点作为根节点
删除
应用：关键数据库索引（MySQL）
散列表算ASL P286 T5
一行写位置，一行写次数
链地址法
成功ASL：不用算结点处
失败ASL：一般不考虑空指针
查找失败ASL是按取余的数来算的 跟表长没关系
查找成功的ASL跟元素有关
第八章-排序
简单选择排序不稳定
其比较次数跟初始序列没关系，第i轮要比n-i次
归并排序也满足
希尔排序不稳定
直接插入排序每一趟都可能改变前面躺的元素的位置
折半插入排序跟直接插入排序相比，其比较次数减少了（定位快了），但移动次数没变，时间复杂度仍为O(n²)
直接插入是局部有序，即当前躺的位置可能后面躺会改变 冒泡排序是全局有序的,快排每趟确定的枢纽元素也是全局有序
快排相当于一颗二叉树，树的高度相当于递归深度，也即空间复杂度
最差：n
如 12345678，此时基本有序，树为一边倒
最好：log2n
空间复杂度的意义为树栈的元素个数
归并排序：空间复杂度最差跟最好都是n
判断一个序列是否是快排第k躺的排序结果
若快排两次且只有两个符号的数，则必然第一次排在边界，否则第二趟会确定三个元素
堆排序
建立初始堆的时候，若左右孩子一样，选左孩子
与二叉排序树的区别在于堆排序的兄弟之间没排序
大顶堆的次第二层一定有第二大的
插入的时候，若插入元素高度为h，不管中间情况怎么样，都只要比较h-1次
删除的时候比较次数注意兄弟节点也要比
多路平衡归并
败者树有两个根节点
理解为什么是【log2k】上界而不是log[2（k+1）]
最佳归并树
错误实例
多路归并树的IO次数
错误！没加虚结点
增加虚段
经典题目
优先级高的最后排序
高优先级具有稳定性
比如16和11
先排个位11，16
再排十位，由于都是1，若不稳定的话，则可能出现16，11的错误结果
在基本有序的情况下，冒泡排序的比较次数要远大于直接插入排序
对于普通情况，简单选择排序的数据移动次数远小于直接插入排序和冒泡排序
