数据结构与程序设计 C++语言描述 英文【2025|PDF下载-Epub版本|mobi电子书|kindle百度云盘下载】

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

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

1 Programming Principles1

1.1 Introduction2

1.2 The Game of Life4

1.2.1 Rules for the Game of Life4

1.2.2 Examples5

1.2.3 The Solution:Classes,Objects,and Methods7

1.2.4 Life:The Main Program8

1.3 Programming Style10

1.3.1 Names10

1.3.2 Documentation and Format13

1.3.3 Refinement and Modularity15

1.4.1 Stubs20

1.4 Coding,Testing,and Further Refinement20

1.4.2 Definition of the Class Life22

1.4.3 Counting Neighbors23

1.4.4 Updating the Grid24

1.4.5 Input and Output25

1.4.6 Drivers27

1.4.7 Program Tracing28

1.4.8 Principles of Program Testing29

1.5 Program Maintenance33

1.5.1 Program Evaluation34

1.5.2 Review of the Life Program35

1.5.3 Program Revision and Redevelopment38

1.6.1 Software Engineering39

1.6 Conclusions and Preview39

1.6.2 Problem Analysis40

1.6.3 Requirements Specification41

1.6.4 Coding41

Pointers and Pitfalls45

Review Questions46

References for Further Study47

C++47

Programming principles47

The Game of Life47

Software Engineering48

2 Introduction to Stacks49

2.1.2 Stacks50

2.1 Stack Specifications50

2.1.1 Lists and Arrays50

2.1.3 First Example:Reversing a List51

2.1.4 Information Hiding54

2.1.5 The Standard Template Library55

2.2 Implementation of Stacks57

2.2.1 Specification of Methods for Stacks57

2.2.2 The Class Specification60

2.2.3 Pushing,Popping and Other Methods61

2.2.4 Encapsulation63

2.3 Application:A Desk Calculator66

2.4 Application:Bracket Matching69

2.5.1 Introduction71

2.5 Abstract Data Types and Their Implementations71

2.5.2 General Definitions73

2.5.3 Refinement of Data Specification74

Pointers and Pitfalls76

Review Questions76

References for Further Study77

3 Queues78

3.1 Definitions79

3.1.1 Queue Operations79

3.1.2 Extended Queue Operations81

3.2 Implementations of Queues84

3.3 Circular Implementation of Queues in C++89

3.4 Demonstration and Testing93

3.5.2 Simulation of an Airport96

3.5 Application of Queues:Simulation96

3.5.1 Introduction96

3.5.3 Random Numbers99

3.5.4 The Runway Class Specification99

3.5.5 The Plane Class Specification100

3.5.6 Functions and Methods of the Simulation101

3.5.7 Sample Results107

Pointers and Pitfalls110

Review Questions110

References for Further Study111

4 Linked Stacks and Queues112

4.1.1 Introduction and Survey113

4.1 Pointers and Linked Structures113

4.1.2 Pointers and Dynamic Memory in C++116

4.1.3 The Basics of Linked Structures122

4.2 Linked Stacks127

4.3 Linked Stacks with Safeguards131

4.3.1 The Destructor131

4.3.2 Overloading the Assignment Operator132

4.3.3 The Copy Constructor135

4.3.4 The Modified Linked-Stack Specification136

4.4 Linked Queues137

4.4.1 Basic Declarations137

4.4.2 Extended Linked Queues139

4.5.2 The Main Program141

4.5 Application:Polynomial Arithmetic141

4.5.1 Purpose of the Project141

4.5.3 The Polynomial Data Structure144

4.5.4 Reading and Writing Polynomials147

4.5.5 Addition of Polynomials148

4.5.6 Completing the Project150

4.6 Abstract Data Types and Their Implementations152

Pointers and Pitfalls154

Review Questions155

5 Recursion157

5.1.1 Stack Frames for Subprograms158

5.1 Introduction to Recursion158

5.1.2 Tree of Subprogram Calls159

5.1.3 Factorials:A Recursive Definition160

5.1.4 Divide and Conquer:The Towers of Hanoi163

5.2 Principles of Recursion170

5.2.1 Designing Recursive Algorithms170

5.2.2 How Recursion Works171

5.2.3 Tail Recursion174

5.2.4 When Not to Use Recursion176

5.2.5 Guildelines and Conclusions180

5.3 Backtracking:Postponing the Work183

5.3.1 Solving the Eight-Queens Puzzle183

5.3.2 Example:Four Queens184

5.3.3 Backtracking185

5.3.4 Overall Outline186

5.3.5 Refinement:The First Data Structure and Its Methods188

5.3.6 Review and Refinement191

5.3.7 Analysis of Backtracking194

5.4 Tree-Structured Programs:Look-Ahead in Games198

5.4.1 Game Trees198

5.4.2 The Minimax Method199

5.4.3 Algorithm Development201

5.4.4 Refinement203

5.4.5 Tic-Tac-Toe204

Pointers and Pitfalls209

Review Questions210

References for Further Study211

6 Lists and Strings212

6.1 List Definition213

6.1.1 Method Specifications214

6.2 Implementation of Lists217

6.2.1 Class Templates218

6.2.2 Contiguous Implementation219

6.2.3 Simply Linked Implementation221

6.2.4 Variation:Keeping the Current Position225

6.2.5 Doubly Linked Lists227

6.2.6 Comparison of Implementations230

6.3.1 Strings in C++233

6.3 Strings233

6.3.2 Implementation of Strings234

6.3.3 Further String Operations238

6.4 Application:A Text Editor242

6.4.1 Specifications242

6.4.2 Implementation243

6.5 Linked Lists in Arrays251

6.6 Application:Generating Permutations260

Pointers and Pitfalls265

Review Questions266

References for Further Study267

7 Searching268

7.1 Searching:Introduction and Notation269

7.2 Sequential Search271

7.3 Binary Search278

7.3.1 Ordered Lists278

7.3.2 Algorithm Development280

7.3.3 The Forgetful Version281

7.3.4 Recognizing Equality284

7.4 Comparison Trees286

7.4.1 Analysis for n=10287

7.4.2 Generalization290

7.4.3 Comparison of Methods294

7.4.4 A General Relationship296

7.5 Lower Bounds297

7.6 Asymptotics302

7.6.1 Introduction302

7.6.2 Orders of Magnitude304

7.6.3 The Big-O and Related Notations310

7.6.4 Keeping the Dominant Term311

Pointers and Pitfalls314

Review Questions315

References for Further Study316

8 Sorting317

8.1 Introduction and Notation318

8.1.1 Sortable Lists319

8.2.1 Ordered Insertion320

8.2 Insertion Sort320

8.2.2 Sorting by Insertion321

8.2.3 Linked Version323

8.2.4 Analysis325

8.3 Selection Sort329

8.3.1 The Algorithm329

8.3.2 Contiguous Implementation330

8.3.3 Analysis331

8.3.4 Comparisons332

8.4 Shell Sort333

8.5 Lower Bounds336

8.6.1 The Main Ideas339

8.6 Divide-and-Conquer Sorting339

8.6.2 An Example340

8.7 Mergesort for Linked Lists344

8.7.1 The Functions345

8.7.2 Analysis of Mergesort348

8.8 Quicksort for Contiguous Lists352

8.8.1 The Main Function352

8.8.2 Partitioning the List353

8.8.3 Analysis of Quicksort356

8.8.4 Average-Case Analysis of Quicksort358

8.8.5 Comparison with Mergesort360

8.9 Heaps and Heapsort363

8.9.1 Two-Way Trees as Lists363

8.9.2 Development of Heapsort365

8.9.3 Analysis of Heapsort368

8.9.4 Priority Queues369

8.10 Review:Comparison of Methods372

Pointers and Pitfalls375

Review Questions376

References for Further Study377

9 Tables and Information Retrieval379

9.1 Introduction:Breaking the Ig n Barrier380

9.2 Rectangular Tables381

9.3 Tables of Various Shapes383

9.3.1 Triangular Tables383

9.3.2 Jagged Tables385

9.3.3 Inverted Tables386

9.4 Tables:A New Abstract Data Type388

9.5 Application:Radix Sort391

9.5.1 The Idea392

9.5.2 Implementation393

9.5.3 Analysis396

9.6 Hashing397

9.6.1 Sparse Tables397

9.6.2 Choosing a Hash Function399

9.6.3 Collision Resolution with Open Addressing401

9.6.4 Collision Resolution by Chaining406

9.7 Analysis of Hashing411

9.8 Conclusions:Comparison of Methods417

9.9.1 Choice of Algorithm418

9.9 Application:The Life Game Revisited418

9.9.2 Specification of Data Structures419

9.9.3 The Life Class421

9.9.4 The Life Functions421

Pointers and Pitfalls426

Review Questions427

References for Further Study428

10 Binary Trees429

10.1 Binary Trees430

10.1.1 Definitions430

10.1.2 Traversal of Binary Trees432

10.1.3 Linked Implementation of Binary Trees437

10.2 Binary Search Trees444

10.2.1 Ordered Lists and Implementations446

10.2.2 Tree Search447

10.2.3 Insertion into a Binary Search Tree451

10.2.4 Treesort453

10.2.5 Removal from a Binary Search Tree455

10.3 Building a Binary Search Tree463

10.3.1 Getting Started464

10.3.2 Declarations and the Main Function465

10.3.3 Inserting a Node466

10.3.4 Finishing the Task467

10.3.5 Evaluation469

10.3.6 Random Search Trees and Optimality470

10.4.1 Definition473

10.4 Height Balance:AVL Trees473

10.4.2 Insertion of a Node477

10.4.3 Removal of a Node484

10.4.4 The Height of an AVL Tree485

10.5 Splay Trees: A Self-Adjusting Data Structure490

10.5.1 Introduction490

10.5.2 Splaying Steps491

10.5.3 Algorithm Development495

10.5.4 Amortized Algorithm Analysis:Introduction505

10.5.5 Amortized Analysis of Splaying509

Pointers and Pitfalls515

Review Questions516

References for Further Study518

11 Multiway Trees520

11.1 Orchards,Trees,and Binary Trees521

11.1.1 On the Classification of Species521

11.1.2 Ordered Trees522

11.1.3 Forests and Orchards524

11.1.4 The Formal Correspondence526

11.1.5 Rotations527

11.1.6 Summary527

11.2 Lexicographic Search Trees:Tries530

11.2.1 Tries530

11.2.2 Searching for a Key530

11.2.3 C++ Algorithm531

11.2.4 Searching a Trie532

11.2.5 Insertion into a Trie533

11.2.6 Deletion from a Trie533

11.2.7 Assessment of Tries534

11.3 External Searching :B-Trees535

11.3.1 Access Time535

11.3.2 Multiway Search Trees535

11.3.3 Balanced Multiway Trees536

11.3.4 Insertion into a B-Tree537

11.3.5 C++ Algorithms:Searching and Insertion539

11.3.6 Deletion from a B-Tree547

11.4.1 Introduction556

11.4 Red-Black Trees556

11.4.2 Definition and Analysis557

11.4.3 Red-Black Tree Specification559

11.4.4 Insertion560

11.4.5 Insertion Method Implementation561

11.4.6 Removal of a Node565

Pointers and Pitfalls566

Review Questions567

References for Further Study568

12 Graphs569

12.1 Mathematical Background570

12.1.1 Definitions and Examples570

12.1.3 Directed Graphs571

12.1.2 Undirected Graphs571

12.2.1 The Set Representation572

12.2 Computer Representation572

12.2.2 Adjacency Lists574

12.2.3 Information Fields575

12.3 Graph Traversal575

12.3.1 Methods575

12.3.2 Depth-First Algorithm577

12.3.3 Breadth-First Algorithm578

12.4 Topological Sorting579

12.4.1 The Problem579

12.4.2 Depth-First Algorithm580

12.4.3 Breadth-First Algorithm581

12.5.1 The Problem583

12.5 A Greedy Algorithm:Shortest Paths583

12.5.2 Method584

12.5.3 Example585

12.5.4 Implementation586

12.6 Minimal Spanning Trees587

12.6.1 The Problem587

12.6.2 Method589

12.6.3 Implementation590

12.6.4 Verification of Prim s Algorithm593

12.7 Graphs as Data Structures594

Pointers and Pitfalls596

References for Further Study597

Review Questions597

13 Case Study:The Polish Notation598

13.1 The Problem599

13.1.1 The Quadratic Formula599

13.2 The Idea601

13.2.1 Expression Trees601

13.2.2 Polish Notation603

13.3 Evaluation of Polish Expressions604

13.3.1 Evaluation of an Expression in Prefix Form605

13.3.2 C++ Conventions606

13.3.3 C++ Function for Prefix Evaluation607

13.3.4 Evaluation of Postfix Expressions608

13.3.5 Proof of the Program:Counting Stack Entries609

13.3.6 Recursive evaluation of Postfix Expressions612

13.4 Translation from Infix Form to Polish Form617

13.5 An Interactive Expression Evaluator623

13.5.1 Overall Structure623

13.5.2 Representation of the Data:Class Specifications625

13.5.3 Tokens629

13.5.4 The Lexicon631

13.5.5 Expressions:Token Lists634

13.5.6 Auxiliary Evaluation Functions639

13.5.7 Graphing the Expression:The Class Plot640

13.5.8 A Graphics-Enhanced Plot Class643

References for Further Study645

A.1 Sums of Powers of Integers647

A Mathematical Methods647

A.2 Logarithms650

A.2.1 Definition of Logarithms651

A.2.2 Simple Properties651

A.2.3 Choice of Base652

A.2.4 Natural Logarithms652

A.2.5 Notation653

A.2.6 Change of Base654

A.2.7 Logarithmic Graphs654

A.2.8 Harmonic Numbers656

A.3.2 Combinations657

A.3 Permutations,Combinations,Factorials657

A.3.1 Permutations657

A.3.3 Factorials658

A.4 Fibonacci Numbers659

A.5 Catalan Numbers661

A.5.1 The Main Result661

A.5.2 The Proof by One-to-One Correspondences662

A.5.3 History664

A.5.4 Numerical Results665

References for Further Study665

B Random Numbers667

B.1 Introduction667

B.2 Strategy668

B.3 Program Development669

References for Further Study673

C Packages and Utility Functions674

C.1 Packages and C++ Translation Units674

C.2 Packages in the Text676

C.3 The Utility Package678

C.4 Timing Methods679

D Programming Precepts,Pointers,and Pitfalls681

D.1 Choice of Data Structures and Algorithms681

D.1.1 Stacks681

D.1.2 Lists681

D.1.5 Tables682

D.1.4 Sorting Methods682

D.1.3 Searching Methods682

D.1.6 Binary Trees683

D.1.7 General Trees684

D.1.8 Graphs684

D.2 Recursion685

D.3 Design of Data Structures686

D.4 Algorithm Design and Analysis687

D.5 Programming688

D.6 Programming with Pointer Objects689

D.7 Debugging and Testing690

D.8 Maintenance690

Index693