数据结构与STLPDF电子书下载

第1章 C+中的类 1

1.1 类 1

1.1.1 方法接口 1

1.1.2 对象 2

1.1.3 数据抽象 4

1.1.4 构造器 6

1.1.5 一个Employee类 7

1.1.6 Employee类的定义 11

实验1：Company项目 13

1.1.7 继承 13

1.1.8 受保护的访问 14

1.1.9 HourlyEmployee类 15

实验2：关于继承的更多的细节 18

1.1.10 运算符的重载 19

1.1.11 友元 20

实验3：重载运算符“=”和运算符“＞＞” 21

1.1.12 信息隐藏 21

总结 22

习题 22

编程项目1.1：一个Sequence类 25

第2章 容器类的存储结构 27

2.1 指针 27

2.1.1 堆和堆栈的对比 29

2.1.2 引用参数 29

2.1.3 指针字段 30

2.1.4 数组和指针 30

实验4：指针变量赋值与动态变量赋值的对比 31

2.1.5 动态变量的存储空间释放 31

2.2 数组 32

2.3 容器类 33

2.3.1 容器类的存储结构 33

2.3.2 链式结构 34

2.3.3 迭代器 37

2.3.4 Iterator类的设计和实现 39

实验5：定义其他的迭代器运算符 40

2.3.5 pop_front方法 40

2.3.6 析构器 41

实验6：重载运算符operator= 42

2.3.7 通用型算法 42

实验7：更多关于通用型算法的知识 46

2.3.8 数据结构和标准模板库 46

总结 46

习题 47

编程项目2.1：扩展Linked类 47

第3章 软件工程简介 49

3.1 软件开发生命周期 49

3.2 问题分析 49

3.3 程序设计 51

3.3.1 方法接口和字段 51

3.3.2 依赖关系图 53

3.4 程序实现 54

3.4.1 方法验证 55

实验8：驱动器 56

3.4.2 正确性实现的可行性 56

3.4.3 方法效率评估 56

3.4.4 大O表示法 57

3.4.5 快速获取大O估算 59

3.4.6 平衡折中 62

3.4.7 运行时间分析 63

3.4.8 随机性 65

实验9：计时和随机性 66

3.4.9 类型转换 66

3.5 程序维护 67

总结 67

习题 67

编程项目3.1：Linked类的进一步扩充 69

第4章 递归 71

4.1 简介 71

4.2 阶乘 71

4.3 十进制到二进制的转换 75

实验10：斐波纳契数 78

4.4 汉诺塔 78

4.5 回溯 86

4.6 折半查找 97

实验11：迭代折半查找 106

4.7 生成置换 106

4.8 间接递归 114

4.9 递归的代价 115

总结 116

习题 116

编程项目4.1：汉诺塔的迭代版本 121

编程项目4.2：八皇后问题 122

编程项目4.3：马的遍历问题 123

第5章 向量和双端队列 127

5.1 标准模板库 127

5.2 向量 128

5.2.1 vector类的方法接口 129

5.2.2 向量迭代器 134

5.2.3 向量和其他容器的对比 136

5.2.4 vector类可能的字段 137

5.2.5 vector类的一个实现 137

实验12：vector类的更多的实现细节 142

5.3 向量的一个应用：高精度算法 142

5.3.1 very_long_int类的设计 143

5.3.2 very_long_int类的一个实现 144

实验13：扩展very_long_int类 147

5.4 双端队列 147

实验14：惠普的deque类实现的更多细节 154

5.5 双端队列的一个应用：非常长的整数 154

总结 154

习题 155

编程项目5.1：扩展very_long_int类 157

编程项目5.2：deque类的另一种实现 157

第6章 表 159

6.1 表 159

6.1.1 list类的方法接口 160

6.1.2 迭代器接口 163

6.1.3 链表方法和向量或双端队列方法的差别 165

6.1.4 list类的字段和实现 166

6.1.5 list节点的存储 171

实验15：更多list类的实现细节 174

实验16：计时顺序容器 174

实验17：迭代器，第二部分 174

6.1.6 list类的其他实现 175

6.2 链表应用：一个行编辑器 177

6.2.1 Editor类的设计 180

6.2.2 Editor。类的实现 182

总结 187

习题 187

编程项目6.1：扩展Editor类 189

编程项目6.2：list类的另一种设计和实现 195

第7章 队列和堆栈 197

7.1 队列 197

7.1.1 queue类的方法接口 197

7.1.2 使用queue类 200

7.1.3 容器配接器 201

7.1.4 一个接近的设计 202

7.2 计算机仿真 204

7.3 队列应用：洗车仿真 205

7.3.1 程序设计 207

7.3.2 CarWash类的实现 208

7.3.3 CarWash方法的分析 212

7.3.4 随机化到达时间 212

实验18：随机化到达时间 214

7.4 堆栈 214

7.4.1 Stack类的方法接口 214

7.4.2 使用stack类 215

7.4.3 stack类是一个容器配接器 216

7.5 堆栈应用1：递归是如何实现的 216

7.6 堆栈应用2：将中缀转换成后缀 222

7.6.1 后缀表示法 224

7.6.2 转换矩阵 226

7.6.3 记号 227

实验19：将中缀转化成后缀 228

7.6.4 前缀表示法 228

总结 230

习题 231

编程项目7.1：扩展洗车仿真 232

编程项目7.2：求一个条件的值 233

编程项目7.3：一个迭代的迷宫搜索 237

编程项目7.4：queue类的另一个设计 237

第8章 二叉树和折半查找树 239

8.1 定义和属性 239

8.1.1 二叉树定理 245

8.1.2 外部路径长度 247

8.1.3 二叉树的遍历 248

8.2 折半查找树 253

8.2.1 BinSearchTree类 254

8.2.2 BinSearchTree类的Iterator类 255

8.2.3 BinSearchTree类的字段和实现 257

8.2.4 递归方法 261

8.2.5 BinSearchIree迭代器 269

实验20：BinSearchTree的平均高度 270

总结 270

习题 271

编程项目8.1：BinSearchTree类的另一种实现 274

第9章 AVL树 277

9.1 平衡的折半查找树 277

9.2 旋转 277

9.3 AVL树 281

9.3.1 AVL树的高度 282

9.3.2 函数对象 284

实验21：更多的函数对象的细节 286

9.3.3 AVLTree类 286

9.3.4 fixAfterInsertion方法 289

9.3.5 insert方法的正确性 297

9.4 AVL树的应用：一个简单的拼写检查器 299

总结 302

习题 302

编程项目9.1：AVLTree类的erase方法 305

编程项目9.2：改进的SpellChecker项目 305

第10章 红黑树 307

10.1 红黑树 307

10.1.1 红黑树的高度 310

10.1.2 惠普的rb_tree类 313

10.1.3 rb_tree类中的insert方法 315

实验22：使用全部三种情况的红黑树插入 320

10.1.4 erase方法 320

实验23：erase的调用，其中应用了全部四种情况 331

10.2 标准模板库的关联容器 331

10.3集合应用：再次讨论拼写检查器 334

10.3.1 multiset类 335

实验24：更多与set和multiset类相关的知识 336

10.3.2 map类 336

10.3.3 multimap类 339

实验25：更多与map和multimap类相关的知识 340

总结 340

习题 340

编程项目10.1：一个简单的辞典 343

编程项目10.2：创建一个词汇索引 343

第11章 优先队列和堆 347

11.1 介绍 347

11.1.1 priority_queue类 348

11.1.2 priority_queue类的字段和实现 350

11.1.3 堆 351

实验26：优先队列中的公平性 359

11.1.4 priority_queue类的另一种设计及实现 359

11.2 优先队列的应用：霍夫曼编码 360

11.2.1 huffman类的设计 364

11.2.2 huffman类的实现 366

总结 371

习题 372

编程项目11.1：解码一个消息 374

第12章 排序 377

12.1 介绍 377

12.2 排序能有多快 380

12.3 快速排序 382

12.3.1 树排序 382

12.3.2 堆排序 383

12.3.3 归并排序 385

12.3.4 快速排序 390

12.3.5 分治法算法 395

实验27：排序算法的运行时间 396

总结 396

习题 397

编程项目12.1：排序一个文件 402

第13章 查找和散列类 405

13.1 分析查找的框架 405

13.2 查找方式复习 405

13.2.1 顺序查找 405

13.2.2 折半查找 406

13.2.3 红黑树查找 408

13.3 hash_map类 408

13.3.1 hash_map类中的字段 409

13.3.2 散列 409

13.3.3 链式 412

13.3.4 iterator类的字段和实现 419

13.3.5 hash_map类的实现 420

13.3.6 链式散列分析 423

13.3.7 value_type类 425

13.3.8 应用 425

实验28：hash_map计时 427

13.4 hash_set类 427

13.5 开放地址散列 427

13.5.1 erase方法 430

13.5.2 主聚类 434

13.5.3 双散列 435

13.5.4 开放地址散列分析 439

总结 441

习题 442

编程项目13.1：使用链式和双散列构造一个符号表的运行时间比较 444

第4章 图、树和网络 445

14.1 无向图 445

14.2 有向图 447

14.3 树 448

14.4 网络 450

14.5 图算法 451

14.5.1 迭代器 451

14.5.2 连通性 457

14.5.3 产生最小生成树 458

14.5.4 寻找网络中的最短路径 462

14.6 开发一个网络类 465

14.7 network类 465

14.7.1 network类中的字段 467

14.7.2 network类的实现 469

14.7.3 与边相关的方法的实现 470

14.7.4 全局方法的实现 472

14.7.5 get_minimum_spanning_tree方法 475

14.7.6 get_shortest_path方法 476

14.7.7 网络方法的时间花费估算 478

实验29：货郎担问题 479

14.7.8 network类的另一种设计和实现 479

14.8 回溯通过网络 481

总结 483

习题 484

编程项目14.1：完成邻接矩阵的实现 486

编程项目14.2：回溯通过一个网络 486

附录1 数学背景 489

附录2 string类 501

附录3 多态性 511

参考文献 515

索引 517