正版新书]普通高校本科计算机专业特色教材精选·算法与程序

第1章绪论1
1.1问题求解与程序设计2
1.1.1程序设计的一般过程2
1.1.2数据结构在程序设计中的作用5
1.1.3算法在程序设计中的作用6
1.1.4本书讨论的主要内容7
1.2数据结构的基本概念9
1.2.1数据结构9
1.2.2抽象数据类型11
1.3算法的基本概念13
1.3.1算法及算法的特性13
1.3.2算法的描述方法14
1.4算法分析16
1.4.1算法的时间复杂度16
1.4.2算法的空间复杂度18
1.4.3算法分析举例18
1.5扩展与提高21
1.5.1从数据到大数据21
1.5.2算法分析的其他渐进符号22
思想火花——概率算法23
习题124
第2章线性表27
2.1引言28
2.2线性表的逻辑结构29
2.2.1线性表的定义29数据结构——从概念到C++实现（第3版）目录2.2.2线性表的抽象数据类型定义30
2.3线性表的顺序存储结构及实现31
2.3.1顺序表的存储结构31
2.3.2顺序表的实现32
2.3.3顺序表的使用37
2.4线性表的链接存储结构及实现38
2.4.1单链表的存储结构38
2.4.2单链表的实现40
2.4.3单链表的使用48
2.4.4双链表49
2.4.5循环链表50
2.5顺序表和链表的比较51
2.6扩展与提高52
2.6.1线性表的静态链表存储52
2.6.2顺序表的动态分配方式54
2.7应用实例56
2.7.1约瑟夫环问题56
2.7.2一元多项式求和59
思想火花——好算法是反复努力和重新修正的结果63
习题264
实验题267
第3章栈和队列69
3.1引言70
3.2栈71
3.2.1栈的逻辑结构71
3.2.2栈的顺序存储结构及实现72
3.2.3栈的链接存储结构及实现75
3.2.4顺序栈和链栈的比较77
3.3队列78
3.3.1队列的逻辑结构78
3.3.2队列的顺序存储结构及实现79
3.3.3队列的链接存储结构及实现83
3.3.4循环队列和链队列的比较86
3.4扩展与提高86
3.4.1两栈共享空间86
3.4.2双端队列88
3.5应用举例89
3.5.1括号匹配问题89
3.5.2表达式求值91
思想火花——好程序要能识别和处理各种输入94
习题395
实验题397
第4章字符串和多维数组99
4.1引言100
4.2字符串101
4.2.1字符串的逻辑结构101
4.2.2字符串的存储结构103
4.2.3模式匹配103
4.3多维数组107
4.3.1数组的逻辑结构107
4.3.2数组的存储结构与寻址108
4.4矩阵的压缩存储109
4.4.1特殊矩阵的压缩存储109
4.4.2稀疏矩阵的压缩存储112
4.5扩展与提高114
4.5.1稀疏矩阵的转置运算114
4.5.2广义表116
4.6应用实例119
4.6.1发纸牌119
4.6.2八皇后问题121
思想火花——用常识性的思维去思考问题124
习题4124
实验题4126
第5章树和二叉树127
5.1引言128
5.2树的逻辑结构129
5.2.1树的定义和基本术语129
5.2.2树的抽象数据类型定义131
5.2.3树的遍历操作131
5.3树的存储结构132
5.3.1双亲表示法132
5.3.2孩子表示法132
5.3.3孩子兄弟表示法133
5.4二叉树的逻辑结构134
5.4.1二叉树的定义134
5.4.2二叉树的基本性质136
5.4.3二叉树的抽象数据类型定义138
5.4.4二叉树的遍历操作139
5.5二叉树的存储结构140
5.5.1顺序存储结构140
5.5.2二叉链表141
5.5.3三叉链表146
5.6森林147
5.6.1森林的逻辑结构147
5.6.2树、森林与二叉树的转换147
5.7最优二叉树149
5.7.1哈夫曼算法149
5.7.2哈夫曼编码152
5.8扩展与提高153
5.8.1二叉树遍历的非递归算法153
5.8.2线索链表157
5.9应用实例161
5.9.1堆与优先队列161
5.9.2并查集164
思想火花——调试程序与魔术表演166
习题5167
实验题5169
第6章图171
6.1引言172
6.2图的逻辑结构173
6.2.1图的定义和基本术语173
6.2.2图的抽象数据类型定义176
6.2.3图的遍历操作176
6.3图的存储结构及实现179
6.3.1邻接矩阵179
6.3.2邻接表182
6.3.3邻接矩阵和邻接表的比较187
6.4最小生成树188
6.4.1Prim算法189
6.4.2Kruskal算法191
6.5最短路径195
6.5.1Dijkstra算法196
6.5.2Floyd算法199
6.6有向无环图及其应用200
6.6.1AOV网与拓扑排序201
6.6.2AOE网与关键路径203
6.7扩展与提高206
6.7.1图的其他存储方法206
6.7.2图的连通性208
6.8应用实例209
6.8.1七巧板涂色问题209
6.8.2医院选址问题211
思想火花——直觉可能是错误的214
习题6214
实验题6218
第7章查找技术219
7.1概述220
7.1.1查找的基本概念220
7.1.2查找算法的性能221
7.2线性表的查找技术221
7.2.1线性表查找结构的类定义221
7.2.2顺序查找222
7.2.3折半查找223
7.3树表的查找技术226
7.3.1二叉排序树226
7.3.2平衡二叉树231
7.3.3B树235
7.4散列表的查找技术239
7.4.1散列查找的基本思想239
7.4.2散列函数的设计241
7.4.3处理冲突的方法242
7.4.4散列查找的性能分析246
7.4.5开散列表与闭散列表的比较247
7.5各种查找方法的比较247
7.6扩展与提高248
7.6.1顺序查找的改进——分块查找248
7.6.2折半查找的改进——插值查找249
7.6.3B树的改进——B+树250
思想火花——把注意力集中于主要因素，不要纠缠于噪声251
习题7251
实验题7254
第8章排序技术255
8.1概述256
8.1.1排序的基本概念256
8.1.2排序算法的性能257
8.1.3排序类的定义257
8.2插入排序258
8.2.1直接插入排序258
8.2.2希尔排序260
8.3交换排序262
8.3.1起泡排序262
8.3.2快速排序264
8.4选择排序267
8.4.1简单选择排序267
8.4.2堆排序269
8.5归并排序274
8.5.1二路归并排序的递归实现274
8.5.2二路归并排序的非递归实现275
8.6各种排序方法的比较277
8.6.1各种排序技术的使用范例277
8.6.2各种排序方法的综合比较278
8.7扩展与提高280
8.7.1排序问题的时间下界280
8.7.2基数排序281
思想火花——学会“盒子以外的思考”283
习题8284
实验题8286
附录A预备知识289
附录BC++语言基本语法293
附录C词汇索引307
参考文献311

第5章树和二叉树本章概述前面讨论的数据结构都属于线性结构，线性结构主要描述具有单一的前驱和后继关系的数据。树结构是一种比线性结构更复杂的数据结构，适合描述具有层次关系的数据，如祖先—后代、上级—下属、整体—部分以及其他类似的关系。树结构在计算机领域有着广泛的应用，例如，在编译程序中用语法树来表示源程序的语法结构，在数据挖掘中用决策树来进行数据分类等。
本章的内容分为树和二叉树两部分。由实际问题引出树结构，介绍树的定义和基本术语，给出树的抽象数据类型定义，讨论树的存储结构；给出二叉树的定义和基本性质，讨论二叉树的存储结构，实现二叉链表存储的二叉树的遍历操作，最后讨论二叉树的经典应用——哈夫曼树。教学重点二叉树的性质；二叉树和树的存储表示；二叉树的遍历及算法实现；树与二叉树的转换关系；哈夫曼树教学难点二叉树的层序遍历算法；二叉树的建立算法；哈夫曼算法教学内容和教学目标知识点树的定义和基本术语树和二叉树的抽象数据类型定义树和二叉树的遍历树的存储结构二叉树的定义二叉树的基本性质二叉树的顺序存储结构二叉链表三叉链表二叉树遍历的递归算法二叉树遍历的非递归算法二叉树的层序遍历算法二叉树的建立算法树、森林和二叉树之间的转换哈夫曼树及哈夫曼编码教学要 求了解理解掌握熟练掌握√√√√√√√√√√√√√√√数据结构——从概念到C++实现（第3版）第5章树和二叉树5.1引言
树结构比较适合描述具有层次关系的数据，如祖先—后代、上级—下属、整体—部分以及其他类似的关系。很多实际问题抽象的数据模型是树结构，请看下面两个例子。
【例51】文件统计。Windows操作系统的文件目录结构如图51(a)所示，其中，“/”表示文件夹，括号内的数字表示文件的大小，单位是KB。假设文件夹本身的大小是1KB，请统计每个文件和文件夹的大小。
【想法——数据模型】文件目录结构具有层次特点，每个文件夹均可包含多个子文件夹和文件，将每个文件或文件夹抽象为一个结点，文件夹与文件之间的关系抽象为结点之间的边，从而将文件目录结构抽象为一个树结构，如图51(b)所示。可以对树进行某种遍历，即对树中所有结点进行没有重复没有遗漏的访问，在遍历过程中统计每个文件和文件夹的大小。那么，应该如何存储文件目录结构并在遍历过程中统计大小呢？
【例52】二叉表示树。编译系统在处理算术表达式时，通常将表达式转换为一棵二叉表示树，通过二叉表示树可以判断算术表达式是否存在语法错误。请将给定的算术表达式转换为二叉表示树。
【想法——数据模型】二叉表示树是对应一个算术表达式的二叉树，并具有以下特点：①叶子结点一定是操作数；②分支结点一定是运算符。将一个算术表达式转化为二叉表示树基于如下规则：①根据运算符的优先顺序，将表达式结合成（左操作数运算符右操作数）的形式；②由外层括号开始，运算符作为二叉表示树的根结点，左操作数作为根结点的左子树，右操作数作为根结点的右子树；③如果某子树对应的操作数为一个表达式，则重复第②步的转换，直到该子树对应的操作数不能再分解。
例如，将表达式(A+B)(C+DE)结合成((A+B)(C+(DE)))，则二叉表示树的根结点是运算符，左操作数即左子树是(A+B)，右操作数即右子树是(C+(DE))。对于左子树(A+B)，其根结点是运算符+，左子树是A，右子树是B。对于右子树(C+(DE))，其根结点是运算符+，左子树是C，右子树是(DE)。依此类推，构造过程如图52所示。