数据结构-C++实现PDF|Epub|txt|kindle电子书版本下载

数据结构-C++实现PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

1 绪论1

1.1 （算法＋数据结构）=程序1

1.2 数据结构的基本概念2

1.2.1 两个简单的数据结构实例2

1.2.2 什么是数据结构3

1.3 C＋＋语言基础4

1.3.1 程序结构5

1.3.2 数据声明和作用域6

1.3.3 输入/输出7

1.3.4 函数9

1.3.5 参数传递10

1.3.7 动态内存分配11

1.3.6 函数名重载11

1.3.8 结构与联合12

1.4 算法性能与复杂度16

1.4.1 算法的定义16

1.4.2 算法的性能标准17

1.4.3 算法的复杂度17

习题121

2 抽象数据类型和C＋＋类23

2.1 抽象数据类型23

2.1.1 从数据类型到抽象数据类型23

2.1.2 封装和信息隐藏24

2.1.3 抽象数据类型描法25

2.2.1 类与对象26

2.2 类与对象的基本概念26

2.2.2 消息与合作28

2.2.3 多态性28

2.3 面向对象的程序设计方法28

2.4 C＋＋类与对象29

2.5 构造函数和析构函数31

2.6 工具函数35

2.7 继承38

2.8 this指针的使用41

2.9 虚函数、多态性以及动态联编42

2.9.1 虚函数和多态性42

2.9.2 动态联编50

2.10 模板类52

习题254

3 线性表56

3.1 线性表的定义56

3.2.1 顺序表的类定义57

3.2.2 顺序表输入、删除算法的复杂度分析60

3.2.3 顺序表的应用61

3.3 线性表的链表表示62

3.3.1 单链表62

3.3.2 单循环链表73

3.3.3 双向循环链表73

3.3.4 静态链表79

3.4.2 多项式相加81

3.4.1 多项式表示81

3.4 多项式抽象数据类型81

习题383

4 栈、队列和递归85

4.1 栈85

4.1.1 顺序栈86

4.1.2 链式栈88

4.1.3 表达式的计算90

4.2 队列94

4.2.1 循环队列95

4.2.2 链队列98

4.3.1 递归的概念100

4.3 递归100

4.3.2 递归过程与递归工作栈101

4.3.3 消除递归103

4.3.4 迷宫问题107

习题4109

5 串、数组和广义表112

5.1 字符串112

5.1.1 字符串的定义、存储结构和操作112

5.1.2 串的操作113

5.1.3 常用的C＋＋字符串函数114

5.1.4 串类及其实现115

5.1.5 模式匹配算法121

5.2 数组125

5.2.2 数组的抽象数据类型表示126

5.2.1 C＋＋中数组的定义126

5.2.3 数组的顺序存储结构128

5.3 稀疏矩阵130

5.3.1 三元组顺序表131

5.3.2 十字链表133

5.4 广义表135

5.4.1 广义表的定义135

5.4.2 广义表的存储结构136

5.4.3 n元多项式的表示139

5.4.4 广义表的递归算法141

习题5144

6.1 树的概念147

6 树和森林147

6.1.1 树的定义148

6.1.2 树的术语148

6.1.3 树的表示形式149

6.1.4 树的基本操作和抽象数据类型149

6.2 二叉树153

6.2.1 二叉树的定义153

6.2.2 二叉树的性质153

6.2.3 二叉树的基本操作和抽象数据类型155

6.3 二叉树的存储结构158

6.3.1 数组表示法159

6.3.2 链表表示法160

6.3.3 二叉树的二叉锭表类声明160

6.4.1 前序遍历164

6.4 遍历二叉树164

6.4.2 中序遍历165

6.4.3 后序遍历165

6.4.4 层序遍历166

6.5 线索二叉树168

6.5.1 线索二叉树的定义168

6.5.2 线索二叉树的类定义170

6.5.3 中序线索二叉树173

6.6 二叉树的应用177

6.6.1 堆177

6.6.2 哈夫曼树183

6.7 树和森林187

6.7.1 树的存储结构187

6.7.2 树、森林和二叉树的转换190

6.7.3 树的高历192

6.7.4 森林的遍历193

6.8 等价类及其表示194

6.8.1 等价关系与等价类194

6.8.2 并查集195

习题6199

7 图203

7.1 图的基本概念203

7.1.1 图的定义203

7.1.2 图的术语204

7.1.3 图的基本操作和抽象数据类型207

7.2.1 邻接矩阵209

7.2 图的存储结构209

7.2.2 邻接表212

7.2.3 邻接多重表217

7.2.4 十字链表219

7.3 图的遍历与连通性220

7.3.1 深度优先遍历220

7.3.2 广度优先遍历221

7.3.3 连通分量223

7.4 最小生成树224

7.4.1 克鲁斯卡尔算法225

7.4.2 普里姆算法228

7.5 最短路径230

7.5.1 弧上权值为非负情形的单源点最短路径问题231

7.5.2 弧上权值为任意值的单源点最短路径问题234

7.5.3 所有顶点之间的最短路径236

7.6 活动风险238

7.6.1 用顶点表示活动的网络238

7.6.2 用边表示活动的网络（AOE网络）242

习题7246

8 查找250

8.1 基本概念250

8.2 顺序表251

8.2.1 顺序表的查找251

8.2.2 有序表的折半查找252

8.3.1 索引顺序表256

8.3 索引顺序表256

8.3.2 倒排表258

8.4 二叉排序树260

8.4.1 二叉排序树定义260

8.4.2 二叉排序树上的查找262

8.4.3 二叉排序树的插入263

8.4.4 二叉排序树的删除265

8.4.5 二叉排序树查找的性能分析266

8.5 平衡二叉树266

8.5.1 平衡二叉树的定义267

8.5.2 平衡旋转267

8.5.3 平衡二叉树的插入和删除269

8.6.1 动态的m路查找树273

8.6 B-树273

8.6.2 B-树274

8.6.3 B-树的插入274

8.6.4 B-树的删除276

8.6.5 B＋树278

8.7 散列表查找279

8.7.1 散列表的基本概念279

8.7.2 散列函数281

8.7.3 处理溢出的闭散列方法282

8.7.4 处理溢出的开散列方法——链地址法286

8.7.5 散列表分析287

习题8288

9.1.1 基本概念292

9 排序292

9.1 基础知识292

9.1.2 排序表的抽象数据类型描述和类定义293

9.2 交换排序299

9.2.1 冒泡排序299

9.2.2 快速排序300

9.3 插入排序302

9.3.1 直接插入排序302

9.3.2 折半插入排序306

9.3.3 希尔排序306

9.4 选择排序308

9.4.1 直接选择排序308

9.4.2 锦标赛排序310

9.4.3 堆排序312

9.5 归并排序314

9.5.1 归并314

9.5.2 两路归并排序315

9.5.3 递归的归并排序317

9.6 基数排序319

9.6.1 多关键字排序319

9.6.2 链式基数排序320

9.7 各种排序方法的选择和使用322

习题9323

主要参考文献326