[数据结构与算法]备战408——《数据结构》

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

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

绪论

线性表

栈、队列和数组

串

树与二叉树

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

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

图

• 无向图中，所有结点的度之和=两倍的边数
  $$\sum _{i=1}^{n}TD(V_i)=2e$$

• 有向图中，所有结点的入度数之和=出度数之和=边数
  $$\sum _{i=1}^{n}ID(V_i)=\sum _{i=1}^{n}OD(V_i)=e$$

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

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

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

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

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

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

• DAG：有向无环图

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

查找

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

排序

重要代码

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

• 顺序表定义
• 顺序表增删改查
• 单链表定义
• 单链表基本操作（头/尾插法、遍历、插入、删除）
• *双链表
• *循环链表
• *静态链表

二、栈、队列和数组
（如只需使用栈与队列这种数据结构，可直接使用C++的STL，补充在后面）

• *实现栈
• *实现队列

三、串（无）

四、树与二叉树

• 顺序存储结构
• 链式存储结构
• 先序遍历
• 中序遍历
• 后序遍历
• 树与二叉树

五、图

• 数据结构与基本操作
• 邻接矩阵
• 邻接表
• 深度优先搜索
• *广度优先搜索

六、查找

• 顺序查找
• 折半查找

七、排序

• 快速排序
• *冒泡排序
• *选择排序
• *插入排序
• *归并排序
• *计数排序
• *桶排序
• *基数排序

补充

C++STL

一、六大组件

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 <C>	//添加相应头文件，例：#include <vector>
using namespace std;	//添加std命名空间

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

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

//通过迭代器访问容器中数据
//例，输出vector中所有数据
for(i=vec.begin();i!=vec.end();i++)
	std::cout<<*it<<end;
//例，添加数据
vec.insert(it,1);

三、常用函数
(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()