数据结构与STL：英文版

CHAPTER l

Classes in C++ 1

1. 1 Classes 2

CHAPTER 2

Storage Structures for Container

Classes 3s

2. 1 Pointers 36

2. 2 Arrays 41

2. 3 Container Classes 42

CHAPIER 3

Introduction to Software

Engineering 63

3. 1 The Software Developmental Life Cycle 64

3. 2 Problem Analysis 64

3. 3 Program Design 67

3. 4 Program Implementation 71

3 .5 Program Maintenance 87

CHAPTER 4

4. 1 Introduction 94

4. 2 Factorials 94

4. 3 Decimal-to-Binary 99

4. 4 Towers of Hanoi 103

4. 5 Backtracking 112

4. 6 Binary Search 125

4. 7 Generating Permutations 135

4. 8 Indirect Recursion 144

4. 9 The Cost of Recursion 145

Summary 146

Exercises 147

Programming Project 4.1 : An Iterative Version of

Towers of Hanoi 154

Programming Project 4.2: The Eight-Queens

Problem 156

Programming Project 4.3: A Knight's Tour 158

CHAPTER 5

5. 1 The Standard Template Library 164

5. 2 Vectors 165

5. 3 A Vector Application: High-Precision

Arithmetic 184

5. 4 Deques 190

5. 5 A Deque Application: Very Long

Integers 198

Summary 199

Exercises 199

Programming Project 5.1 : Extending the

very_long_int Class 203

Programming Project 5.2: An Alternative

Implementation of the deque Class 204

CHAPTER 6

Lists 205

6. 1 Lists 206

6. 2 List Application: A Line Editor 228

Summary 240

Exercises 241

Programming Project 6.1: Extending the Editor

Class 244

Programming Project 6.2: An Alternate Design and

Implementation of the list Class 251

CHAPTER 7

Queues and Staeks 253

7. 1 Queues 254

7. 2 Computer Simulation 261

7. 3 A Queue Application: A Simulated Car

Wash 264

7. 4 Stacks 274

7. 5 Stack Application 1: How Recursion Is

Implemented 277

7. 6 Stack Application 2: Conveting Infix to

Postfix 285

Summary 295

Exercises 295

Programming Project 7.1: Extending the Car Wash

Application 298

Programming Project 7.2: Evaluating a

Condition 300

Programming Project 7.3: An Iterative Maze

Search 304

Programming Project 7.4: An Alternate Design of

the queue Class 305

CHAPTER 8

Binary Trees and Binary Search

8. 1 Definition and Properties 308

8. 2 Binary Search Trees 324

Summary 345

Exercises 346

Programming Project 8. 1 : Alternative

Implementation of the BinSearch Tree

Class 350

CHAPTERg 9

AVL Ttees 353

9. 1 Balanced Binary Search Trees 354

9. 2 Rotations 354

9. 3 AVL Trees 358

9. 4 AVL Tree Application: A Simple Spell-

Checker 380

Summary 383

Exercises 384

Programming Project 9.1: The erase Method in the

AVLTree Class 388

Programming Project 9.2: Enhancing the

SpeIIChecker Project 389

CHAPTER 10

Red-Black Trees 391

10. 1 Red-Black Trees 392

10. 2 The Standard Template Library's Associative

Containers 422

10. 3 Set Application: Spell-Checker,

Revisited 425

Summary 432

Exercises 432

Programming Project 10.1: A Simple

Thesauras 436

Programming Project 10.2: Building a

Concordance 437

CHAPTER 11

Priority Queues

11.1 Introduction 440

11.2 Application of Priority Queues: Huffman

Codes 456

Summary 469

Exercises 469

Programming Project 11.1: Decoding a

Message 473

CHAPTER 12

Sorting 477

12.1 Introduction 478

12.2 How Fast Can We son? 481

12.3 Fast Sorts 483

Summary 501

Exercises 501

Programming Project 12.1: Sorting a File 509

CHPTER 13

Searehing and the Hash

Classe

13.1 A Framework to Analyze Searching 514

13.2 Review of Searching 514

13.3 The hash_map Class 517

13.4 The hash set Class 540

13.5 Open-Address Hashing 540

Summary 557

Exercises 558

Programming Project 13.1: A Run-Time

Comparison of Chaining and Double Hashing

in Building a Symbol Table 561

CHAPTER 14

14. 1 Undirected Graphs 564

14. 2 Directed Graphs 567

14. 3 Trees 568

14. 4 Networks 569

14. 5 Oraph Algorithms 571

14. 6 Developing a Network Class 588

14. 7 The network Class 589

14.8 Backtracking through a Network 607

Summary 610

Exercises 610

Programming Project 14.1 : Completing the

Adjacency-Matrix Implementation 614

Programming Project 14.2: Backtracking through

a Network 615

APPENDIX 1

A1. 1 Introduction 619

A1. 2 Functions and Sequences 619

A1. 3 Sums and Products 620

A1. 4 Logarithms 621

A1. 5 Mathematical Induction 623

A1. 6 Induction and Recursion 630

APPENDIX 2

The string

A2. 1 Introduction 633

A2. 2 Declaration of the string Class 633

A2. 3 Fields and Implementation of the string Class

644

APPENDIX 3

Polymorphism 647

A3. 1 Introduction 647

A3. 2 The Importance of Polymorphism 648

A3. 3 Dynamic Binding 649

References 651

Index 653