内容简介
     《数据结构与算法分析:C语言描述》曾被评为20世纪很好的30部计算机著作之一,作者在数据结构和算法分析方面卓有建树,他的数据结构和算法分析的著作尤其畅销,并受到广泛好评,已被世界500余所大学选作教材。
   在《数据结构与算法分析:C语言描述》中,作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。
   《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构,如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。详细讨论了摊还分析,考查书中介绍的一些高级数据结构。增加了高级数据结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。     
作者简介
     Mark Allen Weiss 1987年在普林斯顿大学获得计算机科学博士学位。师 从Roberl Sedgewick,现任美国佛罗里达国际大学计算与信息科学学院教授。他曾担任全美AP(Advanced Placement)考试计算机学科委员会主席。其主要研究方向是数据结构、算法和教育学。     
内页插图
          目录
   Introduction 1
 1.1. Whats the Book About? 1
 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
 Summary 12
 Exercises 12
 References 13 
 2 Algorithm Analysis 15
 2.1. Mathematical Background 15
 2.2. Model 18
 2.3. What to Analyze 18
 2.4. Running Tune Calculations 20
 2.4.1. A Simple Example 21
 2.4.2. General Rules 21
 2.4.3. Solutions for the Maximum Subsequence Sum Problem 24
 2.4.4. Logarithms in the Running Tune 28
 2.4.5. Checking Your Analysis 33
 2.4.6. A Grain of Salt 33
 Summary 34
 Exercises 35
 References 39 
 3 Lists, Stacks, and Queues 41
 3.1. Abstract Data Types (AnTs) 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 Errors 49
 3.2.5. Doubly Linked Lists 51
 3.2.6. Circularly Unked Lists 52
 3.2.7. Examples 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. AvI 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 150
 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. Strocture 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 Properly 193
 6.6.2. Leftist Heap Operations 194
 6.7. Skew Heaps 200
 6.8. Binomial Queues 202
 6.8.1. Binomial Queue Structure 202
 6.8.2. Binomial Queue Operations 204
 6.8.3. Implementation of Binomial Queues 205
 Summary 212
 Exercises 212
 References 216 
 7 Sorting 219
 7.1. Preliminaries 219
 7.2. Insertion Sort 220
 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.4.1. Worst-Case Analysis of Shellsort 224
 7.5. Heapsort 226
 7.5.1. Analysis of Heapsort 228
 7.6. Mergesort 230
 7.6.1. Analysis of Mergesort 232
 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.9.1. Decision Trees 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
 ……
 8 The Disjoint Set ADT
 9 Graph Algorithms
 10 Algorithm Design Techniques
 11 Amortized Analysis
 12 Advanced Data Structures and Implementation      
精彩书摘
     This example illustrates what we call randomized algorithms. At least onceduring the algorithm, a random number is used to make a decision. The runningtime of the algorithm depends not only on the particular input, but also on therandom numbers that occur.
   The worst-case running time of a randomized algorithm is almost always thesame as the worst-case running time of the nonrandomized algorithm. The importantdifference is that a good randomized algorithm has no bad inputs, but only badrandom numbers (relative to the particular input). This may seem like only aphilosophical difference, but actually it is quite important, as the following exampleshows.
   Consider two variants of quicksort. Variant A uses the first element as pivot,while variant B uses a randomly chosen element as pivot. In both cases, the worst-case running time is (N2), because it is possible at each step that the largestelement is chosen as pivot. The difference between these worst cases is that there is aparticular input that can always be presented to variant A to cause the bad runningtime. Variant A will run in (N2) time every single time it is given an already-sortedlist. If variant B is presented with the same input twice, it will have two differentrunning times, depending on what random numbers occur.      
前言/序言
     This book describes data structures, methods of organizing large amounts of data,and algorithm analysis, the estimation of the running time of algorithms. As com-puters become faster and faster, the need for programs that can handle large amountsof input becomes more acute. Paradoxically, this requires more careful attention toefficiency, since inefficiencies in programs become most obvious when input sizes arelarge. By analyzing an algorithm before it is actually coded, students can decide if aparticular solution will be feasible. For example, in this text students look at specificproblems and see how careful implementations can reduce the time constraint forlarge amounts of data from 16 years to less than a second. Therefore, no algorithmor data structure is presented without an explanation of its running time. In somecases, minute details that affect the running time of the implementation are explored.
  Once a solution method is determined, a program must still be written. Ascomputers have become more powerful, the problems they must solve have becomelarger and more complex, requiring development of more intricate programs. Thegoal of this text is to teach students good programming and algorithm analysis skillssimultaneously so that they can develop such programs with the maximum amountof efficiency.
  This book is suitable for either an advanced data structures (CS7) course ora first-year graduate course in algorithm analysis. Students should have some know-ledge of intermediate programming, including such topics as pointers and recursion,and some background in discrete math.     
				
 
				
				
					《数据结构与算法分析——C语言描述(英文版·第2版)》:探寻计算思维的基石,构建高效程序的蓝图  在日新月异的科技浪潮中,软件开发已成为驱动社会进步的关键力量。而理解和掌握数据结构与算法,则如同建造摩天大楼的地基,是所有高性能、可扩展、可靠软件系统的根基所在。本书《数据结构与算法分析——C语言描述(英文版·第2版)》正是旨在为读者提供这座坚实地基的权威指南。它不仅深入浅出地揭示了数据结构与算法的内在奥秘,更通过 C 语言这一强大而精炼的工具,将抽象的理论转化为可操作的代码实践。  本书并非一本简单的 C 语言编程手册,也非泛泛而谈的计算机科学概论。它聚焦于“如何高效地组织和处理信息”,以及“如何设计出最优的计算流程”。在信息爆炸的时代,能够快速、准确地访问和管理数据,并以最有效率的方式完成计算任务,已成为衡量一个程序员核心竞争力的重要标尺。本书正是为了培养这种“计算思维”而生,它引导读者去思考,在面对海量数据和复杂问题时,我们应该如何选择最合适的数据组织方式,如何设计出最精巧的算法来解决问题。  理解数据结构:信息组织的艺术  数据结构,顾名思义,是数据的组织方式。不同的数据组织方式,决定了我们访问、修改和存储数据的效率。本书将带领读者系统地学习各种 fundamental 的数据结构,并深入剖析它们的特性、优缺点以及适用场景。     线性表 (Linear Lists):作为最基本的数据结构之一,线性表以其简单的结构和直观的操作,为我们理解更复杂的数据结构奠定了基础。本书将详细介绍数组(Arrays)和链表(Linked Lists),剖析它们在插入、删除、查找等操作上的性能差异。读者将了解到,链表的灵活性在于其动态分配内存的能力,而数组则以其高效的随机访问而著称。链表的具体实现,如单向链表、双向链表和循环链表,也将逐一呈现,帮助读者理解它们在不同应用场景下的优势。     栈 (Stacks) 与队列 (Queues):作为特殊的线性表,栈和队列在计算机科学中有着极其重要的应用。栈的“后进先出”(LIFO)原则,使其成为函数调用栈、表达式求值和深度优先搜索等算法的关键;而队列的“先进先出”(FIFO)原则,则广泛应用于任务调度、广度优先搜索和消息队列等场景。本书将阐释它们的抽象数据类型(ADT)定义,并提供高效的 C 语言实现,让读者深刻理解它们的工作原理和应用价值。     树 (Trees):树形结构是描述层次关系数据的理想选择。本书将重点介绍二叉树(Binary Trees)及其变种,特别是二叉搜索树(Binary Search Trees,BST)。BST 的有序性使得查找、插入和删除操作的平均时间复杂度可以达到 O(log n),这在数据检索中具有显著优势。在此基础上,本书还会探讨平衡二叉搜索树,如 AVL 树和红黑树,它们通过自平衡机制,保证了最坏情况下的性能,从而避免了 BST 在某些情况下退化成链表的问题。对树的遍历(前序、中序、后序)以及在实际应用中的案例分析,也将是本书的重要组成部分。     堆 (Heaps):堆是一种特殊的完全二叉树,常用于实现优先队列(Priority Queues)。堆的特性使得最大值或最小值元素能够被快速访问,这在排序算法(如堆排序)和图算法(如 Dijkstra 算法)中至关重要。本书将深入讲解最大堆和最小堆的概念,以及它们在 C 语言中的实现方式,并阐明堆在效率上的独到之处。     图 (Graphs):图结构是描述对象之间复杂关系的最强大工具之一。从社交网络到交通路线,再到计算机网络,图无处不在。本书将介绍图的基本概念,包括顶点(Vertices)、边(Edges)、邻接矩阵(Adjacency Matrix)和邻接表(Adjacency List)等表示方法。在此基础上,读者将学习图的遍历算法,如深度优先搜索(DFS)和广度优先搜索(BFS),以及一些经典的图算法,如单源最短路径(Dijkstra 算法)、所有顶点对最短路径(Floyd-Warshall 算法)和最小生成树(Prim 算法和 Kruskal 算法)。     散列表 (Hash Tables):散列表以其近乎常数时间的平均查找、插入和删除操作,成为一种极其高效的数据结构。本书将详细讲解哈希函数的设计原则、冲突解决方法(如链地址法和开放地址法)以及它们的性能分析。读者将了解到,如何通过精心设计的哈希函数,将数据均匀地分布在散列表中,从而最大化查找效率。  掌握算法分析:效率优化的艺术  仅仅了解数据结构是不够的,更重要的是理解如何设计高效的算法来处理这些数据。算法分析是衡量算法优劣的关键,它关注算法在时间和空间上的资源消耗。     渐近记号 (Asymptotic Notation):本书将深入介绍描述算法效率的数学工具——渐近记号,包括大 O 记号(O)、大 Omega 记号(Ω)和大 Theta 记号(Θ)。通过这些记号,我们可以抽象地描述算法随着输入规模增长,其运行时间或空间占用的增长趋势,从而忽略常数因子和低阶项的影响,聚焦于算法的核心效率。     算法复杂度分析 (Algorithm Complexity Analysis):读者将学习如何运用渐近记号来分析各种算法的时间复杂度和空间复杂度。无论是简单的循环、递归,还是复杂的图算法,都将通过严谨的数学推导,揭示其性能表现。本书将引导读者理解,为什么有些算法在处理大规模数据时表现出惊人的效率,而有些则会迅速变得不可用。     递归与分治 (Recursion and Divide and Conquer):递归是一种强大的编程范式,许多高效算法都建立在递归的基础上。本书将深入探讨递归的思想,以及如何将其应用于解决问题,例如斐波那契数列、阶乘计算等。分治策略,作为一种典型的递归应用,将通过归并排序(Merge Sort)和快速排序(Quick Sort)等经典算法进行讲解。读者将理解,如何将一个大问题分解成若干个规模更小的子问题,然后递归地解决这些子问题,最后将子问题的解合并,从而得到原问题的解。     动态规划 (Dynamic Programming):动态规划是解决具有重叠子问题和最优子结构性质的问题的强大技术。本书将通过一系列经典的动态规划问题,如背包问题(Knapsack Problem)、最长公共子序列(Longest Common Subsequence)和硬币找零(Coin Change Problem),引导读者理解动态规划的思想:将问题分解为子问题,并存储子问题的解,以避免重复计算。     贪心算法 (Greedy Algorithms):贪心算法是一种在每一步选择局部最优解,以期达到全局最优解的算法。本书将介绍贪心算法的原理,并通过实例,如活动选择问题(Activity Selection Problem)和霍夫曼编码(Huffman Coding),来阐释其适用条件和局限性。     回溯与分支限界 (Backtracking and Branch and Bound):当问题空间庞大且难以直接求解时,回溯和分支限界算法提供了系统搜索解决方案的方法。本书将通过解决如 N 皇后问题(N-Queens Problem)和旅行商问题(Traveling Salesperson Problem)的简化版本,来讲解回溯法如何通过试探性地构建解,并在发现不可行时进行回溯。分支限界则在此基础上,通过剪枝策略来优化搜索过程,提高效率。  C 语言的实践应用:将理论化为现实  本书最大的特色之一,在于它始终坚持使用 C 语言来描述和实现各种数据结构与算法。C 语言以其接近硬件的特性、高效的内存管理和精炼的语法,成为实现高性能算法的理想选择。     内存管理与指针 (Memory Management and Pointers):在 C 语言中,对内存的精细控制是实现高效算法的关键。本书将深入讲解 C 语言的指针机制,以及如何通过动态内存分配(`malloc`、`callfree`)来灵活地管理数据结构,例如动态数组和链表。对内存泄漏和野指针等常见问题的处理,也将贯穿其中。     代码实现的详细讲解:对于每一种数据结构和算法,本书都提供了清晰、简洁且高效的 C 语言代码实现。读者可以通过阅读和理解这些代码,将抽象的理论知识转化为实际的编程技能。代码的注释详尽,逻辑清晰,便于读者跟踪算法的执行流程。     实际应用场景的案例分析:理论的学习离不开实际应用。本书将通过一系列具有代表性的实际应用场景,来展示数据结构与算法在解决真实世界问题中的力量。例如,如何利用排序算法加速数据库查询,如何用图算法优化物流配送,如何用散列表实现快速查找等。这些案例分析将帮助读者建立起理论与实践之间的桥梁。  学习本书将为您带来什么?     扎实的计算基础:您将对数据如何组织、如何高效访问和处理有深刻的理解,这是成为一名优秀软件工程师的基石。    解决复杂问题的能力:通过学习各种算法,您将掌握系统地分析和解决复杂计算问题的思维模式和方法。    编写高性能代码的能力:掌握 C 语言的精髓,并将其应用于数据结构和算法的实现,您将能够编写出更加高效、稳定且资源利用率更高的代码。    更强的系统设计能力:对数据结构和算法的深入理解,将帮助您在系统设计时做出更明智的选择,构建出更具可扩展性和可维护性的软件系统。    为进阶学习奠定基础:本书的内容涵盖了计算机科学的核心领域,为进一步学习操作系统、编译原理、数据库系统等更高级的学科打下了坚实的基础。  《数据结构与算法分析——C语言描述(英文版·第2版)》是一本集理论深度、实践指导和工程应用为一体的经典著作。无论您是计算机科学专业的学生,还是希望提升编程技能的在职开发者,本书都将是您不可或缺的学习伙伴。它将引导您穿越数据的海洋,洞察算法的智慧,最终成为一名能够驾驭复杂计算世界的工程师。