数据结构-C++语言描述PDF|Epub|txt|kindle电子书版本网盘下载

数据结构-C++语言描述PDF格式电子书版下载

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

第1章　基础知识1

1.1　算法与数据结构1

目录1

1.2　什么是数据结构2

1.2.1　基本概念2

1.2.2　数据的逻辑结构3

1.2.3　数据的存储表示4

1.2.4　数据结构的运算4

1.3　数据抽象和抽象数据类型5

1.3.1　抽象、数据抽象和过程抽象5

1.3.3　数据类型和抽象数据类型6

1.3.2　封装与信息隐蔽6

1.3.4　数据结构与抽象数据类型7

1.4　面向对象方法7

1.4.1 面向对象方法的由来7

1.4.2　面向对象方法的基本思想7

1.4.3　面向对象方法的要素8

1.4.4　面向对象方法和抽象数据类型9

1.5　＊C++程序设计概要9

1.5.1 函数与参数传递9

1.5.2　动态存储分配12

1.5.3　类与对象13

1.5.4　函数和运算符重载14

1.5.5　继承性和派生类15

1.5.6　多态性、虚函数和动态联编16

1.5.7　纯虚函数和抽象类17

1.5.8　友元函数和友元类18

1.5.9　模板函数和模板类18

1.6　描述数据结构和算法21

1.6.1　数据结构的规范21

1.6.2　实现数据结构22

1.7　算法和算法分析23

1.7.1　算法及其性能标准23

1.7.2　算法的时间复杂度24

1.7.3　使用程序步分析算法26

1.7.4　渐近表示法28

1.7.5　算法按时间复杂度分类29

1.7.6　算法的空间复杂度30

本章小结30

习题31

第2章　数组和链表33

2.1　结构和类33

2.1.1 结构33

2.1.2　结构表示元素34

2.2.1　指针36

2.2　指针和动态存储分配36

2.2.2　动态存储分配37

2.2.3　静态变量和动态变量38

2.3　数组38

2.3.1 一维数组38

2.3.2 二维数组39

2.3.3　多维数组40

2.3.4　数组和指针40

2.4　链表41

2.4.2　单链表42

2.4.1　指向结构的指针42

2.4.3　带表头结点的单链表45

2.4.4　单循环链表45

2.4.5　双向链表46

2.5　采用模拟指针的链表47

2.5.1 结点结构47

2.5.2　可用空间表48

2.6　异常处理50

本章小结51

习题51

3.1　堆栈53

3.1.1　堆栈ADT53

第3章　堆栈和队列53

3.1.2　堆栈的顺序表示54

3.1.3　堆栈的链接表示57

3.2　队列59

3.2.1　队列ADT59

3.2.2　队列的顺序表示61

3.2.3 队列的链接表示64

3.3　＊表达式计算64

3.3.1　表达式64

3.3.2 中缀表达式转换为后缀表达式65

3.3.3　计算后缀表达式的值68

3.4　＊演示与测试71

本章小结75

习题75

第4章　＊递归77

4.1　递归和递归算法77

4.1.1　递归的概念77

4.1.2　递归算法示例78

4.1.3　递推关系80

4.2　实现递归81

4.2.1 函数调用和系统栈81

4.2.2　递归函数的性能82

4.2.4　消去递归83

4.2.3　尾递归83

本章小结87

习题87

第5章　线性表和数组ADT88

5.1　线性表88

5.1.1 线性表ADT88

5.1.2　线性表的顺序表示90

5.1.3　线性表的链接表示93

5.1.4　两种存储表示的比较96

5.2.1　多项式ADT97

5.2　＊一元多项式算术运算97

5.2.2　多项式的链接表示98

5.2.3　项结点类98

5.2.4　多项式类99

5.2.5　多项式的输入和输出100

5.2.6　多项式相加101

5.2.7　多项式相乘102

5.2.8　重载运算符函数103

5.3　数组作为抽象数据类型104

5.3.1　数组ADT104

5.3.2　一维数组的C++类105

5.4.1　对称矩阵106

5.4　特殊矩阵106

5.4.2　＊带状矩阵107

5.5　稀疏矩阵108

5.5.1　稀疏矩阵ADT108

5.5.2　稀疏矩阵的三元组表109

5.5.3　稀疏矩阵转置110

5.5.4　＊稀疏矩阵相乘112

5.6　＊稀疏矩阵的正交链表115

5.6.1 稀疏矩阵的正交链表表示115

5.6.2　正交链表结点类116

5.6.3　正交链表类117

5.6.4　建立正交链表118

5.6.5　打印正交链表119

本章小结120

习题120

第6章　字符串和广义表122

6.1　字符串122

6.1.1 字符串ADT122

6.1.2　字符串的存储表示123

6.1.3 串运算的实现124

6.1.4　简单模式匹配算法125

6.1.5　＊模式匹配的KMP算法127

6.2.1　广义表的概念131

6.2　＊广义表131

6.2.2　广义表ADT132

6.2.3　广义表的存储表示133

6.2.4　广义表算法134

本章小结135

习题135

第7章　树137

7.1　树的基本概念137

7.1.1　树的定义137

7.1.2　基本术语138

7.2.1　二叉树的定义139

7.2　二叉树139

7.2.2　二叉树的性质140

7.2.3　二叉树ADT141

7.2.4　二叉树的存储表示142

7.2.5　二叉树类143

7.2.6　二叉树基本运算144

7.3　二叉树的遍历146

7.3.1　二叉树遍历算法146

7.3.2　二叉树遍历的递归算法147

7.3.3　二叉树遍历的应用示例149

7.4.1　遍历器类151

7.4　＊二叉树遍历的非递归算法151

7.4.2　中序遍历器类153

7.4.3　后序遍历器类154

7.5　＊二叉线索树157

7.5.1 叉线索树的定义157

7.5.2　构造中序线索树158

7.5.3　遍历二叉线索树159

7.6　树和森林161

7.6.1　森林与二叉树的转换161

7.6.2　树和森林的存储表示162

7.7　＊堆和优先权队列164

7.6.3　树和森林的遍历164

7.7.1　堆165

7.7.2　优先权队列ADT167

7.7.3　优先权队列类168

7.7.4　实现优先权队列168

7.8　哈夫曼树和哈夫曼编码170

7.8.1　树的路径长度171

7.8.2　哈夫曼树和哈夫曼算法172

7.8.3　哈夫曼树类173

7.8.4　构造哈夫曼树173

7.8.5　哈夫曼编码175

7.8.6　哈夫曼编码算法176

7.9.1　并查集ADT177

7.9　＊并查集和等价关系177

7.9.2　并查集的存储表示178

7.9.3　并查集类178

7.9.4　函数Union和Find179

7.9.5　改进的函数Union和Find179

7.9.6　按等价关系分组181

本章小结181

习题182

8.1.1　集合和搜索的概念184

第8章　集合和搜索184

8.1　集合及其表示184

8.1.2　动态集ADT185

8.1.3　集合的表示186

8.2　顺序搜索187

8.2.1　无序表的顺序搜索187

8.2.2　有序表的顺序搜索188

8.2.3　平均搜索长度188

8.2.4 自组织表189

8.3.1　二分搜索算法190

8.3　二分搜索190

8.3.2　对半搜索191

8.3.3　二叉判定树192

8.3.4　＊斐波那契搜索193

8.4　＊搜索算法的时间下界195

本章小结196

习题196

第9章　动态集和搜索树197

9.1　二叉搜索树197

9.1.1 二叉搜索树的定义197

9.1.2　二叉搜索树的搜索198

9.1.3　二叉搜索树的插入199

9.1.4　二叉搜索树的删除200

9.1.5　平均情况时间分析201

9.2　＊二叉平衡树203

9.2.1　二叉平衡树的定义203

9.2.2　二叉平衡树类204

9.2.3　二叉平衡树的平衡旋转205

9.2.4　二叉平衡树的插入210

9.2.5　二叉平衡树的删除211

9.2.6　二叉平衡树的高度214

9.3.1 自调节树和伸展树215

9.3.2　伸展树的伸展操作215

9.3　＊伸展树215

9.3.3　伸展树类217

9.3.4　旋转的实现218

9.3.5　伸展树的插入运算218

9.3.6　时间分析220

本章小结222

习题222

第10章　多叉搜索树224

10.1　m叉搜索树224

10.2.2 B树的高度226

10.2.1　B树的定义226

10.2　B树226

10.2.3 B树的搜索227

10.2.4 B树的插入227

10.2.5 B树的删除229

10.2.6 ＊B树类231

10.2.7 ＊B树的搜索运算232

10.2.8　＊B树的插入运算233

10.2.9　＊B树的删除运算235

10.3　＊键树239

10.3.1　键树的定义239

10.3.2 链树239

10.3.3　Trie树240

10.3.4　Trie树的搜索242

10.3.5 Trie树的插入243

10.3.6 Trie树的删除243

10.3.7 Trie树性能分析244

本章小结244

习题244

第11章　跳表和散列表246

11.1　字典246

11.2　＊跳表246

11.2.1　什么是跳表246

11.2.2　跳表类248

11.2.3　跳表的搜索250

11.2.4　跳表的插入251

11.2.5　跳表的删除252

11.3　散列表253

11.3.1　散列技术253

11.3.2　散列函数254

11.3.3　拉链法255

11.3.4　开地址法256

11.3.5　线性探查法256

11.3.6　其他开地址法260

本章小结262

习题262

11.3.7　性能分析262

第12章　图264

12.1　图的基本概念264

12.1.1　图的定义与术语264

12.1.2 图ADT266

12.2　图的存储结构267

12.2.1 图的矩阵表示法267

12.2.2　图的邻接矩阵实现269

12.2.3　图的邻接表表示法271

12.2.4　图的邻接表实现272

12.3　图的遍历274

12.3.1　扩充的图类275

12.3.2　深度优先遍历275

12.3.3　宽度优先遍历277

12.3.4　基本遍历方法278

12.4　拓扑排序279

12.4.1 用顶点代表活动的AOV网279

12.4.2　拓扑排序算法280

12.4.3　实现拓扑排序算法281

12.5　＊关键路径283

12.5.1　用边代表活动的AOE网283

12.5.2　关键路径算法284

12.5.3　实现关键路径算法286

12.6.1　基本概念287

12.6.2　普里姆算法287

12.6　最小代价生成树287

12.6.3　＊克鲁斯卡尔算法289

12.6.4　＊算法正确性291

12.7　单源最短路径292

12.7.1　最短路径问题292

12.7.2　迪杰斯特拉算法292

12.7.3　数据结构选择293

12.7.4　实现迪杰斯特拉算法293

12.8.1　弗洛伊德算法296

12.8　＊所有顶点之间的最短路径296

12.8.2　实现弗洛伊德算法297

本章小结298

习题298

第13章　内排序300

13.1　基本概念300

13.2　插入排序301

13.2.1　直接插入排序301

13.2.2　顺序表直接插入排序302

13.2.3　＊单链表直接插入排序303

13.2.4　＊希尔排序305

13.3　选择排序306

13.3.1　简单选择排序307

13.3.2　＊堆排序308

13.4　交换排序309

13.4.1 冒泡排序309

13.4.2　快速排序311

134.3　快速排序算法311

134.4　＊快速排序性能分析313

13.5　两路合并排序315

13.5.1　合并两个有序序列315

13.5.2　顺序表两路合并排序316

13.5.3　＊合并排序的递归算法317

13.5.4　＊单链表两路合并排序317

13.6　＊排序算法的时间下界320

13.7　＊基数排序321

13.7.1　分配排序321

13.7.2　基数排序算法322

13.7.3　基数排序C++程序323

本章小结325

习题325

14.1.1　主存储器和辅助存储器327

14.1.2　磁盘存储器327

14.1　辅助存储器简介327

第14章　＊文件和外排序327

14.2　文件328

14.2.1　文件的基本概念328

14.2.2　文件的组织方式329

14.3　文件的索引结构332

14.3.1　静态索引结构332

14.3.2　动态索引结构332

14.4　外排序333

14.4.1　外排序的基本过程333

14.4.2　初始游程的生成334

14.4.3　多路合并338

14.4.4　最佳合并树340

本章小结340

习题341

附录A　实习要求和实习题342

A.1　面向对象方法概述342

A.2　实习目的344

A.3　实习要求344

A.4　实习步骤344

A.5　实习报告345

A.6　实习题346

附录B　专有名词中英文对照表349

参考文献355