数据结构：C++版PDF电子书下载

7.5 堆栈应用：后缀表达式计算器 38 1

目 录 1

7.2.7出栈 36 1

1.1软件的生命周期 1

第1章软件工程基本原理和C++类 1

1.2软件开发阶段 2

1.2.1 分析阶段 2

1.2.2设计阶段 2

1.2.3实现阶段 3

1.2.4测试和调试 5

1.3 算法分析：大O表示法 6

1.4类 12

1.4.1统一建模语言图 15

1.4.2变量（对象）的声明 15

1.4.3访问类的成员 16

1.4.4类的内置运算 17

1.4.5赋值运算符和类 17

1.4.6类的作用域 17

1.4.7函数和类 18

1.4.8引用参数和类对象（变量） 18

1.4.9成员函数的实现 19

1.4.10构造函数 23

1.4.1 1调用构造函数 26

1.4.12构造函数和默认参数 26

1.4.13析构函数 27

1.4.14结构 27

1.5数据抽象、类和抽象数据类型 27

1.6编程示例：糖果机 36

1.6.2收银机 36

1.6.1 问题分析和算法设计 36

1.6.3控制装置 38

1.6.4主程序 40

1.8快速回顾 45

1.7标识类、对象和操作 45

1.9练习题 47

1.10编程练习 51

第2章 面向对象的设计方法和C++ 54

2.1 继承 54

2.1.1重新定义基类的成员函数 57

2.1.2派生类与基类的构造函数 58

2.1.3派生类的头文件 64

2.1.4头文件的多重包含 64

2.1.6三种继承方式：公有继承，保护继承或私有继承 66

2.1.5类的保护成员 66

2.2聚合 67

2.3 多态：运算符和函数重载 71

2.4运算符重载 71

2.4.1为什么要重载运算符 71

2.4.2运算符重载 72

2.4.5 this指针 73

2.4.4重载运算符的限制 73

2.4.3运算符函数的语法 73

2.4.6类的友元函数 77

2.4.7定义友元函数 77

2.4.8运算符函数的两种形式：成员函数和非成员函数 80

2.5重载二元运算符 81

2.5.1 重载二元运算符（算术运算符和关系运算符）为成员函数 81

2.5.2重载二元运算符（算术运算符和关系运算符）为非成员函数 83

2.5.4重载输出运算符（＜＜） 84

2.5.3重载输出（＜＜）和输入（＞＞）运算符 84

2.5.5重载输入运算符（＞＞） 85

2.5.6重载运算符形式的选择：成员函数和非成员函数 87

2.6编程示例：复数 87

2.7 函数重载 92

2.8模板 92

2.8.1函数模板 93

2.8.2类模板 95

2.8.3头文件和类模板的实现文件 97

2.9快速回顾 97

2.1 0练习题 99

2.11 编程练习 109

第3章指针和基于数组的表 113

3.1指针数据类型和指针变量 113

3.1.1声明指针变量 113

3.1.2取地址运算符（ ） 114

3.1.3取值运算符（*） 115

3.1.4类、结构和指针变量 120

3.1.6动态变量 123

3.1.5初始化指针变量 123

3.1.7指针变量的运算 125

3.2 动态数组 126

3.2.1 函数和指针 128

3.2.2指针和函数返回值 128

3.3 浅复制、深复制与指针 129

3.4类和指针：一些特例 131

3.4.1析构函数 132

3.4.2赋值运算符 133

3.4.3重载赋值运算符 135

3.4.4复制构造函数 138

3.5 重载数组索引（下标）运算符（［］） 144

3.6编程示例：newString 145

3.7基于数组的表 151

3.7.1复制构造函数 160

3.7.2重载赋值运算符 161

3.7.3搜索 161

3.7.4插入 163

3.7.5删除 163

3.7.6各种表操作的时间复杂度 164

3.8编程示例：多项式的运算 168

3.9快速回顾 175

3.10练习题 177

3.11 编程练习 182

第4章标准模板类库 185

4.1 STL的组成部分 185

4.2顺序容器：向量容器 186

4.1.2顺序容器 186

4.1.1容器类型 186

4.2.1 声明vector对象 187

4.2.2为向量容器声明一个迭代器 189

4.2.3 容器以及begin和end函数 190

4.2.4对所有容器通用的成员函数 193

4.2.5顺序容器公共的成员函数 194

4.2.6 copy算法 194

4.2.7 ostream迭代器和copy函数 196

4.3顺序容器：双端队列 198

4.4迭代器 201

4.4.1迭代器的类型 202

4.4.3输出迭代器 202

4.4.2输入迭代器 202

4.4.5双向迭代器 203

4.4.6随机访问迭代器 203

4.4.4前向迭代器 203

4.4.7流迭代器 205

4.5编程示例：成绩报告单 206

4.5.1 问题分析与算法设计 208

4.5.2 主程序 219

4.5.3程序清单 221

4.6快速回顾 226

4.7练习题 227

4.8 编程练习 231

5.1 链表 234

第5章链表 234

5.2链表的属性 236

5.3项的插入和删除 239

5.3.1 插入 239

5.3.2删除 241

5.4构建链表 243

5.4.1 正向构建链表 243

5.4.2反向构建链表 247

5.5 ADT链表 248

5.5.1默认构造函数 251

5.5.3初始化表 252

5.5.2销毁表 252

5.5.4重载输出运算符 253

5.5.5表的长度 253

5.5.6检索第一个节点的数据 253

5.5.7检索最后一个节点的数据 254

5.5.8搜索表 254

5.5.9在表头插入节点 255

5.5.11删除节点 256

5.5.10在表尾插入节点 256

5.5.12复制表 261

5.5.13析构函数 262

5.5.14复制构造函数 262

5.5.15重载赋值运算符 263

5.6有序链表 264

5.6.1 搜索表 265

5.6.2插入节点 266

5.6.3删除节点 270

5.6.4有序链表的头文件 271

5.7双向链表 273

5.7.1默认构造函数 276

5.7.2 isEmptyList 276

5.7.4 初始化表 277

5.7.5表的长度 277

5.7.3 销毁表 277

5.7.7反向打印表 278

5.7.6重载输出运算符 278

5.7.8 搜索表 279

5.7.9第一个和最后一个元素 279

5.7.10插入节点 280

5.7.11删除节点 282

5.8 STL顺序容器：list 284

5.9带有头节点和尾节点的链表 289

5.10循环链表 290

5.11 编程示例：Video Store 291

5.12 快速回顾 309

5.13练习题 310

5.14编程练习 315

第6章递归 319

6.1递归的定义 319

6.1.1直接递归和间接递归 321

6.1.2无穷递归 321

6.2递归法解决问题 322

6.3递归还是迭代 337

6.4递归和回溯：n－皇后问题 338

6.4.1回溯 338

6.4.2回溯和4皇后问题 340

6.4.3 8皇后问题 341

6.5 快速回顾 345

6.6练习题 346

6.7 编程练习 348

第7章堆栈 353

7.1 堆栈 353

7.2使用数组实现堆栈 355

7.2.1初始化堆栈 358

7.2.5入栈 359

7.2.4满堆栈 359

7.2.3空堆栈 359

7.2.2销毁堆栈 359

7.2.6返回栈顶元素 361

7.2.8复制堆栈 362

7.2.9构造函数和析构函数 363

7.2.10复制构造函数 364

7.2.1 1 重载赋值运算符（＝） 364

7.2.12堆栈的头文件 365

7.3 编程示例：求最高GPA 366

7.4堆栈的链表实现 370

7.4.1默认构造函数 372

7.4.3初始化堆栈 373

7.4.2销毁堆栈 373

7.4.4入栈 374

7.4.5返回栈顶元素 377

7.4.6出栈 377

7.4.7 由类linkedListType派生而来的堆栈 379

7.5.1 主算法 385

7.5.2完整的程序清单 387

7.6消除递归：反向打印一个链表的非递归算法 391

7.7 STL堆栈类（堆栈容器适配器） 396

7.8快速回顾 398

7.9练习题 398

7.10编程练习 402

第8章队列 404

8.1 队列 404

8.1.1 队列操作 404

8.1.2队列的数组实现 405

8.2队列的链式实现 416

8.3 从类linkedListType派生而来的队列 420

8.4 STL类queue（队列容器适配器） 423

8.5优先级队列 425

8.6队列的应用：模拟 426

8.6.1设计队列系统 427

8.6.2客户 427

8.6.3 服务器 430

8.6.4服务器表 433

8.6.5等待客户的队列 438

8.6.6 主程序 440

8.7快速回顾 447

8.8练习题 447

8.9编程练习 451

第9章搜索算法 453

9.1 搜索算法 453

9.1.1 顺序搜索 456

9.1.2顺序搜索算法分析 457

9.1.3有序表 458

9.1.4折半搜索 459

9.1.5折半搜索算法的性能 462

9.1.6将数据项插入到一个有序表 463

9.2基于比较的搜索算法的下限 465

9.3 散列算法 466

9.3.1 散列函数：示例 467

9.3.2冲突解决 467

9.3.3 冲突解决：开型寻址法 467

9.3.4二次探测 469

9.3.5 删除：开型寻址法 472

9.3.6散列法：使用二次探测来实现 473

9.3.7冲突解决：链地址法（开散列方法） 476

9.3.8散列法性能分析 477

9.4快速回顾 478

9.5 练习题 480

9.6编程练习 481

第10章排序算法 484

10.1 排序算法 484

10.2选择排序：基于数组的表 484

10.3插入排序：基于数组的表 490

10.4插入排序：基于链表的表 495

10.5基于比较的排序算法的下限 499

10.6快速排序：基于数组的表 500

10.7归并排序：基于链表的表 505

10.7.1划分 507

10.7.2归并 509

10.7.3分析：归并排序 512

10.8堆排序：基于数组的表 512

10.8.1 构建堆 513

10.8.2分析：堆排序 520

10.9再论优先级队列 520

10.9.1在优先级队列中插入一个元素 521

10.9.2从优先级队列删除一个元素 521

10.10编程示例：选举结果 521

10.10.1 问题分析和算法设计 522

10.10.2主程序 528

10.10.3对姓名排序 530

10.10.4处理投票数据 532

10.10.5计算选票数的总和 534

10.10.6打印标题和结果 534

10.11 快速回顾 538

1 0.1 2 练习题 539

10.13编程练习 540

第1 1章二叉树 543

11.1 二叉树 543

11.2二叉树的遍历 549

11.2.1 中序遍历 549

11.2.2前序遍历 549

11.2.3 后序遍历 549

11.2.4二叉树的实现 552

11.3 二叉搜索树 560

11.3.1 search函数 562

11.3.2 Insert函数 564

11.3.3 Delete函数 565

11.4二叉搜索树分析 572

11.5 二叉树的非递归遍历算法 573

11.5.1 非递归中序遍历 573

11.5.2非递归前序遍历 574

11.5.3非递归后序遍历 576

11.6 二叉树遍历和作为参数的函数 577

11.7 AVL（平衡）树 580

11.7.1 AVL树的插入操作 582

11.7.2 AVL树的旋转 587

11.7.3 AVL树的删除操作 598

11.7.4 AVL树的性能分析 599

11.8 编程示例：Video Store 600

11.9快速回顾 608

11.10练习题 609

11.1 1编程练习 612

第12章图 614

12.1 初识图 614

12.2 图的定义和符号 615

12.3 图的表示方法 617

12.3.1邻接矩阵 617

12.3.2邻接表 618

12.4 图的操作 619

12.6 图的ADT定义 620

12.5 回顾模板 620

12.7 图的遍历 624

12.7.1深度优先遍历 624

12.7.2 广度优先遍历 626

12.8最短路径算法 628

12.9最小生成树 634

12.10拓扑排序 641

12.11快速回顾 647

12.12练习题 648

12.1 3 编程练习 650

13.1 pair类 652

第1 3章标准模板库（STL）Ⅱ 652

13.1.1 比较pair类型的对象 654

13.1.2 pair类型和make pair函数 654

13.2关联容器 656

13.2.1关联容器：集合和多重集合 657

13.2.2关联容器：映射和多重映射 661

13.3 容器、相关头文件和迭代器支持 666

13.4算法 666

13.5 STL算法分类 667

13.5.1非修改算法 667

13.5.2修改算法 667

13.5.4堆算法 668

13.5.3数值算法 668

13.5.5函数对象 669

13.5.6谓词 674

13.5.7插入迭代器 674

1 3.6 STL算法 676

13.6.1 fill和filn函数 676

13.6.2 generate和generate_n函数 678

13.6.3 find、find if、find end和find first of函数 679

13.6.4 remove、remove_if、remove_copy和remove_copy_if函数 681

13.6.5 replace、replace_if、replace_copy和replace_copy_if函数 685

13.6.6 swap、iter_swap和swap_ranges函数 687

13.6.7 search、search n、sort和binary search函数 690

13.6.8 adjacent_find、merge和inplace_merge函数 694

13.6.9 reverse、reverse_copy、rotate、rotate_copy函数 696

13.6.10 count、count if、max、max element、min、min element和random shuffle函数 699

13.6.1l for each和transform函数 702

13.6.12 includes、set_intersection、set_union、set_difference和set_symmetric_difference函数 705

13.6.13 accumulate、adjacent_difference、inner_product和partial_sum函数 713

13.7快速回顾 718

13.8 练习题 720

13.9编程练习 722

附录A保留字 724

附录B运算符优先级 725

附录C字符集 726

附录D 运算符重载 728

E.1 头文件cassert 729

E.2头文件cctype 729

附录E头文件 729

E.3 头文件cmath 730

E.4头文件cstddef 731

E.5 头文件cstring 731

E.6头文件string 732

附录F其他C++主题 734

F.1继承、指针和虚函数 734

F.2类和虚析构函数 740

F.3取地址运算符和类 740

G.1数据类型 744

附录G针对JAVA程序员的C++介绍 744

G.2名称常量、变量以及赋值语句 745

G.3预处理指令 746

G.4 C++程序 746

G.5输入和输出 747

G.6控制结构 756

G.7命名空间 757

G.8函数及其参数 761

G.9数组 765

附录H参考文献 768

附录I精选习题答案 769