数据结构与算法

目　录

第1章　引论　1
1.1　数据结构的概念　1
1.2　数据结构的内容　5
1.2.1　数据的逻辑结构　5
1.2.2　数据的存储结构　6
1.3　算法　6
1.3.1　算法的概念　7
1.3.2　算法的评价标准　7
1.3.3　算法的描述　8
1.3.4　算法性能分析　10
习题　14

第2章　线性表　16
2.1　应用实例　16
2.2　线性表的概念及运算　17
2.2.1　线性表的逻辑结构　17
2.2.2　线性表的运算　17
2.3　线性表的顺序存储　18
2.3.1　顺序表　18
2.3.2　顺序表的基本运算　19
2.4　线性表的链式存储　23
2.4.1　单链表　23
2.4.2　单链表基本运算　24
2.4.3　循环链表　31
2.4.4　双向链表　32
2.4.5　静态链表　33
2.5　顺序表和链表的比较　33
2.6　实例分析与实现　34
习题　42

第3章　栈和队列　45
3.1　应用实例　45
3.2　栈　46
3.2.1　栈的概念及运算　46
3.2.2　栈的顺序存储结构　47
3.2.3　栈的链式存储结构　50
3.2.4　栈的应用　52
3.3　队列　57
3.3.1　队列的概念及其运算　57
3.3.2　循环队列　59
3.3.3　链队列　61
3.4　实例分析与实现　63
3.5　算法总结——递归与分治算法　69
习题　71

第4章　串　73
4.1　应用实例　73
4.2　串及其运算　74
4.2.1　串的基本概念　74
4.2.2　串的基本运算　75
4.2.3　串的基本运算示例　77
4.3　串的存储结构及实现　77
4.3.1　定长顺序串　77
4.3.2　堆串　80
4.3.3　块链串　82
4.4　串的模式匹配　83
4.4.1　BF模式匹配算法　84
4.4.2　KMP模式匹配算法　85
4.5　实例分析与实现　91
4.5.1　串的实例分析　91
4.5.2　简单文本编辑软件的实现　92
4.6　算法总结　94
习题　95

第5章　多维数组和广义表　97
5.1　应用实例　97
5.2　多维数组　97
5.3　矩阵的压缩存储　99
5.3.1　特殊矩阵　99
5.3.2　稀疏矩阵　100
5.4　广义表　107
5.4.1　广义表的概念　107
5.4.2　广义表的存储　108
5.4.3　广义表的操作　109
5.5　实例分析与实现　111
习题　113

第6章　树　115
6.1　应用实例　115
6.2　树的概念　117
6.2.1　树的定义与表示　117
6.2.2　树的基本术语　118
6.2.3　树的抽象数据类型定义　119
6.3　二叉树　120
6.3.1　二叉树的定义　120
6.3.2　二叉树的性质　122
6.3.3　二叉树的存储　124
6.4　二叉树的遍历　126
6.4.1　二叉树的遍历及递归实现　126
6.4.2　二叉树遍历的非递归实现　128
6.4.3　遍历算法的应用　132
6.4.4　由遍历序列确定二叉树　136
6.5　线索二叉树　137
6.5.1　线索二叉树的基本概念　137
6.5.2　线索二叉树的基本操作　138
6.6　树和森林　140
6.6.1　树的存储　140
6.6.2　树、森林与二叉树的转换　143
6.6.3　树和森林的遍历　146
6.7　哈夫曼树及其应用　148
6.7.1　哈夫曼树　148
6.7.2　哈夫曼编译码　151
6.8　实例分析与实现　153
6.8.1　表达式树　153
6.8.2　树与等价类的划分　155
6.8.3　回溯法与N皇后问题　158
6.9　算法总结　160
习题　161

第7章　图　164
7.1　应用实例　164
7.2　图的基本概念　165
7.3　图的存储结构　167
7.3.1　邻接矩阵　167
7.3.2　邻接表　169
7.3.3　十字链表　171
7.3.4　多重链表　172
7.4　图的遍历　173
7.4.1　深度优先搜索遍历　173
7.4.2　广度优先搜索遍历　175
7.5　图的应用　176
7.5.1　最小生成树　176
7.5.2　拓扑排序　181
7.5.3　关键路径　184
7.5.4　最短路径　188
7.6　实例分析与实现　192
7.7　算法总结——贪心算法　199
习题　203

第8章　查找　207
8.1　概述　207
8.2　基于线性表的查找　208
8.2.1　顺序查找　208
8.2.2　折半查找　210
8.2.3　索引查找　213
8.3　基于树的查找　214
8.3.1　二叉排序树　214
8.3.2　平衡二叉树　220
8.3.3　B树和B+树　228
8.3.4　伸展树　234
8.3.5　红黑树　236
8.4　散列　241
8.4.1　Hash函数的构造方法　241
8.4.2　处理冲突的方法　243
8.4.3　Hash表查找　245
8.5　算法总结　248
习题　249

第9章　排序　252
9.1　概述　252
9.2　插入类排序　254
9.2.1　直接插入排序　255
9.2.2　折半插入排序　257
9.2.3　希尔排序　258
9.3　交换类排序　259
9.3.1　冒泡排序　259
9.3.2　快速排序　262
9.4　选择类排序　264
9.4.1　简单选择排序　264
9.4.2　树形选择排序　265
9.4.3　堆排序　267
9.5　归并类排序　272
9.5.1　二路归并排序　272
9.5.2　自然归并排序　274
9.6　分配类排序　275
9.6.1　多关键字排序　275
9.6.2　链式基数排序　276
9.7　外部排序　278
9.7.1　置换选择排序　279
9.7.2　多路归并外排序　281
9.8　算法总结　285
习题　286

参考文献　288