数据结构 用面向对象方法与C++语言描述 第2版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

数据结构 用面向对象方法与C++语言描述 第2版PDF格式电子书版下载

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

第1章　数据结构概论1

1.1　数据结构的概念1

1.1.1　数据结构举例1

1.1.2　数据与数据结构2

1.1.3　数据结构的分类3

1.1.4　数据结构课程的内容4

1.2　数据结构的抽象形式6

1.2.1　数据类型6

1.2.2　数据抽象与抽象数据类型7

1.3 作为ADT的C＋＋类9

1.3.1　面向对象的概念9

1.3.2　C＋＋中的类10

1.3.3　C＋＋中的对象12

1.3.4　C＋＋的输入输出13

1.3.5　C＋＋中的函数14

1.3.6　动态存储分配17

1.3.7　C＋＋中的继承18

1.3.8　多态性19

1.3.9　C＋＋的模板23

1.4　算法定义24

1.5　算法性能分析与度量26

1.5.1　算法的性能标准26

1.5.2　算法的后期测试26

1.5.3　算法的事前估计27

1.5.4　算法的渐进分析32

1.5.5　最坏、最好和平均情况36

习题37

第2章　线性表43

2.1　线性表43

2.1.1　线性表的概念43

2.1.2　线性表的类定义44

2.2　顺序表45

2.2.1　顺序表的定义和特点45

2.2.2　顺序表的类定义及其操作45

2.2.3　顺序表的性能分析50

2.2.4　顺序表的应用52

2.3　单链表52

2.3.1　单链表的概念53

2.3.2　单链表的类定义54

2.3.3　单链表中的插入与删除56

2.3.4　带附加头结点的单链表59

2.3.5　单链表的模板类60

2.4　线性链表的其他变形66

2.4.1　循环链表66

2.4.2　双向链表69

2.5　单链表的应用：多项式及其运算73

2.5.1　多项式的表示74

2.5.2　多项式的类定义75

2.5.3　多项式的加法77

2.5.4　多项式的乘法79

2.6　静态链表80

习题83

第3章　栈和队列88

3.1　栈88

3.1.1　栈的定义88

3.1.2　顺序栈89

3.1.3　链式栈92

3.1.4　栈的应用之一——括号匹配94

3.1.5　栈的应用之二——表达式的计算95

3.2　栈与递归101

3.2.1　递归的概念101

3.2.2　递归过程与递归工作栈105

3.2.3　用回溯法求解迷宫问题109

3.3 队列114

3.3.1　队列的概念114

3.3.2　循环队列114

3.3.3　链式队列118

3.3.4 队列应用举例：打印二项展开式（a+b）i的系数120

3.3.5　队列应用举例：电路布线121

3.4　优先级队列124

3.4.1　优先级队列的概念124

3.4.2　优先级队列的存储表示和实现125

3.5　双端队列126

3.5.1　双端队列的概念126

3.5.2　双端队列的数组表示128

3.5.3　双端队列的链表表示129

习题131

第4章　数组、串与广义表135

4.1　多维数组的概念与存储135

4.1.1　多维数组的概念135

4.1.2　多维数组的存储表示136

4.2　特殊矩阵138

4.2.1　对称矩阵的压缩存储138

4.2.2　三对角线／多对角线矩阵的压缩存储140

4.3　稀疏矩阵141

4.3.1　稀疏矩阵及其三元组数组表示141

4.3.2　稀疏矩阵的转置145

4.3.3　稀疏矩阵的相加和相乘147

4.3.4　矩阵的正交链表表示152

4.4　字符串153

4.4.1　字符串的概念153

4.4.2 C++有关字符串的库函数154

4.4.3　字符串的实现156

4.4.4　字符串的自定义类158

4.4.5　字符串操作的实现159

4.4.6　字符串的模式匹配161

4.4.7　字符串的存储方法167

4.5　广义表169

4.5.1　广义表的定义与性质169

4.5.2　广义表的表示170

4.5.3　广义表存储结构的实现170

4.5.4　广义表的递归算法174

4.5.5　三元多项式的表示181

习题183

第5章　树186

5.1　树的基本概念186

5.1.1　树的定义和术语186

5.1.2　树的抽象数据类型188

5.2　二叉树189

5.2.1　二叉树的定义189

5.2.2　二叉树的性质190

5.2.3　二叉树的抽象数据类型191

5.3　二叉树的存储表示192

5.3.1　二叉树的数组存储表示192

5.3.2　二叉树的链表存储表示193

5.4　二叉树遍历及其应用198

5.4.1　二叉树遍历的递归算法198

5.4.2　二叉树遍历的应用200

5.4.3　二叉树遍历的非递归算法203

5.4.4　二叉树的计数207

5.5　线索二叉树210

5.5.1　线索210

5.5.2 中序线索二叉树的建立和遍历211

5.5.3 中序线索二叉树的插入与删除216

5.5.4　前序与后序的线索化二叉树218

5.6　树与森林220

5.6.1　树的存储表示220

5.6.2　森林与二叉树的转换225

5.6.3　树与二叉树的转换227

5.7　树与森林的遍历及其应用227

5.7.1　树与森林的深度优先遍历227

5.7.2　树和森林的广度优先遍历230

5.7.3　树遍历算法的应用231

5.7.4　其他基于遍历序列的几种存储表示232

5.8　堆235

5.8.1　最小堆和最大堆235

5.8.2　堆的建立236

5.8.3　堆的插入与删除238

5.9　Huffman树及其应用240

5.9.1　路径长度240

5.9.2　Huffman树241

5.9.3 Huffman树的应用：最优判定树243

5.9.4 Huffman树的应用：Huffman编码244

习题246

第6章　集合与字典251

6.1　集合及其表示251

6.1.1　集合的基本概念251

6.1.2　用位向量实现集合抽象数据类型252

6.1.3　用有序链表实现集合的抽象数据类型257

6.2　并查集与等价类262

6.2.1　并查集的定义及其实现262

6.2.2　并查集的应用：等价类划分267

6.3　字典268

6.3.1　字典的概念269

6.3.2　字典的线性表描述270

6.4　跳表273

6.4.1　跳表的概念273

6.4.2　跳表的类定义274

6.4.3　跳表的搜索、插入和删除276

6.5　散列279

6.5.1　散列表与散列方法279

6.5.2　散列函数280

6.5.3　处理冲突的闭散列方法282

6.5.4　处理冲突的开散列方法291

6.5.5　散列表分析293

习题294

第7章　搜索结构297

7.1　静态搜索结构298

7.1.1　静态搜索表298

7.1.2　顺序搜索300

7.1.3　基于有序顺序表的顺序搜索和折半搜索302

7.1.4　基于有序顺序表的其他搜索方法307

7.2　二叉搜索树308

7.2.1　二叉搜索树的概念309

7.2.2　二叉搜索树上的搜索310

7.2.3　二叉搜索树的插入311

7.2.4　二叉搜索树的删除313

7.2.5　二叉搜索树的性能分析314

7.2.6　最优二叉搜索树317

7.3　AVL树320

7.3.1　AVL树的概念321

7.3.2　平衡化旋转321

7.3.3　AVL树的插入326

7.3.4　AVL树的删除329

7.3.5　AVL树的性能分析333

7.4　伸展树334

7.5　红黑树337

7.5.1　红黑树的概念和性质337

7.5.2　红黑树的搜索338

7.5.3　红黑树的插入338

7.5.4　红黑树的删除339

习题342

第8章 图346

8.1　图的基本概念346

8.1.1　与图有关的若干概念346

8.1.2　图的抽象数据类型348

8.2　图的存储结构349

8.2.1　图的邻接矩阵表示350

8.2.2　图的邻接表表示355

8.2.3　图的邻接多重表表示361

8.3 图的遍历363

8.3.1　深度优先搜索364

8.3.2　广度优先搜索365

8.3.3　连通分量366

8.3.4　重连通分量368

8.4　最小生成树370

8.4.1　Kruskal算法371

8.4.2　Prim算法373

8.5　最短路径375

8.5.1　非负权值的单源最短路径376

8.5.2　任意权值的单源最短路径379

8.5.3　所有顶点之间的最短路径381

8.6 用顶点表示活动的网络（AOV网络）383

8.7 用边表示活动的网络（AOE网络）388

习题392

第9章 排序397

9.1　排序的概念及其算法性能分析397

9.1.1　排序的概念397

9.1.2　排序算法的性能评估398

9.1.3　排序表的类定义400

9.2　插入排序401

9.2.1　直接插入排序401

9.2.2　折半插入排序403

9.2.3　希尔排序404

9.3 快速排序405

9.3.1　快速排序的过程406

9.3.2　快速排序的性能分析407

9.3.3　快速排序的改进算法409

9.3.4　三路划分的快速排序算法412

9.4　选择排序413

9.4.1　直接选择排序413

9.4.2　锦标赛排序414

9.4.3　堆排序419

9.5　归并排序422

9.5.1 归并422

9.5.2　归并排序算法423

9.6　基于链表的排序算法425

9.6.1　链表插入排序425

9.6.2　链表归并排序427

9.6.3　链表排序结果的重排428

9.7　分配排序431

9.7.1　桶式排序431

9.7.2　基数排序432

9.7.3　MSD基数排序433

9.7.4　LSD基数排序435

9.8　内部排序算法的分析437

9.8.1　排序方法的下界437

9.8.2　各种内部排序方法的比较439

习题440

第10章　文件、外部排序与搜索444

10.1　主存储器和外存储器444

10.1.1　磁带444

10.1.2　磁盘存储器446

10.1.3　缓冲区与缓冲池448

10.2　文件组织449

10.2.1　文件的概念449

10.2.2　文件的存储结构450

10.3　外排序459

10.3.1　外排序的基本过程459

10.3.2　k路平衡归并与败者树461

10.3.3　初始归并段的生成（run generation）466

10.3.4　并行操作的缓冲区处理470

10.3.5　最佳归并树473

10.4　多级索引结构475

10.4.1　静态的ISAM方法475

10.4.2　动态的m路搜索树476

10.4.3　B树478

10.4.4　B树的插入480

10.4.5　B树的删除482

10.4.6　B+树486

10.4.7　VSAM489

10.5　可扩充散列490

10.5.1　二叉Trie树490

10.5.2　将二叉Trie树转换为目录表491

10.5.3 目录表扩充与收缩493

10.5.4　性能分析494

10.6　Trie树494

10.6.1　Trie树的定义494

10.6.2　Trie树的搜索495

10.6.3　在Trie树上的插入和删除496

习题497

附录A 程序索引500

附录B　词汇索引504

参考文献512