C++编程：数据结构与算法解析第二版

需积分: 9 163 浏览量更新于2024-07-24 收藏 17.02MB PDF 举报

"Data Structures and Algorithms in C++ 2nd ed" 是一本关于数据结构和算法的C++书籍，由Michael T. Goodrich、Roberto Tamassia和David M. Mount合著。这本书可能是大学计算机科学课程的标准教材，适合对C++编程和算法有基础的读者。在深入讨论之前，需要明确数据结构和算法在计算机科学中的重要性。数据结构是组织和存储数据的方式，而算法是解决问题或执行特定任务的步骤。C++是一种强大的系统编程语言，特别适合实现这些数据结构和算法，因为它提供了对内存的低级控制和面向对象的编程特性。本书第二版可能包含了更新的内容和改进，以适应不断发展的计算机科学领域。描述中提到的“需要解决方案”，暗示书内可能包含一系列练习题，但缺乏配套的解答，这可能对学习者来说是一个挑战，他们可能需要寻找其他资源来辅助学习。书中可能涵盖的主题包括但不限于： 1. 基本数据结构：数组、链表、栈、队列、哈希表。 2. 复杂数据结构：树（二叉树、平衡树如AVL和红黑树）、图、堆和优先队列。 3. 算法分析：时间复杂度和空间复杂度分析，以及大O记法。 4. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。 5. 搜索算法：线性搜索、二分搜索、深度优先搜索（DFS）、广度优先搜索（BFS）。 6. 图算法：最短路径算法（Dijkstra、Floyd-Warshall）、拓扑排序、最小生成树（Prim's和Kruskal's算法）。 7. 动态规划和递归问题解决策略。 8. 排列组合与递推关系。 9. 分治和回溯算法。作者们可能通过实例和练习来阐述这些概念，帮助读者理解和应用。此外，书中可能还涉及C++编程技巧，如模板、STL（标准模板库）的使用，以及如何高效地利用C++的特性来实现数据结构和算法。书中的图像和插图可能会帮助解释复杂的概念，使抽象的理论更容易理解。封面提到的“Emu Dreaming”可能代表了艺术与科学的结合，暗示了书中的内容不仅仅是技术性的，也有可能融入了创造性和启发性的元素。然而，由于没有提供具体的书页内容，以上分析基于对一般数据结构和算法教科书的常规理解。实际的学习体验和具体内容会依赖于书中实际的组织结构和教学方法。对于那些希望深入学习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页未读，继续阅读

joe716

粉丝: 0
资源: 1

C++编程：数据结构与算法解析第二版

Data Structures and Algorithms in C++(2nd) --book and Code

Data Structures, Algorithms and Applications in C++ 2nd Edition

data structures and algorithms in java 2nd 编程作业

data structures and algorithms in python

data structures and algorithms

c# data structures and algorithms

data structures and algorithms for python

data structures and algorithms with javascript

data structures and algorithm analysis in c++ 第4版 源码

benjamin baka python data structures and algorithms

最新资源

data structures and algorithm analysis in c++ 第4版源码