基本信息
- 原书名：Data Structures and Other Objects Using C++, 4E
- 原出版社： Pearson Education
- 作者： (美)Michael Main Walter Savitch
- 译者： 金名
- 丛书名： 世界著名计算机教材精选
- 出版社：清华大学出版社
- ISBN：9787302278818
- 上架时间：2012-5-11
- 出版日期：2012 年5月
- 开本：16开
- 页码：727
- 版次：4-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 数据结构
计算机 > 软件与程序设计 > C++ > C++
教材 > 计算机教材 > 高职高专 > 计算机类 > 程序设计
内容简介
书籍
计算机书籍
《数据结构与面向对象程序设计(C++版)(第4版)》是为计算机科学专业的第二门课程CS2编写的，首先介绍了软件开发的各个阶段、C++面向对象程序设计思想，然后从软件开发的角度，利用面向对象设计的思想，系统阐述了指针和动态数组、链表、模板类、迭代器、栈、队列、递归实现、树和图等内容，并对排序与查找的相关算法进行了深入剖析。为了让读者巩固所学知识，在每节后面都给出了大量练习题，并在每章后面给出厂答案。为了锻炼读者的动手能力，每章末给出了大量编程项目，在本书的配套网站www.cs.colorado.edu／~maln还给出了一些更具挑战性的编程项目。
《数据结构与面向对象程序设计(C++版)(第4版)》不仅非常适合于作为计算机及相关专业“数据结构”和“C++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。
计算机书籍
《数据结构与面向对象程序设计(C++版)(第4版)》是为计算机科学专业的第二门课程CS2编写的，首先介绍了软件开发的各个阶段、C++面向对象程序设计思想，然后从软件开发的角度，利用面向对象设计的思想，系统阐述了指针和动态数组、链表、模板类、迭代器、栈、队列、递归实现、树和图等内容，并对排序与查找的相关算法进行了深入剖析。为了让读者巩固所学知识，在每节后面都给出了大量练习题，并在每章后面给出厂答案。为了锻炼读者的动手能力，每章末给出了大量编程项目，在本书的配套网站www.cs.colorado.edu／~maln还给出了一些更具挑战性的编程项目。
《数据结构与面向对象程序设计(C++版)(第4版)》不仅非常适合于作为计算机及相关专业“数据结构”和“C++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。
目录
《数据结构与面向对象程序设计(C++版)(第4版)》
第1章软件开发的阶段
1.1规范说明、设计与实现
1.2运行时间分析
1.3测试与调试
1.4本章小结
第2章抽象数据类型与C++类
2.1类与成员
2.2构造函数
2.3使用名称空间、头文件与实现文件
2.4类与参数
2.5操作符重载
2.6标准模板库与pair类
2.7本章小结
第3章容器类
3.1bag类
3.2编程项目：sequence类
3.3交互式测试程序
3.4STL中的multiset类及其迭代器
3.5本章小结
第1章软件开发的阶段
1.1规范说明、设计与实现
1.2运行时间分析
1.3测试与调试
1.4本章小结
第2章抽象数据类型与C++类
2.1类与成员
2.2构造函数
2.3使用名称空间、头文件与实现文件
2.4类与参数
2.5操作符重载
2.6标准模板库与pair类
2.7本章小结
第3章容器类
3.1bag类
3.2编程项目：sequence类
3.3交互式测试程序
3.4STL中的multiset类及其迭代器
3.5本章小结
译者序
本书以数据结构为基础，以C++为实现语言，从软件开发的角度，利用面向对象设计的思想，系统阐述了指针和动态数组、链接、模板类、迭代器、栈、队列、递归实现、树和图等内容。为了让读者巩固所学知识，在每节后面都给出了大量练习题，并在每章后面给出了答案。为了让读者融会贯通所学知识，对同一个示例，给出了不同的实现，让读者体会到各种实现的优缺点，为了锻炼读者的动手能力，每章末给出了大量编程项目，在本书的配套网站www．CS．colorado．edu／~main还给出了一些更具挑战性的编程项目。
本书不仅非常适合于作为计算机及相关专业“数据结构”和“C++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。
本书由金名主译，张长富、蔡建章、李匀、张建安、邓铁洪、徐君、李强、蒋恩俊、杨文保、李强、苏辛、周成兴、魏敬安、朱建波、徐志平、赵杰辉、傅棉、郭碧莲、郭洵、洪晓煜、黄宣达、江松波、柯渝、赖曲芳、廖阳、刘文红、李伟、郭涛、高磊、王振营、冯哲、韩毅、马以辉、李腾、邓卫、邓凡平、周云、董武、郑晓蕊、陈占军、倪泳智、黄虹、吕巧珍、裘蕾、金颖、陈河南、王嘉佳、吴建伟、宋雁、贺军等人也参与了本书的翻译工作，在此一并表示感谢!
由于水平有限，如有不妥之处，恳请读者指正
本书不仅非常适合于作为计算机及相关专业“数据结构”和“C++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。
本书由金名主译，张长富、蔡建章、李匀、张建安、邓铁洪、徐君、李强、蒋恩俊、杨文保、李强、苏辛、周成兴、魏敬安、朱建波、徐志平、赵杰辉、傅棉、郭碧莲、郭洵、洪晓煜、黄宣达、江松波、柯渝、赖曲芳、廖阳、刘文红、李伟、郭涛、高磊、王振营、冯哲、韩毅、马以辉、李腾、邓卫、邓凡平、周云、董武、郑晓蕊、陈占军、倪泳智、黄虹、吕巧珍、裘蕾、金颖、陈河南、王嘉佳、吴建伟、宋雁、贺军等人也参与了本书的翻译工作，在此一并表示感谢!
由于水平有限，如有不妥之处，恳请读者指正
前言
本书是为计算机科学专业的第二门课程编写的，在美国很多大学中称之为CS2。本书的重点是规范说明、设计和实现，以及基本数据类型的使用，这些内容都将在第二学期的课程中介绍。而且，本书还介绍了很多重要的编程技术，提供了有关抽象技术、面向对象程序设计、算法的大O时间分析以及排序等内容。
本书假设学生已经完成了“计算机科学导论”和“程序设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容(如递归和指针)。本书使用的是C什语言，但对C什类的介绍是从零开始的，因此，对于那些以C而不是以C柑作为程序设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术(参见附录F)，以及C++参数类型(参见第2章)有所了解。当C程序员克服了有关输入／输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强应用背景的学生来说，可以有选择地学习本书的内容。
本版新增内容
C++标准模板库(Standard Template Library，STL)在我们的课程中起着更大的作用了，在本书中增加了精心挑选的素材给予介绍。对我们来说，重要的是让我们的学生既能理解如何在应用程序中使用STL类，也能掌握实现这些类(或类似类)的途径。基于这种思考，
本版进行了以下修改：
新增了2．6节，利用pair类对标准模板库进行早期介绍。我们在学生还没有完全理解模板之前，就向他们介绍STL。
在3．4节提前介绍multiset类和STL迭代器。这是介绍这些内容的好地方，因为学生刚刚明白了如何实现他们自己的第一个集合类(即bag类)，该类是基于multiset类的。
在4．5节继续介绍STL的string类，在这里很适合学生用动态数组来实现自己的string类。
新增5．6节，对3个类似的STL类：vector、list和deque进行比较。此时，学生有足够的知识来理解典型的vector和list类实现。
在6．3节首次介绍STL算法，在11．2节和13．4节进行了扩展介绍。
新增8．4节，介绍了联合使用动态数组和指针，实现STL的deque类的细节。
在12．6节讨论了TRl库中的散列表。
大多数章节增加了很多新编程项目，你还可以关注本书的配套网站了解我们开发的新项目：www．cs．colorado．edu／-main／dsoc．html。
每种数据类型的5个介绍步骤
总体来说，第4版继续介绍如下的经典数据结构：集合、包(或多集)、序列表、有序列表(利用“小于”操作符排序)、栈、队列、表和图。此外，还补充介绍了一些数据结构，比如优先队列。上述每种数据结构都将按照如下固定的模式来进行介绍。
第1步：抽象地理解数据结构。在这一层上，学生从概念和图形的层面上，得到对数据结构及其操作的理解。例如，学生可以可视化一个栈及其压入和弹出元素的操作。简单的应用程序更容易理解，而且可以手工完成，比如使用栈来颠倒一个单词的字母顺序。
第2步：把数据结构的规范说明编写成一个C什类。在这一步中，学生明白和理解如何为实现数据类型的C++类编写规范说明。该规范说明包括构造函数、公用成员函数的原型，以及其他公用属性(比如一个用于确定栈的最大尺寸的基本常量)。每个成员函数的原型都给出了前置条件和后置条件，完整地描述了该函数的行为。在这一层很重要的是，让学生明白规范说明与任何实现技术无关。事实上，相同的规范说明可以用于描述相同数据类型的多种不同实现。
第3步：使用数据类型。有了规范说明，学生就可以编写小型的应用程序或演示程序，来展示所使用的数据结构。这些应用程序只是基于数据类型的规范说明，还没有涉及实现。
第4步：选择适当的数据结构，并继续设计和实现数据类型。在对数据类型有了一个好的抽象理解之后，就可以选择一个恰当的数据结构，比如固定大小的数组、动态数组、节点链表或节点二叉树。对于很多数据类型来说，最初的设计和实现会选择简单的方式，比如固定大小的数组。随后，我们将用更复杂的基本结构来重新设计和重新实现相同的数据结构。
由于本书使用的是C++类，对于某个数据类型的实现，将有多种可供选择的数据结构(比如数组、指针等)来作为类的私有成员变量。对于每个实现的类，我们强调应清楚理解私有成员变量与数据类型抽象表示之间的关联规则。我们要求每个学生应用简洁的语言写出这些规则(我们称之为抽象数据类型的不变式)。一旦不变式编写完毕后，就可以继续实现各种成员函数了。不变式有助于编写正确的函数，原因有两条：(1)当函数开始运行时，每个函数(构造函数除外)都知道不变式已为真；(2)当函数结束运行时，每个函数(析构函数除外)都要确保不变式为真。
本书假设学生已经完成了“计算机科学导论”和“程序设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容(如递归和指针)。本书使用的是C什语言，但对C什类的介绍是从零开始的，因此，对于那些以C而不是以C柑作为程序设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术(参见附录F)，以及C++参数类型(参见第2章)有所了解。当C程序员克服了有关输入／输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强应用背景的学生来说，可以有选择地学习本书的内容。
本版新增内容
C++标准模板库(Standard Template Library，STL)在我们的课程中起着更大的作用了，在本书中增加了精心挑选的素材给予介绍。对我们来说，重要的是让我们的学生既能理解如何在应用程序中使用STL类，也能掌握实现这些类(或类似类)的途径。基于这种思考，
本版进行了以下修改：
新增了2．6节，利用pair类对标准模板库进行早期介绍。我们在学生还没有完全理解模板之前，就向他们介绍STL。
在3．4节提前介绍multiset类和STL迭代器。这是介绍这些内容的好地方，因为学生刚刚明白了如何实现他们自己的第一个集合类(即bag类)，该类是基于multiset类的。
在4．5节继续介绍STL的string类，在这里很适合学生用动态数组来实现自己的string类。
新增5．6节，对3个类似的STL类：vector、list和deque进行比较。此时，学生有足够的知识来理解典型的vector和list类实现。
在6．3节首次介绍STL算法，在11．2节和13．4节进行了扩展介绍。
新增8．4节，介绍了联合使用动态数组和指针，实现STL的deque类的细节。
在12．6节讨论了TRl库中的散列表。
大多数章节增加了很多新编程项目，你还可以关注本书的配套网站了解我们开发的新项目：www．cs．colorado．edu／-main／dsoc．html。
每种数据类型的5个介绍步骤
总体来说，第4版继续介绍如下的经典数据结构：集合、包(或多集)、序列表、有序列表(利用“小于”操作符排序)、栈、队列、表和图。此外，还补充介绍了一些数据结构，比如优先队列。上述每种数据结构都将按照如下固定的模式来进行介绍。
第1步：抽象地理解数据结构。在这一层上，学生从概念和图形的层面上，得到对数据结构及其操作的理解。例如，学生可以可视化一个栈及其压入和弹出元素的操作。简单的应用程序更容易理解，而且可以手工完成，比如使用栈来颠倒一个单词的字母顺序。
第2步：把数据结构的规范说明编写成一个C什类。在这一步中，学生明白和理解如何为实现数据类型的C++类编写规范说明。该规范说明包括构造函数、公用成员函数的原型，以及其他公用属性(比如一个用于确定栈的最大尺寸的基本常量)。每个成员函数的原型都给出了前置条件和后置条件，完整地描述了该函数的行为。在这一层很重要的是，让学生明白规范说明与任何实现技术无关。事实上，相同的规范说明可以用于描述相同数据类型的多种不同实现。
第3步：使用数据类型。有了规范说明，学生就可以编写小型的应用程序或演示程序，来展示所使用的数据结构。这些应用程序只是基于数据类型的规范说明，还没有涉及实现。
第4步：选择适当的数据结构，并继续设计和实现数据类型。在对数据类型有了一个好的抽象理解之后，就可以选择一个恰当的数据结构，比如固定大小的数组、动态数组、节点链表或节点二叉树。对于很多数据类型来说，最初的设计和实现会选择简单的方式，比如固定大小的数组。随后，我们将用更复杂的基本结构来重新设计和重新实现相同的数据结构。
由于本书使用的是C++类，对于某个数据类型的实现，将有多种可供选择的数据结构(比如数组、指针等)来作为类的私有成员变量。对于每个实现的类，我们强调应清楚理解私有成员变量与数据类型抽象表示之间的关联规则。我们要求每个学生应用简洁的语言写出这些规则(我们称之为抽象数据类型的不变式)。一旦不变式编写完毕后，就可以继续实现各种成员函数了。不变式有助于编写正确的函数，原因有两条：(1)当函数开始运行时，每个函数(构造函数除外)都知道不变式已为真；(2)当函数结束运行时，每个函数(析构函数除外)都要确保不变式为真。
