数据结构、算法与应用：C++语言描术——计算机科学丛书 (2008 年度畅销榜NO.211 )

本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。\r\n 本书在简要回顾了基本的C++ 程序设计概念的基础上，全面系统地介绍了队列、堆栈、树、图等基本数据结构，以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，本书不仅仅介绍了理论知识，还提供了50多个应用实例及600多道练习题。\r\n 本书内容广博权威，结构清晰合理，是一本全新的有关数据结构与算法的教材，对于计算机科学与工程领域的从业人员也是一本很好的参考书。

译者序\r\n前言\r\n第一部分 预备知识\r\n 第1章 C++程序设计 \r\n 1.1 引言 \r\n 1.2 函数与参数 \r\n 1.2.1 传值参数 \r\n 1.2.2 模板函数 \r\n 1.2.3 引用参数 \r\n 1.2.4 常量引用参数 \r\n 1.2.5 返回值 \r\n 1.2.6 递归函数 \r\n 1.3 动态存储分配 \r\n 1.3.1 操作符new \r\n 1.3.2 一维数组 \r\n 1.3.3 异常处理 \r\n 1.3.4 操作符delete \r\n 1.3.5 二维数组 \r\n 1.4 类 \r\n 1.4.1 类Currency \r\n 1.4.2 使用不同的描述方法 \r\n 1.4.3 操作符重载 \r\n 1.4.4 引发异常 \r\n 1.4.5 友元和保护类成员 \r\n 1.4.6 增加#ifndef, #define和#endif语句 \r\n 1.5 测试与调试 \r\n 1.5.1 什么是测试 \r\n 1.5.2 设计测试数据 \r\n 1.5.3 调试 \r\n 1.6 参考及推荐读物 \r\n 第2章 程序性能 \r\n 2.1 引言 \r\n 2.2 空间复杂性 \r\n 2.2.1 空间复杂性的组成 \r\n 2.2.2 举例 \r\n 2.3 时间复杂性 \r\n 2.3.1 时间复杂性的组成 \r\n 2.3.2 操作计数 \r\n 2.3.3 执行步数 \r\n 2.4 渐进符号（O、 健?、 o） \r\n 2.4.1 大写O符号 \r\n 2.4.2 椒?\r\n 2.4.3 符号 \r\n 2.4.4 小写o符号 \r\n 2.4.5 特性 \r\n 2.4.6 复杂性分析举例 \r\n 2.5 实际复杂性 \r\n 2.6 性能测量 \r\n 2.6.1 选择实例的大小 \r\n 2.6.2 设计测试数据 \r\n 2.6.3 进行实验 \r\n 2.7 参考及推荐读物 \r\n第二部分 数据结构\r\n 第3章 数据描述 \r\n……\r\n 第4章 数组和矩阵 \r\n 第5章 堆栈 \r\n 第6章 队列 \r\n 第7章 跳表和散列 \r\n 第8章 二叉树和其他树 \r\n 第9章 优先队列 \r\n 第10章 竞赛树 \r\n 第11章 搜索树 \r\n 第12章 图 \r\n第三部分 算法设计方法\r\n 第13章 贪婪算法 \r\n 第14章 分而治之算法 \r\n 第15章 动态规划 \r\n 第16章 回溯 \r\n 第17章 分枝定界

Sartaj Sahni在 Cronell大学获得硕士和博士学位。曾任教于明尼苏达大学。目前是佛罗里达大学计逄机与信息科学工程系主任。Sahni教授在数据结构与算法领域的研究和教学方面享有世界声誉，因此当选为IEEE和ACM两会会士以及欧洲科学院院士，并获得IEEE计算机学会的Taylor L.Booth教育奖和W.Wallace-MCDowell奖，2003年更荣获计算机教育最高荣誉ACM Karl V.Karlstrom杰出教育家奖。

有关数据结构和算法的研究是计算机科学与工程的基础性研究之一，掌握该领域的知识对于我们利用计算机资源高效地开发计算机程序非常必要。因此， 目前所有的计算机专业都开设了一到两门相关的课程来讲授这方面的知识。一般来说，第一门程序设计课程主要向学生介绍基本的数据结构(如堆栈和队列)和基本的算法(如排序和矩阵运算)，第二门程序设计课程进一步介绍更多的数据结构和算法，其后可设置一到两门课程专门致力于对数据结构和算法的研究； 计算机本科专业课程设置过多的问题已迫使许多院校对专业内容进行了大量合并，以尽量减少课程的数量。比如在佛罗里达大学，本科学生仅开设了一门数据结构和算法课程(一个学期)。在学习本课程以前，要求学生们已经学习过一门C++程序设计课程(一个学期)和其他有关离散数学/结构方面的课程。 本书的编写目的有两个，一是作为相关专业课程的教材，二是作为参考材料，为其他进一步研究数据结构和算法的课程服务。全书共分三个部分。第一部分包含第1章和第2章，主要帮助读者回顾一下C++程序设计的概念以及算法分析与测量方法。对C语言程序设计很熟悉的学生应能通过第1章来跨越C与C++之间的鸿沟。第1章并不是C++的入门介绍，它给出了大多数容易为学生们所忽视的C++概念，如参数传递方式、模板函数、递归、动态存储分配、类、异常的引发和捕获等。其他更高级的C++概念(如继承、虚拟函数和抽象类等)则在首次出现的章节内加以介绍。第2章首先回顾了各种分析程序性能的方法——操作计数、执行步数和渐进符号(O、Ω、Θ、o)，然后回顾了实际测量程序性能的方法。在第2章所给出的应用程序中，解决了许多在程序设计入门课程中所研究的基本问题(也是很经典的问题)，如简单的排序算法(冒泡排序、选择排序、插入排序、计数排序)；简单的搜索算法(顺序搜索、折半搜索)；利用Homer法则进行多项式求值以及各种矩阵运算(如矩阵加、矩阵转置、矩阵乘)。尽管第2章的主要目的是研究程序性能分析和测量的方法，但同时也让每个学生都能熟悉一些基本的算法。 本书的第二部分包含第3~12章，它们对数据结构进行了深入的研究。第3章架设起数据结构研究的骨架，主要介绍了各种描述数据的方法——公式化描述、链表描述、模拟指针和间接寻址，同时根据每一种方法，分别设计了一个相应的C++类来描述线性表数据结构。在第3章结束的时候，我们根据各种不同数据描述方法在描述线性表结构时的性能表现，对这些方法进行了具体比较。第二部分的其他章节分别对其他各种数据结构进行了描述(采用第3章中所介绍的数据描述方法)，如数组和矩阵(第4章)、堆栈(第5章)、队列(第6章)、字典.(第7章和第11章)、二叉树(第8章)、优先队列(第9章)、竞赛树(第10章)和图(第12章)。 本书的第三部分包含第13~17章，主要研究了一些常用的算法设计方法，如贪婪算法(第13章)、分而治之算法(第14章)、动态规划(第15章)、回溯算法(第16章)和分枝定界算法(第17章)。此外，14.4节给出了两种下限的证明(最小最大问题和排序问题)；9.5.2节给出机器调度的近似算法；10.5节给出了箱子装载算法；13.3.2节给出了0/1背包问题求解算法。此外，9.5.2节还介绍了NP-复杂问题。 本书的一个唯一特性就是强调应用，通过多个应用实例来演示各种数据结构和算法设计方法。在每一章的最后一节都针对该章所介绍的数据结构或算法设计方法给出了相应的具体应用。也有不少章节一开始就介绍了相关的应用。我们给出了大量来自不同领域的应用：排序(冒泡排序、选择排序、插入排序、计数排序、堆排序、归并排序、快速排序、箱子排序、基数排序和拓扑排序)；矩阵运算(矩阵加、矩阵转置、矩阵乘)；电路设计自动化(搜索电路网组、布线路由、元件折叠、电子布线、设置信号放大器、交叉分布、电路板排列)；压缩编码(LZW压缩、霍夫曼编码、可变位长编码)；计算几何(凸包和最近点对)；仿真(工厂仿真)；图像处理(图元标注)；趣味数学(汉诺塔、残缺棋盘、迷宫)；调度(LPT调度)；优化(箱子装载、货箱装船、0/1背包、矩阵乘法链)；统计(直方图、寻找最大值和最小值、寻找第k个最小值)；图论(生成树、图元、最短路径、最大完备子图、二分覆盖和旅行商)。在引入这些应用时，不需要学生具有相关领域的预备知识，因为本书中所提供的材料已经覆盖了相应的知识。相信这些应用实例可以为学生的学习提供不少趣味。 通过把应用实例与数据结构和算法设计方法紧密结合，我们希望能更好地激发学生的学习兴趣。另外，通过本书所提供的大约600个练习以及相关的Web站点，还可以使所学知识更进一步地巩固和丰富。 WEB站点 本书所在站点的URL地址为：www.cise.ufl.edu/~sahni/dsac。访问该站点，你可以得到本书中的所有程序以及示例数据和所产生的输出。示例数据并不是特意设计的测试数据，而是仅供程序所用，以便比较给定的输出和实际产生的输出。 本书中的所有程序都已经在Borland C++5.01和GNU C++2.7.2.1下编译通过并能够正确运行。相应的文件都已经被压缩，并以两个zip文件的形式(一个对应于Borland C++，一个对应于GNUC++)放置在站点上。书中的程序编号与文件名的对应关系见readme文件(该文件也包含在相应的zip文件中)。 在Web站点中还提供了以下材料：每章练习的解答；一些测试样本以及相应的测试结果；一些附加的应用实例以及对本书中部分材料的进一步讨论。 怎样使用本书 可以采取多种方式来使用本书讲授数据结构和/或算法。教师应该根据学生的背景知识、希望强调哪些应用以及课程的学时数来做出决定。下面我们给出了几个可能的课程安排。我们建议作业的形式是让学生编写并调试一些程序，开始时程序可以比较短，随着课程的深入，程序将逐渐变大。学生应根据课堂上所讲授的主题同步阅读书中的相关内容。