《用C++描述数据结构》求取 ⇩

第一章基本概念1

1.1 综述：系统生命周期1

1.2 面向对象程序设计3

1.2.1 算法分解与面向对象分解3

1.2.2 面向对象程序设计的基本定义和概念3

1.2.3 程序设计语百的演变相C++的历史4

1.3 数据抽象和封装4

1.4 C++基础8

1.4.1 C++中的程序结构8

1.4.2 C++中的表达式和操作符9

1.4.2 C++中的作用域9

1.4.4 C++中的数据声明10

1.4.5 C++中的注释10

1.4.6 C++中的输入／输出11

1.4.7 C++个的函数12

1.4.8 C++中的参数传递12

1.4.9 C++中的函数名重裁13

1.4.10 内联函数13

1.4.11 C++中的动态存储器分配14

1.5 算法详述14

1.5.1 引言14

4.8 稀疏矩阵15

1.5.2 递归算法15

1.6 性能分济与测定21

1.6.1 性能分析21

第七章 排序29

7.1 引言29

1.6.2 性能测定37

2.1.2 C++中的数据抽象与封装42

1.6.3 产生测试数据42

2.1.1 C++类简介45

2.1.3 声明类对象和调用成员函数46

第二章数组47

2.1 抽象数据类型和C++类47

2.1.4 持殊的类操作49

2.1.5 其他方面的概述51

2.1.6 抽象数据类型(ADT)和C++的类52

2.2 作为抽象数据类型的数组53

2.3 多项式抽象数据类型55

2.3.1 多项式表示57

2.3.2 多项式相加59

2.3.3 由数组表示多项式的缺点60

2.4 稀疏矩阵62

2.4.1 引言62

2.4.2 稀疏矩阵的表示方式63

2.4.3 矩阵的转置64

2.4.4 短阵相乘67

2.4.5 由数组表示稀疏短阵的缺点71

2.5 数组的表示73

2.6 字符串抽象数据类型76

2.6.1 字符串模式匹配：一种简单算法77

2.6.2 字符串模式匹配：K—M—P算法77

2.7 附加练习81

第三章 栈和队列86

3.1.1 模板函数86

3.1 C++中的模板86

3.1.2 采用摸板表示包容类87

3.2 栈抽象数据类型91

3.3 队列抽象数据类型95

3.4 C++中的子类型和继承99

3.5 迷宫问题102

3.6表达式的计算107

3.6.1 表达式107

3.6.2 后缀表示法108

3.6.3 中缀转换为后缀109

3.7 多栈和多队列112

3.8 附加练习115

4.1 单链表117

第四章 链表117

4.2.1用C++定义一个链表结点119

4.2 用C++表示链表119

4.2.2 用C++设计链表120

4.2.3 C++中的指针使用123

4.2.4 表处理操作124

4.3 可重用的链表类127

4.3.1 采用模板实现链表127

4.3.2 链麦重复体128

4.3.3 链表操作131

4.3.4 重用一个类132

4.4 循环链表133

4.5 链接栈和链接队列135

4.6 多项式137

4.8.1 稀疏矩阵表示151

4.8.2 稀疏矩阵的输入154

4.8.3 清除稀疏距阵155

4.9 双向链表158

4.10.1 广义表的表示160

4.10 广义表160

4.10.2 链表的递归算法164

4.10.3 共享链表、递归链表和引用数167

4.11 C++中的虚函数和动态联编171

4.12 异质表174

第五章 树179

5.1 引言179

5.1.1 术语179

5.1.2 树的表示法181

5.2 二叉树183

5.2.1 抽象数据类型183

5.2.2二叉树的性质185

5.2.3二叉树的表示法186

5.3.1 引言189

5.3 二叉树遍历189

5.3.2 中序遍历190

5.3.3 中序遍历191

5.3.4 后序遍历192

5.3.5 迭代中序遍历192

5.3.6 层序温历194

5.3.7 不用栈的遍历195

5.4 二叉树的其他操作197

5.4.1 复制二叉树197

5.4.2 测试等价性198

5.4.3 可满足性问题198

5.5.1 线索202

5.5 线索二叉树202

5.5.2 中序遍历线索二叉树203

5.5.3 向线索二叉树小插入结点205

5.6 堆206

5.6.1 优先级队列206

5.6.2 最大准的定义207

5.6.3 向最大堆中插入元素209

5.6.4 从最大堆小删除元索210

5.7 二叉查找树212

5.7.1 定义212

5.7.2 检索一棵二叉查找树213

5.7.3 向二叉查找树中插入元素215

5.7.4 从二叉查找树中删除元素216

5.7.5 连接和分裂二叉树216

5.7.6 二叉杏找树的高度218

5.8 选拔树219

5.8.1 引言219

5.8 2 优胜者树220

5.8.3 失败者树221

5.9森林222

5.11 树数据结构的面向对象系统223

5.9.1 把森林转换成二叉树223

5.9.2 森林的遍历223

5.10 集合的表示方法224

5.10.1 引言224

5.10.2 归并和查找操作225

5.10.3 在等价类中的应用231

5.12 二叉树的计数236

5.12.1 不相同的二叉树236

5.12.2 栈排列237

5.12.3 矩阵乘法238

5.12.4 不同二叉树数239

第六章 图241

6.1 图抽象数据类型241

6.1.1引言241

6.1.2 定义242

6.1.3 图的表示方法245

6.2.1 深度优先搜索251

6.2 图的基本操作251

6.2.3 连通分量253

6.2.2 广度优先搜索253

6.2.4 生成树254

6.2.5 重连通分量255

6.3 最小代价生成树260

6.3.2 普里姆算法263

6.3.3 索林算法264

6.4 最短路径和传北递闭包265

6.4.1 边带非负权值时从一个源点到其余所有顶点的最短路径266

6.4.2 边带任意权值时从一个源点到其余所有顶点的最短路径268

6.4.4 传递闭包273

6.5 活动网络276

6.5.1 顶点表示活动的网络（AOV网）276

6.5.2 边表示活动的网络（AOE网）281

6.6 附加练习288

7.2 插入排序295

7.3 快速排序296

7.4 排序的最小时间复杂度299

7.5 归并排序301

7.5.1 归并301

7.5.2 迭代归并排序305

7.5.3 递归归并排序306

7.6 堆排序310

7.7 对多个关键码的排序313

7.8 链表排序和列表排序316

7.9 内部排序的总结323

7.10 外部排序326

7.10.1 引言326

7.10.2 k一路归并329

7.10.3 对并行操作的缓冲区管理330

7.10.4 归并段产生335

7.10.5 归并段的最健归并337

第八章 散列341

8.1符号表抽象数据类型341

8.2 静态散列342

8.2.1 哈希表342

8.2.2 哈希函数343

8.2.3 溢出处理346

8.3 动态散列353

8.3.1 引言354

8.3.2 使用目录的动态散列354

8.3.3 基于目录的动态散列方法的分析359

8.3.4 无目录的动态散列361

9.1.1 定义365

9.1 最小一最大堆365

第九章 堆结构365

9.1.2 向最小一最大堆中插入元素366

9.1.3 删除最小元素369

9.2 双端堆372

9.2.1 定义372

9.2.2 向双端堆中插入元素374

9.2.3 删除最小元素376

9.3 左树378

9.4 二项堆384

9.4.1 代价分摊384

9.4.2 二项堆的定义385

9.4.3 向二项堆中插入元素386

9.4.4 结合两个二项堆386

9.4.5 删除最小元素387

9.4.6 分析388

9.5.1定义390

9.5 斐波那契堆390

9.5.2 从F—堆中删除结点391

9.5.3 减—码391

9.5.4 级联购切392

9.5.5 分析392

9.5.6 在最短路径问题中的应用394

9.6 附加练习396

第十章查找结构398

10.1 最优二叉查找树398

10.2 AVL树404

10.3 2—3树416

10.3.1 定义和性质416

10.3.2 查找一裸2—3树417

10.3.3 向2—3树中插入元素418

10.3.4 从2—3树中剿除元素420

10.4.1 定义和性质426

10.4 2—3—4树426

10.4.2 自顶向下插入428

10.4.3 自顶向下删除431

10.5 红—黑树432

10.5.1 定义和性质432

10.5.2 查找红—黑树434

10.5.3 自顶向下插入435

10.5.4 自底向上插入437

10.5.5 从红—黑树中删除元素438

10.5.6 连接和分裂红—黑树439

10.6 B—树443

10.6.1 m—路查找树的定义443

10.6.2 查找一棵m—路查找树444

10.6.3 B—树的定义和性质445

10.6.4 向B—树中插入447

10.6.5 从B—树中插入449

10.6.6 可变大小的关键码452

10.7 扁树454

10.8 数字查找树459

10.8.1 定义459

10.8.2 二叉trie树460

10.8.3 Patricia462

10.9 trie树466

10.9.1 定义466

10.9.2 查找一棵trie树467

10.9.3 采样策略467

10.9.4 向trie树中插入关键码468

10.9.5 从trie树中删除关键吗469

10.9.6 结点结构470

10.10 差异文件471

10.10.1 概念471

10.10.2 布卢姆过滤程序472