数据结构与算法分析++C语言描述++英文版++....pdf
General Ination 书名数据结构与算法分析 C语言描述 英文版 第2版 作者(美)韦斯著 页数512 出版社机械工业出版社 出版日期 SS号12646255 DX号 URLhttp// pdxNumberd204018350E153ABB9B73FEBC82B56 715封面 书名 版权 前言 目录 1 Introduction l1.1Whats the Book About1.2Mathematics Review1.2.1Exponents1.2.2Logarithms1.2.3Series1.2.4Modular Arithmetic1.2.5The P Word1.3A Brief Introduction to RecursionSummaryrcisesReferences 2 Algorithm Analysis2.1Mathematical Background2.2Model2.3What to Analyze2.4Running Time Calculations2.4.1A Simple Example2.4.2General Rules2.4.3Solutions for the Maximum Subsequ ence Sum Problem2.4.4Logarithms in the Running Time2.4.5Checking Your Analysis2.4.6A Grain of SaltSummaryrcisesReferences3 Lists,Stacks,and Queues3.1Abstract Data TypesADTs3.2The List ADT3.2.1Simple Array Implementation of li sts3.2.2Linked Lists3.2.3Programming Details3.2.4Common Errors3.2.5Doubly Linked Lists3.2.6Circularly Linked Lists3.2.7Examples3.2.8Cursor Implementation of Linked L ists3.3The Stack ADT3.3.1Stack Model3.3.2Implementation of Stacks3.3.3Applications3.4The Queue ADT3.4.1Quene Model3.4.2Array Implementation of Queues3.4.3Applications of QueuesSummaryrcises 4 Trees4.1Preliminaries4.1.1Implementation of Trees4.1.2Tree Traversals with an Applicati on4.2Binary Trees4.2.1Implementation4.2.2Expression Trees4.3The Search Tree ADTBinary Search T rees4.3.1MakeEmpty4.3.2Find4.3.3FindMin and FindMax4.3.4Insert4.3.5Delete4.3.6Average-Case Analysis4.4AVL Trees4.4.1Single Rotation4.4.2Double Rotation4.5Splay Trees4.5.1A Simple IdeaThat Does Not Work4.5.2Splaying4.6Tree TraversalsRevisited4.7B-TreesSummaryrcisesReferences 5 Hashing5.1General Idea5.2Hash Function5.3Separate Chaining5.4Open Addressing5.4.1Linear Probing5.4.2Quadratic Probing5.4.3Double Hashing5.5Rehashing5.6Extendible HashingSummaryrcisesReferences 6 Priority QueuesHeaps6.1Model6.2Simple Implementations6.3Binary Heap6.3.1Structure Property6.3.2Heap Order Property6.3.3Basic Heap Operations6.3.4Other Heap Operations6.4Applications of Priority Queues6.4.1The Selection Problem6.4.2Event Simulation 6.5d-Heaps 6.6Leftist Heaps6.6.1Leftist Heap Property6.6.2Leftist Heap Operations 6.7Skew Heaps 6.8Binomial Queues6.8.1Binomial Queue Structure6.8.2Binomial Queue Operations6.8.3Implementation of Binomial QueuesSummaryrcisesReferences 7 Sorting7.1Preliminaries7.2Insertion Sort7.2.1The Algorithm7.2.2Analysis of Insertion Sort7.3A Lower Bound for Simple Sorting Algo rithms7.4Shellsort7.4.1Worst-Case Analysis of Shellsort7.5Heapsort7.5.1Analysis of Heapsort7.6Mergesort7.6.1Analysis of Mergesort7.7Quicksort7.7.1Picking the Pivot7.7.2Partitioning Strategy7.7.3Small Arrays7.7.4Actual Quicksort Routines7.7.5Analysis of Quicksort7.7.6A Linear-Expected-Time Algorithm for Selection7.8Sorting Large Structures7.9A General Lower Bound for Sorting7.9.1Decision Trees7.10Bucket Sort7.11External Sorting7.11.1Why We Need New Algorithms7.11.2Model for External Sorting 7.11.3The Simple Algorithm 7.11.4Multiway Merge 7.11.5Polyphase Merge 7.11.6Replacement Selection Summary rcises References8 The Disjoint Set ADT8.1Equivalence Relations8.2The Dynamic Equivalence Problem8.3Basic Data Structure8.4Smart Union Algorithms8.5Path Compression8.6Worst Case for Union-by-Rank and Pa th Compression8.6.1Analysis of the Union/Find Algori thm8.7An ApplicationSummaryrcisesReferences 9 Graph Algorithms9.1Definitions9.1.1Representation of Graphs9.2Topological Sort9.3Shortest-Path Algorithms9.3.1Unweighted Shortest Paths9.3.2Dijkstras Algorithm9.3.3Graphs with Negative Edge Costs9.3.4Acyclic Graphs9.3.5All-Pairs Shortest Path9.4Network Flow Problems9.4.1A Simple Maximum-Flow Algorithm9.5Minimum Spanning Tree9.5.1Prims Algorithm9.5.2Kruskals Algorithm 9.6Applications of Depth-First Search9.6.1Undirected Graphs9.6.2Biconnectivity9.6.3Euler Circuits9.6.4Directed Graphs9.6.5Finding Strong Components 9.7Introduction to NP-Completeness9.7.1Easy vs.Hard9.7.2The Class NP9.7.3NP-Complete ProblemsSummaryrcisesReferences 10 Algorithm Design Techniques10.1Greedy Algorithms10.1.1A Simple Scheduling Problem10.1.2Huffman Codes10.1.3Approximate Bin Packing10.2Divide and Conquer10.2.1Running Time of Divide and Conqu er Algorithms10.2.2Closest-Points Problem10.2.3The Selection Problem10.2.4Theoretical Improvements for Ari thmetic Problems10.3Dynamic Programming10.3.1Using a Table Instead of Recursi on10.3.2Ordering Matrix Multiplications10.3.3Optimal Binary Search Tree10.3.4All-Pairs Shortest Path10.4Randomized Algorithms10.4.1Random Number Generators10.4.2Skip Lists10.4.3Primality Testing10.5Backtracking Algorithms10.5.1The Turnpike Reconstruction Prob lem10.5.2GamesSummaryrcisesReferences 11 Amortized Analysis11.1An Unrelated Puzzle11.2Binomial Queues11.3Skew Heaps11.4Fibonacci Heaps11.4.1Cutting Nodes in Leftist Heaps11.4.2Lazy Merging for Binomial Queues11.4.3The Fibonacci Heap Operations11.4.4Proof of the Time Bound11.5Splay TreesSummaryrcisesReferences 12 Advanced Data Structures and Implementa tion12.1Top-Down Splay Trees12.2Red Black Trees12.2.1Bottom-Up Insertion12.2.2Top-Down Red Black Trees12.2.3Top-Down Deletion12.3Deterministic Skip Lists12.4AA-Trees12.5Treaps12.6k-d Trees12.7Pairing HeapsSummaryrcisesReferences Index
