数据结构与面向对象程序设计（C++版）（第4版）（世界著名计算机教材精选）

　　《数据结构与面向对象程序设计(c++版)(第4版)》是为计算机科学专业的第二门课程cs2编写的，首先介绍了软件开发的各个阶段、c++面向对象程序设计思想，然后从软件开发的角度，利用面向对象设计的思想，系统阐述了指针和动态数组、链表、模板类、迭代器、栈、队列、递归实现、树和图等内容，并对排序与查找的相关算法进行了深入剖析。为了让读者巩固所学知识，在每节后面都给出了大量练习题，并在每章后面给出厂答案。为了锻炼读者的动手能力，每章末给出了大量编程项目，在本书的配套网站／~maln还给出了一些更具挑战性的编程项目。
　　《数据结构与面向对象程序设计(c++版)(第4版)》不仅非常适合于作为计算机及相关专业“数据结构”和“c++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。

第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本章小结
第4章　指针与动态数组
　4.1指针与动态内存
　4.2把指针与数组作为参数
　4.3具有动态数组的bag类
　4.4有关动态类的说明
　4.5stl的string类与编程项目
　4.6编程项目：polynomial类
　4.7本章小结
第5章　链表
　5.1链表的基本节点类
　5.2链表工具包
　5.3用链表实现bag类
　5.4编程项目：用链表实现sequence类
　5.5动态数组、链表与双向链表
　5.6标准模板库的vector、list和deque类
　5.7本章小结
第6章　用模板、迭代器和stl进行软件开发
　6.1模板函数
　6.2模板类
　6.3stl算法与迭代器的使用
　6.4节点模板类
　6.5链表的迭代器
　6.6含迭代器的链表版bag模板类
　6.7本章小结与5个bag类的小结
第7章　栈
　7.1stl的stack类
　7.2栈的应用
　7.3stack类的实现
　7.4更复杂的栈应用
　7.5本章小结
第8章　队列
　8.1stl队列
　8.2队列的应用
　8.3队列类的实现
　8.4实现stl的双端队列
　8.5栈、队列和优先队列类的引用返回值
　8.6本章小结
第9章　递归思想
　9.1.递归函数
　9.2递归的研究：分形和迷宫
　9.3推导递归
　9.4本章小结
第10章　树
　10.1树的简介
　10.2树的表示法
　10.3二叉树节点类
　10.4树的遍历
　10.5二叉查找树
　10.6本章小结
第11章　平衡树
　11.1堆
　11.2stl优先队列与堆算法
　11.3b树
　11.4树、日志和时间分析
　11.5stl的map类和multimap类
　11.6本章小结
第12章　查找
　12.1顺序查找和二叉查找
　12.2开地址散列
　12.3链式散列
　12.4散列的时间分析
　12.5程序设计：使用stl向量的表类
　12.6tri库扩展中的散列表
　12.7本章小结
第13章　排序
　13.1二次排序算法
　13.2递归排序算法
　13.3使用堆的o(n log n)算法
　13.4sn的排序与二叉查找
　13.5本章小结
第14章　派生类与继承
　14.1派生类
　14.2仿真生态系统
　14.3虚拟成员函数和game类
　14.4本章小结
第15章　图
　15.1图的定义
　15.2图的实现
　15.3图的遍历
　15.4路径算法
　15.5本章小结
附录
　附录a ascii字符集
　附录b大o表达式
　附录c操作符的优先顺序
　附录d命令行编译和链接
　附录e使用老式编译器
　附录fc什的输入和输出
　附录g选择库函数
　附录h标准模板类简介
　附录i一些有用函数的工具包
　附录j基本风格指南
　附录k下载gnu编译器和软件
　附录l异常处理

　　本书是为计算机科学专业的第二门课程编写的，在美国很多大学中称之为CS2。本书的重点是规范说明、设计和实现，以及基本数据类型的使用，这些内容都将在第二学期的课程中介绍。而且，本书还介绍了很多重要的编程技术，提供了有关抽象技术、面向对象程序设计、算法的大O时间分析以及排序等内容。
　　本书假设学生已经完成了“计算机科学导论”和“程序设计”课程的学习，但本书也包括了在第一门课中没有完全涵盖的内容(如递归和指针)。本书使用的是C什语言，但对C什类的介绍是从零开始的，因此，对于那些以C而不是以C柑作为程序设计入门语言的学生来说，本书也是适用的。根据笔者的经验，这类学生需要对C++输入和输出技术(参见附录F)，以及C++参数类型(参见第2章)有所了解。当C程序员克服了有关输入／输出和参数的障碍后，就能领略C++的类和面向对象特性。需要指出的是，根据学生不同的知识背景，本书有多种不同的学习方案。对于那些有较强应用背景的学生来说，可以有选择地学习本书的内容。
　　本版新增内容
　　C++标准模板库(Standard TemplateLibrary，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)当函数结束运行时，每个函数(析构函数除外)都要确保不变式为真。