数据结构与算法分析

数据结构与算法分析
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者:
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
查看详情
相关图书 / 更多
数据结构与算法分析
数据新闻与信息可视化
周葆华;徐笛;崔迪
数据结构与算法分析
数据合规师概论
郑少华、商建刚
数据结构与算法分析
数据思维——从数据分析到商业价值(第2版)
王汉生
数据结构与算法分析
数据科学优化方法
孙怡帆
数据结构与算法分析
数据处理技术与方法研究
付雯
数据结构与算法分析
数据治理 工业企业数字化转型之道 第2版
祝守宇
数据结构与算法分析
数据可视化Pyecharts探秘实践教程/新工科大数据专业群实践丛书
余先昊、袁华 编
数据结构与算法分析
数据标注工程——语言知识与应用
于东
数据结构与算法分析
数据可视化基础与应用
刘佳 许桂秋 李静雯
数据结构与算法分析
数据要素的产权分析与治理机制
王凯军 著
数据结构与算法分析
数据权利保护的模式与机制
余圣琪
数据结构与算法分析
数据科学伦理:概念、技术和警世故事
[比利时]大卫·马滕斯(David;Martens
您可能感兴趣 / 更多
数据结构与算法分析
非必要阅读(诺奖得主辛波斯卡私人书单,以阅读回答生活,中文世界初次引进,诗人黄灿然翻译)
维斯瓦娃·辛波斯卡 著;黄灿然 译
数据结构与算法分析
希姆博尔斯卡全集(共5册)
维斯瓦娃·希姆博尔斯卡 著;林洪亮、李怡楠、龚泠兮、吴俣、巩宁波 译
数据结构与算法分析
希姆博尔斯卡选读札记I
维斯瓦娃·希姆博尔斯卡 著;吴俣 译
数据结构与算法分析
希姆博尔斯卡选读札记Ⅱ
维斯瓦娃·希姆博尔斯卡 著;巩宁波、赵祯、张慧玲 译
数据结构与算法分析
希姆博尔斯卡信札
维斯瓦娃•希姆博尔斯卡 著;李怡楠 译
数据结构与算法分析
我曾这样寂寞生活(精装)
维斯拉瓦·辛波斯卡
数据结构与算法分析
牙种植学的负荷方案·牙列缺失的负荷方案(第4卷)
维斯梅耶(D.Wismeijer)、布瑟(D.Buser)、贝尔瑟(U.Belser) 编;宿玉成 译
数据结构与算法分析
数码单反摄影完全自学
维斯摄影 编
数据结构与算法分析
数码单反摄影实用手册
维斯摄影 编
数据结构与算法分析
数据结构与问题求解Java语言描述
维斯
数据结构与算法分析
数据结构与问题求解
维斯
数据结构与算法分析
同居乐无穷:共同生活的权利和义务
维斯寇