C++数据结构导引PDF电子书下载

目录 1

第1章　软件开发 1

1.1 问题分析和需求规格说明 1

1.2　设计 3

1.2.1 对象 3

1.2.2　操作 4

1.2.3　算法 5

1.2.4　函数YearSum（）的设计 5

1.2.5　函数DisplayTable（）的设计 6

1.2.6　关于算法的一些最后说明 7

1.3　编码 10

1.4　测试、执行和调试 14

1.5　维护 18

1.5.1 小测验 18

1.5.2　练习 19

第2章　数据结构入门和抽象数据类型——C风格类型 21

2.1 数据结构、抽象数据类型和实现 21

2.2　简单数据类型 24

2.2.1 Boolean数据 24

2.2.2 Character数据 25

2.2.3　整型数据 26

2.2.4　实数数据 28

2.2.5 小结 30

2.2.7　练习 31

2.2.6　小测验 31

2.3　数组 32

2.3.1 一维数组 33

2.3.2　下标运算 35

2.3.3　数组作为形参 35

2.3.4　越界错误 37

2.3.5　数组的问题 37

2.3.6　多维数组 38

2.3.7　小测验 44

2.3.8　练习 45

2.4.1　为什么需要结构 46

2.4　结构 46

2.4.2 C风格结构 47

2.4.3　结构的运算 49

2.4.4　联合 50

2.4.5　内存中的结构 52

2.4.6　小测验 53

2.4.7　练习 53

2.5　过程式编程 55

2.5.1　例子：一个时间数据类型 55

2.5.2 PP对OOP 59

第3章　数据结构和抽象数据结构进阶——C++类型 64

3.1　类 64

3.1.2　类声明 65

3.1.1 “传统的”（C）结构，OOP（C++）结构以及类之间的区别 65

3.1.3　例子：C++标准I/O类 66

3.2　用户定义类型的例子：一个Time类 67

3.2.1 实现一个类 68

3.2.2　一些现象 70

3.2.3　类构造函数 72

3.2.4　复制操作——初始化和赋值 76

3.2.5　访问函数 77

3.2.6　输入／输出——重载运算符——友元函数 78

3.2.7　其他操作：关系操作和前进 83

3.2.8　总结以及其他一些细节 85

3.2.10　练习 87

3.2.9　小测验 87

3.3　作为ADT的串 88

3.3.1 串的C风格实现 89

3.3.2　一个串类 90

3.3.3　练习 93

3.4 C++串类型 93

3.4.1　定义和构造函数 94

3.4.2　存储 94

3.4.3　输入／输出 94

3.4.4 string流 96

3.4.5　修改符 97

3.4.6　复制符 97

3.4.8　查找操作 98

3.4.7　访问单独的字符 98

3.4.9 比较 99

3.4.10 string和C风格串 100

3.4.11 小测验 100

3.4.12　练习 101

3.5　一个例子：文本编辑 101

3.5.1　对象 102

3.5.2　操作 102

3.5.3　文本编辑算法 102

3.6　数据加密（可选） 105

3.6.1　数据加密标准 107

3.6.2　公共密钥加密 110

3.6.3　练习 113

3.7　模式匹配（可选） 114

第4章　栈 128

4.1　栈的介绍 128

4.2　设计和创建一个Stack类 132

4.2.1　设计一个Stack类 132

4.2.2　实现一个栈类 132

4.2.3　选择数据成员 133

4.2.4　函数成员 135

4.2.5　前瞻 142

4.2.6　小测验 142

4.2.7　练习 143

4.3.1　在函数调用中使用栈 144

4.3　栈的两个应用：函数调用，逆波兰表示 144

4.3.2　逆波兰表示中栈的应用 145

4.3.3　小测验 153

4.3.4　练习 153

第5章　队列 158

5.1 队列入门 158

5.1.1　例子：训练和实践问题 159

5.1.2　调度队列的例子 163

5.2　基于数组的队列实现 165

5.2.1　小测验 168

5.2.2　练习 169

5.3 队列的应用：信息中心仿真 170

5.3.1 问题分析和需求规格说明 171

5.3.2　设计 171

5.3.3　编码和执行 174

第6章 改进ADT——第1部分：模板和标准容器 181

6.1　介绍：可重用性和通用性的发展 181

6.1.1　从算法到算法 182

6.1.2　从数据到容器 183

6.2　函数通用性——重载和模板 183

6.2.1　重载 184

6.2.2　函数模板 186

6.2.3　例子：显示一个数组 189

6.3.2　类模板 190

6.3.1 Typedef有什么错 190

6.3　类通用性——模板 190

6.3.3　一个Stack类模板 192

6.3.4 Stack类模板的另一个版本 196

6.3.5　标准C++的容器类模板 197

6.3.6　小测验 198

6.3.7　练习 198

6.4 vector容器 198

6.4.1 定义vector对象 199

6.4.2　一些vector操作 200

6.4.3　例子：登录计数 204

6.4.4 内部实现一瞥——增加容量 207

6.4.5　对迭代器的第一次探讨 209

6.4.7　综合比较：vector对数组 212

6.4.6　一些涉及到迭代器的vector函数成员 212

6.4.8　小测验 213

6.4.9　练习 214

6.5　多维向量 215

6.5.1　二维vector对象 216

6.5.2　二维vector操作 216

6.5.3　练习 218

6.6　其他标准容器——deque、stack和queue 218

6.6.1 STL的deque类模板 219

6.6.2 Stack类模板的一个新（但是非必需的）版本 221

6.6.3 STL的stack适配器 222

6.7.1 bitset对象的声明 224

6.7 bitsets（可选） 224

6.6.4 STL的queue适配器 224

6.6.5 小测验 224

6.7.2 bitset操作 225

6.7.3　使用bitset实现集合 226

6.7.4　例子：使用埃拉托色尼（Eratoshenes）筛寻找素数 228

6.7.5　练习 230

6.8 valarrays（可选） 230

6.8.1 valarray对象的声明 231

6.8.2 valarray操作 231

6.8.3 slices、masks以及间接数组 232

6.8.4　练习 233

7.1.1　例子：递归的求幂和求阶乘函数 238

7.1　递归 238

第7章　改进ADT——第2部分：递归，算法分析，以及标准算法 238

7.1.2　糟糕递归的例子：Fibonacci数字 242

7.1.3　例子：折半搜索 245

7.1.4　例子：回文检查程序 246

7.1.5　小测验 248

7.1.6　练习 248

7.2　递归的例子：Hanoi塔；分析 251

7.2.1 Hanoi塔 251

7.2.2　分析 253

7.2.3　练习 258

7.3　实现递归 259

7.4　算法效率 261

7.4.1　小测验 271

7.4.2　练习 271

7.5 C++中的标准算法 272

7.5.1　例子：STL的sort算法 272

7.5.2 STL算法的例子 275

7.5.3 〈numeric〉库中的算法 276

7.5.4　例子：花样滑冰评判 277

7.5.5　小测验 278

7.6　算法正确性证明 278

7.6.1　例子：计算平均值 278

7.6.3　总结 280

7.6.2　例子：递归求幂函数 280

7.6.4　练习 281

第8章　列表 287

8.1　列表的顺序存储实现 287

8.1.1　存储结构 287

8.1.2　操作的实现 288

8.1.3　小测验 290

8.1.4　练习 290

8.2　对链表的介绍 290

8.2.1　它们是什么 291

8.2.2　实现基本列表操作 291

8.2.3 小结 294

8.2.5　练习 295

8.2.4　小测验 295

8.3　基于数组的链表实现 296

8.3.1　节点结构 296

8.3.2　存储池管理 298

8.3.3　练习 300

8.4 C++中的指针 301

8.4.1 指针 301

8.4.2　基本指针操作 303

8.4.3　指针的其他用法 309

8.4.4　小测验 310

8.4.5　练习 310

8.5 运行时分配和释放 311

8.5.1 New操作——运行时数组 312

8.5.2 delete操作 314

8.5.3　类中的运行时分配——析构函数、复制构造函数和赋值操作符 317

8.5.4 最后一点 325

8.5.5　小测验 327

8.5.6　练习 328

8.6　在C++中基于指针来实现链表 328

8.6.1 节点结构 329

8.6.2 LinkedList的数据成员 330

8.6.3 LinkedList的函数成员 330

8.6.4　练习 331

8.7.3　基本list操作 334

8.7.2　迭代器 334

8.7　标准list类模板 334

8.7.1 List 其他容器类的比较 334

8.7.4　例子：互联网地址 338

8.7.5 小测验 340

8.7.6　练习 340

第9章　其他链表结构 346

9.1　单向链表的某些变种 346

9.1.1　链式栈和链式队列 346

9.1.2　带头节点或尾节点的链表 347

9.1.3　循环链表 348

9.1.5　练习 350

9.1.4　小测验 350

9.2　稀疏矩阵的链式实现 351

练习 355

9.3 哈希表 356

9.3.1 哈希函数 356

9.3.2 冲突处理策略 356

9.3.3 改进 357

9.3.4　小测验 358

9.3.5　练习 359

9.4　双向链表和标准的C++链表 359

9.4.1　双向链表 359

9.4.2　对C++中列表的内部一瞥 360

9.4.3　应用：长整数运算 363

9.4.4　练习 367

9.5　其他多链列表 368

9.5.1 多序列表 368

9.5.2　稀疏矩阵 368

9.5.3　广义表 370

9.5.4　练习 372

第10章　二叉树 377

10.1 线性查找和折半查找的复习 377

10.1.1　线性查找 377

10.1.2　折半查找 378

10.1.3　练习 380

10.2.1　树的定义和例子 381

10.2　二叉树的介绍 381

10.2.2　二叉树的数组表示 382

10.2.3　二叉树的链表表示 383

10.3　二叉查找树 385

10.3.1　对BST的查找 385

10.3.2　在BST中插入项 386

10.3.3　例子：计算机登录验证 388

10.3.4　不平衡（Lopsidedness）问题 391

10.3.5　小测验 392

10.3.6　练习 392

10.4　作为递归数据结构的二叉树 392

10.4.1 遍历 393

10.4.2　递归查找 396

10.4.4　删除 397

10.4.3 递归插入 397

10.4.5　小测验 402

10.4.6　练习 402

10.5　二叉树的应用：哈夫曼编码 404

10.5.1　变长码 404

10.5.2　立刻可解码性 405

10.5.3　哈夫曼编码 405

10.5.4　练习 412

11.1　某些计算时间为O（n2）的排序方法 417

11.1.1　选择排序 417

第11章　排序 417

11.1.2　交换排序 419

11.1.3　排序算法的性能比较 423

11.1.4　间接排序 424

11.1.5 小测验 424

11.1.6　练习 424

11.2　堆和堆排序 426

11.2.1　堆 426

11.2.2　堆的基本操作 427

11.2.3 STL中的堆算法 430

11.2.4　堆和优先级队列 432

11.2.5 小测验 434

11.2.6　练习 434

11.3.1 拆分操作 436

11.3　快速排序 436

11.3.2　快速排序 438

11.3.3 改进 441

11.3.4　小测验 441

11.3.5　练习 441

11.4　归并排序 442

11.4.1 归并列表 443

11.4.2　折半归并排序 444

11.4.3　自然归并排序 445

11.4.4　小测验 447

11.4.5　练习 448

12.1.1　封装性 452

第12章　OOP和ADT 452

12.1 OOP和ADTs的简要历史和概览 452

12.1.2　继承性 453

12.1.3　多态性和动态联编 453

12.1.4　小测验 454

12.2　继承和面向对象设计 454

12.2.1　从OCD到OOD 454

12.2.2 OOD的第1个例子：许可证 455

12.2.3　类之间的is-a、has-a和uses-a关系 459

12.2.4 OOD的第2个例子：工资 461

12.2.5　派生类中的操作 463

12.2.6　派生类中的构造函数 463

12.2.7 OOD的第3个例子：有限栈 465

12.2.8 OOD的第4个例子：scrolls 468

12.2.9　小测验 469

12.2.1　0练习 469

12.3 多态性、虚拟函数和ADTs 470

12.3.1　联编问题 470

12.3.2　虚拟函数和动态联编 472

12.3.3　例子：栈、有限栈和Scroll 473

12.3.4　纯虚拟函数和抽象类 476

12.3.5　小测验 478

12.3.6　练习 478

12.4　异构数据结构 478

12.4.1　构建异构数据结构 479

12.4.2　虚拟函数的必要性 480

第13章　树 483

13.1　线索化二叉查找树 483

13.1.1　小测验 485

13.1.2　练习 486

13.2　平衡树：AVL树 486

13.2.1 例子：州简称的BST 487

13.2.2　基本的重新平衡旋转操作 491

13.2.3　小测验 493

13.2.4　练习 494

13.3 2-3-4树、红—黑树、B-树和其他树 494

13.3.1 2-3-4树 495

13.3.2 红—黑树 498

13.3.3　B-树 501

13.3.4　用二叉树来表示树和森林 502

13.3.5　小测验 503

13.3.6　练习 503

13.4 STL中的关联容器——map（可选） 504

小测验 507

第14章　图和有向图 509

14.1 有向图 509

14.1.1　邻接矩阵表示 510

14.1.2　邻接表表示 511

14.1.3　小测验 512

14.1.4　练习 513

14.2　搜索和遍历有向图 515

14.2.1　深度优先搜索 516

14.2.2　广度优先搜索 516

14.2.3　遍历和最短路径问题 517

14.2.4 NP完全性问题 523

14.2.5　小测验 524

14.2.6　练习 524

14.3　图 525

14.3.1　邻接矩阵和邻接表表示 526

14.3.2　边列表表示 526

14.3.3　连通性 527

14.3.4　小测验 531

14.3.5　练习 532

附录A ASCII字符集 536

附录B　数制系统 538

练习 539

附录C 基本C++ 542

C1 C++程序结构 542

C2　编译器命令 542

C3　标准库 543

C4　注释 545

C5　标识符和关键字 545

C6　基本数据类型 547

C7　常量 548

C8　声明 548

C9　运算符和表达式 548

C10　控制结构 552

C11　函数 556

C12　对象的生命周期、作用域和名字空间 560

C13　文件 562

附录D　其他C++特性 566

D1　数组、结构和联合 566

D2　流操作 567

D3　串操作 570

D4　异常 575

D5　关于函数模板的更多信息 577

D6　指针的其他应用 578

附录E　小测验答案 583

索引 594