数据结构(C++版)

　　第1章 绪论1
　　 1.1 数据结构在程序设计中的作用1
　　 1.2 本书讨论的主要内容3
　　 1.3 数据结构的基本概念5
　　 1.3.1 数据结构5
　　 1.3.2 抽象数据类型7
　　 1.4 算法及算法分析9
　　 1.4.1 算法及其描述方法9
　　 1.4.2 算法分析12
　　 思想火花――好算法是反复努力和重新修正的结果16
　　 习题117
　　 思考题119
　　第2章 线性表21
　　 2.1 线性表的逻辑结构21
　　 2.1.1 线性表的定义21
　　 2.1.2 线性表的抽象数据类型定义22
　　 2.2 线性表的顺序存储结构及实现24
　　 2.2.1 线性表的顺序存储结构――顺序表24
　　 2.2.2 顺序表的实现25
　　 2.3 线性表的链接存储结构及实现30
　　 2.3.1 单链表30
　　 2.3.2 循环链表40
　　 2.3.3 双链表40
　　 2.4 顺序表和链表的比较42
　　 2.4.1 时间性能比较42
　　 2.4.2 空间性能比较43
　　 2.5 线性表的其他存储方法43
　　 2.5.1 静态链表43
　　 2.5.2 间接寻址45
　　 2.6 应用举例45
　　 2.6.1 顺序表的应用举例――大整数求和45
　　 2.6.2 单链表的应用举例――一元多项式求和47
　　 思想火花――好程序要能识别和处理各种输入50
　　 习题250
　　 思考题253
　　第3章 栈和队列55
　　 3.1 栈55
　　 3.1.1 栈的逻辑结构55
　　 3.1.2 栈的顺序存储结构及实现57
　　 3.1.3 栈的链接存储结构及实现61
　　 3.1.4 顺序栈和链栈的比较63
　　 3.2 队列64
　　 3.2.1 队列的逻辑结构64
　　 3.2.2 队列的顺序存储结构及实现65
　　 3.2.3 队列的链接存储结构及实现68
　　 3.2.4 循环队列和链队列的比较71
　　 3.3 应用举例71
　　 3.3.1 栈的应用举例――表达式求值71
　　 3.3.2 队列的应用举例――火车车厢重排73
　　 思想火花――直觉可能是错误的75
　　 习题375
　　 思考题377
　　第4章 字符串和多维数组79
　　 4.1 字符串79
　　 4.1.1 字符串的定义79
　　 4.1.2 字符串的存储结构80
　　 4.1.3 模式匹配81
　　 4.2 多维数组85
　　 4.2.1 数组的定义85
　　 4.2.2 数组的存储结构与寻址86
　　 4.3 矩阵的压缩存储87
　　 4.3.1 对称矩阵的压缩存储87
　　 4.3.2 三角矩阵的压缩存储88
　　 4.3.3 对角矩阵的压缩存储89
　　 4.3.4 稀疏矩阵的压缩存储90
　　 4.4 应用举例92
　　 4.4.1 字符串的应用举例――凯撒密码92
　　 4.4.2 数组的应用举例――幻方93
　　 思想火花――用常识性的思维去思考问题94
　　 习题494
　　 思考题496
　　第5章 树和二叉树99
　　 5.1 树的逻辑结构99
　　 5.1.1 树的定义和基本术语99
　　 5.1.2 树的抽象数据类型定义101
　　 5.1.3 树的遍历操作102
　　 5.2 树的存储结构103
　　 5.2.1 双亲表示法103
　　 5.2.2 孩子表示法104
　　 5.2.3 双亲孩子表示法106
　　 5.2.4 孩子兄弟表示法107
　　 5.3 二叉树的逻辑结构107
　　 5.3.1 二叉树的定义108
　　 5.3.2 二叉树的基本性质109
　　 5.3.3 二叉树的抽象数据类型定义112
　　 5.3.4 二叉树的遍历操作113
　　 5.4 二叉树的存储结构及实现114
　　 5.4.1 顺序存储结构114
　　 5.4.2 二叉链表115
　　 5.4.3 三叉链表120
　　 5.4.4 线索链表120
　　 5.5 二叉树遍历的非递归算法125
　　 5.5.1 前序遍历非递归算法125
　　 5.5.2 中序遍历非递归算法126
　　 5.5.3 后序遍历非递归算法127
　　 5.6 树、森林与二叉树的转换128
　　 5.7 应用举例131
　　 5.7.1 二叉树的应用举例――哈夫曼树及哈夫曼编码131
　　 5.7.2 树的应用举例――八枚硬币问题136
　　 思想火花――调试程序与魔术表演137
　　 习题5138
　　 思考题5140
　　第6章 图143
　　 6.1 图的逻辑结构143
　　 6.1.1 图的定义和基本术语143
　　 6.1.2 图的抽象数据类型定义147
　　 6.1.3 图的遍历操作148
　　 6.2 图的存储结构及实现151
　　 6.2.1 邻接矩阵152
　　 6.2.2 邻接表155
　　 6.2.3 十字链表159
　　 6.2.4 邻接多重表159
　　 6.2.5 邻接矩阵和邻接表的比较160
　　 6.3 最小生成树161
　　 6.3.1 MST性质161
　　 6.3.2 Prim算法162
　　 6.3.3 Kruskal算法165
　　 6.4 最短路径168
　　 6.4.1 Dijkstra算法169
　　 6.4.2 Floyd算法171
　　 6.5 有向无环图及其应用173
　　 6.5.1 AOV网与拓扑排序173
　　 6.5.2 AOE网与关键路径176
　　 6.6 应用举例179
　　 6.6.1 图的应用举例1――七桥问题179
　　 6.6.2 图的应用举例2――七巧板涂色180
　　 思想火花――数据模型在问题求解中的作用181
　　 习题6181
　　 思考题6185
　　第7章 查找技术187
　　 7.1 概述187
　　 7.1.1 查找的基本概念187
　　 7.1.2 查找算法的性能188
　　 7.2 线性表的查找技术189
　　 7.2.1 顺序查找189
　　 7.2.2 折半查找191
　　 7.3 树表的查找技术195
　　 7.3.1 二叉排序树195
　　 7.3.2 平衡二叉树201
　　 7.4 散列表的查找技术206
　　 7.4.1 概述206
　　 7.4.2 散列函数的设计207
　　 7.4.3 处理冲突的方法210
　　 7.4.4 散列查找的性能分析213
　　 7.4.5 开散列表与闭散列表的比较214
　　 思想火花――把注意力集中于主要因素，不要纠缠于噪声214
　　 习题7215
　　 思考题7218
　　第8章 排序技术219
　　 8.1 概述219
　　 8.1.1 排序的基本概念219
　　 8.1.2 排序算法的性能220
　　 8.2 插入排序221
　　 8.2.1 直接插入排序221
　　 8.2.2 希尔排序223
　　 8.3 交换排序225
　　 8.3.1 起泡排序225
　　 8.3.2 快速排序228
　　 8.4 选择排序231
　　 8.4.1 简单选择排序231
　　 8.4.2 堆排序233
　　 8.5 归并排序238
　　 8.5.1 二路归并排序的非递归实现238
　　 8.5.2 二路归并排序的递归实现241
　　 8.6 分配排序242
　　 8.6.1 桶式排序242
　　 8.6.2 基数排序244
　　 8.7 各种排序方法的比较247
　　 思想火花――学会“盒子以外的思考”249
　　 习题8250
　　 思考题8253
　　第9章 索引技术255
　　 9.1 索引的基本概念255
　　 9.2 线性索引技术256
　　 9.2.1 稠密索引256
　　 9.2.2 分块索引257
　　 9.2.3 多重表258
　　 9.2.4 倒排表258
　　 9.3 树形索引259
　　 9.3.1 2-3树259
　　 9.3.2 B_树262
　　 9.3.3 B+树266
　　 思想火花――随处可见的索引267
　　 习题9268
　　附录A 预备知识271
　　 A.1 数学术语271
　　 A.2 级数求和271
　　 A.3 集合272
　　 A.4 关系273
　　附录B C++语言基本语法275
　　 B.1 程序结构275
　　 B.2 数据类型276
　　 B.3 控制语句278
　　 B.4 输入与输出279
　　 B.5 动态存储分配280
　　 B.6 函数281
　　 B.7 类与对象284
　　 B.8 模板287
　　 B.9 异常处理288
　　附录C 词汇索引289
　　参考文献294