数据结构与算法分析新视角

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

　　周幸妮，西安电子科技大学副教授，长期从事“数据结构”、“C程序设计语言”等课程的教学工作，著有《C程序设计》等教材。

第1章 绪论 1
1．1 从编程说起 1
1．2 程序要处理的数据 5
1．3 数据结构的引入 11
1．4 数据结构的基本概念 13
1．4．1 数据结构基本术语 13
1．4．2 数据结构的三个要素 13
1．5 如何设计算法 16
1．5．1 算法的定义及表示方法 16
1．5．2 算法设计与函数设计的关系 17
1．5．3 软件设计描述方法 18
1．5．4 算法设计的一般步骤 19
1．6 如何评价算法的优劣 21
1．6．1 算法的设计要求 21
1．6．2 算法效率的度量方法 22
1．7 算法性能的事前分析方法 23
1．7．1 问题的规模与算法的策略 23
1．7．2 算法效率的上限与下限 25
1．7．3 渐进的上限――算法的时间
复杂度 28
1．7．4 算法时间复杂度的综合讨论 29
1．7．5 算法的空间效率分析方法 33
1．8 算法性能综合考量 37
1．9 本章小结 38
习题 38
第2章 结点逻辑关系为线性的结构――线性表 41
2．1 从逻辑结构角度看线性表 41
2．1．1 实际问题中的线性关系 41
2．1．2 线性表的逻辑结构 42
2．2 线性表的存储结构方法之一――顺序表 43
2．2．1 顺序表的存储结构设计 43
2．2．2 顺序表的运算 46
2．2．3 顺序存储结构的讨论 53
2．3 线性表的存储结构方法之二――链表 53
2．3．1 单链表的存储 56
2．3．2 单链表的运算 60
2．3．3 单链表的讨论 78
2．3．4 循环链表 78
2．3．5 双向链表 81
2．3．6 链表小结 86
2．4 线性表的应用举例 87
2．4．1 逆序输出单链表结点值 87
2．4．2 一元多项式的相加 88
2．5 顺序表和链表的比较 95
2．6 本章小结 96
习题 97
第3章 运算受限的线性表――栈和队列 100
3．1 栈――按照先入后出的方式管理的线性表 100
3．1．1 栈处理模式的引入 100
3．1．2 栈的逻辑结构 104
3．1．3 栈的存储结构设计 106
3．1．4 栈的操作 107
3．1．5 各种栈结构的比较 123
3．1．6 栈的应用举例 123
3．2 队列――按照先入先出方式管理的线性表 132
3．2．1 队列处理模式的引入 133
3．2．2 队列的逻辑结构 136
3．2．3 队列的顺序存储结构 137
3．2．4 顺序队列的基本操作 148
3．2．5 队列的链式存储结构 152
3．2．6 链队列的基本操作 153
3．2．7 各种队列结构的比较 160
3．2．8 队列的应用举例 161
3．3 本章小结 171
习题 172
第4章 内容特殊的线性表――多维数组与字符串 175
4．1 多维数组 175
4．1．1 数组的概念 175
4．1．2 数组的存储结构 177
4．2 矩阵的压缩存储 181
4．2．1 对称矩阵的压缩存储 182
4．2．2 三角矩阵的压缩存储 183
4．2．3 对角矩阵的压缩存储 183
4．2．4 稀疏矩阵的压缩存储 185
4．3 字符串 189
4．3．1 字符串的定义 189
4．3．2 字符串的存储结构 190
4．3．3 字符串的查找――模式匹配 195
4．4 本章小结 211
习题 213
第5章 结点逻辑关系分层次的非线性结构――树 216
5．1 实际问题中的树 216
5．2 树的逻辑结构 219
5．2．1 树的定义和基本术语 219
5．2．2 树的操作定义 222
5．3 树的存储结构 222
5．3．1 树的连续存储方式 223
5．3．2 树的链式存储方式 224
5．4 二叉树的逻辑结构 226
5．4．1 二叉树的概念 229
5．4．2 二叉树的基本性质 230
5．4．3 二叉树的操作定义 231
5．5 二叉树的存储结构及实现 231
5．5．1 二叉树的顺序结构 232
5．5．2 二叉树的链式存储
结构――二叉链表 235
5．5．3 建立动态二叉链表 236
5．6 二叉树结点的查找 问题――树的遍历 240
5．6．1 树的广度优先遍历 242
5．6．2 树的深度优先遍历 244
5．6．3 树的遍历的应用 255
5．7 树的应用 259
5．7．1 表达式树 259
5．7．2 线索二叉树 260
5．7．3 哈夫曼树及哈夫曼编码 265
5．8 广义表 278
5．8．1 广义表的定义 279
5．8．2 广义表的存储 281
5．8．3 广义表的基本运算 287
5．9 本章小结 293
习题 295
第6章 结点逻辑关系任意的非线性结构――图 299
6．1 实际问题中的图及抽象 299
6．2 图的逻辑结构 304
6．2．1 图的定义和基本术语 304
6．2．2 图的操作定义 307
6．3 图的存储结构及实现 308
6．3．1 图的数组表示法1―― 邻接矩阵 308
6．3．2 图的数组表示法2―― 边集数组 310
6．3．3 图的链表表示法1――邻接表 311
6．3．4 图的链表表示法2―― 十字链表 316
6．3．5 图的链表表示法3――邻接多重表 317
6．3．6 图各种存储结构的归结比较 319
6．4 图的基本操作 320
6．4．1 邻接矩阵的操作 320
6．4．2 邻接表的操作 322
6．5 图的顶点查找问题――图的遍历 328
6．5．1 图的广度优先遍历BFS 329
6．5．2 图的深度优先遍历DFS 334
6．5．3 图的遍历小结 340
6．6 图的经典应用――图中的树问题 340
6．6．1 生成树 342
6．6．2 最小生成树MST 343
6．6．3 求最小生成树算法1――Prim 算法 344
6．6．4 求最小生成树算法2――Kruskal算法 349
6．6．5 生成树算法小结 356
6．7 图的经典应用――最短路径问题 357
6．7．1 最短路径问题的引入 357
6．7．2 单源最短路径算法――Dijkstra算法 359
6．7．3 各顶点对间最短路径算法――Floyd算法 364
6．7．4 最短路径问题小结 369
6．8 图的经典应用――活动顶点与活动边的问题 370
6．8．1 图的活动顶点排序问题的引入 370
6．8．2 AOV网与拓扑排序――活动顶点排序问题 373
6．8．3 AOE网与关键路径――活动边最长问题 378
6．8．4 活动顶点与活动边问题小结 390
6．9 本章小结 390
习题 391
第7章 数据的处理方法――排序技术 397
7．1 概述 397
7．1．1 排序的基本概念 397
7．1．2 排序算法的分类 399
7．2 插入排序 399
7．2．1 直接插入排序 399
7．2．2 希尔排序 402
7．3 交换排序 404
7．3．1 冒泡排序 404
7．3．2 快速排序 406
7．4 选择排序 409
7．4．1 简单选择排序 410
7．4．2 堆排序 411
7．5 归并排序 415
7．6 分配排序 418
7．6．1 桶排序 418
7．6．2 基数排序 421
7．7 各种排序算法的比较 424
7．8 本章小结 427
习题 428
第8章 数据的处理――索引与查找技术 431
8．1 索引的基本概念 433
8．1．1 索引的定义 433
8．1．2 索引的逻辑特征 434
8．1．3 索引的主要操作 435
8．2 线性索引技术 435
8．2．1 稠密索引 435
8．2．2 分块索引 436
8．2．3 多重表 437
8．2．4 倒排表 439
8．3 树形索引 441
8．3．1 二叉排序树 441
8．3．2 B树 448
8．4 查找概述 452
8．4．1 查找的基本概念 452
8．4．2 查找算法的性能 453
8．5 线性表的查找技术 453
8．5．1 顺序查找 453
8．5．2 有序表查找 454
8．5．3 索引查找 459
8．6 树表的查找技术 461
8．6．1 二叉排序树 461
8．6．2 B树 462
8．6．3 在非数值有序表上的查找――字典树 462
8．7 散列表的查找技术 464
8．7．1 散列概述 465
8．7．2 散列函数的设计 467
8．7．3 处理冲突的方法 469
8．7．4 散列查找的性能分析 473
8．8 本章小结 474
习题 476
第9章 经典算法 479
9．1 递归算法 479
9．1．1 递归的概念及要素 479
9．1．2 递归的应用场景 481
9．1．3 递归的计算机实现 482
9．1．4 递归方法特点分析 483
9．1．5 递归算法实例 485
9．1．6 递归小结 487
9．2 分治算法 487
9．2．1 分治是什么 487
9．2．2 分治法的适用条件 488
9．2．3 分治问题的类型 488
9．2．4 分治法小结 490
9．3 动态规划 491
9．3．1 什么是动态规划 491
9．3．2 动态规划的解题方法 493
9．3．3 动态规划解题实例 495
9．3．4 动态规划小结 500
9．4 贪心算法 501
9．4．1 贪心算法是什么 501
9．4．2 贪心算法经典问题 502
9．4．3 贪心算法小结 504
9．5 回溯法 504
9．5．1 回溯法是什么 504
9．5．2 回溯法经典问题 507
9．5．3 回溯法小结 509
9．6 分支限界法 509
9．6．1 什么是分支限界法 509
9．6．2 分支限界法的求解思想 511
9．6．3 分支限界法经典问题 512
9．6．4 分支限界法小结 514
9．7 本章小结 514
习题 516
附录A 数据的联系图 517
附录B 自定义头文件的加入方法 518
附录C 软件设计说明书格式 519
参考文献 521

　　从新视角来看待旧问题，则需要创造性的思维——爱因斯坦

　　数据结构的教与学经历

　　六七年前上数据结构课时，驾轻就熟地依然按照一贯的讲法上课。上了几次课后，收到班上一位同学的E-mail，信中说：“我自己是特别热爱写程序的。一方面我很熟悉电脑，软硬件都有涉猎，所以学起来就不缺基础的相关知识（像内存、寄存器、电子电路等等这些都很熟悉）；另一方面我好像很能适应，也很喜欢这种思维方式……但好像班上不少的同学对数据结构的学习理解和接受起来还是比较困难的……”

　　教授数据结构的课程也有十余年了，一直以来，学生们总是认为数据结构不是一门容易学的课程，“在众多的专业课中，数据结构被很多学生认为是一门很难学习的课程。”[1]虽然我在学校读书时没有学过数据结构的课程，只是因为后来要教书，才自学的数据结构。在自学的过程中，也并没有觉着内容怎么难啊，这是怎么回事呢？

　　仔细回想一下自己学习与工作的经历过程，或许就是来信的这位同学说的，是因为在学习数据结构书本知识之前，已经有了较强的编程的技能、一些数据结构实际应用的先验知识吧。比如，在研究所工作时首次参加的软件开发项目中，就有多进程、链表、队列、散列等的实际应用，虽然在学校并没有学过这些概念，而是先接触到实际项目中要处理的问题，再看到其他程序员的具体算法处理和程序实现方法，从实际的问题切入，就比较容易理解相应的数据组织形式和对应的算法，等到后来再接触到书本的理论知识，就有一种一通百通，豁然开朗的感觉。还有一个原因是在软件开发过程中逐渐熟悉并掌握了程序调试方法，对例程通过跟踪的方法，很容易弄清执行的路径和结果，对算法的设计和实现的理解也起到了事半功倍的效果。

　　回头来看学生们学习的教科书，概念的介绍是传统意义上的叙述方式，抽象度很高，但从实际到抽象、从抽象到实际的过程介绍不足，即感性认识不足，抽象就难以理解接受。“现在有一个不好的倾向，就是教材或课堂过于重视抽象化的知识，忽视应用背景。数据结构的教材是这一倾向的代表。这对入门阶段的学生来讲是不适宜的，因为学生难以走进所涉及的抽象世界，最终表现为不知道在讲什么。”[2]

　　再看我的学生，既没有实际软件开发的经验也没有熟练的编程调试基础，对数据结构结构没有感性认识，先接触的是那些抽象的概念，感到理解和接受困难也就可以理解了。邹恒明在《数据结构：炫动的0、1之弦》一书中指出，对于很多人来说，数据结构的概念并不难，真正的难点是：

　　（1）如何实现从数据结构概念到程序实现的跨越（即如何实现一个数据结构）；

　　（2）如何实现从实际应用到数据结构抽象的跨越（即如何利用数据结构解决实际问题）。

　　对于我来说，仅仅在学校学了一点点程序设计语言（记得所有上机时间加起来不超过20小时），没有任何数据结构的知识，刚出校门就参与了历时三年多后来获得国家科技进步三等奖的大型软件开发工作，以及后续多个电信用户单位的实际软件安装、应用调试和维护工作，亲历了实现了上述两个“跨越”的最实际生动的案例。虽然项目的开发过程非常艰苦，有在用户单位调试现场连续大半年的天天加班到深夜、第二天依然要正点到机房的超负荷工作，有通宵的跟踪调试，有24小时在线系统内存泄漏的巨大压力，有上线后双机备份系统同时崩溃争分夺秒找bug的惊心动魄，等等。应该说自己是很幸运的，虽然在学校仅仅学习了一点点编程的概念，但在工作中根据需要自学和向同事学习了很多新知识、经验和技巧，这样的实践磨练，对后来的程序设计类课程的理解和教授，是非常有益的。

　　学习数据结构困难的症结所在

　　回想与总结起来，之所以要有上述两个鸿沟要“跨越”，也是由于学校的传统教科书教法和实际的应用要求脱节造成的。

　　弗里德里希?威廉?尼采曾写道：“人们无法理解他没有经历过的事情。”[3]换句话来说，我们只接受与过去早已理解的事物相关的信息。这是一种比较学习的过程，在这个过程中，大脑要寻找每条信息之间的联系，借助以往经验来理解新事物[4]。

　　“欧拉认为，如果不能把解决数学问题背后的思维过程教给学生的话，数学教学就是没有意义的。现代计算机实质上的发明者莱布尼兹也说过：在我看来，没有什么能比探索发明的源头还要重要，它远比发明本身更重要。从小到大，我们看过的数学书几乎无一不是欧几里德式的：从定义到定理，再到推论。这样的书完全而彻底地扭曲了数学发现的真实过程。目前几乎所有的算法书的讲解方式也都是欧几里德式的，每一个推导步骤都是精准制导直接面向数据结构目标的，实际上，这完全把人类大脑创造发明的步骤给反过来了。对读者来说，这就等于直接告诉你答案和做法了，然后让你去验证这个答案和做法是可行或成立的，而关于答案和做法到底是怎么来的，从问题到答案之间经历了怎样的思维过程，却鲜有书能够很好地阐释。对于这类知识讲述（欧几里德方式）方式的批判，西方（尤其是在数学领域）早就有了。”[5]

　　传统数据结构教科书的一般模式都是给出问题，然后直接给出算法，而实际上要用计算机解决问题，必须要考虑的处理步骤有：如何分析问题中的已知信息，如何提炼数据及数据间的联系（数据的逻辑结构），如何选用合适的存储方式（数据的存储结构）将逻辑结构存到计算机中，然后在存储结构之上按照自顶向下逐步细化的方法给出算法，这才是真正解决实际问题的思维方法和步骤，也是软件开发中实际采用的方法。传统教科书的问题在于没有一个思维过程的引导与分析，致使概念论述、实现细节有余，设计实现过程描述不足，让学生看到的只是一个个问题具体的详解，而把握不住算法设计的总方法和原则。

　　本书尝试从学以致用的角度，注意给出问题或算法的知识背景或应用背景，增加一些在实际软件开发中的算法应用背景或实例；强调算法的分析方法、设计思路、给出重要算法的测试及调试分析，弥补上述传统教科书中的不足。教学生以“软件开发的方法”处理问题，使学生容易理解并掌握它，在实际的软件开发过程中能灵活地选择适当的逻辑结构、存储结构及相应的算法，设计性能优、效率高、可读性强、易维护的程序，达到数据结构课程最终的目的。

　　程序设计与数据结构的关系

　　我们在学习数据结构知识之前要有程序设计的基础，那么我们先来看看与编程相关的问题。

　　什么是编程？编程不仅仅是对语法的掌握，还涉及下面的诸多方面：

　　（1）程序的解题思路——算法是基本运算及规定的运算顺序所构成的完整的解题步骤，是程序的灵魂，算法的优劣直接影响程序的效率。本书的算法描述方法见稍后的说明。

　　（2）程序的运行速度——程序运行的速度受很多因素的影响。用户对程序的运行速度往往是有要求的，如实时响应系统。

　　（3）程序的运行空间——代码运行需要相应的内存空间及相关运行环境。在有些应用场合，对程序占用空间是有限制的，如嵌入式系统。

　　（4）代码规范——代码要按照一定的规范格式书写，以保证代码的一致性，便于交流和维护。

　　（5）程序的结构—— 一个功能复杂的程序由多个功能相对独立的模块组成。模块内高内聚，模块间低耦合，是判断程序结构是否合理的标准。

　　（6）模块接口——模块间的信息交流通过接口完成，模块间信息传递参数的设置应该合理有效。

　　（7）程序的测试与调试——要有精心设计的测试样例来测试程序是否正确。调试是高效率完成软件产品的有效方法。一个程序高手，也是调试专家，调试的经验方法多数都是实践中得到的。

　　我们在学习数据结构知识之前要有程序设计的基础，那么数据结构与程序设计间的关系是怎样的呢？应该说数据结构是编写规模庞大、逻辑复杂的更高级程序所需的基础。表0.1给出了程序设计与高级编程的特点。

　　表0.1 程序设计与高级编程

　　涉及课程 主要内容 课程目标

　　结构化程序

　　设计 程序设计基础类课程 语言语法形式、语句使用规则

　　模块设计思想 编写简单程序

　　解决简单问题

　　高级编程技术 数据结构 数据的抽象思维方法 编写规模庞大、

　　逻辑复杂的程序

　　算法的规范声明、算法的性能分析、算法的性能评价

　　软件工程 部件（模块）设计思想、软件工程思想

　　……

　　程序设计的首要问题是模块划分及相关问题，另一个重要方面，是把要解决问题的信息转换成计算机能认识并接收的数据，这一转换过程就是数据的抽象过程。要处理规模庞大的复杂问题，必须掌握数据的抽象思维方法，同时还要熟练掌握算法的规范声明、算法的性能分析、算法的性能评价等诸多技能。

　　数据结构与其他课程的关系

　　作为一门重要的专业核心必修课程，“数据结构与算法”课程既是对以往课程的深入和扩展，也为深入学习其他专业课程打下基础。课程中排序问题算法以及基本的树、图等数据结构，是计算机科学的基本功。B+树、散列（Hash）等高级数据结构，也是数据库、操作系统、编译原理、计算机网络等重要专业课程的基础。本课程在计算机学科中与其他课程的关系如图0.1所示。

　　图0.1 “数据结构与算法”课程在计算机学科中的重要地位

　　数据结构的重要性

　　商用程序员肖舸在他的博客中写道：“这么多年，我做过游戏、通信、工业控制、教育、VoIP、服务器集群等各个方向的项目，不可谓不宽。

　　但是我知道的是，其实我都是在用一种方法写程序。那就是从最底层的数据结构和算法开始做起，用最基本的C、C++语言开发。用来用去，还是那么几个数据结构，队列、堆栈，等等。

　　这好比武侠小说里面的内功，内力修好了，学招式，非常容易。但如果没有内力，练再好的招式，见到高手就软了。一力破十慧，就是这个道理。在绝对的实力面前，任何花招都是没有用的。”[6]

　　对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的学生都认为“数据结构”是他们在学校里学过的最有用的课程之一；数据结构是国内外许多软件开发机构要求考核的基本课程之一；IT业公司面试或笔试考核的绝大部分内容是数据结构或算法；数据结构也是计算机科学与技术、软件工程等专业研究生考试必考科目。