热搜关键词: 手机硬件物联网芯片封装C语言

pdf

数据结构、算法与应用(原书第2版) C++语言描述

  • 1星
  • 2022-09-18
  • 215.81MB
  • 需要1积分
  • 2次下载
  • favicon收藏
  • rep举报
  • free评论
标签: 算法

算法

数据结构

数据结构

《数据结构、算法与应用——C++语言描述》是享有盛誉的数据结构教科书的第2版。它完整地包含了基本数据结构的内容,是CS2课程的理想用书。作者Sartaj  Sahni通过循循善诱的讲解、直观具体的讨论和基于现实的应用,让读者轻松、愉快地学习。新版书着重利用标准模板库(STL),把书中开发的数据结构和算法与相应的STL实现方法相互关联。本书还增加了很多新的实例和练习题。

书中的应用实例是它的特色。Sahni博士为每一个数据结构和算法都提供了若干个应用实例,涉及排序、压缩编码和图像处理等多个方面。这些实例把概念和应用结合在一起,使理论与实践统一,从而让概念容易理解,使学生增加学习动力和兴趣。

本书采用的实用教学方法,不仅充实了理论概念,而且大量的习题让学生有了实践机会(书中有800多道练习题,包括理解题和简单的编程题和工程设计题)。除此之外,本书的配套网站上包含书中的所有程序、示例数据、运行结果、部分练习的解答和带有结果的示例测试。

出版者的话

译者序

前言

第一部分 预备知识

第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

15.1 AVL树  360

15.1.1 定义  360

15.1.2 AVL树的高度  361

15.1.3 AVL树的描述  361

15.1.4 AVL搜索树的搜索  361

15.1.5 AVL搜索树的插入  361

15.1.6 AVL搜索树的删除  364

15.2 红-黑树  367

15.2.1 基本概念  367

15.2.2 红-黑树的描述  368

15.2.3 红-黑树的搜索  368

15.2.4 红-黑树的插入  368

15.2.5 红-黑树的删除  371

15.2.6 实现细节的考虑及复杂性分析  374

15.3 分裂树  376

15.3.1 介绍  376

15.3.2 分裂树的操作  376

15.3.3 折算复杂性  378

15.4 B-树  379

15.4.1 索引顺序访问方法  379

15.4.2 m叉搜索树  380

15.4.3 m阶B-树  381

15.4.4 B-树的高度  382

15.4.5 B-树的搜索  382

15.4.6 B-树的插入  382

15.4.7 B-树的删除  384

15.4.8 节点结构  387

15.5 参考及推荐读物  389

第16章 图  390

16.1 基本概念  390

16.2 应用和更多的概念  391

16.3 特性  394

16.4 抽象数据类型graph  395

16.5 无权图的描述  396

16.5.1 邻接矩阵  396

16.5.2 邻接链表  397

16.5.3 邻接数组  398

16.6 加权图的描述  400

16.7 类实现  400

16.7.1 不同的类  400

16.7.2 邻接矩阵类  401

16.7.3 扩充chain类  405

16.7.4 链表类  405

16.8 图的遍历  407

16.8.1 广度优先搜索  407

16.8.2 广度优先搜索的实现  408

16.8.3 方法graph::bfs的复杂性分析  409

16.8.4 深度优先搜索  410

16.8.5 深度优先搜索的实现  411

16.8.6 方法graph::dfs的复杂性分析  412

16.9 应用  412

16.9.1 寻找一条路径  412

16.9.2 连通图及其构成  414

16.9.3 生成树  415

第三部分 算法设计方法

第17章 贪婪算法  420

17.1 最优化问题  420

17.2 贪婪算法思想  421

17.3 应用  424

17.3.1 货箱装载  424

17.3.2 0/1背包问题  425

17.3.3 拓扑排序  427

17.3.4 二分覆盖  430

17.3.5 单源最短路径  433

17.3.6 最小成本生成树  436

17.4 参考及推荐读物  445

第18章 分而治之  446

18.1 算法思想  446

18.2 应用  453

18.2.1 残缺棋盘  453

18.2.2 归并排序  455

18.2.3 快速排序  459

18.2.4 选择  464

18.2.5 相距最近的点对  466

18.3 解递归方程  474

18.4 复杂度的下限  475

18.4.1 最小最大问题的下限  476

18.4.2 排序算法的下限  477

第19章 动态规划  479

19.1 算法思想  479

19.2 应用  481

19.2.1 0/1背包问题  481

19.2.2 矩阵乘法链  484

19.2.3 所有顶点对之间的最短路径  489

19.2.4 带有负值的单源最短路径  492

19.2.5 网组的无交叉子集  496

19.3 参考及推荐读物  501

第20章 回溯法  502

20.1 算法思想  502

20.2 应用  506

20.2.1 货箱装载  506

20.2.2 0/1背包问题  512

20.2.3 最大完备子图  515

20.2.4 旅行商问题  517

20.2.5 电路板排列  519

第21章 分支定界  525

21.1 算法思想  525

21.2 应用  528

21.2.1 货箱装载  528

21.2.2 0/1背包问题  535

21.2.3 最大完备子图  536

21.2.4 旅行商问题  538

21.2.5 电路板排列  541

推荐帖子 最新更新时间:2022-09-29 08:09

DSP TMS320C6000基础学习——体系结构
主要内容 1. CPU架构 一幅图片搞定 2. C6000基本指令集 在“DSP TMS320C6000基础学习(1)”中已经说过:SOP是大部分DSP算法的关键单元。C6000的寄存器包括A,B两组。 我们将看看下面的表达式通过DSP指令是怎么一步步实现的, Y=∑an*xn withn = 1...N (1)an*xn乘法实现,DSP中有专门的硬件乘法模块
Aguilera DSP 与 ARM 处理器
石英晶体振荡器的输出模式详细介绍
       我们在选择和购买石英晶体振荡器时,或者在看厂商所提供的晶振规格书时,都会有输出模式(Output Type)或输出波形这个指标。经常看到的输出模式有CMOS、TTL、Sine Wave等等,这些输出模式代表的是什么意思呢?我们在选购时,究竟又该如何正确选择呢?下面带领大家去了解一下晶体振荡器的各种输出模式。        晶振各输出模式的定义 晶振常用的输出模式主要包括:
fish001 模拟与混合信号
变压器驱动半桥
  图(01)是Unitrode公司(已被德州仪器公司并购)生产的UC1525A(与UC2535A、UC3525A相同,三个型号仅工作温度范围不同)开关电源控制芯片用变压器驱动半桥的电路。图中Q1和Q2为功率开关MOS管,T1为驱动变压器,T2为功率输出的主变压器。             图(01)   图(01)中我们见到驱动变压器T1具有两个次级,反相驱动两个功率开关MOS管Q1和Q
maychang 电源技术
答题闯关:逛MPS芯云展厅,闯过三关有好礼
MPS芯云展厅的正确的打开方式(点此逛>>MPS芯云展厅) (传说好多人找不到展区入口,以下展示了,个人感觉浏览比较方便的途径)     完成三个任务,即视为闯关成功,即有机会赢取帖子下方的精美礼品一份。   活动时间:即日起——5月16日 活动内容: 第一关:点此逛>>MPS芯云展厅 ,进入大功率电源转换区,找到如下问题的答案: 下列
EEWORLD社区 电源技术
MX1081 + 庆科Wifi库函数手册
概览通过阅读头文件: #ifndef __FILE_H__ #define __FILE_H__ #include "stdlib.h" #include "string.h" #include "mxchipWNet_TypeDef.h" #include "stm32f2xx.h" #define AF_INET 2 #define SOCK_STREAM 1 #define SOCK_
cl17726 RF/无线
STM8 最小开发板/核心板 STM8S003F3P6开发与设计效果
STM8S核心板 亮点:   本开发板采用MicroUSB线取电,与智能手机数据线兼容,数据线简单易得,而非USB MINI线取电, USB MINI线不好找到,已经逐渐淘汰,这是本模块区别于其他的家产品的重要特点 。   超低的价格,人性化的设计,全套的资料,让您省钱,省时,省力,省心!STM8S核心板 主要特点:1. 使用STM8S003F3P6为主控IC。2. 可以用板子上的2.54排针取电
hzeeng RF/无线

评论

登录/注册

意见反馈

求资源

回顶部
查找数据手册?

EEWorld Datasheet 技术支持

热门活动

相关视频

可能感兴趣器件

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版 版权声明

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2022 EEWORLD.com.cn, Inc. All rights reserved
×