一、绪论
二、抽象数据类型ADT
1 | ADT 抽象数据类型名称{ |
线性表
1 | ADT 线性表（List） |
顺序表
单链表
静态链表.md 没有审核代码
循环链表
双向链表.md 没有审核代码
特殊线性表-栈、队列和串
栈：后进先出
1 | ADT Stack{ |
栈的顺序储结构栈.md
栈的链式存储结构.md
队列：先进先出
1 | ADT Queue{ |
队列的顺序存储结构.md
队列链式存储结构.md
串
1 | ADT 串(string) |
串的顺序存储结构.md
数组和广义表
数组：由一组类型相同、下标不同的变量构成。
根据数组中存储的数据元素之间的逻辑关系，可以将数组分为 : 一维数组、二维数组、…、n维数组。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25ADT Array {
Data:
相同类型元素有序集合，每个元素受n(n>=1)个线性关系的约束并由一组下标唯一标识
Operation:
InitArray(): //构造一个空数组,数组的维数和各维的长度
DestroyArray()：//销毁数组,释放数组所占用的存储空间
GetValue(A,&e,index1,…,indexn) //求值函数,求某个下标元素的值
初始条件:A是维数组,e为元素变量,随后是n个下标值.
操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.
Assign(&A,e,index1,…,indexn)//赋值函数,给下具体的下标的元素赋值
初始条件:A是n维数组,e为元素变量,随后是n个下标值.
操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK.
}ADT Array
树
1 | ADT Tree{ |
树与森林.md
树的存储结构.md java版
二叉树.md
线索二叉树.md
哈赫夫曼树.md
图
1 | ADT 图(Graph) |
图的术语与定义.md
图的抽象结构与存储结构.md(无向图采用多重邻接表，有向图采用十字链表)
图的遍历.md
最小生成树.md
最短路径问题.md
拓扑排序.md
关键路径.md
区别.md
查找
- 静态查找(Static Search Table)：只作查找操作的查找表。主要操作有：
- 查询某个“特定的”数据元素是否在查找表中。
- 检索某个“特定的”数据元素和各种属性。
线性表的查找.md
- 动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个特定的数据元素。主要操作有两个：
- 查找时插入数据元素；
- 查找时删除数据元素。
查找树.md
平衡二叉树.md
2-3树.md
B树
红黑树
- 哈希表
散列查找.md
排序
- 排序基础代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct {
int r[MAXSIZE + 1]; // 用于存储要排序的数组， r[0]用作哨兵或者临时变量
int length; // 用于记录顺序表的长度
}SqList;
/**
* 交换数组r中下标i和j的值
*/
void swap(SqList *L, int i, int j){
int temp = L->r[i];
L->r[i] = L->r[j];
L->r[j] = temp;
}
插入排序.md (直接插入排序，希尔排序。希尔排序根据直接插入排序而来)
选择排序.md
交换排序.md
归并排序.md(从0开始)
排序代码集合(从0开始).md
性能比较
| 排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 简单选择排序 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 直接插入排序 | $O(n^2)$ | $O(n)$ | $O(n^2)$ | $O(1)$ | 稳定 |
| 希尔排序 | $O(nlogn)~O(n^2)$ | $O(n^{1.3})$ | $O(n^2)$ | $O(1)$ | 不稳定 |
| 堆排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(1)$ | 不稳定 |
| 归并排序 | $O(nlogn)$ | $O(nlogn)$ | $O(nlogn)$ | $O(n)$ | 稳定 |
| 快速排序 | $O(nlogn)$ | $O(nlogn)$ | $O(n^2)$ | $O(nlogn)~O(n)$ | 不稳定 |
附录
图-邻接矩阵代码.md
邻接表代码.md
邻接矩阵与邻接表深度遍历.md
邻接矩阵与邻接表的广度优先遍历算法.md
普里姆（Prim）算法代码.md
克鲁斯卡尔（Kruskal）算法代码.md
迪杰斯特拉（Dijkstra）算法代码.md