内容介绍

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

目   录

第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.

作者介绍

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

前    言

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

数据结构的教与学经历

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

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

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

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

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

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

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

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

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

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

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

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

传统数据结构教科 数据结构与算法分析新视角 电子书 下载 mobi epub pdf txt