数据结构与算法分析：C语言描述(英文版 原书第2版)
| 作者 |
| 马克·艾伦·维斯（Mark Allen Weiss） |
| 丛书名 |
| 经典原版书库 |
| 出版社 |
| 机械工业出版社 |
| ISBN |
| 9787111640080 |
| 简要 |
| 简介 |
| 内容简介书籍计算机书籍 本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有*高效率的程序。 本书可作为高级数据结构课程或研究生一年级算法分析课程的教材,使用本书需具有一些中级程序设计知识,还需要离散数学的一些背景知识。 |
| 目录 |
| 第1章 引论 1 1.1 本书讨论的内容 1 1.2 数学知识复习 3 1.2.1 指数 3 1.2.2 对数 3 1.2.3 级数 4 1.2.4 模运算 5 1.2.5 证明方法 6 1.3 递归简论 8 总结 12 练习 12 参考文献 13 第2章 算法分析 15 2.1 数学基础 15 2.2 模型 18 2.3 要分析的问题 18 2.4 运行时间计算 20 2.4.1 一个简单的例子 21 2.4.2 一般法则 21 2.4.3 最大子序列和 24 2.4.4 运行时间中的对数 28 2.4.5 检验你的分析 33 2.4.6 分析结果的准确性 33 总结 34 练习 35 参考文献 39 第3章 表、栈和队列 41 3.1 抽象数据类型 41 3.2 表ADT 42 3.2.1 表的简单数组实现 43 3.2.2 链表 43 3.2.3 程序设计细节 44 3.2.4 常见的错误 49 3.2.5 双链表 51 3.2.6 循环链表 52 3.2.7 例子 52 3.2.8 链表的游标实现 57 3.3 栈ADT 62 3.3.1 栈模型 62 3.3.2 栈的实现 63 3.3.3 应用 71 3.4 队列ADT 79 3.4.1 队列模型 79 3.4.2 队列的数组实现 79 3.4.3 队列的应用 84 总结 85 练习 85 第4章 树 89 4.1 预备知识 89 4.1.1 树的实现 90 4.1.2 树的遍历及应用 91 4.2 二叉树 95 4.2.1 实现 96 4.2.2 表达式树 97 4.3 查找树ADT—二叉查找树 100 4.3.1 MakeEmpty 101 4.3.2 Find 101 4.3.3 FindMin和FindMax 103 4.3.4 Insert 104 4.3.5 Delete 105 4.3.6 平均情形分析 107 4.4 AVL树 110 4.4.1 单旋转 112 4.4.2 双旋转 115 4.5 伸展树 123 4.5.1 一个简单的想法 124 4.5.2 展开 126 4.6 树的遍历 132 4.7 B树 133 总结 138 练习 139 参考文献 146 第5章 散列 149 5.1 一般想法 149 5.2 散列函数 150 5.3 分离链接法 152 5.4 开放定址法 157 5.4.1 线性探测法 157 5.4.2 平方探测法 160 5.4.3 双散列 164 5.5 再散列 165 5.6 可扩散列 168 总结 171 练习 172 参考文献 175 第6章 优先队列（堆） 177 6.1 模型 177 6.2 一些简单的实现 178 6.3 二叉堆 179 6.3.1 结构性质 179 6.3.2 堆序性质 180 6.3.3 基本的堆操作 182 6.3.4 其他的堆操作 186 6.4 优先队列的应用 189 6.4.1 选择问题 189 6.4.2 事件模拟 191 6.5 d-堆 192 6.6 左式堆 193 6.6.1 左式堆的性质 193 6.6.2 左式堆的操作 194 6.7 斜堆 200 6.8 二项队列 202 6.8.1 二项队列结构 202 6.8.2 二项队列操作 204 6.8.3 二项队列的实现 205 总结 212 练习 212 参考文献 216 第7章 排序 219 7.1 预备知识 219 7.2 插入排序 220 7.2.1 算法 220 7.2.2 插入排序的分析 221 7.3 一些简单排序算法的下界 221 7.4 希尔排序 222 7.5 堆排序 226 7.6 归并排序 230 7.7 快速排序 235 7.7.1 选取枢纽元 236 7.7.2 分割策略 237 7.7.3 小数组 240 7.7.4 实际的快速排序例程 240 7.7.5 快速排序的分析 241 7.7.6 选择的线性期望时间算法 245 7.8 大型结构的排序 247 7.9 排序的一般下界 247 7.10 桶式排序 250 7.11 外部排序 250 7.11.1 为什么需要新的算法 251 7.11.2 外部排序模型 251 7.11.3 简单算法 251 7.11.4 多路合并 253 7.11.5 多相合并 254 7.11.6 替换选择 255 总结 256 练习 257 参考文献 261 第8章 不相交集ADT 263 8.1 等价关系 263 8.2 动态等价性问题 264 8.3 基本数据结构 265 8.4 灵巧求并算法 269 8.5 路径压缩 271 8.6 按秩求并和路径压缩的最坏情形 273 8.7 一个应用 279 总结 279 练习 280 参考文献 281 第9章 图论算法 283 9.1 若干定义 283 9.2 拓扑排序 286 9.3 最短路径算法 290 9.3.1 无权最短路径 291 9.3.2 Dijkstra算法 295 9.3.3 具有负边值的图 304 9.3.4 无圈图 305 9.3.5 所有点对最短路径 308 9.4 网络流问题 308 9.5 最小生成树 313 9.5.1 Prim算法 314 9.5.2 Kruskal算法 316 9.6 深度优先搜索的应用 319 9.6.1 无向图 320 9.6.2 双连通性 322 9.6.3 欧拉回路 326 9.6.4 有向图 329 9.6.5 查找强分支 331 9.7 NP-完全性介绍 332 9.7.1 难与易 333 9.7.2 NP类 334 9.7.3 NP-完全问题 335 总结 337 练习 337 参考文献 343 第10章 算法设计技巧 347 10.1 贪婪算法 347 10.1.1 一个简单的调度问题 348 10.1.2 Huffman编码 351 10.1.3 近似装箱问题 357 10.2 分治算法 365 10.2.1 分治算法的运行时间 366 10.2.2 最近点问题 368 10.2.3 选择问题 373 10.2.4 一些运算问题的理论改进 376 10.3 动态规划 380 10.3.1 用一个表代替递归 380 10.3.2 矩阵乘法的顺序安排 383 10.3.3 最优二叉查找树 387 10.3.4 所有点对最短路径 390 10.4 随机化算法 392 10.4.1 随机数发生器 394 10.4.2 跳跃表 397 10.4.3 素性测试 399 10.5 回溯算法 401 10.5.1 收费公路重建问题 403 10.5.2 博弈 407 总结 413 练习 415 参考文献 422 第11章 摊还分析 427 11.1 一个无关的智力问题 428 11.2 二项队列 428 11.3 斜堆 433 11.4 斐波那契堆 435 11.4.1 切除左式堆中的节点 436 11.4.2 二项队列的懒惰合并 439 11.4.3 斐波那契堆操作 442 11.4.4 时间界的证明 443 11.5 伸展树 445 总结 449 练习 450 参考文献 451 第12章 高级数据结构及其实现 453 12.1 自顶向下伸展树 453 12.2 红黑树 457 12.2.1 自底向上插入 462 12.2.2 自顶向下红黑树 463 12.2.3 自顶向下删除 465 12.3 确定性跳跃表 469 12.4 AA树 476 12.5 treap树 482 12.6 k-d树 485 12.7 配对堆 488 总结 494 练习 495 参考文献 497 索引 501 Contents 1 Introduction 1 1.1 What's the Book About1 1.2 Mathematics Review 3 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 Summary 12 Exercises 12 References 13 2 Algorithm Analysis 15 2.1 Mathematical Backgroud 15 2.2 Model 18 2.3 What to Analyze 18 2.4 Running Time Calculations 20 2.4.1 A Simple Example 21 2.4.2 General Rules 21 2.4.3 Solutions for the Maximun Subsequence Sum Problem 24 2.4.4 Logarithms in the Running Time 28 2.4.5 Checking Your Analysis 33 2.4.6 A Grain of Salt 33 Summary 34 Exercised 35 References 39 3 Lists Stacks, and Queues 41 3.1 Abstract Data Types(ADTs) 41 3.2 The List ADT 42 3.2.1 Simple Array Implementation of Lists 43 3.2.2 Linked Lists 43 3.2.3 Programming Details 44 3.2.4 Common Erros 49 3.2.5 Doubly Linked Lists 51 3.2.6 Example 52 3.2.8 Cursor Implementation of Linked Lists 57 3.3 The Stack ADT 62 3.3.1 Stack Model 62 3.3.2 Implementation of Stacks 63 3.3.3 Applications 71 3.4 The Queue ADT 79 3.4.1 Queue Model 79 3.4.2 Array Implementation of Queues 79 3.4.3 Applications of Queues 84 Summary 85 Exercises 85 4 Trees 89 4.1 Preliminaries 89 4.1.1 Implementation of Trees 90 4.1.2 Tree Traversals with an Application 91 4.2 Binary Trees 95 4.2.1 Implementation 96 4.2.2 Expression Trees 97 4.3 The Search Tree ADT-Binary Search Trees 100 4.3.1 MakeEmpty 101 4.3.2 Find 101 4.3.3 FindMin and FindMax 103 4.3.4 Insert 104 4.3.5 Delete 105 4.3.6 Average-Case Analysis 107 4.4 AVL Trees 110 4.4.1 Single Rotation 112 4.4.2 Double Rotation 115 4.5 Splay Trees 123 4.5.1 A Simple Idea(That Does Not Work) 124 4.5.2 Splaying 126 4.6 Tree Traversals(Revisited)132 4.7 B-Trees 133 Summary 138 Exercises 139 References 146 5 Hashing 149 5.1 General Idea 149 5.2 Hash Function 159 5.3 Separate Chaining 152 5.4 Open Addressing 157 5.4.1 Linear Probing 157 5.4.2 Quadratic Probing 160 5.4.3 Double Hashing 164 5.5 Rehashing 165 5.6 Extendible Hashing 168 Summary 171 Exercises 172 References 175 6 Priority Queues(Heaps) 177 6.1 Model 177 6.2 Simple Implementations 178 6.3 Binary Heap 179 6.3.1 Structure Property 179 6.3.2 Heap Order Property 180 6.3.3 Basic Heap Operations 182 6.3.4 Other Heap Operations 186 6.4 Applications of Priority Queues 189 6.4.1 The Selection Problem 189 6.4.2 Event Simulation 191 6.5 d-Heaps 192 6.6 Leftist Heaps 193 6.6.1 Leftist Heap Property 183 6.6.2 Leftist Heap Operations 194 6.7 Skew Heaps 193 6.8 Binomial Queues 202 6.8.1 Binomial Queues Struccture 202 6.8.2 Binomial Queues Operations 204 6.8.3 Implementation of Binomial Queuse 205 Summary 212 Exercises 212 References 216 7 Sorting 7.1. Preliminaries 219 7.2.1. The Algorithm 220 7.2.2. Analysis of Insertion Sort 221 7.3 A Lower Bound for Simple Sorting Algorithms 221 7.4 SheUsort 222 7.5 Heapsort 226 7.6 Mergesort 230 7.7 Quicksort 235 7.7.1. Picking the Pivot 236 7.7.2. Partitioning Strategy 237 7.7.3. Small Arrays 240 7.7.4. Actual Quicksort Routines 240 7.7.5. Analysis of Quicksort 241 7.7.6. A Linear-Expected-Time Algorithm for Selection 245 7.8 Sorting Large Structures 247 7.9 A General Lower Bound for Sorting 247 7.10 Bucket Sort 250 7.11 External Sorting 250 7.11.1. Why We Need New Algorithms 251 7.11.2. Model for External Sorting 251 7.11.3 The Simple Algorithm 251 7.11.4 Multiway Merge 253 7.11.5 Polyphase Merge 254 7.11.6 Replacement Selection 255 Summary 256 Exercises 257 References 261 8 The Disjoint Set ADT 263 8.1 Equivalence Relations 263 8.2 The Dynamic Equivalence Problem 264 8.3 Basic Data Structure 265 8.4 Smart Union Algorithms 269 8.5 Path Compression 271 8.6 Worst Case for Union-by-Rank and Path Compression 273 8.7. An Application 279 Summary 279 Exercises 280 References 281 9 Graph Algorithms 283 9.1 Definitions 283 9.2. Topological Sort 286 9.3 Shortest-Path Algorithms 290 9.3.1. Unweighted Shortest Paths 291 9.3.2. Dijkstra's Algorithm 295 9.3.3. Graphs with Negative Edge Costs 9.3.4. Acyclic Graphs 305 9.3.5. All-Pairs Shortest Path 308 9.4 Network How Problems 308 9.5 Minimum Spanning Tree 9.5.1. Prim's Algorithm 9.5.2. Krusk~'s Algorithm 9.6. Applications of Depth-First Search 9.6.1. Undirected Graphs 320 9.6.2. Biconnectivity 322 9.6.3. Euler Circuits 326 9.6.4. Directed Graphs 329 9.6.5. Finding Strong Components 331 9.7 Introduction to NP-Completeness 332 9.7.1. Easy vs. Hard 333 9.7.2. The Class NP 334 9.7.3. NP-Complete Problems 335 Summary 337 Exercises 337 References 337 10 Algorithm Design Techniques 347 10.1 Greedy Algorithms 347 10.1.1. A Simple Scheduling Problem 348 10.1.2. Htfffman Codes 351 10.1.3. Approximate Bin Packing 357 10.2 Divide and Conquer 365 10.2.1. Running Time of Divide and Conquer Algorithms 366 10.2.2. Closest-Points Problem 368 10.2.3. The Selection Problem 373 10.2.4. Theoretical Improvements for Arithmetic Problems 376 10.3 Dynamic Programming 380 10.3.1. Using a Table Instead of Recursion 380 10.3.2. Ordering Matrix Multiplications 383 10.3.3. Optimal Binary Search Tree 387 10.3.4. All-Pairs Shortest Path 390 10.4 Randomized Algorithms 392 10.4.1. Random Number Generators 394 10.4.2. Skip Lists 397 10.4.3. Primality Testing 399 10.5 Backtracking Algorithms 401 10.5.1. The Turnpike Reconstruction Problem 10.5.2. Games 407 Summary 413 Exercises 415 References 422 11 Amortized Analysi 427 11.1.An Unrelated Puzzle 428 11.2. Binomial Queues 428 11.3 Skew Heaps 11.4 Fibonacci Heaps 435 11.4.1. Cutting Nodes in Leftist Heaps 436 11.4.2. Lazy Merging for Binomial Queues 439 11.4.3. The Fibonacci Heap Operations 442 11.4.4. Proof of the Time Bound 443 11.5 Sply Trees 45 Summary 449 Exercises 450 References 451 12 Advanced Data Structures and Implementation 453 12.1 Top-Down Splay Trees 453 12.2 Red Black Trees 457 12.2.1 Bottom-Up Insertion 462 12.2.2. Top-Down Red Black Trees 463 12.2.3. Top-Down Deletion 465 12,3 Deterministic Skip Lists 469 12.4 AA-Trees 476 12.5. Treaps 482 12.6 k-d Trees 485 12.7.Pairing Heaps 488 Summary 494 Exercises 495 References 497 Index 501 |
有问题微信扫码联系