基本信息出版社：清华大学出版社
页码：401 页
出版日期：2009年01月
ISBN：7302191794/9787302191797
条形码：9787302191797
版本：第1版
装帧：平装
开本：16
正文语种：中文
丛书名：国外计算机科学经典教材

内容简介 这是一本适合于学生的C++数据结构指南，它基于现代软件发展的现实和职业程序员的需求。《C++类和数据结构》首先从类的全面介绍入手，提供学生成功使用数据结构所需的基础知识。接下来介绍了创建数据结构的方法，包括链表和可扩展/收缩的动态数组。解释了时间复杂度对执行速度的影响方式，帮助程序员理解关键性能之间的权衡考虑。然后以这些为基础，从散列表到二叉搜索树，详细介绍了每一种常见的数据结构。《C++类和数据结构》还详细设计了各种概念性的解释，以帮助程序员使用任何现代程序语言。
《C++类和数据结构》可作为计算机类专业或信息类相关专业的本科或专科教材，也可供从事计算机工程与应用工作的科技工作者参考。
作者简介 Jeffrey S. Childs，先生拥有美国扬斯敦州立大学计算机科学专业的学士学位以及肯特州立大学的计算机科学硕士和博士学位。他致力于图像高斯分解的研究，撰写并发表了多篇该领域的论文。他开发了Quickstep算法，该算法在时间复杂度上大大优于现有的高斯分解算法。在过去的9年中，他一直在讲授数据结构课程。此外，他还从事数据结构的研究，在基于客户教学法设计、内存管理以及特定数据结构设计等领域都有所突破。目前，Jeffrey S.Childs博士是美国宾州克莱瑞恩大学的终身教授。
编辑推荐 《C++类和数据结构》特色
◆为每个关键的数据结构概念提供了清晰易懂的解释
◆书中示例的设计综合考虑速度、内存使用、可靠性和程序员方便性等诸方面的问题
◆每章后面还提供相关的练习，解决程序员实际编程过程中所面临的富有针对性的问题
◆所有的例子都使用Visual C++ 2005编译和测试，并且可以在Microsoft免费的Visual Studio 2005 Express Edition上运行。
目录
第1章 结构和类1
1.1 结构1
1.2 类的基本概念6
1.3 类的实现9
1.4 类的测试17
1.5 将函数定义放在类定义中18
1.6 类的注释20
1.7 结构和类之间的区别21
1.8 小结21
1.9 练习22

第2章 重载运算符、类模板和抽象25
2.1 重载运算符25
2.2 在Checkbook类中使用Check结构31
2.3 类模板34
2.4 类和抽象42
2.5 小结45
2.6 练习45

第3章 类的更多内容51
3.1 const限定符51
3.2 构造函数53
3.3 类的修改57
3.4 修改Checkbook类保存支票历史记录57
3.5 小结67
3.6 练习68

第4章 指针和动态数组69
4.1 指针69
4.2 [ ]运算符75
4.3 动态分配内存77
4.4 动态数组79
4.5 delete操作符80
4.6 对象指针83
4.7 堆内存耗尽84
4.8 可调数组86
4.9 小结88
4.10 练习89

第5章 Array类93
5.1 Array类模板93
5.2 使用Array类103
5.3 析构函数106
5.4 复制构造函数107
5.5 重载赋值运算符函数113
5.6 示例118
5.7 Array类的优缺点121
5.8 标准模板库122
5.9 小结122
5.10 练习123

第6章 面向对象编程简介125
6.1 组合125
6.2 继承129
6.3 多态137
6.4 小结144
6.5 练习144

第7章 生成数据结构的方法147
7.1 在数据结构中使用数组147
7.2 链式结构简介151
7.3 链表编码153
7.3.1 链表代码基础153
7.3.2 在链表中搜索一个肯定存在的值154
7.3.3 在链表中搜索可能不存在的值157
7.3.4 在链表的表头插入一个结点159
7.3.5 在链表中间插入一个结点161
7.3.6 从链表中删除一个包含链表中某个值的结点164
7.3.7 使用header结点简化代码166
7.3.8 删除找到包含某值的结点166
7.4 数组和链表的对比167
7.4.1 数组和链表在速度上的比较167
7.4.2 数组和链表在内存浪费上的比较168
7.4.3 浪费内存分析171
7.5 小结174
7.6 练习175

第8章 栈和队列177
8.1 栈ADT177
8.2 栈的数组实现178
8.3 栈的链表实现184
8.4 队列ADT184
8.5 队列的链表实现184
8.6 队列的其他链表实现193
8.7 队列的数组实现194
8.8 小结202
8.9 练习202

第9章 时间复杂度简介211
9.1 时间复杂度基础213
9.2 常量阶时间复杂度222
9.3 大O表示法223
9.4 对数阶时间复杂度224
9.5 折半搜索算法227
9.6 计算机速度：它来源于什么地方231
9.7 数据结构函数的时间复杂度232
9.8 数组扩展和收缩的平摊分析232
9.9 小结236
9.10 练习237

第10章 链表作为数据结构239
10.1 列表ADT239
10.2 在信息记录中使用关键码值240
10.3 链表实现240
10.3.1 链表说明文件241
10.3.2 链表实现文件244
10.4 其他实现255
10.5 小结259
10.6 练习260

第11章 散列表263
11.1 散列表ADT263
11.2 散列函数和散列表设计263
11.3 散列表的实现问题269
11.4 函数指针271
11.5 散列表实现272
11.6 使用散列表实现277
11.7 双向链表的散列表实现279
11.7.1 实现问题283
11.7.2 DoublyLinkedList类的说明文件284
11.7.3 DoublyLinkedList类的实现文件287
11.8 小结297
11.9 练习297

第12章 优先级队列、树和堆299
12.1 优先级队列ADT299
12.2 优先级队列设计299
12.3 树301
12.4 堆306
12.5 使用单赋值交换314
12.6 优先级队列的堆实现（基于数组）316
12.7 链(内嵌)堆设计324
12.8 优先级队列的链(内嵌)堆实现329
12.9 小结336
12.10 练习337

第13章 递归339
13.1 递归阶乘函数339
13.2 递归函数编写原则344
13.3 在链式结构上使用递归345
13.4 递归函数的时间复杂度348
13.5 小结348
13.6 练习349

第14章 排序算法简介351
14.1 堆排序351
14.2 插入排序353
14.3 快速排序358
14.4 统计排序361
14.5 链表排序364
14.6 小结366
14.7 练习367

第15章 其他数据结构369
15.1 二叉搜索树369
15.2 BST和其他数据结构的对比380
15.3 图382
15.4 邻接矩阵和邻接表之间的对比391
15.5 小结393
15.6 练习394

附录A 如何编译及使用多文件程序397
A.1 Microsoft Visual Studio 2005 C++编译器397
A.2 编译和运行使用类的代码(不是类模板)397
A.3 编译和运行使用类模板的代码398
A.4 使用Microsoft Visual Studio 2005编写代码399
A.5 在Microsoft Visual Studio 2005中打开一个已创建的项目400
A.6 何种情况下事情会变乱400
A.7 UNIX编译器401
……
序言 数据结构是计算机专业的一门重要的基础课，在计算机科学各领域尤其是在软件设计和开发中发挥着举足轻重的作用。几乎所有的计算机软件系统，例如，操作系统、编辑工具和编译器等都要使用不同的数据结构。因此，数据结构是计算机专业的核心课程，是许多其他后续课程的重要基础。
目前，国内外有很多介绍数据结构方面的书籍，这些书籍都各具特色。但是大多数书籍都只注重于技术细节，缺乏详细的解释说明，没有数据结构基础知识的读者难以掌握理解。
考虑到上述事实，本书作者从自己教学的实际需求出发，根据自己对数据结构的理解，结合自己对数据结构的研究，考虑学生的学习需求，编写了本书。本书由易到难，不仅详细介绍了各种常见的数据结构，还提供了学习数据结构的基础知识。读者可以先阅读基础知识，再深入学习数据结构，通过这种安排方式，方便读者的学习，加强概念的理解。
本书采用当前流行的面向对象的C++语言来描述数据结构和算法，因为c++语言是程序员使用最广泛的语言。但是，本书还考虑到目前编程语言的多样性，在详细阐述数据结构概念时尽量避免使用与语言相关的术语解释，强调对概念的透彻理解，注重能力的培养，使读者能够使用其他编程语言编写出自己所需的数据结构。
通过本书的学习，读者不仅可以了解数据结构的基本概念和算法，还可以了解数据结构的应用场合；不仅可以使用数据结构，还可以根据需求设计自己的数据结构；不仅可以选择高效的算法，还可以了解这样做的原因。确切地说，本书内容全面丰富，语言精练简洁，示例和练习的实践性、针对性强，是一本优秀的数据结构教材。
文摘 第2～4行处理Mercedes结点是链表第一个结点的特殊情况。如果Mercedes结点是链表的第一个结点，那么由于第1行代码，ptr早已指向它。我们只需在第3行中将start指针指向链表中的下一个结点即可，因为这个结点将成为链表的新表头。然后，在第4行中，我们将第一个结点占用的内存空间释放。注意这种特殊情况对于链表中只有一个结点的情况也适用。在这种情况下，指针start将在第3行中被赋予NULL。
在第7行中，我们检查下一个结点是否拥有Mercedes，但是并没有将指针ptr指向这个结点。
插图：