数据结构 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.6函数名重载11

1.3.7动态内存分配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类与对象的基本概念26

2.2. 1类与对象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线性表的顺序表示57

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多项式抽象数据类型81

3.4. 1多项式表示81

3.4.2多项式相加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递归100

4. 3. 1递归的概念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. 1 C+++中数组的定义126

5.2.2数组的抽象数据类型表示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树和森林147

6. 1树的概念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遍历二叉树164

6. 4.1前序遍历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图的存储结构209

7.2. 1邻接矩阵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用边表示活动的网络242

习题7246

8查找250

8.1基本概念250

8.2顺序表251

8.2. 1顺序表的查找251

8.2.2有序表的折半查找252

8.3索引顺序表256

8.3. 1索引顺序表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 B-树273

8.6. 1动态的m路查找树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排序292

9.1基础知识292

9.1. 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