《数据结构算法与应用-C++语言描述》pdf电子书下载教程下载

注册登录

《数据结构算法与应用-C++语言描述》pdf电子书下载教程下载

格式:pdf
作者:(美)Sartaj Sahni
视频:无
¥3元
浏览次数:46次
上传时间:2017-09-25 16:02:02
版权说明:本书籍来源百度网盘,如侵犯你版权,请联系我们,我们将立即删除!
电话:15202182625,邮箱:527359484@qq.com,QQ:527359484
  • 图书详情

商品基本信息商品名称:数据结构、算法与应用C++语言描述(原书第2版)

作者:(美)Sartaj Sahni

市场价:79.00元

ISBN号:978-7-111-49600-7

版次:1-1

出版日期:2015-04-01

出版社:机械工业出版社

目录
Data Structures, Algorithms, and Applications in C++, Second Edition
出版者的话
译者序
前言
第一部分 预备知识
第1章 C++回顾 2
1.1 引言 2
1.2 函数与参数 3
1.2.1 传值参数 3
1.2.2 模板函数 4
1.2.3 引用参数 4
1.2.4 常量引用参数 5
1.2.5 返回值 5
1.2.6 重载函数 6
1.3 异常 7
1.3.1 抛出异常 7
1.3.2 处理异常 7
1.4 动态存储空间分配 9
1.4.1 操作符new 9
1.4.2 一维数组 9
1.4.3 异常处理 9
1.4.4 操作符delete 10
1.4.5 二维数组 10
1.5 自有数据类型 12
1.5.1 类currency 12
1.5.2 一种不同的描述方法 18
1.5.3 操作符重载 20
1.5.4 友元和保护性类成员 22
1.5.5 增加#ifndef、#define和#endif语句 23
1.6 异常类illegalParameterValue 24
1.7 递归函数 25
1.7.1 递归的数学函数 25
1.7.2 归纳 25
1.7.3 C++递归函数 26
1.8 标准模板库 30
1.9 测试与调试 32
1.9.1 什么是测试 32
1.9.2 测试数据的设计 34
1.9.3 调试 36
1.10 参考及推荐读物 37
第2章 程序性能分析 38
2.1 什么是程序性能 38
2.2 空间复杂度 39
2.2.1 空间复杂度的组成 39
2.2.2 举例 42
2.3 时间复杂度 44
2.3.1 时间复杂度的组成 44
2.3.2 操作计数 45
2.3.3 最好、最坏和平均操作计数 48
2.3.4 步数 53
第3章 渐近记法 64
3.1 引言 64
3.2 渐近记法 65
3.2.1 大Ο记法 65
3.2.2 渐近记法Ω和Θ 67
3.3 渐近数学(可选) 69
3.3.1 大O记法 69
3.3.2 Ω记法 71
3.3.3 Θ记法 72
3.3.4 小ο记法 73
3.3.5 特性 73
3.4 复杂度分析举例 75
3.5 实际复杂度 78
3.6 参考及推荐读物 80
第4章 性能测量 81
4.1 引言 81
4.2 选择实例的大小 82
4.3 设计测试数据 82
4.4 实验设计 82
4.5 高速缓存 87
4.5.1 简单计算机模型 87
4.5.2 缓存未命中对运行时间的影响 87
4.5.3 矩阵乘法 88
4.6 参考及推荐读物 90
第二部分 数据结构
第5章 线性表——数组描述 92
5.1 数据对象和数据结构 92
5.2 线性表数据结构 93
5.2.1 抽象数据类型linearList 94
5.2.2 抽象类linearList 94
5.3 数组描述 95
5.3.1 描述 95
5.3.2 变长一维数组 96
5.3.3 类arrayList 97
5.3.4 C++迭代器 102
5.3.5 arrayList的一个迭代器 103
5.4 vector的描述 107
5.5 在一个数组中实现的多重表 109
5.6 性能测量 111
5.7 参考及推荐读物 112
第6章 线性表——链式描述 113
6.1 单向链表 113
6.1.1 描述 113
6.1.2 结构chainNode 114
6.1.3 类chain 115
6.1.4 抽象数据类型linearList的扩充 121
6.1.5 类extendedChain 121
6.1.6 性能测量 122
6.2 循环链表和头节点 126
6.3 双向链表 128
6.4 链表用到的词汇表 129
6.5 应用 130
6.5.1 箱子排序 130
6.5.2 基数排序 134
6.5.3 凸包 135
6.5.4 并查集 137
第7章 数组和矩阵 146
7.1 数组 146
7.1.1 抽象数据类型 146
7.1.2 C++数组的索引 147
7.1.3 行主映射和列主映射 147
7.1.4 用数组的数组来描述 148
7.1.5 行主描述和列主描述 149
7.1.6 不规则二维数组 149
7.2 矩阵 151
7.2.1 定义和操作 151
7.2.2 类matrix 152
7.3 特殊矩阵 157
7.3.1 定义和应用 157
7.3.2 对角矩阵 158
7.3.3 三对角矩阵 159
7.3.4 三角矩阵 160
7.3.5 对称矩阵 161
7.4 稀疏矩阵 164
7.4.1 基本概念 164
7.4.2 用单个线性表描述 165
7.4.3 用多个线性表描述 170
7.4.4 性能测量 172
第8章 栈 175
8.1 定义和应用 175
8.2 抽象数据类型 177
8.3 数组描述 178
8.3.1 作为一个派生类实现 178
8.3.2 类arrayStack 179
8.3.3 性能测量 181
8.4 链表描述 182
8.4.1 类derivedLinkedStack 182
8.4.2 类linkedStack 183
8.4.3 性能测量 184
8.5 应用 184
8.5.1 括号匹配 184
8.5.2 汉诺塔 185
8.5.3 列车车厢重排 187
8.5.4 开关盒布线 191
8.5.5 离线等价类问题 193
8.5.6 迷宫老鼠 196
8.6 参考及推荐读物 204
第9章 队列 205
9.1 定义和应用 205
9.2 抽象数据类型 206
9.3 数组描述 207
9.3.1 描述 207
9.3.2 类arrayQueue 209
9.4 链表描述 212
9.5 应用 214
9.5.1 列车车厢重排 214
9.5.2 电路布线 217
9.5.3 图元识别 219
9.5.4 工厂仿真 222
9.6 参考及推荐读物 234
第10章 跳表和散列 235
10.1 字典 235
10.2 抽象数据类型 236
10.3 线性表描述 237
10.4 跳表表示(可选) 239
10.4.1 理想情况 239
10.4.2 插入和删除 241
10.4.3 级的分配 241
10.4.4 结构skipNode 242
10.4.5 类skipList 242
10.4.6 skipList方法的复杂度 246
10.5 散列表描述 246
10.5.1 理想散列 246
10.5.2 散列函数和散列表 248
10.5.3 线性探查 250
10.5.4 链式散列 255
10.6 一个应用——文本压缩 260
10.6.1 LZW压缩 260
10.6.2 LZW压缩的实现 261
10.6.3 LZW解压缩 264
10.6.4 LZW解压缩的实现 265
10.6.5 性能评价 268
10.7 参考及推荐读物 269
第11章 二叉树和其他树 270
11.1 树 270
11.2 二叉树 273
11.3 二叉树的特性 274
11.4 二叉树的描述 275
11.4.1 数组描述 275
11.4.2 链表描述 276
11.5 二叉树常用操作 277
11.6 二叉树遍历 277
11.7 抽象数据类型BinaryTree 281
11.8 类linkedBinaryTree 282
11.9 应用 285
11.9.1 设置信号放大器 285
11.9.2 并查集 288
11.10 参考及推荐读物 296
第12章 优先级队列 297
12.1 定义和应用 297
12.2 抽象数据类型 298
12.3 线性表 299
12.4 堆 299
12.4.1 定义 299
12.4.2 大根堆的插入 300
12.4.3 大根堆的删除 301
12.4.4 大根堆的初始化 301
12.4.5 类maxHeap 302
12.4.6 堆和STL 305
12.5 左高树 306
12.5.1 高度优先与宽度优先的最大及最小左高树 306
12.5.2 最大HBLT的插入 308
12.5.3 最大HBLT的删除 308
12.5.4 两棵最大HBLT的合并 308
12.5.5 初始化 309
12.5.6 类maxHblt 310
12.6 应用 313
12.6.1 堆排序 313
12.6.2 机器调度 314
12.6.3 霍夫曼编码 317
12.7 参考及推荐读物 322
第13章 竞赛树 323
13.1 赢者树和应用 323
13.2 抽象数据类型WinnerTree 326
13.3 赢者树的实现 327
13.3.1 表示 327
13.3.2 赢者树的初始化 328
13.3.3 重新组织比赛 328
13.3.4 类completeWinnerTree 328
13.4 输者树 329
13.5 应用 331
13.5.1 用最先适配法求解箱子装载问题 331
13.5.2 用相邻适配法求解箱子装载问题 335
13.6 参考及推荐读物 337
第14章 搜索树 338
14.1 定义 338
14.1.1 二叉搜索树 338
14.1.2 索引二叉搜索树 340
14.2 抽象数据类型 340
14.3 二叉搜索树的操作和实现 341
14.3.1 类binarySearchTree 341
14.3.2 搜索 342
14.3.3 插入 342
14.3.4 删除 343
14.3.5 二叉搜索树的高度 346
14.4 带有相同关键字元素的二叉搜索树 347
14.5 索引二叉搜索树 348
14.6 应用 349
14.6.1 直方图 349
14.6.2 箱子装载问题的最优匹配法 351
14.6.3 交叉分布 353
第15章 平衡搜索树 359

第16章 图 390

第三部分 算法设计方法
第17章 贪婪算法 420

第18章 分而治之 446

第19章 动态规划 479

第20章 回溯法 502

第21章 分支定界 525


内容简介    

本书共分三个部分。第一部分从第1章到第4章,旨在复习C++程序设计的概念以及程序性能的分析和测量方法。第二部分从第5章到第16章,研究数据结构,包括线性表、数组和矩阵、栈、队列、字典、二叉树、优先级队列、竞赛树、搜索树和图等。第三部分从第17章到第21章,研究常用算法,包括贪婪算法、分而治之算法、动态规划、回溯算法和分枝定界算法。本书有800多道练习题和50多个应用实例。内容广博,组织合理,论述清晰,循序渐进,而且对程序性能的分析和测量系统入微。本书不仅是数据结构和算法的经典教材,而且是计算机科学与工程领域的理想参考书。