数据结构学习指导与习题解答:C++语言版

《数据结构学习指导与习题解答(C++语言版)》由清华大学出版社出版。

数据结构是计算机专业的核心课程，是计算机软件开发和应用人员必备的专业基础。今天的大多数关于数据结构的图书都是大学教科书，而《数据结构学习指导与习题解答(C++语言版)》可用于自学，更适合与使用C++程序设计语言的数据结构方面的常规课程配合使用。
《数据结构学习指导与习题解答(C++语言版)》首先复习了C++的基础知识，然后介绍了数据结构的相关内容，包括递归、栈、队列、链表、表、树、二叉树、查找树、堆和优先级队列、排序。《数据结构学习指导与习题解答(C++语言版)》附录中列出了相关的参考资源，提供了必要的数学知识，并给出了一些算法和类的源代码实现。
《数据结构学习指导与习题解答(C++语言版)》包含大量的示例，有助于读者从中举一反三，深入学习数据结构方面的相关知识。在每一章末还提供了相关的复习题和问题，有利于学生巩固所学的知识，并且给出了所有复习题和问题的答案，为学生学习提供了方便。
《数据结构学习指导与习题解答(C++语言版)》内容简明扼要、结构组织合理、示例丰富，非常适合于高等院校计算机专业的学生阅读，对于从事计算机软件开发的人员，也将从《数据结构学习指导与习题解答(C++语言版)》中受益匪浅。
参加《数据结构学习指导与习题解答(C++语言版)》翻译的人员有陈宗斌、陈红霞、张景友、易小丽、陈婷、管学岗、王新彦、金惠敏、张海峰、徐晔、戴锋、张德福、张士华、张锁玲、杜明宗、高玉琢、王涛、申川、孙玲、李振国、高德杰、宫飞、侯经国、刘淑妮、张春林、李大成、程明、张路红、张淑芝、孙先国、刘冀得、梁永翔、张广东、郁琪琳、邵长凯、蒲书箴、潘曙光、刘瑞东、李军、焦敬俭等。
由于时间紧迫，加之译者水平有限，错误在所难免，恳请广大读者批评指正。

作者：（美国）哈伯德（JohnR.Hubbard）译者：陈宗斌等

第1章C++复习1
1.1标准C++程序设计语言1
1.2条件语句3
1.3运算符5
1.4迭代8
1.5函数10
1.6字符串12
1.7文件14
复习题15
练习题16
复习题答案18
练习题答案20

第2章指针与数组32
2.1指针32
2.2派生类型34
2.3引用35
2.4按引用传递35
2.5空指针异常37
2.6new和delete运算符38
2.7数组39
2.8动态数组40
2.9把数组传递给函数41
2.10多维数组42
复习题43
练习题44
复习题答案46
练习题答案47

第3章类60
3.1Point类60
3.2实例、隐式形参和this指针63
3.3编译类及其客户程序64
3.4友元函数68
3.5Line类68
3.6用于随机数的类71
3.7静态成员73
3.8复合75
3.9继承78
复习题81
练习题82
复习题答案85
练习题答案87

第4章递归98
4.1阶乘函数98
4.2跟踪递归调用99
4.3斐波纳契数列99
4.4二项式系数101
4.5欧几里得算法102
4.6正确性的归纳证明103
4.7递归算法的复杂度分析104
4.8动态程序设计105
4.9汉诺塔105
4.10相互递归107
复习题108
练习题108
复习题答案110
练习题答案111

第5章栈119
5.1stack接口119
5.2使用stack对象119
5.3栈的应用121
5.4消除递归124
5.5连续实现126
5.6链表实现129
复习题133
练习题134
复习题答案135
练习题答案136

第6章队列142
6.1queue接口142
6.2使用queue对象142
6.3队列的应用144
6.4连续实现149
6.5链表实现153
复习题155
练习题156
复习题答案157
练习题答案157

第7章链表164
7.1list接口164
7.2使用list对象165
7.3迭代器166
7.4应用168
7.5循环链表173
7.6有序链表176
7.7不受限制的Integer类177
7.8List类的实现183
复习题188
练习题189
复习题答案191
练习题答案192

第8章表200
8.1标准的pair类型200
8.2使用map类模板的应用202
8.3散列表207
8.4散列函数212
8.5单独串接215
复习题219
练习题219
复习题答案219
练习题答案220

第9章树224
9.1树的术语224
9.2决策树和转换图226
9.3树遍历算法230
9.4Tree类的接口231
9.5Tree类的实现234
复习题238
练习题240
复习题答案244
练习题答案245

第10章二叉树259
10.1定义259
10.2统计二叉树261
10.3完整二叉树262
10.4恒等、相等和同构263
10.5完全二叉树264
10.6树遍历266
10.7表达式树268
10.8森林270
10.9BinaryTree类的接口271
10.10BinaryTree类的实现274
复习题278
练习题279
复习题答案282
练习题答案283

第11章查找树291
11.1二叉查找树291
11.2二叉查找树的实现293
11.3二叉查找树的性能特征296
11.4AVL树297
复习题300
练习题300
复习题答案301
练习题答案301

第12章堆和优先级队列305
12.1堆305
12.2自然映射305
12.3插入到堆中307
12.4从堆中删除308
12.5优先级队列309
12.6使用priority_queue对象309
12.7使用堆实现PriorityQueue类模板311
12.8优先级队列的实现313
复习题318
练习题318
复习题答案319
练习题答案319

第13章排序322
13.1基础知识322
13.2冒泡排序323
13.3选择排序324
13.4插入排序325
13.5归并排序327
13.6快速排序330
13.7堆331
13.8堆排序332
13.9希尔排序337
13.10比较排序的速度限制338
复习题338
练习题338
复习题答案340
练习题答案340
附录A参考资料344
附录B必要的数学知识353
B.1下取整函数和上取整函数353
B.2对数353
B.3数学归纳法的第一定律354
B.4数学归纳法的第二定律355
B.5几何级数356
B.6求和公式357
B.7渐近复杂度等级357
B.8调和数358
B.9斯特灵公式360
B.10斐波纳契数字361
B.11黄金分割率361
B.12欧几里得算法363
附录C标准容器类365
C.1vector类模板365
C.2deque类模板372
C.3stack类模板372
C.4queue类模板372
C.5priority_queue类模板373
C.6list类模板374
C.7map类模板377
C.8set类模板379

附录D泛型算法382
附录E示例类417
E.1BinaryTree类417
E.2BinarySearchTree类425
E.3Card类427
E.4Concordance类430
E.5Date类432
E.6Deck类440
E.7Hand类441
E.8Hash函数结构模板442
E.9HashTable类模板442
E.10Line类445
E.11List类模板447
E.12Matrix类模板454
E.13OrderedList类456
E.14Person类456
E.15Point类460
E.16Polynomial类463
E.17PriorityQueue类模板470
E.18Purse类472
E.19Queue类474
E.20Random类476
E.21RandomLine类477
E.22RandomPoint类477
E.23Ratio类478
E.24Rational类481
E.25SelfOrganizingList类484
E.26Stack类模板484
E.27Tree类486