全书共分三个部分。第一部分从第1章到第4章，旨在复习C++程序设计的概念以及程序性能的分析和测量方法。第二部分从第5章到第16章，研究数据结构，包括线性表、数组和矩阵、栈、队列、字典、二叉树、优先级队列、竞赛树、搜索树和图等。第三部分从第17章到第21章，研究常用算法，包括贪婪算法、分而治之算法、动态规划、回溯算法和分枝定界算法。
本书有800多道练习题和50多个应用实例。内容广博，组织合理，论述清晰，循序渐进，而且对程序性能的分析和测量系统入微。本书不仅是数据结构和算法的经典教材，而且是计算机科学与工程领域的理想参考书。
《数据结构、算法与应用——C++语言描述》是享有盛誉的数据结构教科书的第2版。它完整地包含了基本数据结构的内容，是CS2课程的理想用书。作者Sartaj Sahni通过循循善诱的讲解、直观具体的讨论和基于现实的应用，让读者轻松、愉快地学习。新版书着重利用标准模板库(STL)，把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。
书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例，涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起，使理论与实践统一，从而让概念容易理解，使学生增加学习动力和兴趣。
本书采用的实用教学方法，不仅充实了理论概念，而且大量的习题让学生有了实践机会（书中有800多道练习题，包括理解题和简单的编程题和工程设计题）。除此之外，本书的配套网站上包含书中的所有程序、示例数据、运行结果、部分练习的解答和带有结果的示例测试。
作者简介
Sartaj Sahni 佛罗里达大学计算机与信息科学工程系杰出教授，欧洲科学院院士, 美国电气和电子工程师协会(IEEE)、 美国计算机协会(ACM)、美国科学促进会(AAAS)和明尼苏达超级计算机研究所的成员，坎普尔印度理工学院（IIT）的杰出校友。Sahni博士获得1997年IEEE计算机分会的Taylor L. Booth教育奖，2003年IEEE计算机分会的W. Wallace McDowell奖和2003年ACM的Karl Karlstrom杰出教育家奖。他目前还担任ACM《Computing Surveys》期刊的总编辑，还是17个期刊编委会成员。他在坎普尔印度理工学院获得电子工程学士学位，在康奈尔大学获得计算机科学硕士和博士学位，发表过250多篇论文，编写了15本教科书，研究成果所涉及的领域包括有效算法的设计与分析、并行计算、互联网、自动化设计和医用算法。
对数据结构和算法的研究是计算机科学和工程的基础。精通这方面的知识，对开发能够有效利用计算机资源的程序是必不可少的。因此，所有计算机科学和工程专业都有一门或几门课程专门用来讲授这方面的内容。一般来说，第一门程序设计课程介绍数据结构和算法的基础知识（数据结构的栈和队列，算法的排序和矩阵运算）。第二门程序设计课程介绍数据结构和算法的系统知识。随后，可以对数据结构和算法进行深入的研究，这通常需要一门或两门课程。
计算机科学和工程的本科专业课程过多，已经迫使很多高等院校进行课程整合。例如，在佛罗里达大学，给本科生只开设一学期的数据结构和算法的课程。在学习本课程之前，要求学生已经学过一学期的Java程序设计和离散数学。
本书既可以用于两门或更多的专门研究数据结构和算法的课程，也可以用于相关的一门综合课程。全书共分三个部分。第一部分从第1章到第4章，旨在复习C++程序设计的概念以及程序性能的分析和测量方法。对于熟悉C语言程序设计的学生，通过学习第1章应该能够过渡到C++。第1章虽然不是C++的入门知识，但是依然包含了C++的一些基本概念，这些概念常令学生感到困惑，如参数传递、模板函数、动态存储分配、递归、类、继承、异常的抛出和捕捉。第2章和第3章复习了程序性能的分析和测量方法——操作计数、执行步数和渐近符号（大O、Ω、Θ，小o）。第4章复习了程序性能的实验测量方法，还简要地讨论了高速缓冲存储器对运行时间测量的影响问题。第2章通过程序性能分析方法的应用，深入研究了在程序设计入门课程中遇到的典型的基础性算法：简单的排序算法（冒泡排序、选择排序、插入排序和计数排序），顺序搜索，利用Horner法则进行多项式求值，矩阵运算（矩阵相加、矩阵转置、矩阵相乘）。第3章研究了二分搜索算法。尽管第2章到第4章的主要目的是学习程序性能的分析和测量方法，但是也让学生精通了一组基本算法。
本书第二部分从第5章到第16章，深入研究了数据结构。第5章和第6章分别研究了数据的数组描述方法和指针（或链式）描述方法，构建起数据结构研究的框架。这两章用这两种数据描述方法来创建C++类，以描述线性表数据结构。我们通过实验数据对不同的数据描述方法在描述线性表时的性能进行了比较。第二部分从第7章以后都是应用第5章和第6章的描述方法来描述其他的数据结构，如数组和矩阵（第7章）、栈（第8章）、队列（第9章）、字典（第10、14和15章）、二叉树（第11章）、优先级队列（第12章）、竞赛树（第15章）和图（第16章）。
本书在处理数据结构时，试图做到与C++标准模板库（STL）所使用的结构在相似性或同一性上保持兼容。例如，第5章的线性表数据结构便是按照STL的类vector的模式而建立的。本书通篇都利用了STL的函数，诸如copy、min和max，学生由此会熟悉这些函数。
本书第三部分从第17章到第21章，研究常用的算法设计方法。这些方法有贪婪算法（第17章）、分而治之算法（第18章）、动态规划（第19章）、回溯算法（第20章）和分支定界算法（第21章）。另外还包括两种下限的证明（最小最大问题和排序问题）（18.4节）、机器调度的近似算法（12.6.2节）、箱子装载算法（13.5节）和0/1背包问题（17.3.2节）。12.6.2节还简略地介绍了NP-复杂问题。
本书的一个特色是强调应用。书中的每一种数据结构和算法设计都通过多个应用实例来演示。通常每一章的最后一节都针对本章介绍的数据结构或设计方法给出具体的应用。很多时候，在一章的前面几节也包含一些应用实例。这些应用实例涉及多个方面——排序（冒泡排序、选择排序、插入排序、计数排序、堆排序、归并排序、快速排序、箱子排序、基数排序和拓扑排序）；矩阵运算（矩阵加法、矩阵转置、矩阵乘法）；电路设计自动化（搜索电路网组、电路布线、元件折叠、开关盒布线、设置信号放大器、交叉分布、电路板排列）；压缩编码（LZW压缩、霍夫曼编码）；计算几何（凸包和最近点对）；仿真（工厂仿真）；图像处理（图元标注）；趣味数学（汉诺塔、残缺棋盘、迷宫老鼠）；调度（LPT调度）；优化（装箱问题、货箱装载、0/1背包、矩阵乘法链）；统计（直方图、寻找最大值和最小值、寻找第k个最小值）；图论（生成树、图元、最短路径、最大完备子图、二分覆盖和旅行商）。研究这些应用实例不需要学生具有相关领域的预备知识，因为本书包含了这些知识，而且这些知识会提高学生的学习兴趣。
我们希望通过把实际应用与数据结构和算法设计方法的基础研究紧密结合，能够激发学生更大的专业兴趣。学生通过完成本书和本书网站的800多道练习题，知识将会更加丰富和牢固。
网站
本书网站的URL为http://www.cise.ufl.edu/~sahni/dsaac。
访问该网站可以得到本书的所有程序以及示例数据和输出结果。示例数据并不是特意设计的测试数据，而是用来运行程序以便将输出结果与给定的输出结果进行比较的数据。网站还有每一章的练习答案、一些测试样本以及相应的测试结果、补充的应用实例和对书中一部分内容的进一步讨论。
如何使用本书
使用本书讲授数据结构和算法可以采用多种课程安排，这需要教师根据学生的知识背景、对应用的侧重程度和课时的多少来决定。下面是几种可能的课程安排方案。我们建议学生的作业是编写和调试一些程序，开始是一些小程序，随着课程的深入，程序逐渐复杂。学生应该根据课堂讲授的内容，同步阅读本书的相关内容。
两季度课程安排——第一季度
（一周回顾，数据结构和算法内容系列）
周 主题 阅读
1 回顾C++和程序性能 第1～4章，布置作业1
2 基于数组的描述 第5章，完成作业1
3 链表描述 6.1～6.4节，布置作业2
4 箱子排序和等价类 6.5.1～6.5.4节，完成作业2
5 数组和矩阵 第7章，测试
6 栈和队列 第8章和第9章，布置作业3
7 跳表和散列 第10章，完成作业3
8 二叉树和其他树 11.1～11.8节，布置作业4
9 并查集应用，堆和堆排序 11.9. 2节、12.1～12.4节和12.6.1节，完成作业4
10 左高树，霍夫曼编码和竞赛树 12.5节和12.6.3节，第13章
两季度课程安排——第二季度
（数据结构和算法内容系列）
周 主题 阅读
1 二叉搜索树，AVL或红黑树，直方图 第14章和第15章，布置作业1
2 图 16.1～16.7节，完成作业1
3 图 16.8节和16.9节，布置作业2
4 贪婪算法 17.1～17.3.5节，完成作业2
5 贪婪算法和分而治之算法 17.3.6节和18.1节，布置作业3
6 分而治之算法应用 18.2节，测试
7 求解递归式，下限和动态编程 18.3节、18.4节和19.1节，完成作业3
8 动态编程应用 19.2.1节和19.2.2节，布置作业4
9 动态编程应用 19.2.3～19.2.5节，完成作业4
10 回溯和分支定界算法 第20章和第21章
一学期课程安排
（两周回顾，数据结构内容系列）
周 主题 阅读
1 回顾C++ 第1章，布置作业1
2 回顾程序性能 第2～4章
3 基于数组的描述 第5章，完成作业1
4 链表描述 6.1～6.4节，布置作业2
5 箱子排序和等价类 6.5.1节和6.5.4节
6 数组和矩阵 第7章，完成作业2，第1次测试
7 栈和队列，一或两个应用 第8章和第9章，布置作业3
8 跳表和散列 第10章
9 二叉树和其他树 11.1～11.8节， 完成作业3
10 并查集应用 11.9.2节， 布置作业4，第2次测试
11 优先级队列、堆排序和霍夫曼编码 第12章
12 竞赛树和装箱问题 第13章，完成作业4
13 二叉搜索树，AVL树或红黑树，直方图 第14章和第15章，布置作业5
14 图 16.1～16.7
15 图，最短路径 16.8节、16.9节、17.3.5节和19.2.3节，完成作业5
16 最小生成树，合并排序和快速排序 17.3.6节、18.2.2节和18.2.3节
一学期课程安排
（一周回顾，数据结构和算法内容系列）
周 主题 阅读
1 回顾程序性能 第1～4章
2 基于数组的描述 第5章，布置作业1
3 链表描述 第6章
4 数组和矩阵 第7章，完成作业1
5 栈和队列，一或两个应用 第8章和第9章，布置作业2
6 跳表和散列 第10章，完成作业2，第1次测试
7 二叉树和其他树 11.1～11.8节，布置作业3
8 并查集应用，堆和堆排序 11.9.2节、12.1～12.4节和12.6.1节
9 左高树，霍夫曼编码和竞赛树 12.5节和12.6.3节，第13章，完成作业3
10 二叉搜索树，AVL树或红黑树，直方图 第14章和第15章，布置作4，第2次测试
11 图 16.1～16.7节
12 图和贪婪算法 16.8节、16.9节、17.1节和17.2节，完成作业4
13 货箱装载，0/1背包，最短路径和生成树 17.3节，布置作业5
14 分而治之算法 第18章
15 动态编程 第19章，完成作业5
16 回溯和分支定界算法 第20章和第21章
致谢
本书的出版有赖于很多人的帮助、意见和建议。我对审阅了本书第1版的人士深表感激，他们给予的宝贵意见使本书有了很大的改进。这些人士有：
Jacabo Carrasquel 卡内基梅隆大学
Yu Lo Cyrus Chang 新罕布什尔大学
Teofilo F. Gonzalez 加州大学圣塔芭芭拉分校
Laxmikant V. Kale 伊利诺伊大学
Donald H. Kraft 路易斯安那州立大学
Sang W. Lee 密歇根大学
Jorge Lobo 伊利诺伊大学芝加哥分校
Brian Malloy 克莱姆森大学
Thomas Miller 爱达荷大学
Richard Rasala 东北大学
Craig E. Wills 伍斯特理工学院
Neal E. Young 达特茅斯学院
特别感谢我的学生，他们不仅提出了有价值的反馈意见，而且帮助审查原稿。我还要感谢佛罗里达大学的一些同事所给予的帮助，他们是：Justin Bullart，Edward Y. C. Cheng， Rajesh Dasari， Thomas Davies， Pinkesh Desai， Vinayak Goel， Haejae Jung， Kun-Suk Kim， Haibin Lu， Jawalant Patel， Sanguthevar Rajasekeran， Gauri Sukhatankar， Gayatri Venkataraman和 Joe Wilson。
Sartaj Sahni
2004年6月于盖恩斯维尔
计算机\数据结构
《数据结构、算法与应用——C++语言描述》是享有盛誉的教科书，本书是其第2版。它完整地包含了基本数据结构的内容，是CS2课程的理想用书。作者Sartaj Sahni通过循循善诱的讲解、直观具体的讨论和基于现实的应用，让读者轻松、愉快地学习。新版书着重利用标准模板库(STL)，把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。
书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例，涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起，使理论与实践统一，从而让概念容易理解，使学生增加学习动力和兴趣。
本书采用的实用教学方法，不仅充实了理论概念，而且大量的习题让学生有了实践机会（书中有800多道练习题，包括理解题和简单的编程题和工程设计题）。除此之外，本书的配套网站上包含书中的所有程序、示例数据、运行结果、部分练习的解答和带有结果的示例测试。
作者简介
Sartaj Sahni 是一位杰出的教授，佛罗里达大学计算机与信息科学工程系主任，欧洲科学院院士, 美国电气和电子工程师协会(IEEE)、 美国计算机协会(ACM)、美国科学促进会(AAAS)和明尼苏达超级计算机研究所的成员，坎普尔印度理工学院（IIT）的杰出校友。Sahni博士获得1997年IEEE计算机分会的Taylor L.Booth教育奖，2003年IEEE计算机分会的W.Wallace McDowell奖和2003年ACM的Karl Karlstrom杰出教育家奖。他在坎普尔印度理工学院获得电子工程学士学位，在康奈尔大学获得计算机科学硕士和博士学位，发表过250多篇论文，编写了15本教科书，研究成果所涉及的领域包括有效算法的设计与分析、并行计算、互联网、自动化设计和医用算法。
王立柱 刘志红 译：暂无简介
数据结构和算法是计算机科学和工程的基础。它们的相互联系和作用是程序的本质，Nicklaus Wirth把它们表示为：算法+数据结构=程序。Sartaj Sahni博士的《数据结构、算法与应用——C++语言描述》一书是彰显这一本质的当代经典，这主要表现在五个方面：
1）每一种数据结构和算法设计不仅都用C++语言优美地实现了，而且与C++标准模板库所使用的结构在相似性或同一性上保持兼容，既纯粹又规范。
2）对程序性能的分析和测量系统而严谨，既有严格的数学分析，又有周密的实验测量。
3）几乎每一种数据结构和算法都是从多个应用实例中分析和抽象出来的，既可以拓宽应用领域知识，又可以提高学习兴趣。
4）一个典型的应用实例常常用多种数据结构和算法来实现，既丰富了程序设计经验，又在比较中提高了鉴别能力。
5）练习题丰富。本书及其网站共有800多道练习题，而且和教材正文中的示例代码相辅相成。这些练习题趣味多样且难易相济，可满足各层次读者的需求。
如果你是一名程序设计新手，本书是你拾级而上的阶梯；如果你是一名专业程序设计者，本书是你高屋建瓴的楼台；如果你是在校大学生，本书是你学习数据结构和算法的理想教材或参考书。
对中国学生来说，本书的意义还可以从更高的层次来认识。爱因斯坦认为，西方科学的发展是以两个伟大的成就为基础的：形式逻辑体系和实验体系。今天的计算机科学不仅是这两个成就的综合体现，而且深入社会的每个角落，时刻改变着我们的生活，使每一个人时刻感受到它的力量。数据结构和算法作为计算机科学和工程的核心，可以使更多的中国学子通过这门课程而更积极、更有效地掌握形式逻辑和实验方法。但是长期以来，我国的教材大都使用伪码来描述数据结构和算法，给教学和自学带来极大的困难。因为代码不落实，实验测量就无法进行；没有实验测量，单凭分析就没有可靠的结果（例如高速缓冲存储器对运行时间的影响是不能只靠分析得到的）；分析没有结果，就容易流于形式，以至于理论和实践脱节，成为概念的灌输。这正是Stroustrup在《C++程序设计原理与实践》一书的前言中所批评的学习模式：先学习一个月的理论知识，然后看看是否能使用这些理论。
Sartaj Sahni博士的力作如阳光和雨露照耀和滋养我们，它从五个方面引导我们走上精神探险的旅程，饱览西方科学成就中美丽璀璨的风景，尽情品尝科学智慧中一种鲜美甘甜的果实：数据结构与算法。
王立柱
2014年10月于天津
出版者的话
译者序
前言
第一部分 预备知识
第1章 C++回顾 2
1.1 引言 2
1.2 函数与参数 3
1.2.1 传值参数 3
1.2.2 模板函数 4
1.2.3 引用参数 4
1.2.4 常量引用参数 5
1.2.5 返回值 5
1.2.6 重载函数 6
1.3 异常 7
1.3.1 抛出异常 7
1.3.2 处理异常 7
1.4 动态存储空间分配 9
1.4.1 操作符new 9
1.4.2 一维数组 9
1.4.3 异常处理 9
1.4.4 操作符delete 10
1.4.5 二维数组 10
1.5 自有数据类型 12
1.5.1 类currency 12
1.5.2 一种不同的描述方法 18
1.5.3 操作符重载 20
1.5.4 友元和保护性类成员 22
1.5.5 增加#ifndef、#define和#endif语句 23
1.6 异常类illegalParameterValue 24
1.7 递归函数 25
1.7.1 递归的数学函数 25
1.7.2 归纳 25
1.7.3 C++递归函数 26
1.8 标准模板库 30
1.9 测试与调试 32
1.9.1 什么是测试 32
1.9.2 测试数据的设计 34
1.9.3 调试 36
1.10 参考及推荐读物 37
第2章 程序性能分析 38
2.1 什么是程序性能 38
2.2 空间复杂度 39
2.2.1 空间复杂度的组成 39
2.2.2 举例 42
2.3 时间复杂度 44
2.3.1 时间复杂度的组成 44
2.3.2 操作计数 45
2.3.3 最好、最坏和平均操作计数 48
2.3.4 步数 53
第3章 渐近记法 64
3.1 引言 64
3.2 渐近记法 65
3.2.1 大Ο记法 65
3.2.2 渐近记法Ω和Θ 67
3.3 渐近数学（可选） 69
3.3.1 大O记法 69
3.3.2 Ω记法 71
3.3.3 Θ记法 72
3.3.4 小ο记法 73
3.3.5 特性 73
3.4 复杂度分析举例 75
3.5 实际复杂度 78
3.6 参考及推荐读物 80
第4章 性能测量 81
4.1 引言 81
4.2 选择实例的大小 82
4.3 设计测试数据 82
4.4 实验设计 82
4.5 高速缓存 87
4.5.1 简单计算机模型 87
4.5.2 缓存未命中对运行时间的影响 87
4.5.3 矩阵乘法 88
4.6 参考及推荐读物 90
第二部分 数据结构
第5章 线性表——数组描述 92
5.1 数据对象和数据结构 92
5.2 线性表数据结构 93
5.2.1 抽象数据类型linearList 94
5.2.2 抽象类linearList 94
5.3 数组描述 95
5.3.1 描述 95
5.3.2 变长一维数组 96
5.3.3 类arrayList 97
5.3.4 C++迭代器 102
5.3.5 arrayList的一个迭代器 103
5.4 vector的描述 107
5.5 在一个数组中实现的多重表 109
5.6 性能测量 111
5.7 参考及推荐读物 112
第6章 线性表——链式描述 113
6.1 单向链表 113
6.1.1 描述 113
6.1.2 结构chainNode 114
6.1.3 类chain 115
6.1.4 抽象数据类型linearList的扩充 121
6.1.5 类extendedChain 121
6.1.6 性能测量 122
6.2 循环链表和头节点 126
6.3 双向链表 128
6.4 链表用到的词汇表 129
6.5 应用 130
6.5.1 箱子排序 130
6.5.2 基数排序 134
6.5.3 凸包 135
6.5.4 并查集 137
第7章 数组和矩阵 146
7.1 数组 146
7.1.1 抽象数据类型 146
7.1.2 C++数组的索引 147
7.1.3 行主映射和列主映射 147
7.1.4 用数组的数组来描述 148
7.1.5 行主描述和列主描述 149
7.1.6 不规则二维数组 149
7.2 矩阵 151
7.2.1 定义和操作 151
7.2.2 类matrix 152
7.3 特殊矩阵 157
7.3.1 定义和应用 157
7.3.2 对角矩阵 158
7.3.3 三对角矩阵 159
7.3.4 三角矩阵 160
7.3.5 对称矩阵 161
7.4 稀疏矩阵 164
7.4.1 基本概念 164
7.4.2 用单个线性表描述 165
7.4.3 用多个线性表描述 170
7.4.4 性能测量 172
第8章 栈 175
8.1 定义和应用 175
8.2 抽象数据类型 177
8.3 数组描述 178
8.3.1 作为一个派生类实现 178
8.3.2 类arrayStack 179
8.3.3 性能测量 181
8.4 链表描述 182
8.4.1 类derivedLinkedStack 182
8.4.2 类linkedStack 183
8.4.3 性能测量 184
8.5 应用 184
8.5.1 括号匹配 184
8.5.2 汉诺塔 185
8.5.3 列车车厢重排 187
8.5.4 开关盒布线 191
8.5.5 离线等价类问题 193
8.5.6 迷宫老鼠 196
8.6 参考及推荐读物 204
第9章 队列 205
9.1 定义和应用 205
9.2 抽象数据类型 206
9.3 数组描述 207
9.3.1 描述 207
9.3.2 类arrayQueue 209
9.4 链表描述 212
9.5 应用 214
9.5.1 列车车厢重排 214
9.5.2 电路布线 217
9.5.3 图元识别 219
9.5.4 工厂仿真 222
9.6 参考及推荐读物 234
第10章 跳表和散列 235
10.1 字典 235
10.2 抽象数据类型 236
10.3 线性表描述 237
10.4 跳表表示（可选） 239
10.4.1 理想情况 239
10.4.2 插入和删除 241
10.4.3 级的分配 241
10.4.4 结构skipNode 242
10.4.5 类skipList 242
10.4.6 skipList方法的复杂度 246
10.5 散列表描述 246
10.5.1 理想散列 246
10.5.2 散列函数和散列表 248
10.5.3 线性探查 250
10.5.4 链式散列 255
10.6 一个应用——文本压缩 260
10.6.1 LZW压缩 260
10.6.2 LZW压缩的实现 261
10.6.3 LZW解压缩 264
10.6.4 LZW解压缩的实现 265
10.6.5 性能评价 268
10.7 参考及推荐读物 269
第11章 二叉树和其他树 270
11.1 树 270
11.2 二叉树 273
11.3 二叉树的特性 274
11.4 二叉树的描述 275
11.4.1 数组描述 275
11.4.2 链表描述 276
11.5 二叉树常用操作 277
11.6 二叉树遍历 277
11.7 抽象数据类型BinaryTree 281
11.8 类linkedBinaryTree 282
11.9 应用 285
11.9.1 设置信号放大器 285
11.9.2 并查集 288
11.10 参考及推荐读物 296
第12章 优先级队列 297
12.1 定义和应用 297
12.2 抽象数据类型 298
12.3 线性表 299
12.4 堆 299
12.4.1 定义 299
12.4.2 大根堆的插入 300
12.4.3 大根堆的删除 301
12.4.4 大根堆的初始化 301
12.4.5 类maxHeap 302
12.4.6 堆和STL 305
12.5 左高树 306
12.5.1 高度优先与宽度优先的最大及最小左高树 306
12.5.2 最大HBLT的插入 308
12.5.3 最大HBLT的删除 308
12.5.4 两棵最大HBLT的合并 308
12.5.5 初始化 309
12.5.6 类maxHblt 310
12.6 应用 313
12.6.1 堆排序 313
12.6.2 机器调度 314
12.6.3 霍夫曼编码 317
12.7 参考及推荐读物 322
第13章 竞赛树 323
13.1 赢者树和应用 323
13.2 抽象数据类型WinnerTree 326
13.3 赢者树的实现 327
13.3.1 表示 327
13.3.2 赢者树的初始化 328
13.3.3 重新组织比赛 328
13.3.4 类completeWinnerTree 328
13.4 输者树 329
13.5 应用 331
13.5.1 用最先适配法求解箱子装载问题 331
13.5.2 用相邻适配法求解箱子装载问题 335
13.6 参考及推荐读物 337
第14章 搜索树 338
14.1 定义 338
14.1.1 二叉搜索树 338
14.1.2 索引二叉搜索树 340
14.2 抽象数据类型 340
14.3 二叉搜索树的操作和实现 341
14.3.1 类binarySearchTree 341
14.3.2 搜索 342
14.3.3 插入 342
14.3.4 删除 343
14.3.5 二叉搜索树的高度 346
14.4 带有相同关键字元素的二叉搜索树 347
14.5 索引二叉搜索树 348
14.6 应用 349
14.6.1 直方图 349
14.6.2 箱子装载问题的最优匹配法 351
14.6.3 交叉分布 353
第15章 平衡搜索树 359
15.1 AVL树 360
15.1.1 定义 360
15.1.2 AVL树的高度 361
15.1.3 AVL树的描述 361
15.1.4 AVL搜索树的搜索 361
15.1.5 AVL搜索树的插入 361
15.1.6 AVL搜索树的删除 364
15.2 红-黑树 367
15.2.1 基本概念 367
15.2.2 红-黑树的描述 368
15.2.3 红-黑树的搜索 368
15.2.4 红-黑树的插入 368
15.2.5 红-黑树的删除 371
15.2.6 实现细节的考虑及复杂性分析 374
15.3 分裂树 376
15.3.1 介绍 376
15.3.2 分裂树的操作 376
15.3.3 折算复杂性 378
15.4 B-树 379
15.4.1 索引顺序访问方法 379
15.4.2 m叉搜索树 380
15.4.3 m阶B-树 381
15.4.4 B-树的高度 382
15.4.5 B-树的搜索 382
15.4.6 B-树的插入 382
15.4.7 B-树的删除 384
15.4.8 节点结构 387
15.5 参考及推荐读物 389
第16章 图 390
16.1 基本概念 390
16.2 应用和更多的概念 391
16.3 特性 394
16.4 抽象数据类型graph 395
16.5 无权图的描述 396
16.5.1 邻接矩阵 396
16.5.2 邻接链表 397
16.5.3 邻接数组 398
16.6 加权图的描述 400
16.7 类实现 400
16.7.1 不同的类 400
16.7.2 邻接矩阵类 401
16.7.3 扩充chain类 405
16.7.4 链表类 405
16.8 图的遍历 407
16.8.1 广度优先搜索 407
16.8.2 广度优先搜索的实现 408
16.8.3 方法graph::bfs的复杂性分析 409
16.8.4 深度优先搜索 410
16.8.5 深度优先搜索的实现 411
16.8.6 方法graph::dfs的复杂性分析 412
16.9 应用 412
16.9.1 寻找一条路径 412
16.9.2 连通图及其构成 414
16.9.3 生成树 415
第三部分 算法设计方法
第17章 贪婪算法 420
17.1 最优化问题 420
17.2 贪婪算法思想 421
17.3 应用 424
17.3.1 货箱装载 424
17.3.2 0/1背包问题 425
17.3.3 拓扑排序 427
17.3.4 二分覆盖 430
17.3.5 单源最短路径 433
17.3.6 最小成本生成树 436
17.4 参考及推荐读物 445
第18章 分而治之 446
18.1 算法思想 446
18.2 应用 453
18.2.1 残缺棋盘 453
18.2.2 归并排序 455
18.2.3 快速排序 459
18.2.4 选择 464
18.2.5 相距最近的点对 466
18.3 解递归方程 474
18.4 复杂度的下限 475
18.4.1 最小最大问题的下限 476
18.4.2 排序算法的下限 477
第19章 动态规划 479
19.1 算法思想 479
19.2 应用 481
19.2.1 0/1背包问题 481
19.2.2 矩阵乘法链 484
19.2.3 所有顶点对之间的最短路径 489
19.2.4 带有负值的单源最短路径 492
19.2.5 网组的无交叉子集 496
19.3 参考及推荐读物 501
第20章 回溯法 502
20.1 算法思想 502
20.2 应用 506
20.2.1 货箱装载 506
20.2.2 0/1背包问题 512
20.2.3 最大完备子图 515
20.2.4 旅行商问题 517
20.2.5 电路板排列 519
第21章 分支定界 525
21.1 算法思想 525
21.2 应用 528
21.2.1 货箱装载 528
21.2.2 0/1背包问题 535
21.2.3 最大完备子图 536
21.2.4 旅行商问题 538
21.2.5 电路板排列 541
