C++原版数据结构与算法详解：实战必备

data

structure

需积分: 10 52 浏览量更新于2024-07-19 收藏 16.86MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

《数据结构与算法C++》第二版是一本经典的计算机科学教材，由Michael T. Goodrich、Roberto Tamassia和David M. Mount三位作者合著，他们分别来自加州大学欧文分校、布朗大学和马里兰大学的计算机科学系。本书旨在提供深入的理论和实践指导，涵盖了一系列重要的数据结构，如堆（Heap）、排序（Sort）、树（Tree）以及图（Graph），这些都是软件开发中不可或缺的基础。书中详细阐述了各种数据结构的实现原理和应用场景，帮助读者理解如何利用C++语言高效地组织和操作数据。对于初学者来说，这本书提供了清晰的定义和概念，通过实例和练习，逐步提升编程技能。同时，对高级主题的探讨，如优先队列（Priority Queue）和排序算法的比较，有助于深入理解算法复杂度和优化策略。此外，书中的英文原文使得读者能够接触到更纯粹的技术表述和业界标准，这对于那些希望在国际范围内扩展技术视野的专业人士而言是宝贵的资源。每一章节都可能包含伪代码示例、代码片段以及详尽的注释，使读者能够在实践中学习并掌握核心概念。在出版方面，该书由John Wiley & Sons, Inc.出版，经过编辑团队的精心校对和设计，确保了内容的质量和可读性。封面图像取自艺术家Wuta Wuta Tjan-gala的作品，展示了艺术与科技的融合，同时也体现了原著的国际化视角。印刷方面，本书使用环保纸张，符合可持续发展的理念。值得注意的是，书中提及的一些商标，如Java和UNIX，都是知名技术品牌，这表明本书不仅涵盖了理论知识，还关注了实际工作中可能用到的软件工具和技术标准。通过阅读这本书，读者将不仅能掌握数据结构和算法的基础，还能了解到这些技术在业界的应用现状和发展趋势。《数据结构与算法C++》第二版是一本实用且权威的教材，适合计算机科学学生、工程师以及任何希望通过深入理解数据结构和算法来提升编程能力的人士参考。无论是作为学习资料还是专业参考书籍，它都能提供丰富的知识支持，帮助读者在这个快速发展的领域中保持竞争力。

资源详情

资源推荐

“main” — 2011/1/13 — 9:10 — page xiv — #14

xiv

Preface

We are also grateful to Karen Goodrich, Art Moorshead, Scott Smith, and Ioannis

Tollis for their insightful comments.

We are also truly indebted to the outside reviewers and readers for their co-

pious comments, emails, and constructive criticism, which were extremely use-

ful in writing this edition. We speciﬁcally thank the following reviewers for their

comments and suggestions: Divy Agarwal, University of California, Santa Bar-

bara; Terry Andres, University of Manitoba; Bobby Blumofe, University of Texas,

Austin; Michael Clancy, University of California, Berkeley; Larry Davis, Univer-

sity of Maryland; Scott Drysdale, Dartmouth College; Arup Guha, University of

Central Florida; Chris Ingram, University of Waterloo; Stan Kwasny, Washington

University; Calvin Lin, University of Texas at Austin; John Mark Mercer, McGill

University; Laurent Michel, University of Connecticut; Leonard Myers, California

Polytechnic State University, San Luis Obispo; David Naumann, Stevens Institute

of Technology; Robert Pastel, Michigan Technological University; Bina Rama-

murthy, SUNY Buffalo; Ken Slonneger, University of Iowa; C.V. Ravishankar,

University of Michigan; Val Tannen, University of Pennsylvania; Paul Van Ar-

ragon, Messiah College; and Christopher Wilson, University of Oregon.

We are grateful to our editor, Beth Golub, for her enthusiastic support of this

project. The team at Wiley has been great. Many thanks go to Mike Berlin, Lil-

ian Brady, Regina Brooks, Paul Crockett, Richard DeLorenzo, Jen Devine, Simon

Durkin, Micheline Frederick, Lisa Gee, Katherine Hepburn, Rachael Leblond, An-

dre Legaspi, Madelyn Lesure, Frank Lyman, Hope Miller, Bridget Morrisey, Chris

Ruel, Ken Santor, Lauren Sapira, Dan Sayre, Diana Smith, Bruce Spatz, Dawn

Stanley, Jeri Warner, and Bill Zobrist.

The computing systems and excellent technical support staff in the departments

of computer science at Brown University, University of California, Irvine, and Uni-

versity of Maryland gave us reliable working environments. This manuscript was

prepared primarily with the L

X typesetting package.

inally, we would like to warmly thank Isabel Cruz, Karen Goodrich, Jeanine

Mount, Giuseppe Di Battista, Franco Preparata, Ioannis Tollis, and our parents for

providing advice, encouragement, and support at various stages of the preparation

of this book. We also thank them for reminding us that there are things in life

beyond writing books.

Michael T. Goodrich

Roberto Tamassia

David M. Mount

“main” — 2011/1/13 — 9:10 — page xv — #15

Contents

A C++ Primer 1

1.1 Basic C++ Programming Elements . . . . . . . . . . . . . . . 2

1.1.1 A Simple C++ Program . . . . . . . . . . . . . . . . . . 2

1.1.2 Fundamental Types . . . . . . . . . . . . . . . . . . . . 4

1.1.3 Pointers, Arrays, and Structures . . . . . . . . . . . . . 7

1.1.4 Named Constants, Scope, and Namespaces . . . . . . . 13

1.2 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.2.1 Changing Types through Casti ng . . . . . . . . . . . . . 20

1.3 Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

1.4.1 Argument Passing . . . . . . . . . . . . . . . . . . . . . 28

1.4.2 Overloading and Inlining . . . . . . . . . . . . . . . . . 30

1.5 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.5.1 Class Structure . . . . . . . . . . . . . . . . . . . . . . 33

1.5.2 Constructors and Destructors . . . . . . . . . . . . . . . 37

1.5.3 Classes and Memory Allocation . . . . . . . . . . . . . . 40

1.5.4 Class Friends and Class Members . . . . . . . . . . . . . 43

1.5.5 The Standard Template Library . . . . . . . . . . . . . . 45

1.6 C++ Program and File Organization . . . . . . . . . . . . . . 47

1.6.1 An Example Program . . . . . . . . . . . . . . . . . . . 48

1.7 Writing a C++ Program . . . . . . . . . . . . . . . . . . . . . 53

1.7.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

1.7.2 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . 54

1.7.3 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

1.7.4 Testing and Debugging . . . . . . . . . . . . . . . . . . 57

1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2 Object-Oriented Design 65

2.1 Goals, Principles, and Patterns . .

. . . . . . . . . . . . . . 66

2.1.1 Object-Oriented Design Goals . . . . . . . . . . . . . . 66

2.1.2 Object-Oriented Design Principles . . . . . . . . . . . . 67

2.1.3 Design Patterns . . . . . . . . . . . . . . . . . . . . . . 70

“main” — 2011/1/13 — 9:10 — page xvi — #16

xvi

Contents

2.2 Inheritance and Polymor phism . . . . . . . . . . . . . . . . . 71

2.2.1 Inheritance in C++ . . . . . . . . . . . . . . . . . . . . . 71

2.2.2 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . 78

2.2.3 Examples of Inheritance in C++ . . . . . . . . . . . . . . 79

2.2.4 Multiple Inheritance and Class Casting . . . . . . . . . . 84

2.2.5 Interfaces and Abstract Cl asses . . . . . . . . . . . . . . 87

2.3 Templates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2.3.1 Function Templates . . . . . . . . . . . . . . . . . . . . 90

2.3.2 Class Templates . . . . . . . . . . . . . . . . . . . . . . 91

2.4 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

2.4.1 Exception Objects . . . . . . . . . . . . . . . . . . . . . 93

2.4.2 Throwing and Catching Exceptions . . . . . . . . . . . . 94

2.4.3 Exception Speciﬁcation . . . . . . . . . . . . . . . . . . 96

2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

3 Arrays, Linked Lists, and Recursion 103

3.1 Using Arrays . .

. . . . . . . . . . . . . . . . . . . . . . . . . 104

3.1.1 Storing Game Entries in an Array . . . . . . . . . . . . . 104

3.1.2 Sorting an Array . . . . . . . . . . . . . . . . . . . . . . 109

3.1.3 Two-Dimensional Arrays and Positional Games . . . . . 111

3.2 Singly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . 117

3.2.1 Implementing a Singly Linked List . . . . . . . . . . . . 117

3.2.2 Insertion to the Front of a Singly Linked List . . . . . . 119

3.2.3 Removal from the Front of a Singly Linked List . . . . . 119

3.2.4 Implementing a Generic Singly Linked List . . . . . . . . 121

3.3 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . 123

3.3.1 Insertion into a Doubly Linked List . . . . . . . . . . . . 123

3.3.2 Removal from a Doubly Linked List . . . . . . . . . . . 124

3.3.3 A C++ Implementation . . . . . . . . . . . . . . . . . . 125

3.4 Circularly Linked Lists and List Reversal . . . . . . . . . . . 129

3.4.1 Circularly Linked Lists . . . . . . . . . . . . . . . . . . . 129

3.4.2 Reversing a Linked List . . . . . . . . . . . . . . . . . . 133

3.5 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

3.5.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . 140

3.5.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . 144

3.5.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . 147

3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

4 Analysis Tools 153

4.1 The Seven Functions Used in This Book . .

. . . . . . . . . 154

4.1.1 The Constant Function . . . . . . . . . . . . . . . . . . 154

4.1.2 The Logari thm Function . . . . . . . . . . . . . . . . . 154

“main” — 2011/1/13 — 9:10 — page xvii — #17

Contents

xvii

4.1.3 The Linear Function . . . . . . . . . . . . . . . . . . . . 156

4.1.4 The N-Log-N Function . . . . . . . . . . . . . . . . . . 156

4.1.5 The Quadratic Function . . . . . . . . . . . . . . . . . . 156

4.1.6 The Cubic Function and Other Polynomials . . . . . . . 158

4.1.7 The Exponential Function . . . . . . . . . . . . . . . . . 159

4.1.8 Comparing Growt h Rates . . . . . . . . . . . . . . . . . 161

4.2 Analysis of Algorithms . . . . . . . . . . . . . . . . . . . . . 162

4.2.1 Experimental Studies . . . . . . . . . . . . . . . . . . . 163

4.2.2 Primitive Operations . . . . . . . . . . . . . . . . . . . 164

4.2.3 Asymptotic Notation . . . . . . . . . . . . . . . . . . . 166

4.2.4 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . 170

4.2.5 Using the Big-Oh Notation . . . . . . . . . . . . . . . . 172

4.2.6 A Recursive Algorithm for Computing Powers . . . . . . 176

4.2.7 Some More Examples of Algorithm Analysis . . . . . . . 177

4.3 Simple Justiﬁcation Techniques . . . . . . . . . . . . . . . . 181

4.3.1 By Example . . . . . . . . . . . . . . . . . . . . . . . . 181

4.3.2 The “Contra” Attack . . . . . . . . . . . . . . . . . . . 181

4.3.3 Induction and Loop Invariants . . . . . . . . . . . . . . 182

4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

5 Stacks, Queues, and Deques 193

5.1 Stacks . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

5.1.1 The Stack Abstra ct Data Type . . . . . . . . . . . . . . 195

5.1.2 The STL Stack . . . . . . . . . . . . . . . . . . . . . . 196

5.1.3 A C++ Stack Interface . . . . . . . . . . . . . . . . . . 196

5.1.4 A Simple Array-Based Stack Implementation . . . . . . 198

5.1.5 Implementing a Stack with a Generic Linked List . . . . 202

5.1.6 Reversing a Vector Using a Stack . . . . . . . . . . . . . 203

5.1.7 Matching Parentheses and HTML Tags . . . . . . . . . 204

5.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

5.2.1 The Queue Abstract Data Type . . . . . . . . . . . . . 208

5.2.2 The STL Queue . . . . . . . . . . . . . . . . . . . . . . 209

5.2.3 A C++ Queue Interface . . . . . . . . . . . . . . . . . . 210

5.2.4 A Simple Array-Based Implementation . . . . . . . . . . 211

5.2.5 Implementing a Queue with a Circularly Linked List . . . 213

5.3 Double-Ended Queues . . . . . . . . . . . . . . . . . . . . . . 217

5.3.1 The Deque A bstract Data Type . . . . . . . . . . . . . 217

5.3.2 The STL Deque . . . . . . . . . . . . . . . . . . . . . . 218

5.3.3 Implementing a Deque with a Doubly Linked List . . . . 218

5.3.4 Adapters and the Adapter D esi gn Patt ern . . . . . . . . 220

5.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223

“main” — 2011/1/13 — 9:10 — page xviii — #18

xviii

Contents

6 L ist and Iterator ADT s 227

6.1 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

6.1.1 The Vector Abstract Data Type . . . . . . . . . . . . . 228

6.1.2 A Simple Array-Based Implementation . . . . . . . . . . 229

6.1.3 An Extendable Array Implementation . . . . . . . . . . . 231

6.1.4 STL Vectors . . . . . . . . . . . . . . . . . . . . . . . . 236

6.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

6.2.1 Node-Based Operations and Iterators . . . . . . . . . . . 238

6.2.2 The List Abstract Data Type . . . . . . . . . . . . . . . 240

6.2.3 Doubly Linked List Implementation . . . . . . . . . . . . 242

6.2.4 STL Lists . . . . . . . . . . . . . . . . . . . . . . . . . 247

6.2.5 STL Containers and Iterators . . . . . . . . . . . . . . . 248

6.3 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

6.3.1 The Sequence Abstract Data Type . . . . . . . . . . . . 255

6.3.2 Implementing a Sequence wit h a Doubly Linked List . . 255

6.3.3 Implementing a Sequence wit h an Array . . . . . . . . . 257

6.4 Case Study: Bubble-Sort on a Sequence . . . . . . . . . . . 259

6.4.1 The Bubble-Sort Algorithm . . . . . . . . . . . . . . . . 259

6.4.2 A Sequence-Based Analys is of Bubble-Sort . . . . . . . . 260

6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

7 Trees 267

7.1 General Trees . .

. . . . . . . . . . . . . . . . . . . . . . . . . 268

7.1.1 Tree Deﬁnitions and Properties . . . . . . . . . . . . . . 269

7.1.2 Tree Functions . . . . . . . . . . . . . . . . . . . . . . . 272

7.1.3 A C++ Tree Interface . . . . . . . . . . . . . . . . . . . 273

7.1.4 A Linked Structure for General Trees . . . . . . . . . . . 274

7.2 Tree Traversal Algorithm s . . . . . . . . . . . . . . . . . . . 275

7.2.1 Depth and Height . . . . . . . . . . . . . . . . . . . . . 275

7.2.2 Preorder Traversal . . . . . . . . . . . . . . . . . . . . . 278

7.2.3 Postorder Traversal . . . . . . . . . . . . . . . . . . . . 281

7.3 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

7.3.1 The Binary Tree ADT . . . . . . . . . . . . . . . . . . . 285

7.3.2 A C++ Binary Tree Interface . . . . . . . . . . . . . . . 286

7.3.3 Properties of Binary Trees . . . . . . . . . . . . . . . . 287

7.3.4 A Linked Structure for Binary Trees . . . . . . . . . . . 289

7.3.5 A Vector-Based Structure for Binary Trees . . . . . . . . 295

7.3.6 Traversals of a Binary Tree . . . . . . . . . . . . . . . . 297

7.3.7 The Template Function Pattern . . . . . . . . . . . . . 303

7.3.8 Representing General Trees with Binary Trees . . . . . . 309

7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

剩余737页未读，继续阅读

WANG_MAGUS

粉丝: 1
资源: 6

C++原版数据结构与算法详解：实战必备

数据结构、算法与应用C++语言描述高清版

[数据结构与算法C++版][英文版].Data.Structures.and.Algorithms.in.C++.(Adam.Drozdek).2nd.Ed.2001.part4

数据结构算法与应用——C++语言描述英文原版

数据结构与算法C++

数据结构与算法c++

数据结构 查找算法 c++

数据结构与算法c++版有什么推荐的视频和书？

数据结构与算法c++笔记

C++ stl和数据结构算法的区别

数据结构与算法c++环境搭建

c++数据结构与算法 理解

数据结构与算法c++版第三版答案

数据结构与算法C++语言第4版

数据结构与算法分析c++描述

c++数据结构和算法

数据结构与算法严蔚敏 c++

数据结构与算法学习c++

数据结构与算法分析 c++王立柱pdf

《数据结构与算法——c++版》

C++数据结构与算法

最新资源

数据结构查找算法 c++

c++数据结构与算法理解