数据结构 C++ 语言描述 英文PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

CHAPTER 1 INTRODUCTION1

1.1 Abstract Data Types2

ADT Format3

1.2 C++ Classes and Abstract Types6

Encapsulation and Information Hiding7

Message Passing7

1.3 Objects in C++ Applications8

Application： The Circle Class8

1.4 Object Design11

Objects and Composition11

C++ Geometric Classes13

Objects and Inheritance14

Inheritance in Programming15

Ordered Lists and Inheritance18

Software Reusability19

SeqList and OrderedList Class Specifiications19

1.5 Applications with Class Inheritance21

1.6 Object-Oriented Program Design22

Problem Analysis/Program Definition23

Design23

Coding24

Testing24

Program Design Illustration： A Dice Graph24

1.7 Program Testing and Maintenance31

Object Testing31

Control Module Testing31

Program Maintenance and Documentation32

1.8 The C++ Programming Language32

1.9 Abstract Base Classes and Polymorphism33

Polymorphism and Dynamic Binding34

Written Exercises36

CHAPTER 2 BASIC DATA TYPES38

2.1 Integer Types39

Computer Storage of Integers41

Data in Memory42

C++ Representation of Integers43

2.2 Character Types43

ASCII Characters44

2.3 Real Data Types45

Real Number Representations46

2.4 Enumerated Types48

Implementing C++ Enumerated Types49

2.5 Pointers49

Pointer ADT49

Pointer Values51

2.6 The Array Type52

The Built-In C++ Array Type52

Storageof One-Dimensional Arrays53

Array Bounds54

Two-Dimensional Arrays55

Storage of Two-Dimensional Arrays57

2.7 String Literals and Variables58

C++ Strings61

Application： Reversing Names63

2.8 Records65

C++ Structures66

2.9 Files66

C++ Stream Hierarchy69

2.10 Array and Record Applications72

Sequential Search72

Exchange Sort75

Counting C++ Reserved Words77

Written Exercises80

Programming Exercises88

CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES91

3.1 The User Type CLASS92

Class Declaration92

Constructor94

Object Declaration94

Class Implementation95

Implementing a Constructor96

Building Objects97

3.2 Sample Classes101

The Temperature Class101

The Random Number Class104

3.3 Objects and Information Passing110

An Object as a Return Value110

An Object as a Function Parameter110

3.4 Arrays of Objects111

The Default Constructor112

3.5 Multiple Constructors113

3.6 Case Study： Triangular Matrices116

Upper Triangular Matrix Properties117

Written Exercises126

Programming Exercises131

CHAPTER 4 COLLECTION CLASSES141

4.1 Describing Linear Collections144

Direct Access Collections145

Sequential Access Collections146

Generalized Indexing150

4.2 Describing Nonlinear Collections151

Group Collections152

4.3 Analysis of Algorithms154

Performance Criteria154

Common Orders of Magnitude159

4.4 The Sequential and Binary Search160

Binary Search161

4.5 The Basic Sequential List Class167

List Modification Methods170

Written Exercises178

Programming Exercises181

CHAPTER S STACKS AND QUEUES184

5.1 Stacks185

5.2 The Stack Class188

5.3 Expression Evaluation197

Posttix Evaluation198

Application： A Postfix Calculator199

5.4 Queues204

5.5 The Queue Class207

5.6 Priority Queues221

A Priority Queue Class223

5.7 Case Study： Event-Driven Simulation231

Written Exercises245

Programming Exercises249

CHAPTER 6 ABSTRACT OPERATORS253

6.1 Describing Operator Overloading255

Client-Defiined External Functions255

Class Members256

Friend Functions259

6.2 Rational Number System260

Representing Rational Numbers261

Rational Number Arithmetic261

Rational Number Conversion262

6.3 The Rational Class263

6.4 Rational Operators as Member Functions265

Implementing the Rational Operators266

6.5 The Rational Stream Operators as Friends267

Implementing Rational Stream Operators268

6.6 Converting Rational Numbers269

Conversion to Object Type269

Conversion from Object Type271

6.7 Using Rational Numbers272

Written Exercises277

Programming Exercises284

CHAPTER 7 GENERIC DATA TYPES289

7.1 Template Functions290

Template-Based Sort294

7.2 Template Classes294

Defining a Template Class294

Declaring Template Class Objects295

Defiining Template Class Methods295

7.3 Template List Classes297

7.4 Infiix Expression Evaluation299

Written Exercises308

Programming Exercises309

CHAPTER 8 CLASSES AND DYNAMIC MEMORY313

8.1 Pointers and Dynamic Data Structures315

The Memory Allocation Operator New315

Dynamic Array Allocation316

The Memory Dealiocation Operator Delete317

8.2 Dynamically Allocated Objects318

Deallocating Object Data： The Destructor319

8.3 Assignment and Initialization322

Assignment Issues322

Overloading the Assignment Operator324

The This Pointer325

Initialization Issues325

Creating a Copy Constructor326

8.4 Safe Arrays329

The Array Class329

Memory Allocation for the Array Class331

Array Bounds Checking and the Overloaded ｛} Operator332

Converting an Object to a Pointer333

Using the Array Class335

8.5 A String Class337

String Class Implementation343

8.6 Pattern Matching349

The Find Process350

Pattern Matching Algorithm350

Analysis of the Pattern Matching Algorithm355

8.7 Integral Sets356

Sets of Integral Types356

C++ Bit Handling Operators357

Representing Set Elements360

The Sieve of Eratosthenes363

Set Class Implementation366

Written Exercises369

Programming Exercises379

CHAPTER 9 LINKED LISTS383

Describing a Linked List386

Chapter Overview386

9.1 The Node Class387

Declaring a Node Type387

Implementing the Node Class390

9.2 Building Linked Lists393

Creating a Node393

Inserting a Node： InsertFront393

Traversing a Linked List394

Inserting a Node： InsertRear397

Application： Student Graduation List401

Creating an Ordered List404

Application： Sorting with Linked Lists406

9.3 Designing a Linked List Class409

Linked List Data Members409

Linked List Operations410

9.4 The LinkedList Class413

9.5 Implementing the LinkedList Class421

9.6 Implementing Collections with Linked Lists429

Linked Queues429

Implementing Queue Methods431

Linked SeqList Class432

Implementing SeqList Data Access Methods433

Application： Comparing SeqList Implementations434

9.7 Case Study： A Print Spooler436

implementing the Spooler Update Method439

Spooler Evaluation Methods440

9.8 Circular Lists443

Circular Node Class Implementation445

Application： Solving the Josephus Problem447

9.9 Doubly Linked Lists450

Application： Doubly Linked List Sort452

DNode Class Implementation455

9.10 Case Study： Window Management457

The Window List458

WindowList Class Implementation461

Written Exercises465

Programming Exercises474

CHAPTER 10 RECURSION480

10.1 The Concept of Recursion481

Recursive Definitions483

Recursive Problems484

10.2 Designing Recursive Functions489

10.3 Recursive Code and the Runtime Stack494

The Runtime Stack494

10.4 Problem-Solving with Recursion497

Binary Search497

Combinatorics： The Committee Problem500

Combinatorics： Permutations503

Maze Handling514

Maze Class Implementation518

10.5 Evaluating Recursion521

Written Exercises527

Programming Exercises530

CHAPTER 11 TREES533

Tree Terminology535

Binary Trees537

11.1 Binary Tree Structure540

Designing a TreeNode Class540

Building a Binary Tree543

11.2 Designing TreeNode Functions544

Recursive Tree Traversals546

11.3 Using Tree Scan Algorithms550

Application： Visiting Tree Nodes550

Application： Tree Print552

Application： Copying and Deleting Trees553

Application： Upright Tree Printing559

11.4 Binary Search Trees564

The Key in a Binary Search Tree Node566

Operations on a Binary Search Tree567

Declaring a Binary Search Tree ADT568

11.5 Using Binary Search Trees573

Duplicate Nodes575

11.6 The BinSTree Implementation578

List Operations579

11.7 Case Study： Concordance590

Written Exercises596

Programming Exercises602

CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES606

12.1 A View of Inheritance607

Class Inheritance Terminology609

12.2 Inheritance in C++610

Constructors and Derived Classes612

What Cannot Be Inherited619

12.3 Polymorphism and Virtual Functions620

Demonstrating Polymorphism622

Application： Geometric Figures and Virtual Methods626

Virtual Methods and the Destructor629

12.4 Abstract Base Classes630

Abstract Base Class—List632

Deriving SeqList from Abstract Base Class List633

12.5 Iterators635

The Iterator Abstract Base Class636

Deriving List Iterators637

Building the SeqList Iterator638

Array Iterator643

Application： Merging Sorted Runs644

Arraylterator Implementation649

12.6 Ordered Lists650

OrderedList Class Implementation651

12.7 Heterogeneous Lists654

Heterogeneous Arrays654

Heterogeneous Linked Lists658

Written Exercises664

Programming Exercises674

CHAPTER 13 ADVANCED NONLINEAR STRUCTURES678

13.1 Array-Based Binary Trees679

Application： The Tournament Sort682

13.2 Heaps688

The Heap as a List688

The Heap Class690

13.3 Implementing the Heap Class694

Application： Heap Sort701

13.4 Priority Queues705

Application： Long Runs707

13.5 AVL Trees713

AVL Tree Nodes713

13.6 The AVL Tree Class717

Memory Allocation for the AVLTree720

Evaluating AVL Trees729

13.7 Tree Iterators731

The Inorder Iterator732

lnorderlterator Class Implementation733

Application： TreeSort735

13.8 Graphs737

Connected Components738

13.9 The Graph Class739

Declaring a Graph ADT739

Graph Class Implementation744

Graph Traversals748

Applications751

Reachability and Warshall’s Algorithm760

Written Exercises764

Programming Exercises774

CHAPTER 14 ORGANIZING COLLECTIONS778

14.1 Basic Array Sorting Algorithms779

The Selection Sort779

The Bubble Sort782

The Insertion Sort784

14.2 QuickSort786

QuickSort Description786

QuickSort Algorithm790

Comparison of Array Sort Algorithms794

14.3 Hashing799

Keys and a Hash Function799

Hashing Functions800

Other Hash Methods802

Collision Resolution803

14.4 Hash Table Class805

Application： String Frequency809

HashTable Class Implementation811

HashTablelterator Class Implementation812

14.5 The Performance of Searching Methods815

14.6 Binary Files and External Data Operations816

Binary Files816

The BinFile Class819

External File Searching825

External File Sort830

Long Run MergeSort832

14.7 Dictionaries841

Written Exercises850

Programming Exercises856

APPENDIX ANSWERS TO SELECTED EXERCISES862

BIBLIOGRAPHY882

INDEX884