数据结构与算法分析

作者: 维斯

出版社: 人民邮电出版社

出版时间: 2005-08

版次: 1

ISBN: 9787115139849

定价: 49.00

装帧: 平装

开本: 其他

纸张: 胶版纸

页数: 501页

字数: 727千字

分类: 教材教辅考试>教材>大学教材>工程技术

86人买过

本书是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了本书创新的对算法和数据结构的讲授方法。通过C程序的实现，着重阐述了抽象数据类型（ADT）的概念，并对算法的效率、性能和运行时间进行了分析。本书适合作为本科数据结构课程或研究生第一年算法分析课程的教材。第1~9章为大多数本科一学期数据结构课程提供了足够的材料。多学时课程可讲授第10章。研究生的算法分析课程可以使用第6~12章的内容。 Mark Allen Weiss美国佛罗里达国际大学计算机学院教授，普林斯顿大学计算机科学博士，他目前是AP考试计算机学科委员会的主席。除本书外，他还撰写了Data Structures and Problem Solving Using Java（中文版第3版即将由人民邮电出版社出版）等著作。 Adapter's Foreword

Preface

1  Introduction    1

     1.1.  What's the Book About?    1

     1.2.  A Brief Introduction to Recursion    3

          Summary     7

          Exercises     7

          References     8

2  Algorithm Analysis    9

     2.1.  Mathematical Background    9

     2.2.  Model    12

     2.3.  What to Analyze    12

     2.4.  Running Time Calculations    14

           2.4.1.  A Simple Example    15

           2.4.2.  General Rules    15

           2.4.3.  Solutions for the Maximum Subsequence Sum Problem     18

           2.4.4.  Logarithms in the Running Time     22

           2.4.5.  Checking Your Analysis     27

           2.4.6.  A Grain of Salt     27

          Summary     28

          Exercises     29

          References     33

3  Lists, Stacks, and Queues     35

     3.1.  Abstract Data Types (ADTs)    35

     3.2.  The List AnT    36

           3.2.1.  Simple Array Implementation of Lists    37

           3.2.2.  Linked Lists    37

           3.2.3.  Programming Details    38

           3.2.4.  Common Errors    43

           3.2.5.  Doubly Linked Lists    45

           3.2.6.  Circularly Linked Lists    46

           3.2.7.  Examples    46

           3.2.8.  Cursor Implementation of Linked Lists    50

     3.3.  The Stack ADT    56

           3.3.1.  Stack Model    56

           3.3.2.  Implementation of Stacks   57

           3.3.3.  Applications       65

    3.4.  The Queue AnT               73

           3.4.1.  Queue Model       73

           3.4.2.  Array Implementation of Queues    73

           3.4.3.  Applications of Queues     78

          Summary    79

          Exercises    79

4  Trees    83

     4.1.  Preliminaries    83

           4.1.1.  Terminology      83

           4.1.2.  Tree Traversals with an Application    84

     4.2.  Binary Trees                 85

           4.2.1.  Implementation     86

           4.2.2.  Expression Trees    87

           4.2.3.  Tree Traversals     90

    4.3.  The Search Tree ADT  Binary Search Trees    97

           4.3.1. MakeEmpty   97

           4.3.2. Find         97

           4.3.3.  FindMin and FindMax    99

           4.3.4.  Insert    100

           4.3.5.  Delete   101

           4.3.6.  Average-Case Analysis103

     4.4.  AVL Trees    106

           4.4.1.  Single Rotation     108

           4.4.2.  Double Rotation    111

     4.5.  Splay Trees    119

           4.5.1.  A Simple Idea (That Does Not Work)    12 0

           4.5.2. Splaying   12 2

     4.6.  B-Trees            128

           Summary     133

           Exercises     134

           References     141

5  Priority Queues (Heaps)    145

     5.1.  Model    145

     5.2.  Simple Implementations    146

     5.3.  Binary Heap    147

           5.3.1.  Structure Property       147

           5.3.2.  Heap Order Property     148

           5.3.3.  Basic Heap Operations    150

           5.3.4.  Other Heap Operations    154

     5.4.  Applications of Priority Queues     157

           5.4.1.  The Selection Problem    157

           5.4.2.  Event Simulation    159

     5.5.  d-Heaps    160

     5.6.  Leftist Heaps    161

           5.6.1.  Leftist Heap Property    161

           5.6.2.  Leftist Heap Operations   162

     5.7.  Skew Heaps    168

     5.8.  Binomial Queues    170

           5.8.1.  Binomial Queue Structure    170

           5.8.2.  Binomial Queue Operations    172

           5.8.3.  Implementation of Binomial Queues    173

          Summary    180

          Exercises    180

          References   184

6  Sorting   187

     6.1.  Preliminaries    187

     6.2.  Insertion Sort    188

           6.2.1.  The Algorithm    188

           6.2.2.  Analysis of Insertion Sort    189

           6.3.  A Lower Bound for Simple Sorting Algorithms    189

     6.4.  Shellsort    190

           6.4.1.  Worst-Case Analysis of Shellsort    192

     6.5.  Heapsort    194

           6.5.1.  Analysis of Heapsort    196

     6.6.  Mergesort    198

           6.6.1.  Analysis of Mergesort    200

     6.7.  Quicksort    203

           6.7.1.  Picking the Pivot    204

           6.7.2.  Partitioning Strategy   205

           6.7.3.  Small Arrays    20 8

           6.7.4.  Actual Quicksort Routines    208

           6.7.5. Analysis of Quicksort   209

           6.7.6.  A Linear-Expected-Time Algorithm for Selection    213

     6.8.  Sorting Large Structures    215

     6.9.  A General Lower Bound for Sorting    216

           6.9.1.  Decision Trees    217

     6.10.  Bucket Sort and Radix Sort    219

     6.11.  External Sorting         222

           6.11.1.  Why We Need New Algorithms    222

           6.11.2.  Model for External Sorting    222

           6.11.3.  The Simple Algorithm    222

           6.11.4.  Multiway Merge    224

           6.11.5.  Polyphase Merge     225

           6.11.6.  Replacement Selection    226

           Summary    227

           Exercises    229

7  Hashing    235

    7.1.  General Idea    235

    7.2.  Hash Function    237

    7.3.  Separate Chaining    239

    7.4.  Open Addressing      244

          7.4.1.  Linear Probing     244

          7.4.2.  Quadratic Probing  247

          7.4.3.  Double Hashing    251

    7.5.  Rehashing    252

    7.6.  Extendible Hashing    255

         Summary    258

         Exercises    259

         References    262

8  The Disjoint Set AnT    265

     8.1.  Equivalence Relations    265

     8.2.  The Dynamic Equivalence Problem    266

     8.3.  Basic Data Structure    267

     8.4.  Smart Union Algorithms    271

     8.5.  Path Compression    273

     8.6.  Worst Case for Union-by-Rank and Path Compression    275

           8.6.1.  Analysis of the Union/Find Algorithm    275

     8.7.  An Application    281

          Summary    281

          Exercises    282

          References    283

9  Graph Algorithms    285

     9.1.  Definitions    285

           9.1.1.  Representation of Graphs    286

     9.2.  Topological Sort    288

     9.3.  Shortest-Path Algorithms    292

           9.3.1.  Unweighted Shortest Paths    293

           9.3.2.  Dijkstra's Algorithm    297

           9.3.3.  Graphs with Negative Edge Costs    306

           9.3.4.  Acyclic Graphs   307

           9.3.5. All-Pairs Shortest Path    310

     9.4.  Network Flow Problems   310

           9.4.1.  A Simple Maximum-Flow Algorithm    311

     9.5.  Minimum Spanning Tree    315

           9.5.1.  Prim's Algorithm    316

           9.5.2.  Kruskal's Algorithm    318

     9.6.  Applications of Depth-First Search    3:21

           9.6.1.  Undirected Graphs    322

           9.6.2.  Biconnectivity    324

           9.6.3.  Euler Circuits    328

           9.6.4.  Directed Graphs    331

           9.6.5.  Finding Strong Components    333

     9.7.  Introduction to NP-Completeness    334

           9.7.2.  The Class NP    336

           9.7.3.  NP-Complete Problems    337

           Summary    339

           Exercises    339

           References    345

10  Algorithm Design Techniques    349

     10.1.  Greedy Algorithms    349

           10.1.1.  A Simple Scheduling Problem    350

           10.1.2.  Huffman Codes    353

           10.1.3.  Approximate Bin Packing    359

     10.2.  Divide and Conquer    367

            10.2.1.  Running Time of Divide and Conquer Algorithms    368

           10.2.2.  Closest-Points Problem    370

           10.2.3.  The Selection Problem    375

           10.2.4.  Theoretical Improvements for Arithmetic Problems    378

     10.3.  Dynamic Programming    382

           10.3.1.  Using a Table Instead of Recursion    382

           10.3.2.  Ordering Matrix Multiplications    385

           10.3.3.  Optimal Binary Search Tree    389

           10.3.4.  All-Pairs Shortest Path    392

     10.4.  Randomized Algorithms    394

           10.4.1.  Random Number Generators    396

           10.4.2. Skip Lists   399

           10.4.3.  Primality Testing    401

     10.5.  Backtracking Algorithms    403

           10.5.1.  The Turnpike Reconstruction Problem    405

           10.5.2.  Games    407

            Summary    415

            Exercises    417

            References     424

ll  Amortized Analysis    429

     11.1.  An Unrelated Puzzle    430

     11.2.  Binomial Queues    430

     11.3.  Skew Heaps    435

     11.4.  Fibonacci Heaps    437

           11.4.1.  Cutting Nodes in Leftist Heaps    430

           11.4.2.  Lazy Merging for Binomial Queues    441

           11.4.3.  The Fibonacci Heap Operations    444

           11.4.4.  Proof of the Time Bound    445

     11.5.  Splay Trees    447

           Summary    451

           Exercises    452

           References   453

12  Advanced Data Structures and Implementation    455

      12.1.  Top-Down Splay Trees    455

      12.2.  Red Black Trees    459

           12.2.1.  Bottom-Up Insertion    464

           12.2.2.  Top-Down Red Black Trees    465

           12.2.3.  Top-Down Deletion    467

     12.3.  Deterministic Skip Lists    471

     12.4.  &A-Trees    478

     12.5.  Treaps    484

     12.6.  k-d Trees    487

     12.7.  Pairing Heaps    490

           Summary    496

           Exercises    497

           References    499
内容简介:
本书是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了本书创新的对算法和数据结构的讲授方法。通过C程序的实现，着重阐述了抽象数据类型（ADT）的概念，并对算法的效率、性能和运行时间进行了分析。本书适合作为本科数据结构课程或研究生第一年算法分析课程的教材。第1~9章为大多数本科一学期数据结构课程提供了足够的材料。多学时课程可讲授第10章。研究生的算法分析课程可以使用第6~12章的内容。
作者简介:
Mark Allen Weiss美国佛罗里达国际大学计算机学院教授，普林斯顿大学计算机科学博士，他目前是AP考试计算机学科委员会的主席。除本书外，他还撰写了Data Structures and Problem Solving Using Java（中文版第3版即将由人民邮电出版社出版）等著作。
目录:
Adapter's Foreword

Preface

1  Introduction    1

     1.1.  What's the Book About?    1

     1.2.  A Brief Introduction to Recursion    3

          Summary     7

          Exercises     7

          References     8

2  Algorithm Analysis    9

     2.1.  Mathematical Background    9

     2.2.  Model    12

     2.3.  What to Analyze    12

     2.4.  Running Time Calculations    14

           2.4.1.  A Simple Example    15

           2.4.2.  General Rules    15

           2.4.3.  Solutions for the Maximum Subsequence Sum Problem     18

           2.4.4.  Logarithms in the Running Time     22

           2.4.5.  Checking Your Analysis     27

           2.4.6.  A Grain of Salt     27

          Summary     28

          Exercises     29

          References     33

3  Lists, Stacks, and Queues     35

     3.1.  Abstract Data Types (ADTs)    35

     3.2.  The List AnT    36

           3.2.1.  Simple Array Implementation of Lists    37

           3.2.2.  Linked Lists    37

           3.2.3.  Programming Details    38

           3.2.4.  Common Errors    43

           3.2.5.  Doubly Linked Lists    45

           3.2.6.  Circularly Linked Lists    46

           3.2.7.  Examples    46

           3.2.8.  Cursor Implementation of Linked Lists    50

     3.3.  The Stack ADT    56

           3.3.1.  Stack Model    56

           3.3.2.  Implementation of Stacks   57

           3.3.3.  Applications       65

    3.4.  The Queue AnT               73

           3.4.1.  Queue Model       73

           3.4.2.  Array Implementation of Queues    73

           3.4.3.  Applications of Queues     78

          Summary    79

          Exercises    79

4  Trees    83

     4.1.  Preliminaries    83

           4.1.1.  Terminology      83

           4.1.2.  Tree Traversals with an Application    84

     4.2.  Binary Trees                 85

           4.2.1.  Implementation     86

           4.2.2.  Expression Trees    87

           4.2.3.  Tree Traversals     90

    4.3.  The Search Tree ADT  Binary Search Trees    97

           4.3.1. MakeEmpty   97

           4.3.2. Find         97

           4.3.3.  FindMin and FindMax    99

           4.3.4.  Insert    100

           4.3.5.  Delete   101

           4.3.6.  Average-Case Analysis103

     4.4.  AVL Trees    106

           4.4.1.  Single Rotation     108

           4.4.2.  Double Rotation    111

     4.5.  Splay Trees    119

           4.5.1.  A Simple Idea (That Does Not Work)    12 0

           4.5.2. Splaying   12 2

     4.6.  B-Trees            128

           Summary     133

           Exercises     134

           References     141

5  Priority Queues (Heaps)    145

     5.1.  Model    145

     5.2.  Simple Implementations    146

     5.3.  Binary Heap    147

           5.3.1.  Structure Property       147

           5.3.2.  Heap Order Property     148

           5.3.3.  Basic Heap Operations    150

           5.3.4.  Other Heap Operations    154

     5.4.  Applications of Priority Queues     157

           5.4.1.  The Selection Problem    157

           5.4.2.  Event Simulation    159

     5.5.  d-Heaps    160

     5.6.  Leftist Heaps    161

           5.6.1.  Leftist Heap Property    161

           5.6.2.  Leftist Heap Operations   162

     5.7.  Skew Heaps    168

     5.8.  Binomial Queues    170

           5.8.1.  Binomial Queue Structure    170

           5.8.2.  Binomial Queue Operations    172

           5.8.3.  Implementation of Binomial Queues    173

          Summary    180

          Exercises    180

          References   184

6  Sorting   187

     6.1.  Preliminaries    187

     6.2.  Insertion Sort    188

           6.2.1.  The Algorithm    188

           6.2.2.  Analysis of Insertion Sort    189

           6.3.  A Lower Bound for Simple Sorting Algorithms    189

     6.4.  Shellsort    190

           6.4.1.  Worst-Case Analysis of Shellsort    192

     6.5.  Heapsort    194

           6.5.1.  Analysis of Heapsort    196

     6.6.  Mergesort    198

           6.6.1.  Analysis of Mergesort    200

     6.7.  Quicksort    203

           6.7.1.  Picking the Pivot    204

           6.7.2.  Partitioning Strategy   205

           6.7.3.  Small Arrays    20 8

           6.7.4.  Actual Quicksort Routines    208

           6.7.5. Analysis of Quicksort   209

           6.7.6.  A Linear-Expected-Time Algorithm for Selection    213

     6.8.  Sorting Large Structures    215

     6.9.  A General Lower Bound for Sorting    216

           6.9.1.  Decision Trees    217

     6.10.  Bucket Sort and Radix Sort    219

     6.11.  External Sorting         222

           6.11.1.  Why We Need New Algorithms    222

           6.11.2.  Model for External Sorting    222

           6.11.3.  The Simple Algorithm    222

           6.11.4.  Multiway Merge    224

           6.11.5.  Polyphase Merge     225

           6.11.6.  Replacement Selection    226

           Summary    227

           Exercises    229

7  Hashing    235

    7.1.  General Idea    235

    7.2.  Hash Function    237

    7.3.  Separate Chaining    239

    7.4.  Open Addressing      244

          7.4.1.  Linear Probing     244

          7.4.2.  Quadratic Probing  247

          7.4.3.  Double Hashing    251

    7.5.  Rehashing    252

    7.6.  Extendible Hashing    255

         Summary    258

         Exercises    259

         References    262

8  The Disjoint Set AnT    265

     8.1.  Equivalence Relations    265

     8.2.  The Dynamic Equivalence Problem    266

     8.3.  Basic Data Structure    267

     8.4.  Smart Union Algorithms    271

     8.5.  Path Compression    273

     8.6.  Worst Case for Union-by-Rank and Path Compression    275

           8.6.1.  Analysis of the Union/Find Algorithm    275

     8.7.  An Application    281

          Summary    281

          Exercises    282

          References    283

9  Graph Algorithms    285

     9.1.  Definitions    285

           9.1.1.  Representation of Graphs    286

     9.2.  Topological Sort    288

     9.3.  Shortest-Path Algorithms    292

           9.3.1.  Unweighted Shortest Paths    293

           9.3.2.  Dijkstra's Algorithm    297

           9.3.3.  Graphs with Negative Edge Costs    306

           9.3.4.  Acyclic Graphs   307

           9.3.5. All-Pairs Shortest Path    310

     9.4.  Network Flow Problems   310

           9.4.1.  A Simple Maximum-Flow Algorithm    311

     9.5.  Minimum Spanning Tree    315

           9.5.1.  Prim's Algorithm    316

           9.5.2.  Kruskal's Algorithm    318

     9.6.  Applications of Depth-First Search    3:21

           9.6.1.  Undirected Graphs    322

           9.6.2.  Biconnectivity    324

           9.6.3.  Euler Circuits    328

           9.6.4.  Directed Graphs    331

           9.6.5.  Finding Strong Components    333

     9.7.  Introduction to NP-Completeness    334

           9.7.2.  The Class NP    336

           9.7.3.  NP-Complete Problems    337

           Summary    339

           Exercises    339

           References    345

10  Algorithm Design Techniques    349

     10.1.  Greedy Algorithms    349

           10.1.1.  A Simple Scheduling Problem    350

           10.1.2.  Huffman Codes    353

           10.1.3.  Approximate Bin Packing    359

     10.2.  Divide and Conquer    367

            10.2.1.  Running Time of Divide and Conquer Algorithms    368

           10.2.2.  Closest-Points Problem    370

           10.2.3.  The Selection Problem    375

           10.2.4.  Theoretical Improvements for Arithmetic Problems    378

     10.3.  Dynamic Programming    382

           10.3.1.  Using a Table Instead of Recursion    382

           10.3.2.  Ordering Matrix Multiplications    385

           10.3.3.  Optimal Binary Search Tree    389

           10.3.4.  All-Pairs Shortest Path    392

     10.4.  Randomized Algorithms    394

           10.4.1.  Random Number Generators    396

           10.4.2. Skip Lists   399

           10.4.3.  Primality Testing    401

     10.5.  Backtracking Algorithms    403

           10.5.1.  The Turnpike Reconstruction Problem    405

           10.5.2.  Games    407

            Summary    415

            Exercises    417

            References     424

ll  Amortized Analysis    429

     11.1.  An Unrelated Puzzle    430

     11.2.  Binomial Queues    430

     11.3.  Skew Heaps    435

     11.4.  Fibonacci Heaps    437

           11.4.1.  Cutting Nodes in Leftist Heaps    430

           11.4.2.  Lazy Merging for Binomial Queues    441

           11.4.3.  The Fibonacci Heap Operations    444

           11.4.4.  Proof of the Time Bound    445

     11.5.  Splay Trees    447

           Summary    451

           Exercises    452

           References   453

12  Advanced Data Structures and Implementation    455

      12.1.  Top-Down Splay Trees    455

      12.2.  Red Black Trees    459

           12.2.1.  Bottom-Up Insertion    464

           12.2.2.  Top-Down Red Black Trees    465

           12.2.3.  Top-Down Deletion    467

     12.3.  Deterministic Skip Lists    471

     12.4.  &A-Trees    478

     12.5.  Treaps    484

     12.6.  k-d Trees    487

     12.7.  Pairing Heaps    490

           Summary    496

           Exercises    497

           References    499