数据结构、算法与应用--C++语言描述
点击看大图基本信息
- 作者： （美）Sartaj Sahni [作译者介绍]
- 译者： 汪诗林 孙晓东 等
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：7111076451
- 上架时间：2006-10-17
- 出版日期：2004 年5月
- 开本：16开
- 页码：535
- 版次：1-8
- 所属分类：
计算机 > 计算机科学理论与基础知识 > 数据结构
教材 > 研究生/本科/专科教材 > 工学 > 计算机
内容简介回到顶部↑
书籍
计算机书籍
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。
本书在简要回顾了基本的c++程序设计概念的基础上，全面系统地介绍了队列、堆栈、树、图等基本数据结构，以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，本书不仅仅介绍了理论知识，还提供了50多个应用实例及600多道练习题。
本书内容广博权威，结构清晰合理，是一本全新的有关数据结构与算法的教材，对广计算机科学与工程领域的从业人员也是一本很好的参考书。
本书特色：
“纵览全书可以看出作者具有丰富的教材编写经验。它是一本新的、有关数据结构与算法的教材，适合于当前计算机本科教学的需要。”
——sang w．lee，密歇根大学
“注重应用不仅可以使课堂教学更生动，而且可以激励学生投身于相关的应用。”
——yu lo c．chang，新汉普郡大学
本书不同于以往介绍数据结构或介绍算法的书，而是囊括了数据结构及算法，是作者在该领域做出的又一个创新性的贡献。本书的另一个独特之处在于其充分强调了应用性。对于每一种数据结构及算法，都分别采用了若干个来自不同领域的应用进行具体演示。
本书为学习和研究数据结构及算法奠定了坚实的基础。
计算机书籍
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。
本书在简要回顾了基本的c++程序设计概念的基础上，全面系统地介绍了队列、堆栈、树、图等基本数据结构，以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法，为数据结构与算法的继续学习和研究奠定了一个坚实的基础。更为可贵的是，本书不仅仅介绍了理论知识，还提供了50多个应用实例及600多道练习题。
本书内容广博权威，结构清晰合理，是一本全新的有关数据结构与算法的教材，对广计算机科学与工程领域的从业人员也是一本很好的参考书。
本书特色：
“纵览全书可以看出作者具有丰富的教材编写经验。它是一本新的、有关数据结构与算法的教材，适合于当前计算机本科教学的需要。”
——sang w．lee，密歇根大学
“注重应用不仅可以使课堂教学更生动，而且可以激励学生投身于相关的应用。”
——yu lo c．chang，新汉普郡大学
本书不同于以往介绍数据结构或介绍算法的书，而是囊括了数据结构及算法，是作者在该领域做出的又一个创新性的贡献。本书的另一个独特之处在于其充分强调了应用性。对于每一种数据结构及算法，都分别采用了若干个来自不同领域的应用进行具体演示。
本书为学习和研究数据结构及算法奠定了坚实的基础。
作译者回到顶部↑
本书提供作译者介绍
汪诗林，1968年3月生，国防科技大学许算机学院在职博士。近年来主要从事计算机软件、数据库、多媒体及虚拟现实等领域的教学和研究工作，独立完成多项软件研制任务，共发表教学和科研论文近30篇，获部委级科技进步成果二等奖2项，三等奖4项，获校级优秀教学成果三等奖1项。编写及编译教材各1部(《数字逻辑》、《最新人工智能语言--CommonLisp及CLOS的系统开发方法》)。1997年参加全国第一届863高级技术人才培训班。
王广芳，1938年2月生，国防科技大学计算机学院教授。多年来从事计算机软件的教学工作和.. << 查看详细
王广芳，1938年2月生，国防科技大学计算机学院教授。多年来从事计算机软件的教学工作和.. << 查看详细
目录回到顶部↑
译者序
前言
第一部分 预备知识
第1章c++程序设计
1.1 引言
1.2 函数与参数
1.2.1 传值参数
1.2.2 模板函数
1.2.3 引用参数
1.2.4 常镇引用参数
1.2.5 返问值
1.2.6 递归函数
1.3 动态存储分配
1.3.1 操作符new
1.3.2 一维数组
1.3.3 异常处理
1.3.4操作符delete
1.3.5 二维数组
1.4 类
1.4.1 类currency
前言
第一部分 预备知识
第1章c++程序设计
1.1 引言
1.2 函数与参数
1.2.1 传值参数
1.2.2 模板函数
1.2.3 引用参数
1.2.4 常镇引用参数
1.2.5 返问值
1.2.6 递归函数
1.3 动态存储分配
1.3.1 操作符new
1.3.2 一维数组
1.3.3 异常处理
1.3.4操作符delete
1.3.5 二维数组
1.4 类
1.4.1 类currency
译者序回到顶部↑
在可视化程序设计平台广泛流行和应用的今天，程序设计不再是一件神秘的、专业性的工作，很多非计算机专业的人员都可以亲自动手设计应用程序。这似乎让人觉得，只要掌握了一门可视化程序设计语言，人人都可以成为编程高手，但事实并非如此。要想成为一个熟练的专业化程序设计人员，他(她)至少应该满足以下三个条件：一是能够熟练地选择和设计各种数据结构和算法，二是熟练掌握一门程序设计语言，三是熟知应用领域的相关知识。其中后两个条件比较容易实现，而第一个条件则需要花相当的时间和精力才能达到，它是区分一个程序设计人员水平高低的重要标志。之所以如此，是因为在绝大多数应用程序中都需要广泛使用各种各样的数据结构和算法。缺少数据结构和算法的深厚功底，很难设计出高水平的具有专业水准的应用程序。
本书的作者Sartaj Sahni博士，多年来一直从事数据结构和算法方面的研究和教育工作，具有丰富的教学经验，曾获得IEEE计算机分会1997年Taylor L．Booth教育奖。他撰写了多部有关数据结构和算法方面的著作，本书是他在该领域为广大读者奉献的又一力作。
全书共包含三个部分，第一部分主要回顾一些重要的C++程序设计概念以及算法分析与评价的方法。第二部分首先对各种数据描述方法进行了精辟地概括，然后依次介绍了数组、矩阵、堆栈、队列、字典、二叉树、优先队列、竞赛树和图等基本数据结构，对于每一种数据结构都分别采用若干个来自不同领域的应用实例进行了具体的演示。第三部分重点介绍了一些常用的算法设计方法及应用，如贪婪算法，分而治之算法、动态规划方法、回溯算法和分枝定界算法。
本书的最大特色就是强调应用。通过现实生活中的许多应用实例具体演示了书中所介绍的各种数据结构和算法设计方法。根据实例，'读者不但可以印证许多基本概念，而且能加深对它们的理解，从而更好地掌握相应的数据结构和算法并能达到熟练应用。通过把应用与理论知识紧密结合，极大地激发了读者学习数据结构和算法的兴趣。
如果你是一名程序设计新手，本书可以为你架起一座桥梁，使你如愿以偿地跨入专业程序设计人员的行列；如果你已经是一名专业程序设计人员，本书可以使你的程序设计水平更上一层楼。当然，如果你是一名计算机专业的在校学生，本书将是一本非常理想的关于数据结构和算法课程的教材或参考书。
参加本书翻译工作的有汪诗林、孙晓东、蒋艳凰、孙海燕、刘娜、郑倩冰、史军慧、陈海燕，由王广芳教授和汪诗林博士完成全书的审校工作。
因时间仓促，翻译若有不妥之处，恳请读者批评指正。
译 者
1999年9月于长沙
本书的作者Sartaj Sahni博士，多年来一直从事数据结构和算法方面的研究和教育工作，具有丰富的教学经验，曾获得IEEE计算机分会1997年Taylor L．Booth教育奖。他撰写了多部有关数据结构和算法方面的著作，本书是他在该领域为广大读者奉献的又一力作。
全书共包含三个部分，第一部分主要回顾一些重要的C++程序设计概念以及算法分析与评价的方法。第二部分首先对各种数据描述方法进行了精辟地概括，然后依次介绍了数组、矩阵、堆栈、队列、字典、二叉树、优先队列、竞赛树和图等基本数据结构，对于每一种数据结构都分别采用若干个来自不同领域的应用实例进行了具体的演示。第三部分重点介绍了一些常用的算法设计方法及应用，如贪婪算法，分而治之算法、动态规划方法、回溯算法和分枝定界算法。
本书的最大特色就是强调应用。通过现实生活中的许多应用实例具体演示了书中所介绍的各种数据结构和算法设计方法。根据实例，'读者不但可以印证许多基本概念，而且能加深对它们的理解，从而更好地掌握相应的数据结构和算法并能达到熟练应用。通过把应用与理论知识紧密结合，极大地激发了读者学习数据结构和算法的兴趣。
如果你是一名程序设计新手，本书可以为你架起一座桥梁，使你如愿以偿地跨入专业程序设计人员的行列；如果你已经是一名专业程序设计人员，本书可以使你的程序设计水平更上一层楼。当然，如果你是一名计算机专业的在校学生，本书将是一本非常理想的关于数据结构和算法课程的教材或参考书。
参加本书翻译工作的有汪诗林、孙晓东、蒋艳凰、孙海燕、刘娜、郑倩冰、史军慧、陈海燕，由王广芳教授和汪诗林博士完成全书的审校工作。
因时间仓促，翻译若有不妥之处，恳请读者批评指正。
译 者
1999年9月于长沙
前言回到顶部↑
有关数据结构和算法的研究是计算机科学与工程的基础性研究之一，掌握该领域的知识对于我们利用计算机资源高效地开发计算机程序非常必要。因此，目前所有的计算机专业都开设了一到两门相关的课程来讲授这方面的知识。一般来说，第一门程序设计课程主要向学生介绍基本的数据结构(如堆栈和队列)和基本的算法(如排序和矩阵运算)，第二门程序设计课程进一步介绍更多的数据结构和算法，其后可设置一到两门课程专门致力于对数据结构和算法的研究。
计算机本科专业课程设置过多的问题已迫使许多院校对专业内容进行了大量合并，以尽量减少课程的数量。比如在佛罗里达大学，本科学生仅开设了一门数据结构和算法课程(一个学期)。在学习本课程以前，要求学生们已经学习过一门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站点中还提供了以下材料：每章练习的解答；一些测试样本以及相应的测试结果；一些附加的应用实例以及对本书中部分材料的进一步讨论。
怎样使用本书
可以采取多种方式来使用本书讲授数据结构和/或算法。教师应该根据学生的背景知识、希望强调哪些应用以及课程的学时数来做出决定。下面我们给出了几个可能的课程安排。我们建议作业的形式是让学生编写并调试一些程序，开始时程序可以比较短，随着课程的深入，程序将逐渐变大。学生应根据课堂上所讲授的主题同步阅读书中的相关内容。
计算机本科专业课程设置过多的问题已迫使许多院校对专业内容进行了大量合并，以尽量减少课程的数量。比如在佛罗里达大学，本科学生仅开设了一门数据结构和算法课程(一个学期)。在学习本课程以前，要求学生们已经学习过一门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站点中还提供了以下材料：每章练习的解答；一些测试样本以及相应的测试结果；一些附加的应用实例以及对本书中部分材料的进一步讨论。
怎样使用本书
可以采取多种方式来使用本书讲授数据结构和/或算法。教师应该根据学生的背景知识、希望强调哪些应用以及课程的学时数来做出决定。下面我们给出了几个可能的课程安排。我们建议作业的形式是让学生编写并调试一些程序，开始时程序可以比较短，随着课程的深入，程序将逐渐变大。学生应根据课堂上所讲授的主题同步阅读书中的相关内容。
)
加载中...
