1.1 引言 1
1.1.1 几个例子 1
第1章 概论 1
1.1.2数据结构的产生和发展 3
1.1.3基本概念和术语 4
1.2问题、算法和程序 9
1.2.1 问题 9
1.2.2算法 9
1.3算法描述和分析 10
1.3.1算法描述 10
1.2.3程序 10
1.3.2算法分析 12
1.4小结 15
习题 15
第2章 线性表 17
2.1概述 17
2.1.1线性表的概念 17
2.1.2线性表的类型定义 19
2.2顺序表 20
2.2.1线性表的顺序表示 20
2.2.2顺序表的实现 21
2.3.1线性表的链式表示 25
2.3.2线性链表的实现 25
2.3链表 25
2.3.3循环链表的实现 29
2.3.4双向链表的实现 30
2.3.5静态链表的实现 31
2.4栈 31
2.4.1栈的类型定义 31
2.4.2顺序栈的表示和实现 33
2.4.3链栈的表示和实现 34
2.5 队列 36
2.5.1 队列的类型定义 36
2.5.2顺序队列的表示和实现 37
2.5.3链队的表示和实现 39
2.6应用举例 41
2.7小结 44
习题 44
第3章 串 45
3.1概述 45
3.1.1 串的概念 45
3.1.2串的基本操作 46
3.2串的存储表示和操作算法 47
3.2.1定长顺序存储表示 47
3.2.2块链存储表示 49
3.2.3堆分配存储表示 50
3.3.1 模式匹配的基本算法（BF算法） 54
3.3模式匹配 54
3.3.2模式匹配的改进算法（KMP算法） 56
3.4应用举例 59
3.4.1 文本编辑 59
3.4.2建立词索引表 60
3.5 小结 62
习题 62
第4章 数组和广义表 65
4.1数组的定义、表示和实现 65
4.1.1数组的定义 65
4.1.2数组的表示 66
4.1.3数组的实现 67
4.2矩阵的压缩存储 69
4.2.1特殊矩阵 69
4.2.2稀疏矩阵 71
4.3广义表的定义和表示 78
4.3.1广义表的定义 78
4.3.2广义表的存储结构 79
4.3.3广义表的基本算法 81
4.4小结 84
习题 84
5.1树的定义和术语 87
5.1.1树的定义 87
第5章 树和二叉树 87
5.1.2树的基本术语 88
5.1.3树的表示 89
5.1.4树的遍历 90
5.2二叉树 90
5.2.1二叉树的定义 90
5.2.2二叉树的重要性质 91
5.2.3二叉树的存储结构 92
5.3二叉树的遍历和线索二叉树 94
5.3.1二叉树的遍历 94
5.3.2线索二叉树 96
5.4.1树的存储结构 100
5.4树和森林 100
5.4.2森林与二叉树的转换 102
5.4.3森林的遍历 103
5.5哈夫曼树及其应用 104
5.5.1哈夫曼树 104
5.5.2哈夫曼树的应用——哈夫曼编码 105
5.6小结 106
习题 106
第6章 图 109
6.1图的基本概念 109
6.1.1图的定义 109
6.1.2基本术语 110
6.2图的表示和实现 112
6.2.1邻接矩阵 112
6.2.2邻接表 114
6.2.3十字链表 116
6.2.4邻接多重表 117
6.3图的遍历 119
6.3.1深度优先搜索 119
6.3.2广度优先搜索 121
6.3.3非连通图的遍历 122
6.4.1 生成树 123
6.4应用举例 123
6.4.2拓扑排序 128
6.4.3关键路径 132
6.4.4最短路径 137
6.5小结 140
习题 140
第7章 排序 143
7.1内部排序 144
7.1.1简单排序 144
7.1.2希尔排序 148
7.1.3快速排序 149
7.1.4归并排序 152
7.1.5堆排序 154
7.1.6基数排序 156
7.2外部排序 158
7.2.1外部排序方法 158
7.2.2自然归并 159
7.2.3多路平衡归并 160
7.2.4置换－选择排序 161
7.2.5最佳归并树 163
7.3排序效益评估 164
7.4小结 164
习题 164
8.1.1查找的定义 167
第8章 查找 167
8.1基本概念 167
8.1.2基本术语 168
8.2线性表的查找 169
8.2.1顺序查找 169
8.2.2二分查找 170
8.2.3分块查找 173
8.3树表的查找 175
8.3.1二叉排序树和平衡二叉树 175
8.3.2 B树 187
8.3.3键树 196
8.4.1散列表 199
8.4散列查找 199
8.4.2散列函数的构造方法 201
8.4.3处理冲突的方法 203
8.4.4散列表的查找及分析 206
8.5小结 209
习题 209
第9章 算法设计方法 211
9.1递归与分治法 211
9.1.1递归技术 211
9.1.2分治法 214
9.2.2 0-1背包问题 217
9.2.1回溯法的基本思想 217
9.2回溯法 217
9.2.3旅行售货员问题 219
9.2.4 n皇后问题 220
9.3动态规划法 222
9.3.1动态规划法的基本思想 222
9.3.2计算矩阵连乘积 223
9.3.3动态规划法的基本要素 223
9.4贪心法 227
9.4.1贪心法的基本思想 227
9.4.2哈夫曼编码问题 227
9.4.3贪心法与动态规划法的差异 231
9.5.1分支限界法的基本思想 232
9.5分支限界法 232
9.5.2 0-1背包问题 233
9.5.3旅行售货员问题 234
9.6小结 238
习题 238
第10章 高级专题 239
10.1集合 239
10.1.1集合的定义 239
10.1.2字典 243
10.1.3有序字典 248
10.1.4优先队列 250
10.2.1自组织线性表 253
10.2线性结构的扩展 253
10.2.2跳跃表 254
10.2.3动态存储管理 256
10.3树形结构的扩展 259
10.3.1竞赛树 259
10.3.2 Trie树 260
10.3.3伸展树 262
10.4 小结 263
习题 263
附录 数学预备知识 265
参考文献 269