（已有16条评价）基本信息
- 原书名：Data Structures and Algorithm Analysis in C++ (3rd Edition)
- 原出版社： Addison Wesley
- 作者： （美）Mark Allen Weiss
- 丛书名： 图灵原版计算机科学系列
- 出版社：人民邮电出版社
- ISBN：7115152330
- 上架时间：2006-10-8
- 出版日期：2006 年11月
- 开本：16开
- 页码：586
- 版次：3-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 数据结构
计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
计算机 > 软件与程序设计 > C++ > C++
教材 > 研究生/本科/专科教材 > 工学 > 计算机
教材 > 计算机教材 > 本科/研究生 > 计算机专业教材 > 计算机基础课程 > 算法与数学基础
内容简介
作译者
Mark Allen Weiss 1987年在普林斯顿大学获得汁算机科学博士学位，师从著名算法大师Robert Sedgewick，现任美国佛罗里达国际大学汁算与信息科学学院教授。他曾经担任全美AP(Advanced Placement)考试计算机学科委员会的主席(2000-2004)。他的主要研究方向是数据结构、算法和教育学。...
目录
Chapter 1 Introduction.
1.1 What's the Book About?
1.2 Mathematics Review
1.3 A Brief Introduction to Recursion
1.4 C++ Classes
1.5 C++ Details
1.6 Templates
1.7 Using Matrices
Chapter 2 Algorithm Analysis
2.1 Mathematical Background
2.2 Model
2.3 What to Analyze
2.4 Running Time Calculations
Chapter 3 Lists, Stacks, and Queues
3.1 Abstract Data Types (ADTs)
3.2 The List ADT
3.3 vector and list in the STL
3.4 Implementation of vector
3.5 Implementation of list
3.6 The Stack ADT
1.1 What's the Book About?
1.2 Mathematics Review
1.3 A Brief Introduction to Recursion
1.4 C++ Classes
1.5 C++ Details
1.6 Templates
1.7 Using Matrices
Chapter 2 Algorithm Analysis
2.1 Mathematical Background
2.2 Model
2.3 What to Analyze
2.4 Running Time Calculations
Chapter 3 Lists, Stacks, and Queues
3.1 Abstract Data Types (ADTs)
3.2 The List ADT
3.3 vector and list in the STL
3.4 Implementation of vector
3.5 Implementation of list
3.6 The Stack ADT
前言
目的／目标
本书全面论述了数据结构和算法分析，即组织大量数据的方法和对算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。具有讽刺意味的是，由于在输入量很大时程序的效率明显降低，因此这又要求更加关注效率问题。通过在实际编程之前对算法进行分析，学生可以确定一个特定的解法是否可行。例如，在本书中学生可看到一些特定的问题，并了解精心的实现如何能够把处理大量数据的时间从16年减至不到1秒。因此，本书中论述的算法和数据结构均对其运行时间进行了分析。在某些情况下，还研究了影响实现运行时间的一些微小细节。.
一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也越来越大，越来越复杂，这就要求开发更加复杂的程序。本书的目的是在教会学生使用良好的程序设计技巧的同时让学生具备算法分析能力，使得他们能够开发这种具有最高效率的程序。
本书适用于本科生的高级数据结构课程或是研究生的算法分析课程。使用本书的学生应该具有中等程度的程序设计方面的知识，包括指针、递归和面向对象程序设计，还要具有离散数学的某些知识。
方法
虽然本书中的内容大部分都是与语言无关的，但是，程序设计还是需要使用某种特定的语言。正如书名指出的，我们为本书选择了C++。
C++已经成为系统编程的主流语言。除了修正了许多C语言的语法方面的缺陷之外，C++还提供了直接结构(类和模板)来实现抽象数据类型的通用数据结构。
撰写本书最困难的部分是确定C++在书中所占的比例。使用太多的C++的特性将使教材变得很晦涩，使用得太少又会和使用支持类的C语言撰写的教材区别不大。
我们采用的方法是以基于对象的方法来阐述文中的内容。这样，本书中几乎没有用到继承性。我们采用类模板来描述通用数据结构。通常情况下尽量避免使用深奥的C++特性，而是使用标准C++中的vector和string类。通过采用C++的现代特性来取代在本书第1版中所用的次级特性简化了很多代码。本书前几版已经实现了类模板，方法是将类模板的接口与其实现分离开。毫无疑问，这是一种好方法，但是这种方法暴露出了编译的问题，读者事实上很难利用这些代码。本版中，在线的源代码将类模板作为一个单元来表示，而不再将接口和实现分离开。本书第1章对书中所用到的C++特性进行了介绍，并阐述了对类模板的处理方法。附录A描述了如何重写类模板，用于分离编译。
以Java和C++两种语言描述的数据结构的完全版在因特网上可以得到。我们使用类似的编码习惯使得这两种语言间的相似性表现得更加明显。
第3版中的主要变化
第3版中包含了大量的错误修正，并且书中的大部分章节都经过了修订以提高其可读性。另外，本版还有以下几方面的变化：
·书中的所有代码都做了更新以适应现代的C++特性。
·第3章进行了大量的修订，并且讨论了标准vector和list类的使用及其实现。标准vector类在其他数据结构的实现中被广泛使用。
·第4章修订后包含了关于set和map类的讨论，并通过一个扩展的例子介绍了它们在有效算法设计中的应用。在第9章中也包含了一个使用标准map类来实现最短路径算法的例子。
·第7章讨论了标准sort算法，其中包括一个关于实现重载的标准sort算法所涉及的技巧。
·书中提供的源代码都已经进行了简化，从而避免了与类模板的分离编译有关的复杂语法。
修订后的代码可以使读者更专心于算法本身，而不是过多地关注C++。
内容概述
第1章包含离散数学和递归的一些内容。我相信熟悉递归的唯一办法是反复不断地看一些好的用法。因此，除第5章外，递归遍布本书每一章的例子中。第1章还介绍了一些C++的内容，作为对C++基础知识的了解，包含在C++类设计中模板和重要结构的讨论。
本书全面论述了数据结构和算法分析，即组织大量数据的方法和对算法运行时间的估计。随着计算机的速度越来越快，对于能够处理大量输入数据的程序的需求变得日益迫切。具有讽刺意味的是，由于在输入量很大时程序的效率明显降低，因此这又要求更加关注效率问题。通过在实际编程之前对算法进行分析，学生可以确定一个特定的解法是否可行。例如，在本书中学生可看到一些特定的问题，并了解精心的实现如何能够把处理大量数据的时间从16年减至不到1秒。因此，本书中论述的算法和数据结构均对其运行时间进行了分析。在某些情况下，还研究了影响实现运行时间的一些微小细节。.
一旦确定了解法，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题也越来越大，越来越复杂，这就要求开发更加复杂的程序。本书的目的是在教会学生使用良好的程序设计技巧的同时让学生具备算法分析能力，使得他们能够开发这种具有最高效率的程序。
本书适用于本科生的高级数据结构课程或是研究生的算法分析课程。使用本书的学生应该具有中等程度的程序设计方面的知识，包括指针、递归和面向对象程序设计，还要具有离散数学的某些知识。
方法
虽然本书中的内容大部分都是与语言无关的，但是，程序设计还是需要使用某种特定的语言。正如书名指出的，我们为本书选择了C++。
C++已经成为系统编程的主流语言。除了修正了许多C语言的语法方面的缺陷之外，C++还提供了直接结构(类和模板)来实现抽象数据类型的通用数据结构。
撰写本书最困难的部分是确定C++在书中所占的比例。使用太多的C++的特性将使教材变得很晦涩，使用得太少又会和使用支持类的C语言撰写的教材区别不大。
我们采用的方法是以基于对象的方法来阐述文中的内容。这样，本书中几乎没有用到继承性。我们采用类模板来描述通用数据结构。通常情况下尽量避免使用深奥的C++特性，而是使用标准C++中的vector和string类。通过采用C++的现代特性来取代在本书第1版中所用的次级特性简化了很多代码。本书前几版已经实现了类模板，方法是将类模板的接口与其实现分离开。毫无疑问，这是一种好方法，但是这种方法暴露出了编译的问题，读者事实上很难利用这些代码。本版中，在线的源代码将类模板作为一个单元来表示，而不再将接口和实现分离开。本书第1章对书中所用到的C++特性进行了介绍，并阐述了对类模板的处理方法。附录A描述了如何重写类模板，用于分离编译。
以Java和C++两种语言描述的数据结构的完全版在因特网上可以得到。我们使用类似的编码习惯使得这两种语言间的相似性表现得更加明显。
第3版中的主要变化
第3版中包含了大量的错误修正，并且书中的大部分章节都经过了修订以提高其可读性。另外，本版还有以下几方面的变化：
·书中的所有代码都做了更新以适应现代的C++特性。
·第3章进行了大量的修订，并且讨论了标准vector和list类的使用及其实现。标准vector类在其他数据结构的实现中被广泛使用。
·第4章修订后包含了关于set和map类的讨论，并通过一个扩展的例子介绍了它们在有效算法设计中的应用。在第9章中也包含了一个使用标准map类来实现最短路径算法的例子。
·第7章讨论了标准sort算法，其中包括一个关于实现重载的标准sort算法所涉及的技巧。
·书中提供的源代码都已经进行了简化，从而避免了与类模板的分离编译有关的复杂语法。
修订后的代码可以使读者更专心于算法本身，而不是过多地关注C++。
内容概述
第1章包含离散数学和递归的一些内容。我相信熟悉递归的唯一办法是反复不断地看一些好的用法。因此，除第5章外，递归遍布本书每一章的例子中。第1章还介绍了一些C++的内容，作为对C++基础知识的了解，包含在C++类设计中模板和重要结构的讨论。
