更新时间：2024-09-21 15:06
全书采用面向对象的C++语言作为描述语言，以标准模板库的设计理念为描述和实现框架，内容丰富，叙述简明，理论与实践并重，每章设计有应用举例、数据结构与算法实验题，并为任课教师免费提供电子课件和课程实验用数据。
数据结构（STL框架）
普通高等教育“十一五”国家级规划教材、国家精品课程主讲教材
作者：王晓东
定价：34.80元
印次：1-2
ISBN：9787302203933
出版日期：2009.09.01
印刷日期：2011.01.17
本书以ACM和IEEE/CS Computing Curricula 2005课程体系以及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中制定的关于数据结构和算法设计与分析的知识结构和体系为依据，以基本数据结构和抽象数据类型为知识单元而编写。本书一个明显的特色是在标准模板库 (Standard Template Library）框架下描述数据结构的设计思想和实现方法，使读者循序渐进地理解数据抽象，面向对象设计方法和泛型算法设计三位一体的面向高层次的现代化软件设计风格。全书共分16章，涵盖 CC2005 课程体系中有关算法与数据结构、知识结构和体系的重要内容，包括算法与数据结构引论、向量、双端队列、表、栈和队列、排序与选择、树、二叉搜索树、平衡搜索树、集合、映射、堆与优先队列、散列、并查集、图与相关算法。
本书可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业数据结构课程教材，也适合工程技术人员和自学者学习参考。
第1章 算法与数据结构引论1
1.1 算法及其复杂性的概念1
1.1.1 算法与程序1
1.1.2 算法复杂性的概念1
1.1.3 算法复杂性的渐近性态2
1.2 数据结构与抽象数据类型3
1.3 用C++描述数据结构与算法4
1.3.1 指针和引用4
1.3.2 函数与参数传递4
1.3.3 C++的类5
1.3.4 类的对象6
1.3.5 模板6
1.3.6 动态存储分配7
1.4 递归8
1.5 标准模板库STL与泛型算法9
1.5.1 STL概述9
1.5.2 容器10
1.5.3 迭代器10
1.5.4 泛型算法11
1.5.5 函数对象14
1.6 应用举例19
1.6.1 用C++的类实现抽象数据类型19
1.6.2 顺序搜索与二分搜索算法的设计与分析23
1.6.3 递归算法的设计与分析25
习题126
数据结构与算法实验127
数据结构与算法实验题1.1 实系数复变多项式问题27
数据结构与算法实验题1.2 平面几何问题28
数据结构与算法实验题1.3 m进制数问题29
第2章 向量30
2.1 向量的基本概念30
2.2 抽象数据类型向量30
2.3 向量的迭代器30
2.4 向量的实现方法31
2.5 矩阵与多维向量35
2.6 高精度整数36
2.7 应用举例47
2.7.1 搜索公共元素问题47
2.7.2 同色方块识别问题48
2.7.3 全排列问题49
习题249
数据结构与算法实验250
数据结构与算法实验题2.1 前缀与后缀和问题50
数据结构与算法实验题2.2投票选举问题50
数据结构与算法实验题2.3稳定婚姻问题51
数据结构与算法实验题2.4凸多边形的三角剖分问题52
目录数据结构(STL框架)第3章双端队列53
3.1双端队列的基本概念53
3.2抽象数据类型双端队列53
3.3双端队列的实现方法54
3.4双端队列的迭代器60
3.5应用举例62
3.5.1双端队列的简单应用62
3.5.2简单多边形的凸壳问题63
习题365
数据结构与算法实验365
数据结构与算法实验题3.1排队购票问题65
第4章线性表68
4.1表的基本概念68
4.2用数组实现表69
4.3用指针实现表73
4.3.1用指针实现单链表的方法73
4.3.2单链表的迭代器75
4.4用间接寻址方法实现表79
4.4.1间接寻址方法的基本思想79
4.4.2间接寻址表的迭代器82
4.5用游标实现表84
4.5.1用游标实现表的基本思想84
4.5.2游标实现的表的迭代器89
4.6循环链表90
4.6.1实现单循环链表的基本思想90
4.6.2单循环链表的迭代器92
4.7双链表94
4.7.1实现双向循环链表的基本思想94
4.7.2双向循环链表的迭代器97
4.8应用举例101
4.8.1多项式函数101
4.8.2Josephus排列问题106
习题4107
数据结构与算法实验4108
数据结构与算法实验题4.1实系数一元多项式问题108
数据结构与算法实验题4.2Josephus排列问题1109
数据结构与算法实验题4.3向量分类问题110
数据结构与算法实验题4.4条形图轮廓问题110
数据结构与算法实验题4.5Josephus排列问题2111
第5章栈113
5.1栈的基本概念113
5.2栈的实现方法114
5.3应用举例115
5.3.1等价类划分问题115
5.3.2模拟递归问题117
5.3.3电路板布线问题119
习题5121
数据结构与算法实验5121
数据结构与算法实验题5.1车皮编序问题121
数据结构与算法实验题5.2单柱Hanoi塔问题122
数据结构与算法实验题5.3多栈模拟问题123
数据结构与算法实验题5.4亲兄弟问题124
第6章队列125
6.1队列的基本概念125
6.2队列的实现方法125
6.3应用举例126
6.3.1最优电路布线问题126
6.3.2和谐短信问题129
习题6130
数据结构与算法实验6130
数据结构与算法实验题6.1组队列问题130
数据结构与算法实验题6.2双栈队列问题131
数据结构与算法实验题6.3猴子分桃问题132
数据结构与算法实验题6.4逆序表问题132
第7章排序与选择134
7.1简单排序算法134
7.1.1冒泡排序算法134
7.1.2插入排序算法135
7.1.3选择排序算法136
7.1.4简单排序算法的计算复杂性136
7.2快速排序算法137
7.2.1算法基本思想及实现137
7.2.2算法性能分析139
7.2.3随机快速排序算法139
7.3合并排序算法140
7.3.1算法基本思想及实现140
7.3.2消除递归141
7.3.3自然合并排序算法141
7.4链表排序与索引排序算法142
7.4.1链表排序算法142
7.4.2索引排序算法149
7.5线性时间排序算法151
7.5.1计数排序算法151
7.5.2桶排序算法152
7.6中位数与第k小元素152
7.6.1平均情况下的线性时间选择算法153
7.6.2最坏情况下的线性时间选择算法154
7.7泛型排序算法156
7.7.1排序算法的泛化方法156
7.7.2泛型合并排序算法158
7.7.3泛型快速排序算法159
7.7.4泛型选择算法160
7.8应用举例161
7.8.1区间覆盖问题161
7.8.2输油管道问题161
习题7162
数据结构与算法实验7163
数据结构与算法实验题7.1交换排序问题163
数据结构与算法实验题7.2脱氧核糖核酸排序问题163
数据结构与算法实验题7.3邮局选址问题164
数据结构与算法实验题7.4最优服务次序问题165
第8章树166
8.1树的定义166
8.2树的遍历168
8.3树的表示法170
8.3.1父结点数组表示法170
8.3.2儿子链表表示法170
8.3.3左儿子右兄弟表示法171
8.4二叉树的基本概念171
8.5二叉树的运算173
8.6二叉树的实现174
8.6.1二叉树的顺序存储结构174
8.6.2二叉树的结点度表示法175
8.6.3用指针实现二叉树176
8.7线索二叉树179
8.8应用举例--信号增强装置布局问题181
习题8184
数据结构与算法实验8185
数据结构与算法实验题8.1层序列表问题185
数据结构与算法实验题8.2最近公共祖先问题186
数据结构与算法实验题8.3子树问题187
数据结构与算法实验题8.4同构二叉树问题187
数据结构与算法实验题8.5后序中序遍历问题188
第9章二叉搜索树189
9.1有序集与二叉搜索树189
9.1.1抽象数据类型字典189
9.1.2用数组实现字典189
9.1.3二叉搜索树的基本概念190
9.2实现二叉搜索树190
9.3二叉搜索树的迭代器199
9.4二叉搜索树的效率205
9.5应用举例--条形图统计问题207
习题9209
数据结构与算法实验9209
数据结构与算法实验题9.1装箱问题209
数据结构与算法实验题9.2电路板连线问题210
数据结构与算法实验题9.3字典问题211
第10章平衡搜索树212
10.1红黑树212
10.1.1红黑树的定义和性质212
10.1.2旋转变换213
10.1.3红黑树的插入运算与重平衡216
10.1.4红黑树的删除运算与重平衡218
10.2AVL树223
10.2.1AVL树的定义和性质223
10.2.2AVL树的插入运算与重平衡224
10.2.3AVL树的删除运算与重平衡226
10.3应用举例229
10.3.1条形图统计问题229
10.3.2动态选择问题230
10.3.3Josephus排列问题232
习题10233
数据结构与算法实验10234
数据结构与算法实验题10.1逆序计数问题234
数据结构与算法实验题10.2k后继问题234
数据结构与算法实验题10.3圆内相交弦问题235
数据结构与算法实验题10.4最小间隙问题236
数据结构与算法实验题10.5图形周长问题237
数据结构与算法实验题10.6动态选择问题237
第11章集合239
11.1集合的基本概念239
11.2用位向量实现集合240
11.3用平衡二叉搜索树实现集合246
11.3.1直接应用红黑树实现集合246
11.3.2平衡二叉搜索树的泛化247
11.3.3符合STL标准的集合252
11.4多重集合254
11.5泛型集合运算256
11.6应用举例259
11.6.1Eratosthenes筛法259
11.6.2子集和问题260
11.6.3拼写检查问题260
11.6.4软件产品数据库问题261
习题11262
数据结构与算法实验11263
数据结构与算法实验题11.1半数集问题263
数据结构与算法实验题11.2账单支付问题263
数据结构与算法实验题11.3张贴海报问题264
数据结构与算法实验题11.4三色棋游戏问题265
第12章映射266
12.1映射的基本概念266
12.2用平衡二叉搜索树实现映射266
12.2.1二叉搜索树的进一步泛化266
12.2.2符合STL标准的映射272
12.3多重映射274
12.4应用举例275
12.4.1种群分布统计问题275
12.4.2电子字典问题276
习题12278
数据结构与算法实验12278
数据结构与算法实验题12.1工作薪酬问题278
数据结构与算法实验题12.2扑克游戏智能分析问题279
数据结构与算法实验题12.3最优行驶路线问题280
数据结构与算法实验题12.4库存调整问题281
数据结构与算法实验题12.5双字符字频分析问题282
数据结构与算法实验题12.6英文词汇分析问题283
第13章散列285
13.1符号表285
13.2开散列286
13.3闭散列292
13.4散列函数的效率297
13.5重新散列298
13.6散列集299
13.6.1用散列表实现集合299
13.6.2用散列表实现多重集合300
13.7散列映射301
13.7.1开散列表的泛化301
13.7.2用散列表实现映射307
13.7.3用散列表实现多重映射308
13.8应用举例309
13.8.1字符串频率统计问题309
13.8.2拼写检查问题310
13.8.3种群分布统计问题311
13.8.4电子字典问题312
习题13313
数据结构与算法实验13313
数据结构与算法实验题13.1伪随机排列问题313
数据结构与算法实验题13.2字符串散列问题314
数据结构与算法实验题13.3英文文本分析问题314
数据结构与算法实验题13.4最长模式串问题315
第14章堆与优先队列316
14.1优先队列的基本概念316
14.2优先级树和堆316
14.3堆的顺序存储方式317
14.4堆的有关算法318
14.5堆的泛型算法323
14.6用堆实现优先队列326
14.7可并优先队列327
14.7.1左偏树的定义327
14.7.2用左偏树实现可并优先队列328
14.7.3泛化左偏树331
14.8应用举例332
14.8.1优先队列的比较模式332
14.8.2哈夫曼编码问题334
14.8.3活动安排问题337
习题14338
数据结构与算法实验14338
数据结构与算法实验题14.1区间相交问题338
数据结构与算法实验题14.2整数字典问题338
数据结构与算法实验题14.3最小权语言问题339
数据结构与算法实验题14.4二叉搜索堆问题339
数据结构与算法实验题14.5区间覆盖问题340
数据结构与算法实验题14.6批作业调度问题341
第15章并查集342
15.1并查集的基本概念342
15.2用父结点向量实现并查集343
15.3应用举例--离线最小值问题346
习题15347
数据结构与算法实验15348
数据结构与算法实验题15.1二进制方程问题348
数据结构与算法实验题15.2网络连通问题349
数据结构与算法实验题15.3朋友问题349
数据结构与算法实验题15.4等价类划分问题350
第16章图352
16.1图的基本概念352
16.2抽象数据类型图355
16.3图的表示法355
16.3.1邻接矩阵表示法355
16.3.2邻接表表示法356
16.3.3紧缩邻接表356
16.4用邻接矩阵实现图357
16.4.1用邻接矩阵实现图的方法357
16.4.2邻接矩阵图的顶点迭代器359
0.www.tup.tsinghua.edu.cn.2018-03-17
目录.清华大学出版社.2018-03-18