数据结构C++语言描述 应用标准模板库 STL 第2版PDF电子书下载

第1章 数据结构入门 1

1.1 本书主要内容 1

1.2 数据结构的抽象形式 4

1.3 作为类的ADT 6

1.3.1 C++类 6

1.3.2 private和public部分 7

1.3.3 封装和信息隐藏 7

1.3.4 time24类 7

1.4 实现C++类 10

1.5 明和使用对象 14

1.6 使用嵌入码实现类 16

1.7 应用程序编程接口(API) 18

1.7.1 随机数 19

1.7.2 randomNumber API 19

1.7.3 应用程序：掷骰子游戏 21

1.8 字符串 23

1.8.1 字符串类 24

1.8.2 附加字符串函数和操作 25

1.9 本章小结 29

1.10 本章使用的类和库 30

1.11 复习题 31

1.12 书面作业 35

1.13 上机题 41

1.14 项目设计 44

第2章 对象设计技术 46

2.1 软件设计 47

2.1.1 需求和问题分析 48

2.1.2 程序设计 48

2.1.3 设计日历类 49

2.1.4 程序实现 52

2.1.5 实现日历类 52

2.1.6 程序测试与调试 54

2.1.7 程序维护 57

2.2 处理运行时错误 57

2.2.1 终止程序 57

2.2.2 设置标志 58

2.2.3 C++异常 59

2.3 对象复合 62

2.3.1 timeCard类 63

2.3.2 实现timeCard类 64

2.4 运算符重载 68

2.4.1 运算符函数 71

2.4.2 自由函数的运算符重载 72

2.4.3 友元函数的运算符重载 72

2.4.4 重载数据流I/O运算符 75

2.4.5 成员函数重载 78

2.5 本章小结 81

2.6 本章使用的类和库 82

2.7 复习题 82

2.8 书面作业 86

2.9 上机题 90

2.10 项目设计 91

第3章 算法概述 96

3.1 选择排序 97

3.2 简单查找算法 101

3.2.1 顺序查找 101

3.2.2 二分查找 103

3.3 算法分析 108

3.3.1 系统/内存性能标准 108

3.3.2 算法性能标准：时间复杂度分析 108

3.3.3 大O符号 111

3.3.4 常见数量级 112

3.4 分析查找算法 114

3.4.1 二分查找时间复杂度 114

3.4.2 查找算法比较 115

3.5 算法的通用性 118

3.5.1 模板语法 119

3.5.2 运行时模板扩展 120

3.5.3 基于模板的查找函数 122

3.6 递归的概念 123

3.6.1 实现递归函数 125

3.6.2 递归的工作方式 127

3.6.3 应用：多进制输出 129

3.7 用递归解决问题 131

3.7.1 汉诺塔 131

3.7.2 数论：最大公约数 134

3.7.3 gcd的应用：有理数 136

3.7.4 计算递归式 139

3.8 本章小结 142

3.9 本章使用的类和库 143

3.10 复习题 143

3.11 书面作业 147

3.12 上机题 153

3.13 项目设计 156

第4章 向量容器 157

4.1 STL容器类概述 158

4.2 模板类 161

4.2.1 构造模板类 161

4.2.2 声明模板类对象 163

4.3 向量类 164

4.3.1 向量容器入门 166

4.3.2 向量API 171

4.4 向量应用 173

4.4.1 合并向量 173

4.4.2 插入排序 173

4.5 本章小结 177

4.6 本章使用的类和库 178

4.7 复习题 178

4.8 书面作业 181

4.9 上机题 186

4.10 项目设计 187

第5章 指针和动态内存 188

5.1 C++指针 189

5.1.1 声明指针变量 190

5.1.2 指针赋值 190

5.1.3 用指针访问数据 191

5.1.4 数组和指针 192

5.1.5 指针和类类型 194

5.2 动态内存 196

5.2.1 内存分配运算符new 196

5.2.2 动态数组分配 198

5.2.3 内存释放运算符delete 199

5.3 使用动态内存的类 200

5.3.1 dynamicClass类 200

5.3.2 析构函数 202

5.4 赋值和初始化 204

5.4.1 赋值问题 205

5.4.2 重载的赋值运算符 206

5.4.3 指针this 207

5.4.4 初始化问题 207

5.4.5 创建复制构造函数 208

5.5 miniVector类 211

5.5.1 miniVector类的设计 212

5.5.2 分配更多的容量 214

5.5.3 miniVector的构造函数、析构函数和赋值 215

5.5.4 从miniVector对象中增加和删除元素 217

5.5.5 重载下标运算符 220

5.6 矩阵类 222

5.6.1 描述矩阵容器 223

5.6.2 实现矩阵函数 226

5.7 本章小结 227

5.8 本章中的类和库 227

5.9 复习题 228

5.10 书面作业 231

5.11 上机题 238

5.12 项目设计 239

第6章 表容器和迭代器 241

6.1 表容器 242

6.1.1 表ADT 243

6.1.2 表API 245

6.1.3 应用：表回文 246

6.2 迭代器 248

6.2.1 迭代器的概念 248

6.2.2 常量迭代器 251

6.2.3 顺序查找表 252

6.2.4 应用：词的出现频率 255

6.3 表插入和删除操作 258

6.3.1 有序表 260

6.3.2 删除重复项 262

6.3.3 合并两个表 264

6.4 实例研究：毕业生表 265

6.4.1 问题分析 265

6.4.2 程序设计 265

6.4.3 程序实现 266

6.5 本章小结 269

6.6 本章使用的类和库 270

6.7 复习题 270

6.8 书面作业 273

6.9 上机题 276

6.10 项目设计 279

第7章 栈 281

7.1 栈ADT 282

7.1.1 多进制输出 285

7.1.2 分解栈元素 288

7.2 递归代码和运行栈 291

7.3 栈的实现 294

7.3.1 miniStack类的实现 296

7.3.2 STL stack类的实现(选学) 297

7.4 后缀表达式 299

7.4.1 后缀计算 300

7.4.2 postfixEval类 301

7.5 实例研究：中缀表达式计算 307

7.5.1 中缀表达式的特征 307

7.5.2 中缀到后缀的转换：算法设计 308

7.5.3 中缀转换为后缀：对象设计 312

7.5.4 infix2Postfix类的实现 314

7.6 本章小结 318

7.7 本章使用的类 319

7.8 复习题 320

7.9 书面作业 323

7.10 上机题 328

7.11 项目设计 328

第8章 队列和优先级队列 330

8.1 队列 ADT 331

8.2 基数排序 335

8.3 实现miniQueue类 339

8.4 实例研究：时间驱动的模拟 343

8.4.1 模拟程序设计 343

8.4.2 模拟程序的具体实现 344

8.5 用数组实现队列 349

8.5.1 设计有界队列 351

8.5.2 有界队列的实现 353

8.6 优先级队列 354

8.6.1 优先级队列ADT 355

8.6.2 优先级队列排序 357

8.6.3 公司内的支持服务 358

8.7 本章小结 362

8.8 本章使用的类和库 363

8.9 复习题 363

8.10 书面作业 367

8.11 上机题 371

8.12 项目设计 373

第9章 链表 376

9.1 链表结点 378

9.1.1 链表结点类 378

9.1.2 添加和删除结点 381

9.2 建立链表 382

9.2.1 定义单向链表 382

9.2.2 在链表表头插入结点 384

9.2.3 在链表表头删除结点 385

9.2.4 删除特定的结点 386

9.3 处理链表表尾 389

9.4 用链表实现队列 393

9.4.1 linkedQueue类 393

9.4.2 实现linkedQueue类 395

9.5 双向链表 398

9.5.1 dnode对象 399

9.5.2 双向循环链表 401

9.6 更新双向链表 403

9.6.1 insert()函数 404

9.6.2 erase()函数 405

9.7 约瑟夫问题 409

9.8 miniList类 411

9.8.1 miniList类的私有成员 412

9.8.2 miniList类的构造函数和析构函数 413

9.8.3 处理表两端元素的函数 414

9.8.4 miniList的迭代器 415

9.8.5 miniList类成员函数begin()和end() 417

9.8.6 miniList类的通用插入函数 418

9.9 选择顺序容器 419

9.10 本章小结 419

9.11 本章使用的类和库 421

9.12 复习题 421

9.13 书面作业 427

9.14 上机题 430

9.15 项目设计 431

第10章 二叉树 434

10.1 树结构 435

10.1.1 术语 436

10.1.2 二叉树 437

10.2 二叉树结点 440

10.3 二叉树遍历算法 443

10.3.1 递归的树遍历 443

10.3.2 迭代层次遍历 446

10.4 使用树遍历算法 450

10.4.1 叶结点计数 450

10.4.2 计算树的深度 450

10.4.3 复制二叉树 453

10.4.4 删除树结点 456

10.4.5 显示二叉树 457

10.5 二叉搜索树 458

10.5.1 二叉搜索树概述 459

10.5.2 创建二叉搜索树 459

10.5.3 二叉搜索树中的数据查找 460

10.5.4 二叉搜索树的删除 461

10.5.5 二叉搜索树类 462

10.5.6 访问和更新操作 463

10.6 二叉搜索树的应用 467

10.6.1 应用：消除重复项 467

10.6.2 应用：录像带商店 469

10.7 stree类的实现 474

10.7.1 stree类数据成员 475

10.7.2 构造函数、析构函数和赋值运算符 475

10.7.3 更新操作 476

10.7.4 二叉搜索树的算法复杂度 483

10.8 stree迭代器(选学) 483

10.9 本章小结 488

10.10 本章使用的类和库 489

10.11 复习题 489

10.12 书面作业 494

10.13 上机题 497

10.14 项目设计 499

第11章 关联容器 503

11.1 关联容器概述 503

11.1.1 关联容器的种类 504

11.1.2 STL关联容器 506

11.1.3 实现关联容器 506

11.2 集合 507

11.2.1 使用迭代器显示容器元素 508

11.2.2 集合的访问和更新函数 508

11.2.3 简单的拼写检查程序 511

11.2.4 应用：埃拉托斯特尼筛法 514

11.2.5 集合运算 517

11.2.6 应用：更新计算机账号 520

11.3 映射 522

11.3.1 map类接口 523

11.3.2 映射的操作函数 525

11.3.3 映射的下标运算符 526

11.3.4 实例学习：单词统计 529

11.4 多重集 534

11.5 实现集合和映射 538

11.5.1 实现miniSet的操作函数 539

11.5.2 miniMap类 540

11.5.3 实现miniMap类 542

11.5.4 miniMap的下标运算符 543

11.6 本章小结 543

11.7 本章使用的类和库 544

11.8 复习题 545

11.9 书面作业 548

11.10 上机题 551

11.11 项目设计 552

第12章 高级关联结构 555

12.1 哈希法 557

12.2 设计哈希函数 559

12.2.1 函数对象 559

12.2.2 函数对象举例 561

12.2.3 整型哈希函数 563

12.2.4 字符串哈希函数 564

12.2.5 定制哈希函数 565

12.3 哈希表 566

12.3.1 线性探测开放寻址法 566

12.3.2 独立表链地址法 568

12.4 hash类 569

12.4.1 应用：使用哈希表 571

12.4.2 hash类的实现 574

12.4.3 实现哈希迭代器 577

12.4.4 无序关联容器 580

12.5 哈希表的性能 581

12.6 2-3-4树 586

12.6.1 2-3-4树的插入算法 588

12.6.2 2-3-4树操作函数的时间复杂度 591

12.7 红黑树 592

12.7.1 红黑树的属性 593

12.7.2 向红黑树中添加结点 595

12.7.3 构造红黑树 599

12.7.4 查找算法的时间复杂度(选学) 601

12.7.5 从红黑树中删除结点 602

12.8 rbtree类 603

12.8.1 rbtree类的私有部分 606

12.8.2 拆分4-结点 606

12.8.3 insert()操作函数 608

12.9 本章小结 609

12.10 本章用到的类和库 610

12.11 复习题 610

12.12 书面作业 615

12.13 上机题 621

12.14 项目设计 623

第13章 继承和抽象类 625

13.1 C++中的继承 626

13.1.1 明员工层次关系 628

13.1.2 派生类的构造函数 631

13.1.3 实现成员函数 632

13.2 图形层次 635

13.2.1 circleShape类 637

13.2.2 其他图形类和文本类 639

13.2.3 polyShape类的实现 641

13.3 图形系统 644

13.4 安全向量 647

13.5 有序表 649

13.6 多态属性和虚函数 651

13.6.1 动态绑定 653

13.6.2 应用：用多态性机制编写支付员工薪金的程序 655

13.6.3 C++的多态实现 657

13.6.4 虚函数和析构函数 659

13.7 抽象类 661

13.7.1 抽象类接口 662

13.7.2 栈接口 662

13.8 本章小结 663

13.9 本章使用的类和库 664

13.10 复习题 664

13.11 书面作业 669

13.12 上机题 675

13.13 项目设计 677

第14章 堆、2进制文件和位组 679

14.1 基于数组的二叉树 680

14.2 堆 681

14.2.1 堆的插入操作 682

14.2.2 从堆中删除元素 684

14.2.3 堆排序 688

14.2.4 向量堆化 691

14.3 优先级队列的实现 693

14.4 2进制文件 696

14.4.1 文件结构 696

14.4.2 直接读写文件 697

14.4.3 读写2 进制文件 698

14.4.4 应用：银行账户记录 698

14.5 位组 702

14.5.1 bitVector类 703

14.5.2 实现bitVector类 706

14.6 实例研究：霍夫曼压缩 709

14.6.1 创建霍夫曼树 712

14.6.2 霍夫曼压缩的实现 714

14.6.3 霍夫曼解压缩 720

14.7 本章小结 722

14.8 本章使用的类和库 724

14.9 复习题 724

14.10 书面作业 728

14.11 上机题 735

14.12 项目设计 738

第15章 递归算法 740

15.1 分而治之算法 741

15.1.1 创建标尺 741

15.1.2 并排序 743

15.1.3 快速排序 750

15.1.4 排序算法的比较 758

15.1.5 应用：搜索第k大的元素 760

15.2 组合学 762

15.2.1 查找所有子集 763

15.2.2 排列 766

15.3 动态编程 769

15.3.1 自顶向下的动态编程 770

15.3.2 应用：组合 772

15.3.3 自底向上动态编程 774

15.3.4 背包问题 775

15.4 回溯法：八皇后问题 782

15.4.1 问题分析 783

15.4.2 程序设计 785

15.4.3 显示棋盘 788

15.4.4 八皇后问题实例分析 789

15.5 本章小结 790

15.6 本章使用的类和库 791

15.7 复习题 792

15.8 书面作业 797

15.9 上机题 800

15.10 项目设计 804

第16章 图 807

16.1 图论术语 808

16.1.1 有向图 809

16.1.2 加权图 810

16.2 图类 810

16.2.1 图的API清单 810

16.2.2 图的表示 815

16.3 图类设计 816

16.3.1 顶点信息表示 817

16.3.2 顶点映射和Vinfo表 818

16.3.3 图类声明 821

16.3.4 图类的实现 822

16.4 图的遍历算法 826

16.4.1 广度优先搜索算法 827

16.4.2 深度优先访问算法 830

16.4.3 深度优先搜索 834

16.5 图遍历的应用 835

16.5.1 无环图 835

16.5.2 拓扑排序 838

16.5.3 强连通分量 841

16.6 图的最小化算法 845

16.6.1 最短路径算法 845

16.6.2 Dijkstra最小路径算法 849

16.6.3 最小生成树 855

16.7 本章小结 862

16.8 本章使用的类和库 862

16.9 复习题 863

16.10 书面作业 865

16.11 上机题 873

16.12 项目设计 874