数据结构 用面向对象方法与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　VSAM 489

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