3.6逐步求精法 7 1
第1章 概论 1
1.1什么是数据结构 1
目 录 1
1.2数据的逻辑结构 3
1.3数据的类型 4
1.4数据的存储结构 6
1.5数据的运算 8
1.6数据的分析和性能评价 12
1.6.1算法设计的要求 12
1.6.2选择数据结构 13
1.6.3算法效率的度量 13
1.6.4算法的存储空间需求 14
小结 15
综合练习一 15
一、选择题 15
小结 1 16
二、思考题 16
三、上机题 17
第2章类C语言基础知识 18
2.1.1 C语言简史 18
2.1 C语言简介 18
2.1.2特点 19
2.1.3 C语言程序的结构 19
2.2 C语言数据类型 19
2.2.1常量与变量 19
2.2.2基本类型 20
2.2.3构造类型 20
2.2.4其他重要数据类型 22
2.3 C语言运算符与表达式 23
2.3.1 算术运算 23
2.3.2逻辑运算 24
2.3.3位运算 24
2.3.4其他重要运算符 24
2.4 C语言函数 25
2.3.5 运算符的优先级 25
2.4.2 函数的调用 26
2.4.1定义函数 26
2.4.3 函数的返回 27
2.5 C语言常用语句 28
2.5.1输入／输出语句 28
2.5.2条件语句、开关语句 29
2.5.3循环语句 30
2.6综合应用实例 33
二、思考题 1 35
三、上机题 1 36
一、选择题 38
小结 38
综合练习二 38
二、思考题 39
三、上机题 40
第3章算法基础 42
3.1 递归法 42
3.1.1递归的概念 42
3.1.2递归过程和递归工作栈 46
3.1.3递归的应用 50
3.2穷举法 54
3.3迭代法 57
3.4.1 倒推法 59
3.4递推法 59
3.4.2顺推法 61
3.5 分治法 65
3.5.1分治法的设计思想 65
3.5.2分治法所能解决的问题 65
3.5.3分治法的几种变形 70
小结 73
综合练习三 73
一、选择题 73
二、思考题 74
三、上机题 74
4.1 向量 75
4.1.1向量的运算 75
第4章顺序表 75
4.1.2 Josephus问题 77
4.2栈 78
4.3.1数制转换 81
4.3栈的应用 81
4.3.2表达式求值 82
4.3.3迷宫求解 84
4.4 队列 87
4.5利用队列打印二次展开式的算法 89
4.6限制存取点的表 91
小结 91
综合练习四 91
一、选择题 91
二、思考题 91
三、上机题 92
5.1 单链表 93
第5章链表 93
5.2栈的链表表示 96
5.3队列的链表表示 97
5.4特殊的链表 99
5.4.1 双向链表 99
5.4.2循环链表 100
5.4.3队列的循环链表表示 101
5.5一元多项式的链表表示及其运算 101
小结 104
综合练习五 104
一、选择题 104
二、思考题 105
三、上机题 106
第6章 串 107
6.1 串的概念 107
6.2串的运算实现 110
6.2.1基本的串运算 110
6.2.2串运算的实现 111
6.3字符串的模式匹配 112
6.4 KMP算法 113
综合练习六 116
一、选择题 116
二、思考题 116
三、上机题 117
第7章 多维数组与广义表 118
7.1多维数组的定义 118
7.2多维数组的逻辑结构 119
7.3多维数组的顺序存储 119
7.4矩阵的压缩存储 120
7.4.1 特殊矩阵 121
7.4.2稀疏矩阵 122
7.5 广义表 127
7.5.1 广义表的定义 127
7.5.2 广义表的存储结构 128
7.5.3 广义表的运算 130
小结 134
综合练习七 134
一、选择题 134
第8章树和森林 138
8.1树的定义和基本术语 138
8.2 二叉树 140
8.2.1二叉树的定义 140
8.2.2二叉树的性质 141
8.2.3二叉树的存储结构 142
8.3.1遍历的递归算法 143
8.3遍历二叉树 143
8.3.2遍历的非递归算法 145
8.4线索二叉树 148
8.4.1线索化二叉树 148
8.4.2遍历线索二叉树 150
8.5树的存储结构 152
8.6森林和二叉树的转换 154
8.7树和森林的遍历 155
8.8.1最优二叉树 156
8.8赫夫曼树及其应用 156
8.8.2赫夫曼编码 158
小结 160
综合练习八 160
一、选择题 160
二、思考题 161
三、上机题 161
9.1 基本概念 162
第9章查找 162
9.2线性表的查找 163
9.2.1 顺序查找 163
9.2.2二分查找 164
9.2.3 分块查找 166
9.3树表的查找 168
9.3.1 二叉排序树 168
9.3.2平衡的二叉排序树 173
9.4散列表的查找 176
9.4.1 散列表 176
9.4.2散列函数的构造方法 176
9.4.3冲突的处理 178
小结 180
综合练习九 180
一、选择题 180
三、上机题 181
二、思考题 181
第10章 图 182
10.1 图的定义和术语 182
10.2图的存储结构 184
10.2.1数组表示法 184
10.2.2邻接表表示法 185
10.2.3十字链表 188
10.2.4邻接多重表 189
10.3图的遍历 190
10.3.1深度优先搜索 190
10.3.2广度优先搜索 191
10.4图的连通性 192
10.5图的最小生成树 193
10.6拓扑排序 196
10.7关键路径（图） 197
10.8最短路径 199
10.8.1从一个结点到其他各个结点的最短路径 200
10.8.2任意两个结点的最短路径 202
小结 203
综合练习十 203
一、选择题 203
二、思考题 204
三、上机题 205
第11章排序 206
11.1概述 206
1 1.2插入排序 208
11.2.1直接插入排序 208
1 1.2.2折半插入排序 210
11.2.3表插入排序 210
11.2.4希尔排序 211
11.3交换排序 213
11.3.1起泡排序 213
11.3.2快速排序 215
11.4.1直接选择排序 216
11.4选择排序 216
1 1.4.2锦标赛排序 217
11.4.3堆排序 218
11.5归并排序 221
1 1.5.1 归并 221
11.5.2迭代的归并排序算法 222
11.5.3递归的表归并排序 223
1 1.6基数排序 224
1 1.6.1多排序码排序 224
1 1.6.2链式基数排序 225
1 1.7外排序 228
11.7.1外排序的基本过程 228
11.7.2 K路平衡归并 229
11.7.3初始归并段的生成 231
11.7.4并行操作的缓冲区处理 232
11.7.5最佳归并树 233
小结 234
综合练习十一 235
一、选择题 235
二、思考题 236
三、上机题 236
第12章文件 237
12.1文件基本概念 237
12.2顺序文件 238
12.3索引文件 239
12.4 Hash文件 240
12.5多关键字文件 241
小结 242
综合练习十二 242
一、选择题 242
二、思考题 242
三、上机题 242
13.1回溯与界限剪枝法 243
第13章算法设计基本方法 243
13.1.1 回溯与界限剪枝法经典问题 244
13.1.2回溯与界限剪枝法概述 245
13.1.3 回溯与界限剪枝法实例分析 246
13.1.4回溯与界限剪枝法综述 251
13.2贪心法 251
13.2.1贪心法经典问题 251
13.2.2贪心法概述 253
13.2.3贪心法实例分析 254
13.2.4贪心法小结 255
13.3动态规划法 255
13.3.1动态规划法经典问题 255
13.3.2动态规划法概述 256
13.3.3动态规划法实例分析 258
综合练习十三 264
一、选择题 264
小结 264
13.3.4动态规划法小结 264
二、思考题 265
三、上机题 265
参考答案 267
第1章 267
第2章 267
第3章 268
第4章 269
第5章 271
第6章 272
第7章 274
第8章 275
第9章 276
第10章 277
第11章 279
第12章 281
第13章 282
参考文献 284