数据结构与算法：编程的基石

发表时间: 2023-08-29 20:56

数据结构（Data Structure）及相关算法

存储数据的方式

结构体（Struct）或类（class）

结构：具有多个属性的变量

struct 结构名{	类1 属性1；	类2 属性2；	...}

线性表（List）

结构：n个元素构成的有序序列。有表头、表尾。

直接前驱、直接后继反映元素之间一对一的邻接逻辑关系

顺序表（Array）

结构：一个结构体类型的变量（一般包括1个数组、有效数据数量max）

struct 结构名1{	类 s[max];	int max;}

链表（Linked List）

结构：（头结点head+）n个变量
特点：变量均为同一结构体类型（包括自生属性、附近变量地址）
分类

有/无头结点。一般有头结点，仅Next有效
单向/双向。一般单向，即属性中包含下一个的地址Next，但不包含上一个的地址Previous

struct 结构名1{	类1 属性1；	类2 属性2；	...	*struct 结构名1 Next；}

栈（Stack）

结构：（链）表
特点：先进后出（尾进头出）
操作：

返回类型	函数名、方法	操作
Stack	CreateStack	生成空堆栈
void	push	入栈
Item	pop	出栈
bool	isEmpty	是/否为空
int	size	栈的规模
bool	isFull	是/否已满

队列（Queue）

结构：（链）表
特点：先进先出（头进头出）
操作：

返回类型	函数名、方法	操作
Queue	CreateQueue	生成空队列
bool	isFull	是/否已满
bool	AddQ	入队
bool	IsEmpty	是/否为空
Item	DeleteQ	出队

树（Tree）

结构：

数组
结构体的组合（每个结构体包含自生属性、各个子节点地址）

二叉树（BinTree）

包括二叉搜索树和完全二叉树，完全二叉树包括堆
结构（选其一）：

数组
结构体的组合（每个结构体包含自生属性、左节点地址Left、右节点地址Right）

操作：

返回类型	函数名、方法	操作
Item	CreateBinTree	生成空树
bool	IsEmpty	是/否为空
viod	Traversal	遍历树

遍历分类：
按照是否递归分为：

递归遍历
非递归遍历

按照递归顺序分为：

中序遍历(InoederTraversal)、
先序遍历(PreoederTraversal)、
右序遍历(PostoederTraversal)、
层序遍历(LeveloederTraversal)

其中非递归后序遍历较困难

二叉搜索树（Binary Search Tree）

结构：二叉树
特点：左小右大/左大右小

左小右大：父节点大于左子树上的任何值，小于右子树上的任何值
左大右小：与上面相反

红黑树（Red-Black BST，属于平衡二叉查找树）

完全二叉树（Complete Binary Tree）

结构：二叉树（一般为一个顺序表）
特点：下标连续，即编号与下标相同
包括堆

堆（Heap，优先队列（Priorty Queue））

结构：完全二叉树
特点：小/大键值优先

小键值优先->最小堆（MinHeap，小顶堆）
大键值优先->最大堆（MaxHeap，大顶堆）

操作：

返回类型	函数名、方法	操作
Item	CreateHeap	生成相应的堆
bool	IsFull	是/否已满
bool	Insert	入堆
bool	IsEmpty	是/否为空
Item	Delete…	删除并返回相应的堆顶

哈夫曼树（Huffman Tree）

结构：堆
特点：叶节点为一个独立的权值，父节点的权值为其两子节点之和

散列（Hash）

结构：线性表
特点：hash函数映射+冲突处理
操作：

冲突处理：

开放定址法
线性探测法
平方探测法
双散列探测法
再散列法
分离链接法

图（Graph）

结构：邻接矩阵 或邻接表
分类
操作：

Item	CreateHeap	生成相应的堆
Item	CreateGraph	生成一个无边图
void	InsertEdge	增加新边E
void	DeleteEdge	删除边E
bool	IsEmpty	是/否为空
void	DFS	从点V深度优先搜索
void	BFS	从点V广度优先搜索

DFS（深度优先搜索，到底回头）：从V开始同时做标记（保证节点不被二次访问），一直向下访问，直至没有未被访问的邻接点时回头，V找不到其他的邻接点访问时停止。
BFS（广度优先搜索，类似于层序遍历）：从V开始同时做标记（保证节点不被二次访问），只访问邻接点，访问完毕后再访问他们的邻接点，没有邻接点可访问时停止。

强连通性（Kosaraju）

最小生成树（算法）

DFS、BFS

见上

Prim算法

从指定点出发，每次加入一个最近的点。直至没有满足条件的点

Kruskal算法

每次加入连接不连通区域的、权值最小的边。直至没有满足条件的边。（可引入并查集表示是否联通）

单源最短路径（算法）

Dijkstra

Prim+最短路程+来向

Acyclic

拓扑排序

CPM

Floyd算法

矩阵运算（每两个点之间找一遍最短路程，最多边数+1，保留最短路程）max-1次，
path[n+1][i][j]=min(path[n][i][j],path[n][i][k]+path[n][k][j]),1<=j<=max

Bellman-Ford

拓扑排序（有向无环图）

每次添加一个（未输入的入度为0的）点
这里的入度为0指的是与未收录的点之间的关系

B树（B-树）

B+树

跳表

LSM树（Log-Struct-Merge Tree）

参考：
https://zhuanlan.zhihu.com/p/181498475

空间树

R-tree

其他

https://www.cnblogs.com/KillerAery/p/10878367.html

算法（Algorithms）

并查集

quick-find
union-find
加权union-find

排序

复杂度

算法	平均时间O()	最坏时间O()	空间O()	稳定性
简单选择排序	N^2	N^2	1	×
简单插入排序	N^2	N^2	1	√
冒泡排序	N^2	N^2	1	√
希尔排序(5,3,1)	N^2	N^2	1	×
堆排序	NlogN	NlogN	1	×
快速排序	NlogN	N^2	1	×
归并排序	NlogN	NlogN	1	√
基数排序	D(N+R)	D(N+R)	N+R	√

选择排序

简单选择排序

堆排序

插入排序

简单插入排序

希尔排序（5,3,1）

交换排序

冒泡排序

快速排序

归并排序

基数排序

桶排序

基数排序（次位优先、主位优先）

△外部排序（归并）

字符串

排序

基础：键索引计数法
分类：低位优先（长度不同），高位优先（长度相同）
高位排序又有快速排序和普通排序