出版時間:2005-8 出版社:人民郵電出版社 作者:維斯 頁數(shù):501
Tag標簽:無
內(nèi)容概要
《數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)是數(shù)據(jù)結(jié)構(gòu)和算法分析方面的經(jīng)典教材。第2版更加精煉并強化了《數(shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)創(chuàng)新的對算法和數(shù)據(jù)結(jié)構(gòu)的講授方法。通過C程序的實現(xiàn),著重闡述了抽象數(shù)據(jù)類型(ADT)的概念,并對算法的效率、性能和運行時間進行了分析?!稊?shù)據(jù)結(jié)構(gòu)與算法分析:C語言描述》(英文版第2版)適合作為本科數(shù)據(jù)結(jié)構(gòu)課程或研究生第一年算法分析課程的教材。第1~9章為大多數(shù)本科一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程提供了足夠的材料。多學(xué)時課程可講授第10章。研究生的算法分析課程可以使用第6~12章的內(nèi)容。
作者簡介
Mark Allen Weiss,美國佛羅里達國際大學(xué)計算機學(xué)院教授,普林斯頓大學(xué)汁算機科學(xué)博士,他目前是AP(Advanced Placemenl)考試汁算機學(xué)科委員會的主席。除本書外,他還撰寫了Data Structures and Problem Solving Using Java(中文版第3版即將山人民郵電出版社出版)等著作。
書籍目錄
Adapters ForewordPreface1 Introduction 11.1. Whats the Book About? 11.2. A Brief Introduction to Recursion 3Summary7Exercises7References82 Algorithm Analysis 92.1. Mathematical Background 92.2. Model 122.3. What to Analyze 122.4. Running Time Calculations 142.4.1. A Simple Example 152.4.2. General Rules 152.4.3. Solutions for the Maximum Subsequence Sum Problem182.4.4. Logarithms in the Running Time222.4.5. Checking Your Analysis272.4.6. A Grain of Salt27Summary28Exercises29References333 Lists, Stacks, and Queues353.1. Abstract Data Types (ADTs) 353.2. The List AnT 363.2.1. Simple Array Implementation of Lists 373.2.2. Linked Lists 373.2.3. Programming Details 383.2.4. Common Errors 433.2.5. Doubly Linked Lists 453.2.6. Circularly Linked Lists 463.2.7. Examples 463.2.8. Cursor Implementation of Linked Lists 503.3. The Stack ADT 563.3.1. Stack Model 563.3.2. Implementation of Stacks 573.3.3. Applications 653.4. The Queue AnT 733.4.1. Queue Model 733.4.2. Array Implementation of Queues 733.4.3. Applications of Queues78Summary 79Exercises 794 Trees 834.1. Preliminaries 834.1.1. Terminology 834.1.2. Tree Traversals with an Application 844.2. Binary Trees 854.2.1. Implementation864.2.2. Expression Trees 874.2.3. Tree Traversals904.3. The Search Tree ADT Binary Search Trees 974.3.1. MakeEmpty 974.3.2. Find 974.3.3. FindMin and FindMax 994.3.4. Insert 1004.3.5. Delete 1014.3.6. Average-Case Analysis 1034.4. AVL Trees 1064.4.1. Single Rotation1084.4.2. Double Rotation 1114.5. Splay Trees 1194.5.1. A Simple Idea (That Does Not Work) 12 04.5.2. Splaying 12 24.6. B-Trees 128Summary133Exercises134References1415 Priority Queues (Heaps) 1455.1. Model 1455.2. Simple Implementations 1465.3. Binary Heap 1475.3.1. Structure Property 1475.3.2. Heap Order Property1485.3.3. Basic Heap Operations 1505.3.4. Other Heap Operations 1545.4. Applications of Priority Queues1575.4.1. The Selection Problem 1575.4.2. Event Simulation 1595.5. d-Heaps 1605.6. Leftist Heaps 1615.6.1. Leftist Heap Property 1615.6.2. Leftist Heap Operations 1625.7. Skew Heaps 1685.8. Binomial Queues 1705.8.1. Binomial Queue Structure 1705.8.2. Binomial Queue Operations 1725.8.3. Implementation of Binomial Queues 173Summary 180Exercises 180References 1846 Sorting 1876.1. Preliminaries 1876.2. Insertion Sort 1886.2.1. The Algorithm 1886.2.2. Analysis of Insertion Sort 1896.3. A Lower Bound for Simple Sorting Algorithms 1896.4. Shellsort 1906.4.1. Worst-Case Analysis of Shellsort 1926.5. Heapsort 1946.5.1. Analysis of Heapsort 1966.6. Mergesort 1986.6.1. Analysis of Mergesort 2006.7. Quicksort 2036.7.1. Picking the Pivot 2046.7.2. Partitioning Strategy 2056.7.3. Small Arrays 20 86.7.4. Actual Quicksort Routines 2086.7.5. Analysis of Quicksort 2096.7.6. A Linear-Expected-Time Algorithm for Selection 2136.8. Sorting Large Structures 2156.9. A General Lower Bound for Sorting 2166.9.1. Decision Trees 2176.10. Bucket Sort and Radix Sort 2196.11. External Sorting 2226.11.1. Why We Need New Algorithms 2226.11.2. Model for External Sorting 2226.11.3. The Simple Algorithm 2226.11.4. Multiway Merge 2246.11.5. Polyphase Merge2256.11.6. Replacement Selection 226Summary 227Exercises 2297 Hashing 2357.1. General Idea 2357.2. Hash Function 2377.3. Separate Chaining 2397.4. Open Addressing 2447.4.1. Linear Probing2447.4.2. Quadratic Probing 2477.4.3. Double Hashing 2517.5. Rehashing 2527.6. Extendible Hashing 255Summary 258Exercises 259References 2628 The Disjoint Set AnT 2658.1. Equivalence Relations 2658.2. The Dynamic Equivalence Problem 2668.3. Basic Data Structure 2678.4. Smart Union Algorithms 2718.5. Path Compression 2738.6. Worst Case for Union-by-Rank and Path Compression 2758.6.1. Analysis of the Union/Find Algorithm 2758.7. An Application 281Summary 281Exercises 282References 2839 Graph Algorithms 2859.1. Definitions 2859.1.1. Representation of Graphs 2869.2. Topological Sort 2889.3. Shortest-Path Algorithms 2929.3.1. Unweighted Shortest Paths 2939.3.2. Dijkstras Algorithm 2979.3.3. Graphs with Negative Edge Costs 3069.3.4. Acyclic Graphs 3079.3.5. All-Pairs Shortest Path 3109.4. Network Flow Problems 3109.4.1. A Simple Maximum-Flow Algorithm 3119.5. Minimum Spanning Tree 3159.5.1. Prims Algorithm 3169.5.2. Kruskals Algorithm 3189.6. Applications of Depth-First Search 3:219.6.1. Undirected Graphs 3229.6.2. Biconnectivity 3249.6.3. Euler Circuits 3289.6.4. Directed Graphs 3319.6.5. Finding Strong Components 3339.7. Introduction to NP-Completeness 3349.7.2. The Class NP 3369.7.3. NP-Complete Problems 337Summary 339Exercises 339References 34510 Algorithm Design Techniques 34910.1. Greedy Algorithms 34910.1.1. A Simple Scheduling Problem 35010.1.2. Huffman Codes 35310.1.3. Approximate Bin Packing 35910.2. Divide and Conquer 36710.2.1. Running Time of Divide and Conquer Algorithms 36810.2.2. Closest-Points Problem 37010.2.3. The Selection Problem 37510.2.4. Theoretical Improvements for Arithmetic Problems 37810.3. Dynamic Programming 38210.3.1. Using a Table Instead of Recursion 38210.3.2. Ordering Matrix Multiplications 38510.3.3. Optimal Binary Search Tree 38910.3.4. All-Pairs Shortest Path 39210.4. Randomized Algorithms 39410.4.1. Random Number Generators 39610.4.2. Skip Lists 39910.4.3. Primality Testing 40110.5. Backtracking Algorithms 40310.5.1. The Turnpike Reconstruction Problem 40510.5.2. Games 407Summary 415Exercises 417References424ll Amortized Analysis 42911.1. An Unrelated Puzzle 43011.2. Binomial Queues 43011.3. Skew Heaps 43511.4. Fibonacci Heaps 43711.4.1. Cutting Nodes in Leftist Heaps 43011.4.2. Lazy Merging for Binomial Queues 44111.4.3. The Fibonacci Heap Operations 44411.4.4. Proof of the Time Bound 44511.5. Splay Trees 447Summary 451Exercises 452References 45312 Advanced Data Structures and Implementation 45512.1. Top-Down Splay Trees 45512.2. Red Black Trees 45912.2.1. Bottom-Up Insertion 46412.2.2. Top-Down Red Black Trees 46512.2.3. Top-Down Deletion 46712.3. Deterministic Skip Lists 47112.4. &A-Trees 47812.5. Treaps 48412.6. k-d Trees 48712.7. Pairing Heaps 490Summary 496Exercises 497References 499
編輯推薦
作者Mark Allen Weiss在數(shù)據(jù)結(jié)構(gòu)與算法分析方面卓有建樹,他在此方面的著作尤其暢銷,并受到廣泛好評。他的Data Structures and Algorithm Analysis曾被評為20世紀最佳的30療計算機著作之一,本書是此書的C語言版。他在數(shù)據(jù)結(jié)構(gòu)與算法分析方面的系列著作已被國際上500余所大學(xué)用做教材?! ”緯鶕?jù)國內(nèi)的教學(xué)實際對原版部分章節(jié)的內(nèi)容做了調(diào)整和改編,使之更加緊湊,改編工作得到了原書作者的首肯和支持。
圖書封面
圖書標簽Tags
無
評論、評分、閱讀與下載
數(shù)據(jù)結(jié)構(gòu)與算法分析 PDF格式下載