数据马克·艾伦·维斯人民邮电出版社9787115580924 语言程序设计高等学校教材英文 下载 pdf 百度网盘 epub 免费 2025 电子版 mobi 在线

暂无相关简介，正在全力查找中！

Chapter 1 Programming: A General Overview / 第 1章 程序设计：概述 1

1.1 What's This Book About / 本书讨论的内容 1

1.2 Mathematics Review / 数学知识复 2

1.2.1 Exponents / 指数 3

1.2.2 Logarithms / 对数 3

1.2.3 Series / 级数 4

1.2.4 Modular Arithmetic / 模运算 5

1.2.5 The P Word / 证明方法 6

1.3 A Brief Introduction to Recursion / 递归简论 8

1.4 C++ Classes / C类 12

1.4.1 Basic class Syntax / 基本的class语法 12

1.4.2 Extra Constructor Syntax and Accessors / 构造函数的附加语法和访问函数 13

1.4.3 Separation of Interface and Implementation / 接口与实现的分离 16

1.4.4 vector and string / vector类和string类 19

1.5 C++Details / C细节 21

1.5.1 Pointers / 指针 21

1.5.2 Lvalues, Rvalues, and References / 左值、右值和引用 23

1.5.3 Parameter Passing / 参数传递 25

1.5.4 Return Passing / 返回值传递 27

1.5.5 std::swap and std::move / std::swap和std::move 29

1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= / 五大函数：析构函数、拷贝构造函数、移动构造函数、拷贝赋值operator=和移动赋值operator= 30

1.5.7 C-style Arrays and Strings / C风格数组和字符串 35

1.6 Templates / 模板 36

1.6.1 Function Templates / 函数模板 37

1.6.2 Class Templates / 类模板 38

1.6.3 Object, Comparable, and an Example / Object、Comparable和一个例子 39

1.6.4 Function Objects / 函数对象 41

1.6.5 Separate Compilation of Class Templates / 类模板的分离式编译 44

1.7 Using Matrices / 使用矩阵 44

1.7.1 The Data Members, Constructor, and Basic Accessors / 数据成员、构造函数和基本访问函数 44

1.7.2 operator[] / operator[] 45

1.7.3 Big-Five / 五大函数 46

Summary / 小结 46

Exercises / 练 46

References / 参考文献 48

Chapter 2 Algorithm Analysis / 第 2章 算法分析 51

2.1 Mathematical Background / 数学基础 51

2.2 Model / 模型 54

2.3 What to Analyze / 要分析的问题 54

2.4 Running-Time Calculations / 运行时间计算 57

2.4.1 A Simple Example / 一个简单的例子 58

2.4.2 General Rules / 一般法则 58

2.4.3 Solutions for the Maximum Subsequence Sum Problem / 大子序列和问题的求解 60

2.4.4 Logarithms in the Running Time / 运行时间中的对数 66

2.4.5 Limitations of Worst-Case Analysis / 坏情形分析的局限 70

Summary / 小结 70

Exercises / 练 71

References / 参考文献

76

Chapter 3 Lists, Stacks, and Queues / 第3章 表、栈和队列 77

3.1 Abstract Data Types (ADTs) / 抽象数据类型 77

3.2 The List ADT / 表的抽象数据类型 78

3.2.1 Simple Array Implementation of Lists / 表的简单数组实现 78

3.2.2 Simple Linked Lists / 简单链表 79

3.3 vector and list in the STL / STL中的vector和list 80

3.3.1 Iterators / 迭代器 82

3.3.2 Example: Using erase on a List / 例子：对表使用erase 83

3.3.3 const_iterators / const_iterators 84

3.4 Implementation of vector / vector的实现 86

3.5 Implementation of list / list的实现 91

3.6 The Stack ADT / 栈的抽象数据类型 103

3.6.1 Stack Model / 栈模型 103

3.6.2 Implementation of Stacks / 栈的实现 104

3.6.3 Applications / 应用 104

3.7 The Queue ADT / 队列的抽象数据类型 112

3.7.1 Queue Model / 队列模型 113

3.7.2 Array Implementation of Queues / 队列的数组实现 113

3.7.3 Applications of Queues / 队列的应用 115

Summary / 小结 116

Exercises / 练 116

Chapter 4 Trees / 第4章 树 121

4.1 Preliminaries / 预备知识 121

4.1.1 Implementation of Trees / 树的实现 122

4.1.2 Tree Traversals with an Application / 树的遍历及应用 123

4.2 Binary Trees / 二叉树 126

4.2.1 Implementation / 实现 128

4.2.2 An Example: Expression Trees / 一个例子——表达式树 128

4.3 The Search Tree ADT—Binary Search Trees / 查找树的抽象数据类型——二叉查找树 132

4.3.1 contains / contains 134

4.3.2 findMin and findMax / findMin和findMax 135

4.3.3 insert / insert 136

4.3.4 remove / remove 139

4.3.5 Destructor and Copy Constructor / 析构函数和拷贝构造函数 141

4.3.6 Average-Case Analysis /均情况分析 141

4.4 AVL Trees / AVL树 144

4.4.1 Single Rotation / 单旋转 147

4.4.2 Double Rotation / 双旋转 149

4.5 Splay Trees / 伸展树 158

4.5.1 A Simple Idea (That Does Not Work) / 一个简单的想法（不能直接使用） 158

4.5.2 Splaying / 展开 160

4.6 Tree Traversals (Revisited) / 树的遍历（再次讨论） 166

4.7 B-Trees / B树 168

4.8 Sets and Maps in the Standard Library / 标准库中的集合与映射 173

4.8.1 Sets / 集合 173

4.8.2 Maps / 映射 174

4.8.3 Implementation of set and map / set和map的实现 175

4.8.4 An Example That Uses Several Maps / 使用多个映射的示例 176

Summary / 小结 181

Exercises / 练 182

References / 参考文献 189

Chapter 5 Hashing / 第5章 哈希 193

5.1 General Idea / 一般想法 193

5.2 Hash Function / 哈希函数 194

5.3 Separate Chaining / 分离链接法 196

5.4 Hash Tables without Linked Lists / 不用链表的哈希表 1

5.4.1 Linear Probing / 线探测法 1

5.4.2 Quadratic Probing /方探测法 2

5.4.3 Double Hashing / 双哈希 7

5.5 Rehashing / 再哈希 8

5.6 Hash Tables in the Standard Library / 标准库中的哈希表 210

5.7 Hash Tables with Worst-Case O(1) Access / 以坏情形O(1)访问的哈希表 212

5.7.1 Perfect Hashing / 哈希 213

5.7.2 Cuckoo Hashing / 杜鹃哈希 215

5.7.3 Hopscotch Hashing / 跳房子哈希 227

5.8 Universal Hashing / 通用哈希 230

5.9 Extendible Hashing / 可扩哈希 233

Summary / 小结 236

Exercises / 练 237

References / 参考文献 241

Chapter 6 Priority Queues (Heaps) / 第6章 优先队列（堆） 245

6.1 Model / 模型 245

6.2 Simple Implementations / 一些简单的实现 246

6.3 Binary Heap / 二叉堆 247

6.3.1 Structure Property / 结构质 247

6.3.2 Heap-Order Property / 堆序质 248

6.3.3 Basic Heap Operations / 基本的堆操作 249

6.3.4 Other Heap Operations / 其他的堆操作 252

6.4 Applications of Priority Queues / 优先队列的应用 257

6.4.1 The Selection Problem / 选择问题 258

6.4.2 Event Simulation / 事件模拟 259

6.5 d-Heaps / d堆 260

6.6 Leftist Heaps / 左式堆 261

6.6.1 Leftist Heap Property / 左式堆的质 261

6.6.2 Leftist Heap Operations / 左式堆操作 262

6.7 Skew Heaps / 斜堆 269

6.8 Binomial Queues / 二项队列 271

6.8.1 Binomial Queue Structure / 二项队列构建 271

6.8.2 Binomial Queue Operations / 二项队列操作 271

6.8.3 Implementation of Binomial Queues / 二项队列的实现 276

6.9 Priority Queues in the Standard Library / 标准库中的优先队列 282

Summary / 小结 283

Exercises / 练 283

References / 参考文献 288

Chapter 7 Sorting / 第7章 排序 291

7.1 Preliminaries / 预备知识 291

7.2 Insertion Sort / 插入排序 292

7.2.1 The Algorithm / 算法 292

7.2.2 STL Implementation of Insertion Sort / 插入排序的STL实现 293

7.2.3 Analysis of Insertion Sort / 插入排序的分析 294

7.3 A Lower Bound for Simple Sorting Algorithms / 一些简单排序算法的下界 295

7.4 Shellsort / 希尔排序 296

7.4.1 Worst-Case Analysis of Shellsort / 希尔排序的坏情形分析 297

7.5 Heapsort / 堆排序 300

7.5.1 Analysis of Heapsort / 堆排序的分析 301

7.6 Mergesort / 归并排序 304

7.6.1 Analysis of Mergesort / 归并排序的分析 306

7.7 Quicksort / 快速排序 309

7.7.1 Pi the Pivot / 选取枢纽元 311

7.7.2 Partitioning Strategy / 分割策略 313

7.7.3 Small Arrays / 小数组 315

7.7.4 Actual Quicksort Routines / 实际的快速排序例程 315

7.7.5 Analysis of Quicksort / 快速排序的分析 318

7.7.6 A Linear-Expected-Time Algorithm for Selection / 选择问题的线期望时间算法 321

7.8 A General Lower Bound for Sorting / 排序算法的一般下界 323

7.8.1 Decision Trees / 决策树 323

7.9 Decision-Tree Lower Bounds for Selection Problems / 选择问题的决策树下界 325

7.10 Adversary Lower Bounds / 对手下界 328

7.11 Linear-Time Sorts: Bucket Sort and Radix Sort / 线时间排序：桶式排序和基数排序 331

7.12 External Sorting / 外部排序 336

7.12.1 Why We Need New Algorithms / 为什么需要一些新的算法 336

7.12.2 Model for External Sorting / 外部排序模型 336

7.12.3 The Simple Algorithm / 简单算法 337

7.12.4 Multiway Merge / 多路合并 338

7.12.5 Polyphase Merge / 多相合并 339

7.12.6 Replacement Selection / 替换选择 340

Summary / 小结 341

Exercises / 练 341

References / 参考文献 347

Chapter 8 The Disjoint Sets Class / 第8章 不相交集算法 351

8.1 Equivalence Relations / 等价关系 351

8.2 The Dynamic Equivalence Problem / 动态等价问题 352

8.3 Basic Data Structure / 基本数据结构 353

8.4 Smart Union Algorithms / 灵巧求并算法 357

8.5 Path Compression / 路径压缩 360

8.6 Worst Case for Union-by-Rank and Path Compression / 按秩求并和路径压缩的坏情形 361

8.6.1 Slowly Growing Functions / 缓慢增长的函数 362

8.6.2 An Analysiy Recursive Decomposition / 通过递归分行的分析 362

8.6.3 An O (M log*N) Bound / 一个O (M log*N)界 369

8.6.4 An O (Mα(M, N)) Bound / 一个O (Mα(M, N))界 370

8.7 An Application / 一个应用 372

Summary / 小结 374

Exercises / 练 375

References / 参考文献 376

Chapter 9 Graph Algorithms / 第9章 图论算法 379

9.1 Definitions / 若干定义 379

9.1.1 Representation of Graphs / 图的表示 380

9.2 Topological Sort / 拓扑排序 382

9.3 Shortest-Path Algorithms / 短路径算法 386

9.3.1 Unweighted Shortest Paths / 无权短路径 387

9.3.2 Dijkstra's Algorithm / Dijkstra算法 391

9.3.3 Graphs with Negative Edge Costs / 具有负边值的图 400

9.3.4 Acyclic Graphs / 无圈图 400

9.3.5 All-Pairs Shortest Path / 所有顶点对间的短路径 404

9.3.6 Shortest Path Example / 短路径的例 404

9.4 Network Flow Problems / 网络流问题 406

9.4.1 A Simple Maximum-Flow Algorithm / 一个简单的大流算法 408

9.5 Minimum Spanning Tree / 小生成树 413

9.5.1 Prim's Algorithm / Prim算法 414

9.5.2 Kruskal's Algorithm / Kruskal算法 417

9.6 Applications of Depth-First Search / 深度优先搜索的应用 419

9.6.1 Undirected Graphs / 无向图 4

9.6.2 Biconnectivity / 双连通 421

9.6.3 Euler Circuits / 欧拉回路 425

9.6.4 Directed Graphs / 有向图 429

9.6.5 Finding Strong Components / 查找强分支 431

9.7 Introduction to NP-Completeness / NP介绍 432

9.7.1 Easy vs. Hard / 难与易 433

9.7.2 The Class NP / NP类 434

9.7.3 NP-Complete Problems / NP问题 434

Summary / 小结 437

Exercises / 练 437

References / 参考文献 445

Chapter 10 Algorithm Design Techniques / 第 10章 算法设计技巧 449

10.1 Greedy Algorithms / 贪婪算法 449

10.1.1 A Simple Scheduling Problem / 一个简单的调度问题 450

10.1.2 Huffman Codes / 哈夫曼编码 453

10.1.3 Approximate Bin Pa /似装箱问题 459

10.2 Divide and Conquer / 分治算法 467

10.2.1 Running Time of Divide-and-Conquer Algorithms / 分治算法的运行时间 468

10.2.2 Closest-Points Problem / 点问题 470

10.2.3 The Selection Problem / 选择问题 475

10.2.4 Theoretical Improvements for Arithmetic Problems / 一些算术问题的理论 478

10.3 Dynamic Programming / 动态规划 482

10.3.ing a Table Instead of Recursion / 用表代替递归 483

10.3.2 Ordering Matrix Multiplications / 矩阵乘法的顺序安排 485

10.3.3 Optimal Binary Search Tree / 二叉查找树 487

10.3.4 All-Pairs Shortest Path / 所有点对短路径 491

10.4 Randomized Algorithms / 化算法 494

10.4.1 Random-Number Generators / 数发生器 495

10.4.2 Skip Lists / 跳跃表 500

10.4.3 Primality Testing / 素测试 503

10.5 Backtra Algorithms / 回溯算法 506

10.5.1 The Turnpike Reconstruction Problem / 收费公路重建问题 506

10.5.2 Games / 游戏 511

Summary / 小结 518

Exercises / 练 518

References / 参考文献 527

Chapter 11 Amortized Analysis / 第 11章 摊还分析 533

11.1 An Unrelated Puzzle / 一个无关的智力问题 534

11.2 Binomial Queues / 二项队列 534

11.3 Skew Heaps / 斜堆 539

11.4 Fibonacci Heaps / 斐波那契堆 541

11.4.1 Cutting Nodes in Leftist Heaps / 切除左式堆中的节点 542

11.4.2 Lazy Merging for Binomial Queues / 二项队列的懒惰合并 544

11.4.3 The Fibonacci Heap Operations / 斐波那契堆操作 548

11.4.4 Proof of the Time Bound / 时间界的证明 549

11.5 Splay Trees / 伸展树 551

Summary / 小结 555

Exercises / 练 556

References / 参考文献 557

Chapter 12 Advanced Data Structures and Implementation / 第 12章 数据结构及其实现 559

12.1 Top-Down Splay Trees / 自顶向下伸展树 559

12.2 Red-Black Trees / 红黑树 566

12.2.1 Bottom-Up Insertion / 自底向上的插入 567

12.2.2 Top-Down Red-Black Trees / 自顶向下红黑树 568

12.2.3 Top-Down Deletion / 自顶向下删除 570

12.3 Treaps / treap 树 576

12.4 Suffix Arrays and Suffix Trees / 后缀数组和后缀树 579

12.4.1 Suffix Arrays / 后缀数组 580

12.4.2 Suffix Trees / 后缀树 583

12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees / 后缀数组和后缀树的线 586

12.5 k -d Trees / k-d 树 596

12.6 Pairing Heaps / 配对堆 602

Summary / 小结 606

Exercises / 练 608

References / 参考文献 612

Appendix A Separate Compilation of Class Templates / 附录A 类模板的分离式编译 615

A.1 Everything in the Header / 头文件中的内容 616

A.2 Explicit Instantiation / 显示实例化 616

暂无相关内容，正在全力查找中

暂无出版社相关信息，正在全力查找中！

暂无相关书籍摘录，正在全力查找中！

在线阅读地址：数据马克·艾伦·维斯人民邮电出版社9787115580924 语言程序设计高等学校教材英文在线阅读

在线听书地址：数据马克·艾伦·维斯人民邮电出版社9787115580924 语言程序设计高等学校教材英文在线收听

在线购买地址：数据马克·艾伦·维斯人民邮电出版社9787115580924 语言程序设计高等学校教材英文在线购买

暂无原文赏析，正在全力查找中！

编辑推荐

1. 用C++新标准C++11的代码讲数据结构和算法分析； 2. 作者所写的数据结构和算法分析书籍销量好，好评多，已被世界上很多大学用作教材。