数据结构与算法复习知识点总结
写在前边：本篇根据老师发的知识点复习所写，若有疏忽或总结不全，本人不承担任何责任
本篇除了非常重要的代码以外，代码均不收录。
复杂度分析
复杂度分为时间复杂度和空间复杂度
O函数只需要取复杂度的最高项，是为了简算复杂度而出现的
一般来说，计算时间复杂度只需要根据某运算的进行次数来计算，如加法运算、比较运算等。空间复杂度一般会考虑开辟了多少的相应变量的空间
后边的哈希表和二叉搜索树等算法会用到
线性表
线性结构特点
凡是线性结构只有两种存储方式:顺序存储与链式存储，分别对应顺序表和链表
顺序表
顺序表有一个非常显然的例子------数组
顺序表插入与删除很繁琐，读写很容易
链表
链表的代码实现请自行复习，在此不赘述
读取修改复杂度为O(n)
栈与队列
栈
一般会选择用数组（顺序存储）模拟栈，但不代表链表（链式存储）不能实现
一些栈的操作(stl中的函数是不需要给参数的，此处的函数是老师自己封装的)，这些函数建议手写一下，此处不赘述
除去递归的应用，其余的大家的代码作业都有涉及，这部分是代码内容（除了中缀与后缀表达式），请自行复习。
尾部递归可以用for循环代替，非尾部递归可以用栈来模拟
队列
（此处依然是老师自己封装的函数，可以尝试去看看stl的函数）
一般会选择用链表（链式存储）模拟队列，但不代表数组（顺序存储）不能实现（而且一般考数组模拟）
循环队列：
队列的应用大家的代码作业都有涉及，自行复习代码
栈的出栈顺序经常会有选择题，一般有两种：
这种简单，可以自行模拟出栈顺序，或者看大小顺序来判断
这种题比较麻烦，涉及到一个卡塔兰数，可以直接记公式，如下：
Cn即为答案
字符串
一些常识
KMP算法
这个算法非常的抽象，建议好好了解一下，可以去csdn或者b站等等地方找讲解
我的建议是你直接看一遍ppt，看不懂直接去搜教程，别看这里了
来练个手
树
树的性质
这一页的东西都很重要
到时候能认出来就行了，我们画树一直是树形法
二叉树
非常显而易见的特点（会考选择题）
非常重要的特点（会考选择题）
在之后的搜索二叉树 堆中都会有所应用
长这样
下边这个关系不是很重要
这是二叉树的性质，不要迁移到普通树上
会考选择题，你可以画一个树试试看
对于根节点为1的完全二叉树，节点编号为i时，他的左儿子编号为(i)*2,右儿子编号为(i)*2+1,他的父节点编号为(i)/2。奇数节点(1除外)一定是右孩子
对于根节点为0的完全二叉树，节点编号为i时，他的左儿子编号为(i)*2+1,右儿子编号为(i)*2+2,他的父节点编号为(i-1)/2。奇数节点一定是左孩子
二叉树可以用顺序存储(用于完全二叉树)也可以用链式存储(用于普通二叉树)
二叉树的周游
先（后）序找根，中序找左右子树
二叉搜索树
二叉搜索树=二叉排序树=二叉查找树=二叉检索树
对二叉搜索树执行中序排序可以得到从小到大的序列
插入会考查找成功（失败）的平均比较次数此处给两个实例，自行体会
我们没有考察过合并删除
我们一直都用的是复制删除
右子树高，要往右子树的右子树插入
左子树高，要往左子树的左子树插入
左子树高，要往左子树的右子树插入，先使左子树左旋，再右旋
右子树高，要往右子树的左子树插入，先使右子树右旋，再左旋
这个最不平衡的平衡二叉树不用看，但是高度要记好
堆
插入操作：在完全二叉树的末尾插入，然后依次向上交换，直到不能交换为止
删除堆顶：将堆顶与最末尾元素交换，删除最末尾元素，堆顶向下交换直至交换不了为止（堆排就是不断删除堆顶进行排序）
并不涉及考题
Huffman树（离散数学讲过了）
每次取两个最小的，合成一个新节点放回原序列，重复直到只剩1个
树与森林
右孩子与自己同级，左孩子是自己的孩子（下一级）
右孩子与自己同级，左孩子是自己的孩子（下一级）
右孩子与自己同级，左孩子是自己的孩子（下一级）
先根=先序 后根=中序 给出先根和后根可以唯一确定一棵树（森林）
先根=先序 后根=中序 给出先根和后根可以唯一确定一棵树（森林）
树的存储不考，这里仅供了解
图
基本性质（与离散基本相同，学过离散的就不用看了）
图的存储
在离散中讲过的邻接矩阵
十字链表仅供了解，一般不会考察
没考过
生成树（离散讲过了，学过的离散可以略过）
Prim：从某一个点开始，选择一个最小的边以及它所连接的点（未访问过的）加入访问过的节点，紧接着从访问过的点集出发选择一个最小的边以及它所连接的点（未访问过的）加入访问过的节点，以此类推，直到访问完
Kruskal：将边按权值排序，依次选择不成环的最小的边加入最小生成树，直到加满n-1条边为止（需要并查集）
最短路
分为单源最短路径和对点之间的最短路径
Dijkstra不接受有负边权的图
Dij：从某一个点开始，选择一个最小的边以及它所连接的点（未访问过的）加入访问过的节点，紧接着从访问过的点集出发选择一个最小的边以及它所连接的点（未访问过的）加入访问过的节点，以此类推，直到找到目的地为止
写题的时候画这个图就行了
枚举点k，用点k更新i到j的最短路径
写题时会让你算A1 A2 A3等，画出来就行了
拓扑序与关键路径
拓扑序是针对有向无环图的
写题画这个表就行
查找
顺序查找
二分查找（折半法查找）
分块法查找
块内是顺序，块间是二分查找
B树
我们只考察2-3树
当根节点分裂时，2-3树长高
B+树（掌握概念，不考操作）
散列查找（哈希）
这个简单，考的少
这个考的东西多，除了画出哈希表，还有求查找成功（失败）的平均次数
给个例题，自行体会
不考，了解
排序
直接插入排序
折半插入排序（二分）
希尔排序
冒泡排序
快排
直接选择排序
堆排
归并
基数排序（桶排）
总结
