数据结构与算法分析新视角(第2版)

数据结构是高等学校计算机及其相关专业的核心课程，是计算机程序设计的基础。本书按照“像外行一样思考，像专家一样实践”的解决问题的思维方法，基于学习者的认知规律，列举大量实际或工程案例，从具体问题中引出抽象概念，运用类比、图形化描述等方式，对经典数据结构内容做深入浅出的介绍。在介绍数据结构和算法的基本概念和算法分析方法的基础上，从软件开发的角度，通过应用背景或知识背景介绍、数据分析、函数设计、算法设计、测试调试等环节，分别对顺序表、链表、栈、队列、串、数组、树、图等基本类型的数据结构进行了分析和讨论；介绍数据的典型操作方法，如数据排序方法和查找方法；介绍常见的如递归、分治法、动态规划、贪心法等经典算法。

第1章 绪论 1
1.1 从编程说起 1
1.1.1 计算机解题的一般步骤 1
1.1.2 从程序设计角度看数据与数据的处理 2
1.1.3 程序设计方法 3
1.1.4 程序开发过程 3
1.2 程序要处理的数据 4
1.2.1 数值计算与非数值计算的概念 5
1.2.2 数值计算实例 5
1.2.3 非数值计算实例―表 6
1.2.4 非数值计算实例―图 9
1.2.5 非数值计算实例―树 10
1.3 数据结构的引入 11
1.4 数据结构的基本概念 12
1.4.1 数据结构的基本术语 12
1.4.2 数据结构的三个要素 12
1.5 如何设计算法 15
1.5.1 算法的定义与表示方法 15
1.5.2 算法设计与函数设计的关系 16
1.5.3 软件设计方法 17
1.5.4 算法设计的一般步骤 18
1.6 如何评价算法的优劣 21
1.6.1 算法的设计要求 21
1.6.2 算法效率的度量方法 22
1.7 算法性能的事前分析方法 23
1.7.1 问题的规模与算法的策略 24
1.7.2 算法效率的上限与下限 25
1.7.3 上下限问题的数学描述 26
1.7.4 渐近的上限―算法的时间复杂度 29
1.7.5 算法时间复杂度的综合讨论 30
1.7.6 算法的空间效率分析方法 34
1.7.7 算法效率分析的综合例子 37
1.8 算法性能综合考量 39
1.9 本章小结 40
习题 40
第2章 结点逻辑关系为线性的结构―线性表 43
2.1 从逻辑结构角度看线性表 43
2.1.1 实际问题中的线性关系 43
2.1.2 线性表的逻辑结构 44
2.2 线性表的存储结构方法之一―顺序表 45
2.2.1 顺序表的存储结构设计 45
2.2.2 关于结构类型应用的思考与讨论 47
2.2.3 顺序表的运算 49
2.2.4 顺序存储结构的讨论 56
2.3 线性表的存储结构方法之二―链表 56
2.3.1 问题的引入 56
2.3.2 单链表的存储 59
2.3.3 单链表的运算 65
2.3.4 单链表的讨论 78
2.3.5 循环链表 79
2.3.6 双向链表 82
2.3.7 静态链表 83
2.3.8 链表小结 83
2.4 线性表应用举例 84
2.4.1 逆序输出单链表结点值 84
2.4.2 一元多项式的相加 85
2.5 顺序表和链表的比较 92
2.6 本章小结 93
习题 93
第3章 运算受限的线性表―栈和队列 97
3.1 栈―按优选后出方式管理的线性表 97
3.1.1 栈处理模式的引入 97
3.1.2 栈的逻辑结构 100
3.1.3 栈的存储结构设计 102
3.1.4 顺序栈的操作 103
3.1.5 链栈的基本操作 114
3.1.6 各种栈结构的比较 119
3.1.7 栈的应用举例 119
3.2 队列―按优选先出方式管理的线性表 127
3.2.1 队列处理模式的引入 127
3.2.2 队列的逻辑结构 130
3.2.3 队列的顺序存储结构 131
3.2.4 顺序队列的基本操作 143
3.2.5 队列的链式存储结构 147
3.2.6 链队列的基本操作 148
3.2.7 各种队列结构的比较 156
3.2.8 优先队列 156
3.2.9 队列的应用举例 156
3.3 本章小结 168
习题 169
第4章 内容特殊的线性表―多维数组与字符串 171
4.1 多维数组 171
4.1.1 数组的概念 171
4.1.2 数组的存储结构 172
4.2 矩阵的压缩存储 175
4.2.1 对称矩阵的压缩存储 176
4.2.2 三角矩阵的压缩存储 177
4.2.3 对角矩阵的压缩存储 178
4.2.4 稀疏矩阵的压缩存储 179
4.3 字符串 183
4.3.1 字符串的概念 184
4.3.2 字符串的存储结构 185
4.3.3 字符串的查找―模式匹配 189
4.3.4 BF算法 190
4.3.5 KMP算法 196
4.4 本章小结 204
习题 205
第5章 结点逻辑关系分层次的非线性结构―树 208
5.1 实际问题中的树形结构 208
5.1.1 日常生活中的树形结构 208
5.1.2 计算机中的目录结构 209
5.1.3 网站的树形结构 209
5.1.4 表达式树 210
5.2 树的逻辑结构 210
5.2.1 树的定义和基本术语 210
5.2.2 树的操作定义 213
5.3 树的存储结构 213
5.3.1 树的连续存储方式 214
5.3.2 树的链式存储方式 215
5.4 二叉树的逻辑结构 218
5.4.1 二叉树与普通树的转换 218
5.4.2 二叉树的概念 220
5.4.3 二叉树的基本性质 222
5.4.4 二叉树的操作定义 222
5.5 二叉树的存储结构及实现 223
5.5.1 二叉树的顺序结构 223
5.5.2 二叉树的链式存储结构 224
5.5.3 建立动态二叉链表 226
5.6 二叉树结点的查找问题―树的遍历 230
5.6.1 问题引例 230
5.6.2 树的广度优先遍历 233
5.6.3 树的深度优先遍历 235
5.6.4 树的遍历的应用 243
5.7 树的应用 248
5.7.1 表达式树 248
5.7.2 线索二叉树 249
5.7.3 哈夫曼树及哈夫曼编码 254
5.8 线性与非线性结构的集合―广义表 268
5.8.1 广义表的定义 269
5.8.2 广义表的存储 271
5.8.3 广义表的基本运算 277
5.9 本章小结 280
习题 281
第6章 结点逻辑关系任意的非线性结构―图 285
6.1 实际问题中的图及抽象 285
6.2 图的逻辑结构 289
6.2.1 图的定义和基本术语 289
6.2.2 图的基本术语 290
6.2.3 图的操作定义 292
6.3 图的存储结构及实现 292
6.3.1 图的数组表示法1―邻接矩阵 293
6.3.2 图的数组表示法2―边集数组 295
6.3.3 图的链表表示法1―邻接表 296
6.3.4 图的链表表示法2―十字链表 301
6.3.5 图的链表表示法3―邻接多重表 302
6.3.6 图各种存储结构的归结比较 304
6.4 图的基本操作 305
6.4.1 邻接矩阵的操作 305
6.4.2 邻接表的操作 307
6.4.3 图的运算实例 309
6.5 图的顶点查找问题―图的遍历 313
6.5.1 问题的引入 313
6.5.2 图的广度优先遍历―BFS 314
6.5.3 图的深度优先遍历―DFS 318
6.6 图的经典应用―图中的树问题 324
6.6.1 引例 324
6.6.2 生成树 326
6.6.3 最小生成树 327
6.6.4 求最小生成树算法1―Prim算法 328
6.6.5 求最小生成树算法2―Kruskal算法 334
6.6.6 生成树算法小结 341
6.7 图的经典应用―最短路径问题 341
6.7.1 最短路径问题的引入 341
6.7.2 单源最短路径算法―Dijkstra算法 343
6.7.3 各顶点对间最短路径算法―Floyd算法 348
6.7.4 最短路径问题小结 353
6.8 图的经典应用―活动顶点与活动边的问题 354
6.8.1 图的活动顶点排序问题的引入 354
6.8.2 AOV网与拓扑排序―活动顶点排序问题 356
6.8.3 AOE网与关键路径―活动边最长问题 362
6.8.4 活动顶点与活动边问题小结 373
6.9 本章小结 373
习题 374
第7章 数据的处理方法―排序技术 380
7.1 概述 380
7.1.1 排序的基本概念 380
7.1.2 排序算法的分类 382
7.2 插入排序 382
7.2.1 直接插入排序 382
7.2.2 希尔排序 385
7.3 交换排序 387
7.3.1 冒泡排序 387
7.3.2 快速排序 389
7.4 选择排序 393
7.4.1 简单选择排序 393
7.4.2 堆排序 394
7.5 归并排序 398
7.6 分配排序 402
7.6.1 桶排序 402
7.6.2 基数排序 405
7.7 各种排序算法的比较 408
7.8 本章小结 411
习题 411
第8章 数据的处理方法―索引与查找技术 414
8.1 索引的基本概念 415
8.1.1 索引的定义 416
8.1.2 表示索引的逻辑结构 416
8.1.3 索引的主要操作 417
8.2 线性索引技术 417
8.2.1 稠密索引 417
8.2.2 分块索引 418
8.2.3 分级索引 419
8.2.4 多重表 420
8.2.5 倒排表 422
8.3 树形索引 424
8.3.1 二叉排序树 424
8.3.2 B树 428
8.4 查找概述 430
8.4.1 查找的基本概念 431
8.4.2 查找算法的性能 431
8.5 线性表的查找技术 432
8.5.1 顺序查找 432
8.5.2 有序表查找 433
8.5.3 索引查找 437
8.6 树表的查找技术 439
8.6.1 二叉排序树的查找 439
8.6.2 B树的查找 439
8.6.3 在非数值有序表上的查找―字典树 440
8.7 散列表存储及其查找技术 442
8.7.1 问题引入 442
8.7.2 散列概述 443
8.7.3 散列函数的设计 446
8.7.4 处理冲突的方法 447
8.7.5 散列查找的性能分析 452
8.8 本章小结 454
习题 455
第9章 经典算法 457
9.1 递归―有去有回的过程 457
9.1.1 “优选后出”的递归 457
9.1.2 递归的计算机实现 458
9.1.3 递归方法特点分析 460
9.1.4 递归算法实例 462
9.1.5 递归小结 464
9.2 分治法―分而治之策略 464
9.2.1 分治法 464
9.2.2 分治法的适用条件 465
9.2.3 分治问题的类型 465
9.2.4 分治法小结 468
9.3 动态规划―多段决策法 468
9.3.1 动态规划 468
9.3.2 动态规划的解题方法 470
9.3.3 动态规划解题实例 473
9.3.4 动态规划小结 478
9.4 贪心算法―局部很优解法 478
9.4.1 贪心算法 478
9.4.2 贪心算法经典问题 480
9.4.3 贪心算法小结 482
9.5 回溯法―深度优先搜索解空间 483
9.5.1 回溯法 483
9.5.2 回溯法实例 484
9.5.3 回溯法小结 488
9.6 分支限界法―广度优先搜索解空间 488
9.6.1 分支限界法简介 488
9.6.2 分支限界法的求解思想 490
9.6.3 分支限界法经典问题 491
9.6.4 分支限界法小结 493
9.7 本章小结 494
习题 494
附录A 数据的联系 496