备战408——《数据结构》

考研408复习
复习顺序为《数据结构》、《组成原理》、《操作系统》、《计算机网络》
复习教材：专业408教材（4本）+《王道考研复习指导》

【注意】
个人比较喜欢实质化的笔记，所以在这在这里只记录部分零散的知识点，记录会坑坑洼洼的，不全（慢慢填充），不喜勿喷
本人23考研，目前专业课复习进度为一轮复习，计网过半（7月），欢迎研友交流（但我一般不看消息）

• 绪论
• 线性表
• 栈、队列和数组
• 串
• 树与二叉树
• 图
• 查找
• 排序
• 重要代码
• 补充
• • C++STL

F：森林；B：二叉树；T：树

• F–>B，B中右指针域为空的数量=F中非终端结点数+1
• T–>B，T的后序遍历=B的中序遍历
• F–>B，F中叶结点数=B中左孩子指针为空的结点数
• 数的边数=结点数-1，e=n-1
• WPL：带权路径长度

• 无向图中，所有结点的度之和=两倍的边数
  ∑ i = 1 n T D ( V i ) = 2 e sum_{i=1}^{n}{TD(V_i)}=2e i=1∑n​TD(Vi​)=2e

• 有向图中，所有结点的入度数之和=出度数之和=边数
  ∑ i = 1 n I D ( V i ) = ∑ i = 1 n O D ( V i ) = e sum_{i=1}^{n}{ID(V_i)}=sum_{i=1}^{n}{OD(V_i)}=e i=1∑n​ID(Vi​)=i=1∑n​OD(Vi​)=e

• G为无向连通图，当G中度为奇数的顶点个数为不大于2的偶数（0或2）时，G中存在：包含所有边且长度为|E|的路径

• BFS，广度优先遍历，借助队列

• DFS，深度优先遍历，借助栈

• BFS与DFS算法复杂度
  空间复杂度：O(|V|)
  时间复杂度：
  邻 接 矩 阵 ： O ( ∣ V ∣ 2 ) 邻接矩阵：O(|V|^{2}) 邻接矩阵：O(∣V∣2) 邻 接 表 ： O ( ∣ V ∣ + ∣ E ∣ ) 邻接表：O(|V|+|E|) 邻接表：O(∣V∣+∣E∣)
  |V|：结点数；|E|：边数

• 最小生成树：
  Prim：边稠密，时间复杂度: O ( ∣ V ∣ 2 ) O(|V|^{2}) O(∣V∣2)
  Kruskal：边稀疏，多顶点，时间复杂度: O ( ∣ E ∣ l o g ∣ E ∣ ) O(|E|log|E|) O(∣E∣log∣E∣)

• 最短路径
  Dijkstra：单源，贪心，时间复杂度: O ( ∣ V ∣ 2 ) O(|V|^{2}) O(∣V∣2)
  Floyd：所有顶点对，不断加入中间结点，时间复杂度: O ( ∣ V ∣ 3 ) O(|V|^{3}) O(∣V∣3)
  |V|次Dijkstra➡Floyd

• DAG：有向无环图

• 拓扑排序：依次输出并删除ID=0的顶点

• 具有n个结点的k叉树的高 log ⁡ k n ( 向 下 取 整 ) + 1 log_k{n}(向下取整)+1 logk​n(向下取整)+1
• 二叉排序树的中序遍历是递增有序序列

（不会涉及所有代码，筛选自各位大佬压的重点代码，大部分摘录自王道书）
一、线性表

二、栈、队列和数组

三、串

四、树与二叉树

五、图

六、查找

七、排序

一、六大组件

1. 容器Container：一种数据结构
2. 迭代器/游标iterator
3. 算法Algorithm
4. 仿函数Function object
5. 迭代适配器Adapt
6. 空间适配器Allocator

关于容器：
分为顺序容器：list（双向链表）、vector（动态数组）、dequeue（双端队列）；关联容器：set（集合，有序且唯一）、map（地图，以key排序且唯一）；
stack（栈）为vector的Adapt；queue（队列）为dequeue的Adapt

二、使用

//
#include 	//添加相应头文件，例：#include 
using namespace std;	//添加std命名空间

//实例化容器
typedef C Cname();
		//例：typedef vector vec(2,4)	//{4,4}
		//					     vec(4)		//{0,0,0,0}
		//						 vec(a,a+i)	//数组a,从0~i-1个元素

//声明迭代器
C<>::iterator itname;	//例：vector::iterator it;

//通过迭代器访问容器中数据
//例，输出vector中所有数据
for(i=vec.begin();i!=vec.end();i++)
	std::cout<<*it< 
三、常用函数
 (c为实例化后容器名）
 
c.size()
c.empty()
c.push_back()
c.pop_back()
c.push_front()
c.pop_front()
c.back()
c.front()
c.erase()
c.remove()