《數據結構與算法分析：C++描述》是2006年人民郵電出版社出版的圖書，作者是(美)維斯。
基本介紹
- 書名：數據結構與算法分析：C++描述
- 作者：(美)維斯
- ISBN：7115152330、9787115152336
- 頁數： 586頁
- 出版社：人民郵電出版社
- 出版時間：2006年11月1日
- 開本：16開
- 叢書名：圖靈原版計算機科學系列
- 版本：第1版
作者簡介,內容簡介,目錄,
作者簡介
Mark Allen Weiss,美國佛羅里達國際大學計算機學院教授，普林斯頓大學汁算機科學博士，他目前是AP(Advanced Placemenl)考試汁算機學科委員會的主席。除本書外，他還撰寫了Data Structures and Problem Solving Using Java(中文版第3版即將山人民郵電出版社出版)等著作。
內容簡介
《數據結構與算法分析：C++描述》一書秉承Weiss著全一貫的嚴謹風格，同時又突出了實踐。書中充分套用了現代C++語言特性，透徹地講述了數據結構的原理和套用，不僅使學生具備算法分析能力，能夠開發高效的程式，而且讓學生掌握良好的程式設計技巧。
Mark Allen Weiss教授撰寫的數據結構與算法分析方面的著作曾被評為20世紀最佳的30部計算機著作之一，已經成為公認的經典之作，被全球數百所大學採用為教材，廣受好評。
目錄
Chapter 1 Introduction 1
1.1 What's the Book About? 1
1.2 Mathematics Review 2
1.2.1 Exponents 3
1.2.2 kogarithms 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 7
1.4 C++ Classes 11
1.4.i Basic class Syntax 12
1.4.2 Extra Constructor Syntax and Accessors 12
1.4.3 Separation of Interface and Implementation 15
1.4.4 vector and string 17
1.5 C++ Details 19
1.5.1 Pointers 19
1.5.2 Parameter Passing 21
1.5.3 Return Passing 22
1.5.4 Reference Variables 23
1.5.5 The Big Three: Destructor, Copy Constructor, operator= 23
1.5.6 C-style Arrays and Strings 26
1.6 Templates 29
1.6.1 Function Templates 29
1.6.2 Class Templates 30
1.6.3 Object, Comparable, and an Example 32
1.6.4 Function Objects 34
1.6.5 Separate Compilation of Class Templates 35
1.7 Using Matrices 37
1.7.1 The Data Members, Constructor, and Basic Accessors 37
1.7.2 operator[] 37
1.7.3 Destructor, Copy Assignment, Copy Constructor 39
Summary 39
Exercises 39
References 41
Chapter 2 Algorithm Analysis 43
2.1 Mathematical Background 43
2.2 Model 46
2.3 What to Analyze 46
2.4 Running Time Calculations 49
2.4.1 A Simple Example 49
2.4.2 General Rules 50
2.4.3 Solutions for the Maximum Subsequence Sum Problem 52
2.4.4 Logarithms in the Running Time 58
2.4.5 Checking Your Analysis 62
2.4.6 A Grain of Salt 63
Summary 63
Exercises 64
References 69
Chapter 3 Lists, Stacks, and Queues 71
3.1 Abstract Data Types (ADTs) 71
3.2 The List ADT 72
3.2.1 Simple Array Implementation of Lists 72
3.2.2 Simple Linked Lists 73
3.3 vector and list in the STL 74
3.3.1 Iterators 75
3.3.2 Example: Using erase on a List 77
3.3.3 const iterators 77
3.4 Implementation of vector 79
3.5 Implementation of list 83
3.6 The Stack ADT 94
3.6.1 Stack Model 94
3.6.2 Implementation of Stacks 95
3.6.3 Applications 96
3.7 The Queue ADT 104
3.7.1 Queue Model 104
3.7.2 Array Implementation of Queues 104
3.7.3 Applications of Queues 106
Summary 107
Exercises 108
Chapter 4 Trees 113
4.1 Preliminaries 113
4.1.1 Implementation of Trees 114
4.1.2 Tree Traversals with an Application 115
4.2 Binary Trees 119
4.2.1 Implementation 120
4.2.2 An Example: Expression Trees 121
4.3 The Search Tree ADT Binary Search Trees 124
4.3.1 contains 125
4.3.2 findMin and findMax 125
4.3.3 insert 129
4.3.4 remove 130
4.3.5 Destructor and Copy Assignment Operator 132
4.3.6 Average-Case Analysis 133
4.4 AVL Trees 136
4.4.1 Single Rotation 139
4.4.2 Double Rotation 142
4.5 Splay Trees 149
4.5.1 A Simple Idea (That Does Not Work) 150
4.5.2 Splaying 152
4.6 Tree Traversals (Revisited) 158
4.7 B-Trees 159
4.8 Sets and Maps in the Standard Library 165
4.8.1 Sets 165
4.8.2 Maps 166
4.8.3 Implementation of set and map 167
4.8.4 An Example That Uses Several Maps 168
Summary 174
Exercises 174
References 181
Chapter 5 Hashing 185
5.1 General Idea 185
5.2 Hash Function 186
5.3 Separate Chaining 188
5.4 Hash Tables Without Linked Lists 192
5.4.1 Linear Probing 193
5.4.2 Quadratic Probing 195
5.4.3 Double Hashing 199
5.5 Rehashing 200
5.6 Hash Tables in the Standard Library 204
5.7 Extendible Hashing 204
Summary 207
Exercises 208
References 211
Chapter 6 Priority Queues (Heaps) 213
6.1 Model 213
6.2 Simple Implementations 214
6.3 Binary Heap 215
6.3.1 Structure Property 215
6.3.2 Heap-Order Property 216
6.3.3 Basic Heap Operations 217
6.3.4 Other Heap Operations 220
6.4 Applications of Priority Queues 225
6.4.1 The Selection Problem 226
6.4.2 Event Simulation 227
6.5 d-Heaps 228
6.6 Leftist Heaps 229
6.6.1 Leftist Heap Property 229
6.6.2 Leftist Heap Operations 230
6.7 Skew Heaps 235
6.8 Binomial Queues 239
6.8.1 Binomial Queue Structure 240
6.8.2 Binomial Queue Operations 241
6.8.3 Implementation of Binomial Queues 244
6.9 Priority Queues in the Standard Library 251
Summary 251
Exercises 251
References 257
Chapter 7 Sorting 261
7.1 Preliminaries 261
7.2 Insertion Sort 262
7.2.1 The Algorithm 262
7.2.2 STL Implementation of Insertion Sort 263
7.2.3 Analysis of Insertion Sort 264
7.3 A Lower Bound for Simple Sorting Algorithms 265
7.4 Shellsort 266
7.4.1 Worst-Case Analysis of Shellsort 268
7.5 Heapsort 270
7.5.1 Analysis of Heapsort 272
7.6 Mergesort 274
7.6.1 Analysis of Mergesort 276
7.7 Quicksort 279
7.7.1 Picking the Pivot 280
7.7.2 Partitioning Strategy 282
7.7.3 Small Arrays 284
7.7.4 Actual Quicksort Routines 284
7.7.5 Analysis of Quicksort 287
7.7.6 A Linear-Expected-Time Algorithm for Selection 290
7.8 Indirect Sorting 292
7.8.1 vector Does Not Work 295
7 8.2 Smart Pointer Class 295
7 8.3 Overloading operator< 295
7 8.4 Dereferencing a Pointer with * 295
7 8.5 Overloading the Type Conversion Operator 295
7 8.6 Implicit Type Conversions Are Everywhere 296
7 8.7 Dual-Direction Implicit Conversions Can Cause Ambiguities 296
7 8.8 Pointer Subtraction Is Legal 297
7.9 A General Lower Bound for Sorting 297
7.9.1 Decision Trees 297
7.10 Bucket Sort 299
7.11 External Sorting 300
7 11.1 Why We Need New Algorithms 300
7 11.2 Model for External Sorting 300
7 11.3 The Simple Algorithm 301
7 11.4 Multiway Merge 302
7 11.5 Polyphase Merge 303
7 11.6 Replacement Selection 304
Summary 305
Exercises 306
References 311
Chapter 8 The Disjoint Set Class 315
8.1 Equivalence Relations 315
8.2 The Dynamic Equivalence Problem 316
8.3 Basic Data Structure 317
8.4 Smart Union Algorithms 321
8.5 Path Compression 324
8.6 Worst Case for Union-by-Rank and Path Compression 325
8.6.1 Analysis of the Union~ind Algorithm 326
8.7 An Application 331
Summary 334
Exercises 335
References 336
Chapter 9 Graph Algorithms 339
9.1 Definitions 339
9.1.1 Representation of Graphs 340
9.2 Topological Sort 342
9.3 Shortest-Path Algorithms 345
9.3.1 Unweighted Shortest Paths 347
9.3.2 Dijkstra's Algorithm 351
9.3.3 Graphs with Negative Edge Costs 360
9.3.4 Acyclic Graphs 360
9.3.5 All-Pairs Shortest Path 364
9.3.6 Shortest Path Example 365
9.4 Network Flow Problems 367
9.4.1 A Simple Maximum-Flow Algorithm 367
9.5 Minimum Spanning Tree 372
9.5.1 Prim's Algorithm 373
9.5.2 Kruskal's Algorithm 376
9.6 Applications of Depth-First Search 378
9.6.1 Undirected Graphs 379
9.6.2 Biconnectivity 381
9.6.3 Euler Circuits 385
9.6.4 Directed Graphs 388
9.6.5 Finding Strong Components 390
9.7 Introduction to NP-Completeness 392
9.7.1 Easy vs. Hard 392
9.7.2 The Class NP 393
9.7.3 NP-Complete Problems 394
Summary 396
Exercises 396
References 404
Chapter 10 Algorithm Design Techniques 409
10.1 Greedy Algorithms 409
10.1.1 A Simple Scheduling Problem 410
10.1.2 Huffman Codes 413
10.1.3 Approximate Bin Packing 419
10.2 Divide and Conquer 427
10.2.1 Running Time of Divide and Conquer Algorithms 428
10.2.2 Closest-Points Problem 430
10.2.3 The Selection Problem 435
10.2.4 Theoretical Improvements for Arithmetic Problems 438
10.3 Dynamic Programming 442
10.3.1 Using a Table Instead of Recursion 442
10.3.2 Ordering Matrix Multiplications 444
10.3.3 Optimal Binary Search Tree 447
10.3.4 All-Pairs Shortest Path 451
10.4 Randomized Algorithms 454
10.4.1 Random Number Generators 455
10.4.2 Skip Lists 459
10.4.3 Primality Testing 461
10.5 Backtracking Algorithms 464
10.5.1 The Turnpike Reconstruction Problem 465
10.5.2 Games 469
Summary 475
Exercises 475
References 485
Chapter 11 Amortized Analysis 491
11.1 An Unrelated Puzzle 492
11.2 Binomial Queues 492
11.3 Skew Heaps 497
11.4 Fibonacci Heaps 499
11.4.1 Cutting Nodes in Leftist Heaps 500
11.4.2 Lazy Merging for Binomial Queues 502
11.4.3 The Fibonacci Heap Operations 506
11.4.4 Proof of the Time Bound 506
11.5 Splay Trees 509
Summary 513
Exercises 513
References 515
Chapter 12 Advanced Data Structures and Implementation 517
12.1 Top-Down Splay Trees 517
12.2 Red-Black Trees 525
12.2.1 Bottom-Up Insertion 526
12.2.2 Top-Down Red-Black Trees 527
12.2.3 Top-Down Deletion 531
12.3 Deterministic Skip Lists 535
12.4 AA-Trees 540
12.5 Treaps 547
12.6 k-d Trees 549
12.7 Pairing Heaps 553
Summary 558
Exercises 558
References 563
Appendix A Separate Compilation of Class Templates 567
A.1 Everything in the Header 568
A.2 Explicit Instantiation 568
A.3 The export Directive 570
Index 571
