数据结构 C++ 语言描述 英文PDF电子书下载

CHAPTER 1 INTRODUCTION 1

1.1 Abstract Data Types 2

ADT Format 3

1.2 C++ Classes and Abstract Types 6

Encapsulation and Information Hiding 7

Message Passing 7

1.3 Objects in C++ Applications 8

Application： The Circle Class 8

1.4 Object Design 11

Objects and Composition 11

C++ Geometric Classes 13

Objects and Inheritance 14

Inheritance in Programming 15

Ordered Lists and Inheritance 18

Software Reusability 19

SeqList and OrderedList Class Specifiications 19

1.5 Applications with Class Inheritance 21

1.6 Object-Oriented Program Design 22

Problem Analysis/Program Definition 23

Design 23

Coding 24

Testing 24

Program Design Illustration： A Dice Graph 24

1.7 Program Testing and Maintenance 31

Object Testing 31

Control Module Testing 31

Program Maintenance and Documentation 32

1.8 The C++ Programming Language 32

1.9 Abstract Base Classes and Polymorphism 33

Polymorphism and Dynamic Binding 34

Written Exercises 36

CHAPTER 2 BASIC DATA TYPES 38

2.1 Integer Types 39

Computer Storage of Integers 41

Data in Memory 42

C++ Representation of Integers 43

2.2 Character Types 43

ASCII Characters 44

2.3 Real Data Types 45

Real Number Representations 46

2.4 Enumerated Types 48

Implementing C++ Enumerated Types 49

2.5 Pointers 49

Pointer ADT 49

Pointer Values 51

2.6 The Array Type 52

The Built-In C++ Array Type 52

Storageof One-Dimensional Arrays 53

Array Bounds 54

Two-Dimensional Arrays 55

Storage of Two-Dimensional Arrays 57

2.7 String Literals and Variables 58

C++ Strings 61

Application： Reversing Names 63

2.8 Records 65

C++ Structures 66

2.9 Files 66

C++ Stream Hierarchy 69

2.10 Array and Record Applications 72

Sequential Search 72

Exchange Sort 75

Counting C++ Reserved Words 77

Written Exercises 80

Programming Exercises 88

CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES 91

3.1 The User Type CLASS 92

Class Declaration 92

Constructor 94

Object Declaration 94

Class Implementation 95

Implementing a Constructor 96

Building Objects 97

3.2 Sample Classes 101

The Temperature Class 101

The Random Number Class 104

3.3 Objects and Information Passing 110

An Object as a Return Value 110

An Object as a Function Parameter 110

3.4 Arrays of Objects 111

The Default Constructor 112

3.5 Multiple Constructors 113

3.6 Case Study： Triangular Matrices 116

Upper Triangular Matrix Properties 117

Written Exercises 126

Programming Exercises 131

CHAPTER 4 COLLECTION CLASSES 141

4.1 Describing Linear Collections 144

Direct Access Collections 145

Sequential Access Collections 146

Generalized Indexing 150

4.2 Describing Nonlinear Collections 151

Group Collections 152

4.3 Analysis of Algorithms 154

Performance Criteria 154

Common Orders of Magnitude 159

4.4 The Sequential and Binary Search 160

Binary Search 161

4.5 The Basic Sequential List Class 167

List Modification Methods 170

Written Exercises 178

Programming Exercises 181

CHAPTER S STACKS AND QUEUES 184

5.1 Stacks 185

5.2 The Stack Class 188

5.3 Expression Evaluation 197

Posttix Evaluation 198

Application： A Postfix Calculator 199

5.4 Queues 204

5.5 The Queue Class 207

5.6 Priority Queues 221

A Priority Queue Class 223

5.7 Case Study： Event-Driven Simulation 231

Written Exercises 245

Programming Exercises 249

CHAPTER 6 ABSTRACT OPERATORS 253

6.1 Describing Operator Overloading 255

Client-Defiined External Functions 255

Class Members 256

Friend Functions 259

6.2 Rational Number System 260

Representing Rational Numbers 261

Rational Number Arithmetic 261

Rational Number Conversion 262

6.3 The Rational Class 263

6.4 Rational Operators as Member Functions 265

Implementing the Rational Operators 266

6.5 The Rational Stream Operators as Friends 267

Implementing Rational Stream Operators 268

6.6 Converting Rational Numbers 269

Conversion to Object Type 269

Conversion from Object Type 271

6.7 Using Rational Numbers 272

Written Exercises 277

Programming Exercises 284

CHAPTER 7 GENERIC DATA TYPES 289

7.1 Template Functions 290

Template-Based Sort 294

7.2 Template Classes 294

Defining a Template Class 294

Declaring Template Class Objects 295

Defiining Template Class Methods 295

7.3 Template List Classes 297

7.4 Infiix Expression Evaluation 299

Written Exercises 308

Programming Exercises 309

CHAPTER 8 CLASSES AND DYNAMIC MEMORY 313

8.1 Pointers and Dynamic Data Structures 315

The Memory Allocation Operator New 315

Dynamic Array Allocation 316

The Memory Dealiocation Operator Delete 317

8.2 Dynamically Allocated Objects 318

Deallocating Object Data： The Destructor 319

8.3 Assignment and Initialization 322

Assignment Issues 322

Overloading the Assignment Operator 324

The This Pointer 325

Initialization Issues 325

Creating a Copy Constructor 326

8.4 Safe Arrays 329

The Array Class 329

Memory Allocation for the Array Class 331

Array Bounds Checking and the Overloaded ｛} Operator 332

Converting an Object to a Pointer 333

Using the Array Class 335

8.5 A String Class 337

String Class Implementation 343

8.6 Pattern Matching 349

The Find Process 350

Pattern Matching Algorithm 350

Analysis of the Pattern Matching Algorithm 355

8.7 Integral Sets 356

Sets of Integral Types 356

C++ Bit Handling Operators 357

Representing Set Elements 360

The Sieve of Eratosthenes 363

Set Class Implementation 366

Written Exercises 369

Programming Exercises 379

CHAPTER 9 LINKED LISTS 383

Describing a Linked List 386

Chapter Overview 386

9.1 The Node Class 387

Declaring a Node Type 387

Implementing the Node Class 390

9.2 Building Linked Lists 393

Creating a Node 393

Inserting a Node： InsertFront 393

Traversing a Linked List 394

Inserting a Node： InsertRear 397

Application： Student Graduation List 401

Creating an Ordered List 404

Application： Sorting with Linked Lists 406

9.3 Designing a Linked List Class 409

Linked List Data Members 409

Linked List Operations 410

9.4 The LinkedList Class 413

9.5 Implementing the LinkedList Class 421

9.6 Implementing Collections with Linked Lists 429

Linked Queues 429

Implementing Queue Methods 431

Linked SeqList Class 432

Implementing SeqList Data Access Methods 433

Application： Comparing SeqList Implementations 434

9.7 Case Study： A Print Spooler 436

implementing the Spooler Update Method 439

Spooler Evaluation Methods 440

9.8 Circular Lists 443

Circular Node Class Implementation 445

Application： Solving the Josephus Problem 447

9.9 Doubly Linked Lists 450

Application： Doubly Linked List Sort 452

DNode Class Implementation 455

9.10 Case Study： Window Management 457

The Window List 458

WindowList Class Implementation 461

Written Exercises 465

Programming Exercises 474

CHAPTER 10 RECURSION 480

10.1 The Concept of Recursion 481

Recursive Definitions 483

Recursive Problems 484

10.2 Designing Recursive Functions 489

10.3 Recursive Code and the Runtime Stack 494

The Runtime Stack 494

10.4 Problem-Solving with Recursion 497

Binary Search 497

Combinatorics： The Committee Problem 500

Combinatorics： Permutations 503

Maze Handling 514

Maze Class Implementation 518

10.5 Evaluating Recursion 521

Written Exercises 527

Programming Exercises 530

CHAPTER 11 TREES 533

Tree Terminology 535

Binary Trees 537

11.1 Binary Tree Structure 540

Designing a TreeNode Class 540

Building a Binary Tree 543

11.2 Designing TreeNode Functions 544

Recursive Tree Traversals 546

11.3 Using Tree Scan Algorithms 550

Application： Visiting Tree Nodes 550

Application： Tree Print 552

Application： Copying and Deleting Trees 553

Application： Upright Tree Printing 559

11.4 Binary Search Trees 564

The Key in a Binary Search Tree Node 566

Operations on a Binary Search Tree 567

Declaring a Binary Search Tree ADT 568

11.5 Using Binary Search Trees 573

Duplicate Nodes 575

11.6 The BinSTree Implementation 578

List Operations 579

11.7 Case Study： Concordance 590

Written Exercises 596

Programming Exercises 602

CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES 606

12.1 A View of Inheritance 607

Class Inheritance Terminology 609

12.2 Inheritance in C++ 610

Constructors and Derived Classes 612

What Cannot Be Inherited 619

12.3 Polymorphism and Virtual Functions 620

Demonstrating Polymorphism 622

Application： Geometric Figures and Virtual Methods 626

Virtual Methods and the Destructor 629

12.4 Abstract Base Classes 630

Abstract Base Class—List 632

Deriving SeqList from Abstract Base Class List 633

12.5 Iterators 635

The Iterator Abstract Base Class 636

Deriving List Iterators 637

Building the SeqList Iterator 638

Array Iterator 643

Application： Merging Sorted Runs 644

Arraylterator Implementation 649

12.6 Ordered Lists 650

OrderedList Class Implementation 651

12.7 Heterogeneous Lists 654

Heterogeneous Arrays 654

Heterogeneous Linked Lists 658

Written Exercises 664

Programming Exercises 674

CHAPTER 13 ADVANCED NONLINEAR STRUCTURES 678

13.1 Array-Based Binary Trees 679

Application： The Tournament Sort 682

13.2 Heaps 688

The Heap as a List 688

The Heap Class 690

13.3 Implementing the Heap Class 694

Application： Heap Sort 701

13.4 Priority Queues 705

Application： Long Runs 707

13.5 AVL Trees 713

AVL Tree Nodes 713

13.6 The AVL Tree Class 717

Memory Allocation for the AVLTree 720

Evaluating AVL Trees 729

13.7 Tree Iterators 731

The Inorder Iterator 732

lnorderlterator Class Implementation 733

Application： TreeSort 735

13.8 Graphs 737

Connected Components 738

13.9 The Graph Class 739

Declaring a Graph ADT 739

Graph Class Implementation 744

Graph Traversals 748

Applications 751

Reachability and Warshall’s Algorithm 760

Written Exercises 764

Programming Exercises 774

CHAPTER 14 ORGANIZING COLLECTIONS 778

14.1 Basic Array Sorting Algorithms 779

The Selection Sort 779

The Bubble Sort 782

The Insertion Sort 784

14.2 QuickSort 786

QuickSort Description 786

QuickSort Algorithm 790

Comparison of Array Sort Algorithms 794

14.3 Hashing 799

Keys and a Hash Function 799

Hashing Functions 800

Other Hash Methods 802

Collision Resolution 803

14.4 Hash Table Class 805

Application： String Frequency 809

HashTable Class Implementation 811

HashTablelterator Class Implementation 812

14.5 The Performance of Searching Methods 815

14.6 Binary Files and External Data Operations 816

Binary Files 816

The BinFile Class 819

External File Searching 825

External File Sort 830

Long Run MergeSort 832

14.7 Dictionaries 841

Written Exercises 850

Programming Exercises 856

APPENDIX ANSWERS TO SELECTED EXERCISES 862

BIBLIOGRAPHY 882

INDEX 884