出版社:高等教育
出版日期:2001-1
ISBN:9787040092035
作者:张乃孝//裘宗燕
页数:392页
作者简介
《数据结构:C++与面向对象的途径(修订版)》是1998年6月出版的《数据结构——C++与面向对象的途径》一书的修订版.它采用面向对象的思想组织数据结构的内容，运用C什语言作为讨论数据结构的工作语言。在第一版的基础上，除对各章的顺序及内容安排进行了进一步的调整之外，还补充了各章的例子、习题，并增加了若干上机实习题，使读者可以更好地对数据结构进行学习、实践.在《数据结构:C++与面向对象的途径(修订版)》的最后还附加了一个上机实习报告的例子，使其具有较强的实用性。《数据结构:C++与面向对象的途径(修订版)》除延续了第一版的风格外，内容更加充实、完整，，讲解更加清楚、透彻。可作为本科计算机专业或相关专业数据结构课程教材，也可作为面向对象程序设计课程或C++程序设计实践课程的教材和参考书。
书籍目录
第一章 绪论/l 1.1 问题求解/1 1.1.1问题/2 1.1.2问题的分析/2 1.1.3算法的选择/3 1.1.4解的精化/4 1.2 数据结构/4 1.3 算法/6 l.3.1算法的设计/6 1.3.2算法的分析/7 1.4 抽象数据类型/9 1.5 程序设计方法和语言/11 小结/12 习题/12第二章 C++与面向对象初步/13 2.1 C++语言对c的基本扩充/13 2.1.1注释/13 2.1.2函数原型说明/14 2.1.3引用和引用参数/14 2.1.4重载/16 2.1.5缺省参数/16 2.1.6变量说明/17 2.1.7输入和输出/17 2.1.8动态存储分配/17 2.1.9类型定义/18 2.1.10强制类型转换/18 2.2 对象和类/18 2.3 类的界面描述和实现/22 2.3.1类的数据域/24 2.3.2对象的行为——成员函数/24 2.3.3运算符作为成员函数/25 2.3.4用构造函数进行实例的初始化/27 2.4 普通运算符和普通函数/31 2.4.1普通运算符/31 2.4.2普通函数/33 2.4.3输入和输出/33 2.5 类的合成、继承和多态性/36 2.5.1合成/36 2.5.2继承/38 2.5.3多态性/39 小结/40 习题/42第三章 字符串二—数据封装技术/44 3.1 C语言的字符和字符串/44 3.2 字符串数据抽象的描述和实现/46 3.2.1字符串类的定义/47 3.2.2构造函数的定义/49 3.2.3析构函数/52 3.2.4基本成员函数的实现/53 3.2.5比较运算符/57 3.2.6串连接/59 3.2.7输入和输出/60 3.3子串/62 3.4 模式匹配/67 3.4.1简单字符串匹配/69 3.4.2 Knuth-Mords-Pratt模式匹配算法/72 3.4.3 Bovermore符串匹配算法/76 小结/80 习题/80第四章 向量——类的重用技术/83 4.1 模板类/84 4.2 向量的实现/86 4.3 定界向量和枚举向量——继承方式的重用/90 4.3.1定界向量/90 4.3.2枚举向量/94 4.4 排序向量和矩阵——舍成方式的重用/96 4.4.1排序向量和二分法检索/96 4.4.2矩阵/100 4.5 向量遍历器/103 4.5.1遍历器的抽象/103 4.5.2向量遍历器/105 4.6 向量的排序一模板函数/110 4.6.1插入排序/110 4.6.2起泡排序/112 4.6.3选择排序/113 4.6.4快速排序算法/114 4.7 继承和多态的若干讨论/l16 4.7.1父类与子类/116 4.7.2静态类型和动态类型/117 4.7.3框架和框架类/118 4.7.4遮蔽和虚函数/118 4.7.5虚遮蔽和非虚遮蔽/119 4.7.6两类继承/120 4.7.7多态的主要形式/121 4.7.8参数多态性——归约/121 4.7.9切割问题/123小结/125习题/125第五章 动态数据结构一链表/128 5.1 单链表的定义/128 5.1.1表类/128 5.1.2链类/130 5.2 单链表的实现/131 5.2.I链类的实现/131 5.2.2表类的实现/133 5.3 表遍历器/136 5.3.1表遍历器类/136 5.3.2表遍历器类的实现/138 5.4 表的应用：多项式处理/142 5.4.1项类/143 5.4.2多项式类/145 5.5 排序表“/148 5.5.1排序表类/148 5.5.2排序表类的实现/148 5.5.3排序表的应用——表插入排序/149 5.6 其他链表/150 5.6.1 自组织表/150 5.6.2双端表/152 5.6-3循环表/154 5.6.4双链表/155 5.7 可利用空间表/155小结/157习题/159第六章 栈和队列/161 6.1 抽象类栈和队列161 6.2 栈的实现/162 6.2.1栈的向量实现/163 6.2.2栈的链表实现/165 6.3栈的应用——表达式计算/167 6.3.1、后缀表达式的求值/167 6.3.2中缀表达式到后缀表达式 的转换/170 6.4 队列的实现/172 6.4.1队列的向量实现/172 6.4.2队列的链表实现/174 6.5 队列的应用——农夫过河问题/177小结/181习题/181第七章 树和二叉树/184 7.1 基本概念/185 7.1.1树/185 7.1.2二叉树/187 7.1.3树与二叉树的关系/190 7.2 二叉树的实现/191 7.2.1二叉树结点类/191 7.2.2基本二叉树类/193 7.2.3可构造二叉树类/195 7.3 二叉树的周游/197 7.3.1周游的递归实现/197 7.3.2通过遍历器实现周游/199 7.3.3前序周游器类/199 7.3.4中序周游器类/202 7.3.5后序周游器类/203 7.3.6层次周游算法(按宽度方向周游)/205 7.4 二叉树的向量表示/207 7.4.1二叉树向量表示的一种基本方法/207 7.4.2记录结构信息的二叉树向量表示/208 7.5 二叉排序树/209 7.6 平衡的二叉排序树/214 7.6.1AVL树上的操作/215 7.6.2AVL树的设计与实现/218 7.7 二叉树的应用——哈夫曼树/225小、结/228习题/228第八章 优先队列/23l 8.1 优先队列的抽象/231 8.2 堆/234 8.3 堆排序/238 8.4 斜堆/240 8.5 离散事件模拟/244 8.5.1模拟类的结构/246 8.5.2冰淇淋店的模拟/248 8.5.3随机数/251小结/253习题/253第九章 集合与字典/256 9.1 集合及其运算/256 9.1.1集合运算/257 9.1.2集合类/258 9.2 位向量集合/259 9.2.1位向量/260 9.2.2位向量集合/266 9.2.3字符集合/269 9.2.4字符集类的应用——将字符串分解为单词/270 9.3 集合的表实现/273 9.4 关联与字典/275 9.5 字典的关联表实现/278 9.6 字典的应用/281 9.6.1稀疏矩阵/281 9.6.2排序字典/284 9.6.3索引的实现/285小结/287习题/289 第十章散列结构/291 10.1散列结构/291 10.2散列函数/295 10.3开地址散列向量/297 10.4桶散列——用桶解决碰撞/300 IO.4.桶散列的抽象模板类/301 10.4.2用树作为桶的实现/302 10.4.3桶散列结构操作时间的分析/304lO.5桶散列结构的遍历器/30510.6用散列表实现集合/307 10.6.1应用——拼写检查器/30910.7用桶散列表实现字典/311小结/313习题/314第十一章 图/316 11.1 基本概念/316 11.2 图的邻接矩阵表示和Warshall算法/318 11.2.1图的邻接矩阵表示/318 Il.2.2图结点的可达性问题/318 11.3 邻接表方式的图表示和深度优先搜索/320 11.3.1邻接表表示中的结点类/321 11.3.2用深度优先方式求解可达性问题/322 11.4 带权图的矩阵表示和Floyd算法/324 11.4.1带权图的邻接矩阵/325 11.4.2带权图最短路径问题Floyd算法/325 11.5 带权图的邻接表表示与Dijkstra算法/327 11.5.1带权图的邻接表表示/327 11.5.2从一个结点出发的最短路径和Dijkstra算法/328 11.6 连通性、带权连通无向图与最小生成树/330 11.7有限自动机/333 11.8拓扑排序}/336小结/338习题/339第十二章 文件/342 12.1 外存、文件及其问题/342 12.1.1外存储器的特点与信息组织/342 12.1.2文件基本结构和操作/344 12.1.3文件与字典/345 12.1.4文件组织/346 12.2 C++的字符流文件及其操作/347 12.3 归并排序/352 12.4 文件的随机访问/356 12.5 文件索引结构/359 12.5.1索引向量/359 12.5.2树形索引结构/360 12.5.3 B树/361 12.5.4 B+树/364 12.6 树索引文件的实现/367小结/369习题/369附录/371 附录A 主要抽象数据类及其相互关系/371 附录B Borland C++集成开发环境使用入门/375 附录C“多叉路口的交通管理系统”上机报告/387
前言
本书是一本系统介绍数据结构的教材。在本书的论述过程中会反复联系到计算机领域的许多重要问题，包括问题求解，算法的分析与设计、抽象数据类型、程序设计方法、程序设计语言等内容，根据目前计算机科学发展的情况，本书采用面向对象的思想组织与课程有关的内容，运用C++语言作为数据结构和算法的描述语言，其目的是为了保证本书的先进性和适用性。 数据结构的一般讨论并不依赖于具体的语言，然而，在具体问题求解时，使用什么语言描述数据结构会在很大程度上影响程序设计者的思维方式和方法，选择一种实用的程序语言作为工作语言，有利于使讨论更面向实际应用，使参加课程学习的学生不仅可以掌握数据结构的抽象概念和性质，也有助于了解实现的思想和方法。 由于程序设计语言的发展，适合用来讨论数据结构的语言越来越多，今天国际上新的数据结构教材已经不再用伪语言作为工具了，随着面向对象方法的广泛应用，许多学校已经把C++语言定为学习计算机的第一种程序设计语言，越来越多的教材采用C++作为数据结构的教学语言。 在本书中，不仅讨论了抽象的数据结构，而且讨论了各种数据结构的不同实现方式并对它们进行了比较，从中可以看到不同数据结构的相互关系，包括结构上的（逻辑）关系和实现上的（表示）关系。采用C++语言和面向对象的方法讲解数据结构，对这些关系的讨论提供了有力的工具。 由于C++语言的一些优点，特别是它的模板机制，使我们可以比较清晰地讨论具有类型参数的数据结构。例如，我们实现的不是整数的堆栈，也不是字符串的堆栈，而是一般的具有类型参数的堆栈。一个实现可以满足各种程序对于堆栈的需要。这样学习的数据结构不仅更接近那种抽象概念上的数据结构，同时也可以直接用到不同类型对象的相同计算过程中去。 本书的讨论力图反映计算机科学的最新发展，用面向对象的方法组织数据结构的主要内容，以抽象数据类型的方式定义各种结构的用户界面，以时间和空间开销作为评价各种结构使用好坏的主要标准，从简到繁，系统地介绍各种常用的数据结构，强调不同结构之间的联系。书中采用C++语言描述各种类的界面和实现。把面向对象的程序设计方法与数据结构的主要原理紧密结合起来，讲解过程中还插入大量实例。读者通过本书的学习不仅能掌握数据结构的基本原理和基本方法，同时可以把所学的知识用于实际问题求解的过程之中。
章节摘录
另一种常用的算法设计方法称为“分治法”，其基本思想是：把一个规模较大的问题分成两个或多个较小的与原问题相似的子问题。首先对子问题进行求解，然后设法把子问题的解合并起来，得出整个问题的解，即对问题分而治之。如果一个子问题的规模仍然比较大，不能很容易地求得解，就可以对这个子问题重复地应用分治策略。 “二分法检索”就是用分治策略的典型例子。如果要在一个整数的有序数组（可以假设元素按增序排列）中找一个数，要求查出这个数在这个数组里的位置，二分法检索采用的方法是先找到数组中居于中间位置的元素，将该元素与所找数字进行比较，如果所查数字比较小，那么它一定不会出现在中间元素的右边，下面只需在左半个数组中检索。反过来，若所查数字较大，则不必在左半个数组中继续寻找，只需在右半个数组中检索。这样，通过一次比较就能够排除掉一半元素。再做下去，只要对剩下的半个数组重复使用同样方式，又可以再排除掉四分之一的元素，如此重复若干次就能很快确定整数的存在与否，并确定如果存在时它在什么位置。 还有一类常用算法被称为“回溯法”。有一些问题，只能通过彻底搜索所有可能情况寻找一个满足某些预定条件的最优解。由于彻底搜索的运算量通常非常大，往往大到使用计算机也不能在合理时间内得到解。回溯算法是处理这类问题的一个方法，基本思想是一步一步向前试探，当有多种选择时可以任意选择一种，只要可行（或暂时没有失败）就继续向前，一旦发现问题或失败就后退，回到上一步重新选择，借助于回溯技巧和中间判断，常常可以大大地减少搜索时间。常见的迷宫问题以及八皇后问题都可以用回溯方法来解决。 除上面提到的几种典型方法外，常用的算法设计方法还有“动态规划”、“局部搜索”和“分支限界”等。 本书在讨论数据结构的同时，自然涉及与数据结构相关的许多算法，掌握这些算法的设计方法和共性，对于提高程序设计的水平是十分重要的。