课程内容提要
数组
数组的内存地址是连续的。
len代表一个元素占用的字节数，a代表数组的第一个元素位置
解答：a + (2*5+3)*2
稀疏矩阵
解：
这里压缩存储的数组M是以1开始的，因此压缩A[0,0]压缩后对应M[1], 代入排除B,C
A[1,1]对应M[3], 由此代入排除D，选A
数据结构的定义
线性表
顺序表就是一维数组的形式，空间连续
链表每个单元分为值和指针两部分，通过指针链上下一个单元
链表的基本操作
顺序存储域链式存储对比
队列与栈
队列：先进先出
栈：先进后出
循环队列：队空和队满都是tail = head, 为了解决这个问题有两种解决方案，一是保存当前状态是队满还是对空，但是这种方法比较麻烦，因此更多采用第二种方法，队列少存一个元素。如此次size为5，head为0，当tail=4时， (tail + 1)%size=head, 队满
解答：
n个元素的出栈序列共有C(n, 2n)/(n+1)种，因此这里有5种，如下：abc, acb, bac, bca, cba
更多可以看我的博客 https://blog.csdn.net/ion_L/article/details/108811836
分析：
要得到A选项的输出序列，可以从左侧依次输入e1, e2, e3, e4
要得到B选项的输出序列，可以从左侧输入e1, e2, e4, 右侧输入e3
要得到C选项的输出序列，可以从左侧输入e1,e2, 右侧输入e3, e4
依次选D
广义表
长度：最外层包含元素的个数。 深度：包含括号的层数，即嵌套的次数
表尾：除了表头外的所有的元素
例1：长度为3，深度为2
例2：head(head(tail(LS1)))
树与二叉树
一些概念
结点的度：即该结点孩子结点的个数，如1结点的度为2
树的度：树种所有结点度数最高的度数即树的度，如图中树的度为2
叶子结点：没有孩子结点的结点
分支结点：存在分支的结点
内部结点：既不是叶子结点，也不是根节点的结点
父结点/子结点：相对概念，如2是4的父结点，4是2的子结点
兄弟结点：相对概念，同一个父亲结点的结点称为兄弟结点，如4和5是兄弟结点。
树的层次：树有多少层级，如图是4级
二叉树的重要特性
完全二叉树的定义非常方便用线性表的形式表示一棵完全二叉树。而非完全二叉树用线性表需要引入额外的空元素。
第二点由等比数列前n项和公式可得
等差数列
等比数列
对于一棵结点数为n的二叉树，满足
n = n0 + n1 + n2(n0表示度为0的结点，n1表示度为1的结点，n2表示度为2的结点)， 同时n = n1 + 2*n2 + 1(结点数等于边数加1，一个度为m的结点可以引出m条边)由上面的两个公式，可以推导出3，
n0 = n2 + 1
二叉树的遍历
这里的前中后是指访问根结点的顺序。
例题解答：
前序遍历的结果是：12457836（根左右）
中序遍历的结果是：42785136（左根右）
后序遍历的结果是：48752631（左右根）
层次遍历的结果是：12345678（自上而下，自左往右）
感觉前序遍历和层次遍历与我们平时看树结构的顺序最接近
反向构造二叉树
给出两个序列确定二叉树的结构
给定一棵二叉树的后序和中序遍历序列 或者 给定一棵二叉树的先序和中序遍历序列可以唯一确定一棵二叉树
结果：
树转二叉树
基本原则：树中一个结点的孩子结点，转成二叉树后是其左子树结点
树中一个结点的兄弟结点，转成二叉树后是其右孩子结点。
方法：树的兄弟结点（不包括旁兄弟）用横线画起来，孩子结点只保留最左侧的线，就得到了一个二叉树的结构，最后对其进行旋转得到一棵二叉树
查找二叉树
查找二叉树又称为排序二叉树。可以极大提高数据的查找速度
最优二叉树（哈夫曼树）
树的路径长度：树的路径之和，之类左边第一个二叉树的路径之和就是6（连线的条数）
权：结点的数值，如图中的15,14,2,12,4,8,1这些数值
带权路径长度：该结点的权值乘以该节点的路径长度。如2结点的带权路径长度为2*2 = 4
树的带权路径长度：树中的所有结点的带权路径长度之和
构造一棵哈夫曼树（最优二叉树）即是使得该树的带权路径长度最小
总是最小的两个构成一个子树
哈夫曼编码是一种前缀码。解码的时候，左0，右1。
线索二叉树
先序线索二叉树的前驱和后序二叉树的后继无法推导得出，因为需要知道其双亲结点。（先序前驱，后序后继）
中序线索二叉树的结点前驱是左子树的最右结点，后继是右子树的最左结点。（如果孩子结点存在时）
平衡二叉树
提出原因：分析二叉排序树的查找过程可知，只有在树的形态比较均匀的情况下，查找效率才能达到最佳。因此，希望在构造二叉排序树的过程中，保持其为一棵平衡二叉树。
在题目中构造平衡二叉树的过程就是构建一棵保持平衡的二叉排序树。
插入操作
LL 右旋
RR 左旋
LR 左旋 后 右旋
RL 右旋 后 左旋
图
基本概念
具有n个顶点的无向完全图有 n* (n-1)/2 条边
具有n个顶点的有向完全图有 n* (n-1) 条边
图的存储
无向图的邻接矩阵是对称矩阵
图的遍历
拓扑排序
AOV网：在有向图中，顶点表示活动，有向边表示活动之间的优先关系表示活动的网（Activity On Vertex network）
拓扑序列满足：若在AOV网中从顶点vi到顶点vj有一条路径，则在该线性序列中，顶点vi一定在顶点vj前面。另外，入度为0的顶点在开始位置，出度为0的在结束位置。
对AOV网进行拓扑排序的方法如下：
图的最小生成树 - 普里姆算法
树的线条数是结点数-1
用普里姆算法得到的最小生成数如图：
图的最小生成树 - 克鲁斯卡尔算法
注意不能选取的边构成环
算法
算法基础
算法的特性
算法的复杂度
时间复杂度是重点
O(1): 有限的时间复杂度（如赋值操作，运算操作等）
O(n), O(n^2), O(n^3)：如for循环，双重for循环， 三重for循环
O(log2n): 如排序二叉树的查找—二分查找（Log2N是数学中的对数,是以2为底N的对数为多少,也就是2的多少次方是N）https://blog.csdn.net/u010452388/article/details/80891462
一个算法的时间复杂度往往是看最高的时间复杂度为准
查找
顺序查找
时间复杂度为：O(n)
二分查找
二分查找需要查找的序列是有序的
时间复杂度为：O(log2N)
散列表
存储的时候根据一定的规则（散列函数）设定存储位置，这样子查找和取值就很方便
排序（必考）
https://blog.csdn.net/qq_31116753/article/details/84103610
稳定和不稳定的区别就是相同的元素经过排序后是否会改变位置，如上图的两个相同的21
内排序就是在内存中进行排序
直接插入排序
希尔排序
例子中的第一个增量选取了小于10的整数5，先根据增量5进行分组，即57和28一组，68和96一组，59和33一组 ，以此类推。然后对每个组进行直接插入排序，如第一组57大于28，需要交换两个值。
上面例子中的组用了线条标识起来
直接选择排序
堆排序
所有的孩子结点比父节点大（父节点小于孩子结点）称为小顶堆
所有的孩子结点比父节点小（父节点大于孩子结点）称为大顶堆
构造大顶堆输出的最后结果是从大到小排序，小顶堆最后结果是从小到大排序
这里是建立一个大顶堆，首先根据数组建立一个完全二叉树（层次填入），然后从最后一个非叶子结点调整结点值，使得父节点大于所有孩子结点，然后从倒数第二个非叶子结点调整结点值，依次类推。值得注意的是调整后的子树也要满足父亲结点大于孩子结点，否则需要调整子树。
首先顺序表是一个大顶堆，不需要再初建堆，然后将堆顶的元素80输出，堆尾元素20放到堆顶，这时候如果堆结构被破坏，重新调整为大顶堆，输出调整后大顶堆的堆顶元素60。以此类推，直到所有元素输出。
最佳应用场景是取出前几名或者后几名的情况。如班级前十名的同学
冒泡排序
快速排序
https://www.runoob.com/w3cnote/quick-sort.html
归并排序
这里不太清楚，k是什么？
https://www.runoob.com/w3cnote/implementation-of-merge-sort.html
基数排序
总结
本文链接： http://www.ionluo.cn/blog/posts/7e686e7c.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
