第1章 概论 1
1.1什么是数据结构 1
1.1.1基本概念 1
1.1.2数据的逻辑结构 2
1.1.3数据的存储结构 3
1.1.4数据结构的运算 4
1.2数据抽象和抽象数据类型 5
1.2.1抽象、数据抽象和过程抽象 5
1.2.2封装与信息隐蔽 5
1.2.3数据类型和抽象数据类型 5
1.2.4数据结构与抽象数据类型 6
1.3描述数据结构 7
1.3.1数据结构的规范 7
1.3.2实现数据结构 8
1.4算法和算法分析 9
1.4.1算法及其性能标准 9
1.4.2算法的时间复杂度 10
1.4.3渐近时间复杂度 12
1.4.4最坏、最好和平均情况时间复杂度 13
1.4.5算法的空间复杂度 13
小结 14
习题1 14
第2章 数组和链表 16
2.1结构与联合 16
2.1.1结构 16
2.1.2联合 17
2.2数组 18
2.2.1一维数组 18
2.2.2二维数组 18
2.2.3多维数组 20
2.3链表 20
2.3.1指针 20
2.3.2单链表 24
2.3.3带表头结点的单链表 30
2.3.4循环链表 31
2.3.5双向链表 31
小结 33
习题2 33
第3章 堆栈和队列 35
3.1堆栈 35
3.1.1堆栈ADT 35
3.1.2堆栈的顺序表示 36
3.1.3堆栈的链接表示 38
3.2队列 39
3.2.1队列ADT 39
3.2.2队列的顺序表示 40
3.2.3队列的链接表示 43
*3.3表达式的计算 43
3.3.1表达式 43
3.3.2中缀表达式转换为后缀表达式 44
3.3.3计算后缀表达式的值 48
*3.4递归和递归过程 50
3.4.1递归的概念 50
3.4.2递归的实现 51
*3.5演示和测试 53
小结 55
习题3 55
第4章 线性表和数组ADT 57
4.1线性表 57
4.1.1线性表ADT 57
4.1.2线性表的顺序表示 58
4.1.3线性表的链接表示 61
4.1.4两种存储表示的比较 65
*4.2多项式的算术运算 65
4.2.1多项式ADT 65
4.2.2多项式的链接表示 66
4.2.3多项式的输入和输出 67
4.2.4多项式相加 69
4.3数组作为抽象数据类型 71
4.4特殊矩阵 72
4.4.1对称矩阵 72
*4.4.2带状矩阵 72
4.5稀疏矩阵 74
4.5.1稀疏矩阵ADT 74
4.5.2稀疏矩阵的顺序表示 74
4.5.3稀疏矩阵转置 76
*4.5.4稀疏矩阵相乘 78
4.5.5稀疏矩阵的正交链表表示 81
*4.5.6建立正交链表 84
*4.5.7打印正交链表 85
小结 86
习题4 86
第5章 字符串和广义表 88
5.1字符串 88
5.1.1字符串ADT 88
5.1.2字符串的存储表示 89
5.1.3简单模式匹配算法 90
*5.1.4模式匹配的KMP算法 93
*5.2广义表 97
5.2.1广义表的概念 97
5.2.2广义表ADT 98
5.2.3广义表的存储表示 99
5.2.4广义表的算法 100
小结 101
习题5 101
第6章 树 102
6.1树的基本概念 102
6.1.1树的定义 102
6.1.2基本术语 103
6.2二叉树 104
6.2.1二叉树的定义和性质 104
6.2.2二叉树ADT 106
6.2.3二叉树的存储表示 107
6.2.4二叉树的遍历 111
*6.2.5二叉树遍历的非递归算法 114
*6.2.6二叉树遍历的应用实例 117
*6.2.7线索二叉树 119
6.3树和森林 122
6.3.1森林与二叉树的转换 122
6.3.2树和森林的存储表示 123
6.3.3树和森林的遍历 125
*6.4堆和优先权队列 126
6.4.1堆 127
6.4.2优先权队列 129
6.5哈夫曼树和哈夫曼编码 132
6.5.1树的路径长度 132
6.5.2哈夫曼树和哈夫曼算法 134
6.5.3哈夫曼编码 136
*6.6并查集和等价关系 137
6.6.1并查集 137
6.6.2并查集的实现 138
6.6.3集合按等价关系分组 141
小结 142
习题6 142
第7章 集合和搜索 145
7.1集合及其表示 145
7.1.1集合和搜索 145
7.1.2集合ADT 146
7.1.3集合的表示 147
7.2顺序搜索 147
7.3二分搜索 149
7.3.1对半搜索 150
7.3.2二叉判定树 151
*7.3.3斐波那契搜索 153
*7.4搜索算法的时间下界 154
小结 155
习题7 156
第8章 搜索树 157
8.1二叉搜索树 157
8.1.1二叉搜索树的定义 157
8.1.2二叉搜索树的搜索 157
8.1.3二叉搜索树的插入 158
8.1.4二叉搜索树的删除 160
*8.1.5二叉搜索树的高度 162
8.2二叉平衡树 163
8.2.1二叉平衡树的定义 163
8.2.2二叉平衡树的平衡旋转 164
8.2.3二叉平衡树的插入 170
8.2.4二叉平衡树的删除 173
8.2.5二叉平衡数的高度 176
8.3 B-树 176
8.3.1 m叉搜索树 176
8.3.2 B-树的定义 178
8.3.3 B-树的高度 179
8.3.4 B-树的搜索 179
8.3.5 B-树的插入 179
8.3.6 B-树的删除 182
*8.4键树 184
8.4.1键树的定义 184
8.4.2双链树 185
8.4.3 Trie树 186
*8.5伸展树 187
小结 190
习题8 190
第9章 跳表和散列表 192
9.1字典 192
*9.2跳表 192
9.2.1什么是跳表 193
9.2.2跳表的搜索 196
9.2.3跳表的插入 197
9.2.4跳表的删除 198
9.3散列表 199
9.3.1散列技术 199
9.3.2散列函数 200
9.3.3解决冲突的拉链法 202
9.3.4解决冲突的线性探查法 203
9.3.5解决冲突的其他开地址法 207
9.3.6性能分析 209
小结 209
习题9 210
第10章 图 211
10.1图的基本概念 211
10.1.1图的定义与术语 211
10.1.2图ADT 214
10.2图的存储结构 215
10.2.1矩阵表示法 215
10.2.2邻接表表示法 218
*10.2.3多重表表示法 221
10.3图的遍历 222
10.3.1深度优先遍历 222
10.3.2宽度优先遍历 224
10.4拓扑排序和关键路径 226
10.4.1拓扑排序 226
*10.4.2关键路径 230
10.5最小代价生成树 233
10.5.1普里姆算法 234
*10.5.2克鲁斯卡尔算法 235
*10.6最短路径 237
10.6.1单源最短路径 238
10.6.2所有顶点之间的最短路径 241
小结 244
习题10 244
第11章 内排序 247
11.1排序的基本概念 247
11.2插入排序 248
11.2.1直接插入排序 248
11.2.2*希尔排序 252
11.3交换排序 253
11.3.1冒泡排序 253
11.3.2快速排序 255
11.4合并排序 260
11.4.1两路合并排序 260
11.4.2合并排序的迭代算法 260
*11.4.3链表上的合并排序 262
11.5选择排序 265
11.5.1简单选择排序 266
*11.5.2堆排序 267
*11.6排序算法的时间下界 268
*11.7基数排序 269
小结 273
习题11 273
第12章 文件和外排序 275
*12.1辅助存储器简介 275
12.1.1主存储器和辅助存储器 275
12.1.2磁盘存储器 275
12.2文件 277
12.2.1文件的基本概念 277
12.2.2文件的组织方式 277
12.2.3 C语言文件 281
12.3文件的索引结构 282
12.3.1静态索引结构 282
12.3.2动态索引结构 283
*12.4外排序 283
12.4.1外排序的基本过程 284
12.4.2初始游程的生成 284
12.4.3多路合并 286
12.4.4最佳合并树 288
小结 289
习题12 290
第13章 实习指导和实习题 291
13.1实习目的和要求 291
13.1.1实习目的 291
13.1.2实习要求 291
13.2实习步骤 292
13.3实习报告 292
13.4实习题 293
实习1数组操作 293
实习2链表操作 294
实习3表达式计算 294
实习4队列运算和用户界面设计 295
实习5线性表运算及应用 295
实习6一元多项式的相加和相乘 295
实习7对称矩阵的压缩存储 296
实习8稀疏矩阵的三元组表 296
实习9稀疏矩阵的正交链表 296
实习10字符串运算和文本处理 297
实习11二叉树的基本运算 297
实习12哈夫曼编码和译码系统 298
实习13 B-树检索 298
实习14散列表检索 299
实习15 图运算及其应用 299
实习16内排序算法及其性能比较 300
实习17外排序 300
13.5实习报告范例 301
13.5.1实习题：表达式计算 301
13.5.2实习报告 301
附录A 软件工程概述 307
A.1软件开发方法 307
A.2软件文档写作 309
A.3系统测试方法 310
附录B 专用名词中英文对照表 314
参考文献 320