第一章 绪论 1
§1-1 学习数据结构的意义 1
§1-2 有关数据结构的基本概念和术语 5
§1-3 算法的描述工具——拟PASCAL语言 7
§1-4 算法分析技术初步 12
练习 16
第二章 线性表 17
§2-1 线性表的定义和运算 17
一、线性表的定义 17
二、线性表的运算 18
§2-2 顺序分配的存贮结构 18
一、向量——线性表的顺序存贮结构 18
二、向量中基本运算的实现 19
三、运算的时间分析 23
四、其它运算示例 24
§2-3 链式分配的存贮结构 30
一、单链表和指针 30
二、链表的基本运算 34
三、链表的实现 36
四、链表的其它运算示例 41
五、循环链表 49
六、双向链表 53
§2-4 向量和链表的综合比较 55
练习 58
第三章 栈和队列 60
§3-1 栈的结构特点和运算 60
一、栈的定义和运算 60
二、栈的存贮结构和基本运算的实现 61
§3-2 LIFO原则和栈的应用 62
§3-3 队列的结构特点及运算 68
一、队列的定义和运算 68
二、队列的存贮结构和基本运算的实现 68
§3-4 FIFO原则和队列的应用 72
§3-5 求迷宫的最短路径——栈和队列的综合应用 77
练习 82
第四章 树和二叉树 84
§4-1 树的定义和术语 84
§4-2 二叉树 88
一、二叉树的定义和存贮结构 88
二、二叉树的几个基本性质 89
三、几种特殊形态的二叉树 90
四、二叉树的生成算法 93
§4-3 遍历二叉树 95
一、遍历二叉树的递归定义和递归算法 96
二、遍历算法的非递归形式 100
三、遍历算法应用示例 102
§4-4 树的存贮结构和树的遍历 113
一、孩子-兄弟链表 113
二、树的遍历 114
§4-5 二叉排序树 115
一、二叉排序树的生成 116
二、二叉排序树上结点的删除 118
§4-6 哈夫曼树 122
§4-7 解答树 127
练习 132
第五章 图 134
§5-1 图的定义和基本术语 134
§5-2 图的存贮结构 137
一、深度优先搜索遍历连通图 142
§5-3 图的遍历 142
二、广度优先搜索遍历连通图 146
三、非连通图的遍历 151
四、图的遍历算法的应用 152
§5-4 最小生成树 156
§5-5 单源最短路径 158
§5-6 拓扑排序 162
§5-7 关键路径 167
练习 171
第六章 查找 173
§6-1 查找的基本概念 173
§6-2 顺序表的查找 174
一、顺序查找 175
二、二分查找 176
三、分块查找 179
§6-3 二叉排序树查找和动态平衡技术介绍 182
§6-4 最优二叉查找树及其近似算法 187
§6-5 哈希表及其查找 192
一、哈希表 192
二、构造均匀的哈希函数的几种方法 195
三、解决冲突的方法和建哈希表示例 198
四、哈希表的查找及性能分析 201
练习 205
第七章 排序 206
§7-1 排序的基本概念 206
§7-2 简单排序方法 209
一、插入排序 209
二、起泡排序 211
§7-3 先进排序方法 214
一、快速排序 214
二、归并排序 219
三、堆排序 221
四、基数排序 226
§7-4 排序方法的选择和使用 230
§7-5 外排简介 234
练习 235
第八章 文件 236
§8-1 文件的基本概念 236
§8-2 顺序文件 238
§8-3 索引文件 240
§8-4 索引顺序文件 241
§8-5 直接存取文件 248
§8-6 多关键字文件 249
一、多重表文件 249
二、倒排文件 249
练习 251
第九章 数据结构的程序设计实例 252
§9-1 从问题到程序的一般过程 252
一、建立数据模型和设计算法 252
二、编制伪码算法 253
三、设定存贮结构并求精算法 254
四、编制上机代码并调试运行 257
§9-2 程序实例 262
一、任务分配问题 262
二、排队问题的系统仿真 271
三、集合的一种表示法及其应用 282
四、课程安排问题 293
五、建造符号表示例 305
六、二叉排序树索引的文件查找 310
七、计算网络图的关键路径 324
附录 过程名索引 335