高级搜索  |  搜索帮助
最近的浏览历史
购买此书的人还购买过
书  名:数据结构(STL框架)
  • 作  者: 王晓东
  • 出版时间: 2009-09-01
  • 出 版 社: 清华大学出版社
  • 字  数: 631 千字
  • 印  次: 1-2
  • 印  张: 26
  • 开  本: 16开
  • ISBN: 9787302203933
  • 装  帧: 平装
  • 定  价:¥34.80
电子书价:¥24.40 折扣:70折 节省:¥10.40 vip价:¥24.40 电子书大小:5.47M
配套资源下载:
  • 名称
  • 说明
  • 权限
  • 文件大小
  • 点击图标下载
  • 图书样章
  • 所有用户
  • 256K
共有商品评论0条 查看评论摘要
内容简介
  本书以ACM和IEEE/CS Computing Curricula 2005课程体系以及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中制定的关于数据结构和算法设计与分析的知识结构和体系为依据,以基本数据结构和抽象数据类型为知识单元而编写。本书一个明显的特色是在STL (Standard Template Library)框架下描述数据结构的设计思想和实现方法,使读者循序渐进地理解数据抽象,面向对象设计方法和泛型算法设计三位一体的面向高层次的现代化软件设计风格。全书共分16章,涵盖 CC2005 课程体系中有关算法与数据结构、知识结构和体系的重要内容,包括算法与数据结构引论、向量、双端队列、表、栈和队列、排序与选择、树、二叉搜索树、平衡搜索树、集合、映射、堆与优先队列、散列、并查集、图与相关算法。
全书采用面向对象的C++语言作为描述语言,以STL的设计理念为描述和实现框架,内容丰富,叙述简明,理论与实践并重,每章设计有应用举例、数据结构与算法实验题,并为任课教师免费提供电子课件和课程实验用数据。
本书可作为高等学校计算机、电子信息、信息与计算科学、信息管理与信息系统等专业数据结构课程教材,也适合工程技术人员和自学者学习参考。
前言
  计算机技术和计算机的应用技术已经成为信息社会的重要基础设施。高等教育中计算机学科的培养目标,教学计划和课程设置也随着领域的变化在不断地调整,巩固和完善。计算机科学是一种创造性思维活动,其教育必须面向设计。数据结构正是一门面向设计,且处于计算机学科核心地位的技术基础和主干必修课,是计算学科的九个主科目之一。它不仅是计算机科学教育后续课程的理论基础,而且还广泛地用于新兴的技术和研究领域。本书是在国家精品课程“算法与数据结构”的建设过程中,以ACM 和 IEEE/CS Computing Curricula 2005 课程体系及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中关于算法与数据结构的知识结构和体系为依据编写。数据结构课程的主要特点是既有严格的理论证明,又具有很强的构造性和应用性,因此本书围绕计算学科常用的基本数据结构和基本算法组织教学内容。在概念的编织上,贯穿学科中反复出现的12个基本概念。在内容的组织上,体现计算学科的新概括,融会为学科形态的理论、抽象和设计三个过程。本书的一个明显的特色是在STL (Standard Template Library)的框架下描述数据结构的设计思想和实现方法,使读者循序渐进地理解数据抽象、面向对象设计方法和泛型算法设计三位一体的面向高层次的现代化软件设计风格。全书共分16章。
第1章是算法与数据结构引论,介绍数据结构、抽象数据类型和算法等基本概念,并简要阐述了算法的计算复杂性和用面向对象的C++语言描述算法的方法。介绍了C++标准库中最重要的组成部分标准模板库STL以及与其相关的容器,泛型算法和迭代器等泛型数据结构和算法的基本概念。
第2~16章以抽象数据类型为主线索,以STL的设计理念为描述和实现框架,围绕计算学科中常用的基本数据结构组织内容。
第2~6章依次介绍基于序列的数据结构向量、双端队列、表、栈和队列。
第7章介绍在实际应用中常用的排序与选择算法。
第8章讨论反映层次关系的抽象数据类型树。
第9章的主题是二叉搜索树以及以有序集为基础的抽象数据类型字典的实现方法。
第10章平衡搜索树是第9章内容的延伸,主要从提升二叉搜索树效率的角度来考察搜索树的平衡性。
第11章和第12章讨论的集合和映射是STL中最有用的关联式容器。在这两章中详细讨论了它们的设计思想和实现方法。
第13章讨论散列技术及用散列技术实现符号表,集合和映射的方法。
第14章讨论堆与优先队列的实现方法。
第15章讨论以不相交集合为基础的抽象数据类型并查集及其实现方法。
第16章介绍非线性结构图及相关算法。
数据结构是一门理论性强,而且实践难度较大的专业基础课程。为了使学生在深刻理解课程内容的基础上,灵活运用所学的知识解决实际问题,在每个知识单元都特别设置了“应用举例”作为该知识单元的小结,以期通过本知识单元内容的具体应用来深化学生对学习内容的理解和实际应用的能力。另外每章末有难易适当的习题,并特别设计了数据结构与算法实验题,以强化实践环节,要求学生课后通过上机实验来完成。作者的教学实践表明,这类实验题对学生掌握课堂教学内容有很大帮助,效果非常好。作者还结合国家精品课程建设,建立了教学网站http://ds.fzu.edu.cn,欢迎广大读者访问教学网站,并提出宝贵意见。
数据结构(STL框架)在本书的编写过程中,得到了教育部高等学校计算机科学与技术教学指导委员会的关心和支持。福州大学和泉州师范学院“211工程”计算机与信息工程重点学科实验室为本书的编写提供了优良的设备和工作环境。在此谨向每一位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意!
由于作者的知识和写作水平有限,书稿虽几经修改,仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正。使本书在使用中不断得到改进,日臻完善。

作 者
2009年7月
目录
第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
数据结构与算法实验题3.2 循环向量的极值问题66
第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.2 Josephus排列问题106
习题4107
数据结构与算法实验4108
数据结构与算法实验题4.1 实系数一元多项式问题108
数据结构与算法实验题4.2 Josephus排列问题1109
数据结构与算法实验题4.3 向量分类问题110
数据结构与算法实验题4.4 条形图轮廓问题110
数据结构与算法实验题4.5 Josephus排列问题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 DNA排序问题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.2 AVL树223
10.2.1 AVL树的定义和性质223
10.2.2 AVL树的插入运算与重平衡224
10.2.3 AVL树的删除运算与重平衡226
10.3 应用举例229
10.3.1 条形图统计问题229
10.3.2 动态选择问题230
10.3.3 Josephus排列问题232
习题10233
数据结构与算法实验10234
数据结构与算法实验题10.1 逆序计数问题234
数据结构与算法实验题10.2 k后继问题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.1 Eratosthenes筛法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
16.5 用邻接表实现图360
16.5.1 用邻接表实现图的方法360
16.5.2 邻接表图的顶点迭代器362
16.6 用邻接矩阵实现赋权图362
16.6.1 用邻接矩阵实现赋权图的方法362
16.6.2 邻接矩阵赋权图的顶点迭代器365
16.7 用邻接表实现赋权图365
16.7.1 用邻接表实现赋权图的方法365
16.7.2 邻接表赋权图的顶点迭代器368
16.8 图的遍历搜索算法369
16.8.1 广度优先搜索369
16.8.2 深度优先搜索370
16.9 最短路径算法371
16.9.1 单源最短路算法371
16.9.2 Bellman-Ford最短路算法374
16.9.3 所有顶点对之间的最短路算法375
16.10 无圈有向图DAG376
16.10.1 拓扑排序376
16.10.2 DAG的最短路径378
16.10.3 DAG的最长路径379
16.10.4 DAG所有顶点对之间的最短路径379
16.11 最小支撑树380
16.11.1 最小支撑树的性质380
16.11.2 最小支撑树的Prim算法380
16.11.3 最小支撑树的Kruskal算法382
16.12 图匹配算法383
16.13 应用举例386
16.13.1 最长嵌套序列问题386
16.13.2 套汇问题388
习题16388
数据结构与算法实验16390
数据结构与算法实验题16.1 图的二着色问题390
数据结构与算法实验题16.2 有向赋权图中心问题390
数据结构与算法实验题16.3 最长简单路径问题391
数据结构与算法实验题16.4 计算机网络问题392
数据结构与算法实验题16.5 差分约束问题393
数据结构与算法实验题16.6 有截止时间的工作排序问题393
数据结构与算法实验题16.7 无向图的连通分支问题394
参考文献396
Copyright(C)清华大学出版社有限公司,All Rights Reserved 京ICP备10035462号 联系我们