《数据结构 用面向对象方法与C++描述》求取 ⇩

第1章 绪论1

1．1 什么是数据结构2

1．2 抽象数据类型及面向对象概念4

1．2．1 数据类型4

1．2．2 数据抽象与抽象数据类型（ADTs:Abstract Data Types）4

1．2．3 面向对象的概念5

1．2．4 用于描述数据结构的语言7

1．3 数据结构的抽象层次7

1．4．1 C++的函数特征9

*1．4 用C++描述面向对象程序9

1．4．2 C++的数据声明10

1．4．3 C++的作用域11

1．4．4 C++的类11

1．4．5 C++中的对象13

1．4．6 C++的输入输出13

1．4．7 C++中的函数15

1．4．8 C++中的参数传递15

1．4．9 C++中的函数名重载和操作符重载16

1．4．10 C++中的动态存储分配17

1．4．11 友元（friend）函数18

1．4．12 内联（inline）函数18

1．4．13 结构（struct）与类18

1．4．14 联合（Union）与类19

1．5 算法定义19

1．6 模板（template）20

1．7．1 算法的性能标准23

1．7 性能分析与度量23

*1．7．2 算法的后期测试24

1．7．3 算法的事前估计26

1．7．4 空间复杂度度量26

1．7．5 时间复杂度度量27

1．7．6 时间复杂度的渐进表示法31

1．7．7 渐进的空间复杂度34

习题34

2．1．1 在C++中数组的定义和初始化37

第2章 数组37

2．1 作为抽象数据类型的数组37

2．1．2 作为抽象数据类型的数组38

2．1．3 数组的顺序存储方式40

2．2 顺序表42

2．2．1 顺序表的定义和特点43

2．2．2 顺序表的类定义43

2．2．3 顺序表的查找、插入和删除45

2．2．4 作为抽象数据类型，使用顺序表的事例47

*2．3 多项式抽象数据类型47

2．3．1 多项式抽象数据类型48

2．3．2 多项式的表示49

2．3．3 多项式的相加51

2．4 稀疏矩阵53

2．4．1 稀疏矩阵的抽象数据类型53

2．4．2 稀疏矩阵的压缩表示53

*2．4．3 稀疏矩阵的转置54

*2．4．4 稀疏矩阵相乘57

2．5 字符串59

2．5．1 字符串抽象数据类型和类定义59

2．5．2 字符串操作的实现61

2．5．3 字符串的模式匹配63

*2．5．4 模式匹配的改进算法——KMP（D.E.Knuth -J.H.Morris—V.R.Pratt）算法64

习题68

第3章 链表71

3．1 单链表（Singly Linked List）71

3．1．1 单链表的结构71

3．1．2 单链表的类定义72

3．1．3 单链表中的插入与删除73

3．3．4 带表头结点的单链表75

3．3．5 用模板定义的单链表类76

3．3．6 单链表的游标（Iterator）类79

3．3．7 静态链表81

3．2．1 循环链表的类定义82

3．2 循环链表82

3．2．2 用循环链表求解约瑟夫问题83

*3．3 多项式及其相加84

3．3．1 多项式的类定义84

3．3．2 多项式的加法85

3．4 双向链表87

3．5 稀疏矩阵92

3．5．1 稀疏矩阵的类定义92

3．5．2 稀疏矩阵的建立94

3．5．3 删除稀疏矩阵95

3．6 C++中的虚函数和动态联编96

3．6．1 C++中的继承（inheritance）96

3．6．2 基类与派生类对象指针的转换97

3．6．3 虚函数（virtual function）99

3．6．4 纯虚函数和抽象基类99

3．6．5 多态性（polymorphism）和动态联编99

习题101

4．1．1 栈的抽象数据类型103

第4章 栈和队列103

4．1 栈103

4．1．2 栈抽象数据类型的顺序存储表示与实现——顺序栈104

4．1．3 栈抽象数据类型的链接存储表示——链式栈106

*4．2 表达式的计算（Expression Evaluation）107

4．2．1 表达式107

4．2．2 应用后缀表示计算表达式的值108

4．2．3 中缀表达式转换为后缀表达式111

4．3 队列113

4．3．1 队列的抽象数据类型113

4．3．2 队列的顺序存储表示——循环队列114

4．3．3 队列的链接存储表示——链式队列116

4．3．4 队列的应用举例—打印二项展开式（a+b）j的系数118

4．4 优先级队列（Priority Queue）119

4．4．1 优先级队列的定义119

4．4．2 优先级队列的存储表示和实现120

*4．5 事件驱动模拟（Event-Driven Simulation）121

习题130

第5章 递归（RECURVE）132

5．1 递归的概念132

5．2 迷宫问题135

5．3 递归过程与递归工作栈138

*5．4 利用栈实现的迷宫问题非递归解法142

5．5 广义表（General Lists）145

5．5．1 广义表的概念146

5．5．2 广义表的表示及操作147

5．5．3 广义表存储结构的实现149

5．5．4 广义表的访问算法151

5．5．5 广义表的递归算法153

*5．5．6 三元多项式的表示159

习题161

6．1．2 树的术语163

6．1．1 树的定义163

6．1 树与森林的概念163

第6章 树与森林163

6．1．3 树的抽象数据类型164

6．2 二叉树（Binary Tree）165

6．2．1 二叉树的定义165

6．2．2 二叉树的性质166

6．2．3 二叉树的抽象数据类型167

6．3．1 数组表示168

6．3 二叉树的表示168

6．3．2 链表存储表示169

6．4 二叉树遍历（Binary Tree Traversal）172

6．4．1 中序遍历（Inorder Traversal）173

6．4．2 前序遍历（preorder Traversal）173

6．4．3 后序遍历（Postorder Traversal）174

6．4．4 应用二叉树遍历的事例175

*6．4．5 二叉树遍历的游标类（Tree Iterator）177

6．5．1 线索（Thread）182

*6．5 线索化二叉树（Threaded Binary Tree）182

*6．4．6 不用栈的二叉树中序遍历算法182

6．5．2 中序线索化二叉树183

6．5．3 前序与后序的线索化二叉树188

6．6 堆（Heap）189

6．6．1 堆的定义190

6．6．1 堆的建立191

6．6．3 堆的插入与删除192

6．7 树与森林194

6．7．1 树的存储表示194

6．7．2 森林与二叉树的转换199

6．7．3 树的遍历200

6．7．4 森林的遍历202

*6．8 二叉树的计数203

6．9 霍夫曼树（Huffman Tree）206

6．9．1 路径长度（Path Length）206

6．9．2 霍夫曼树207

9．9．3 霍夫曼编码209

习题210

第7章 集合与搜索212

7．1 集合及其表示212

7．1．1 集合基本概念212

7．1．2 以集合为基础的抽象数据类型213

7．1．3 用位向量实现集合抽象数据类型213

7．1．4 用有序链表实现集合的抽象数据类型215

7．2 等价类和并查集219

7．2．1 等价关系与等价类219

7．2．2 确定等价类的链表方法220

7．2．3 并查集222

7．3 静态搜索结构227

7．3．1 搜索的概念227

7．3．2 静态搜索结构228

7．3．3 顺序搜索229

7．3．4 基于有序顺序表的折半搜索231

*7．3．5 基于有序顺序表的斐波那契搜索和插值搜索234

7．4 二叉搜索树235

7．4．1 定义235

7．4．2 二叉搜索树上的搜索237

7．4．3 二叉搜索树的插入238

7．4．4 二叉搜索树的删除239

*7．4．5 与二叉搜索树相关的中序游标类240

*7．5 最优二叉搜索树242

7．5．1 扩充二叉搜索树242

7．5．2 最优二叉搜索树243

7．6 AVL树247

7．6．1 AVL树的定义247

7．6．2 平衡化旋转248

7．6．3 AVL树的插入和删除252

7．6．4 AVL树的高度255

习题256

8．1．1 图的基本概念259

8．1 图的基本概念259

第8章 图259

8．1．2 图的抽象数据类型261

8．2 图的存储表示262

8．2．1 邻接矩阵262

8．2．2 邻接表265

8．2．3 邻接多重表269

8．3 图的遍历与连通性270

8．3．1 深度优先搜索271

8．3．2 广度优先搜索272

8．3．3 连通分量273

8．3．4 重连通分量274

8．4 最小生成树277

8．4．1 克鲁斯卡尔（Kruskal）算法278

8．4．2 普里姆（Prim）算法280

8．5 最短路径283

8．5．1 边上权值非负情形的单源最短路径问题283

*8．5．2 边上权值为任意值的单源最短路径问题286

8．5．3 所有顶点之间的最短路径288

8．6 活动网络290

8．6．1 用顶点表示活动的网络290

8．6．1 用边表示活动的网络294

习题298

第9章 排序301

9．1 概述301

9．2 插入排序303

9．2．1 直接插入排序303

9．2．2 折半插入排序304

9．2．3 链表插入排序305

9．2．4 希尔排序307

9．3 交换排序309

9．3．1 起泡排序309

9．3．2 快速排序310

9．4 选择排序312

9．4．2 锦标赛排序313

9．4．1 直接选择排序313

9．4．3 堆排序317

9．5 归并排序318

9．5．1 归并318

9．5．2 迭代的归并排序算法319

9．5．3 递归的表归并排序321

*9．6 基数排序323

9．6．1 多关键码排序323

9．6．2 链式基数排序324

9．7 外排序326

9．7．1 外排序的基本过程326

9．7．2 k路平衡归并329

9．7．3 初始归并段的生成333

*9．7．4 并行操作的缓冲区处理337

9．7．5 最佳归并树339

习题341

10．1．1 线性索引344

10．1 静态索引结构344

第10章 索引结构与散列344

10．1．2 倒排表346

10．1．3 m路静态搜索树347

10．2 动态索引结构348

10．2．1 动态的m路搜索树348

10．2．2 B_树350

10．2．3 B_树的插入352

10．2．4 B_树的删除354

10．2．5 B+树358

*10．3 Trie树361

10．3．1 Trie树的定义361

10．3．2 Trie树的搜索362

10．3．3 在Trie树上的插入和删除363

10．4 散列（Hashing）364

10．4．1 词典（Dictionary）的抽象数据类型364

10．4．3 散列函数365

10．4．2 散列表与散列方法365

10．4．4 处理溢出的闭散列方法369

10．4．5 处理溢出的开散列方法——链地址法376

10．4．6 散列表分析378

*10．5 可扩充散列379

10．5．1 二叉Trie树379

10．5．2 将二叉Trie树转换为目录380

10．5．3 插入与目录扩充383

10．5．4 删除与目录收缩385

10．5．5 性能分析386

习题388

附录 实习要求与实习报告391

实习1 栈和队列396

实习2 串（内容：全屏幕文本编辑器）396

实习3 树（内容：作业调度）398

实习4 图（内容：某公园导游图）399

实习5 查找、排序（内容：简单的职工管理系统）399

参考文献401