《数据结构与程序设计 C 语言描述 第2版 英文》求取 ⇩

CHAPTER1

Programming Principles1

1.1 Introduction2

CHAPTER2

CHAPTER3

1.2 The Game of Life4

1.2.1 Rules for the Gane of Life4

CHAPTER4

1.2.2 Examples5

CHAPTER5

1.2.3 The Solution6

CHAPTER6

1.2.4 Life:The Main Program7

CHAPTER7

CHAPTER8

CHAPTER9

1.3.1 Names10

1.3 Programming Style10

CHAPTER10

Contents11

PREFACE11

CHAPTER11

Synopsis12

1.3.2 Documentation and Format12

CHAPTER12

Changes in the Second Edition13

Course Structure14

1.3.3 Refinement and Modularity14

Book Production15

Acknowledgments16

1.4 Coding,Testing,and19

Further Refinement19

1.4.1 Stubs19

1.4.2 Counting Neighbors20

1.4.3 Input and Output21

1.4.4 Drivers24

1.4.5 Program Tracing25

1.4.6 Principles of Program Testing26

Pointers and Pitfalls30

Review Questions32

References for Further Study32

C32

Programming Principles33

The Game of Life33

Introduction to34

Software Engineering34

2.1 Program Maintenance35

2.1.1 Review of the Life Program35

2.1.2 A Fresh Start and a New Method forLife37

2.2 Algorithm Development:40

2.2.1 Lists:Specifications for a40

Data Structure40

A Second Version of Life40

2.2.2 The Main Program45

2.2.3 Information Hiding47

Subprograms48

2.2.4 Refinement:Development of the48

2.2.5 Verification of Algorithms50

2.3 Coding55

2.3.1 The List Functions55

2.3.2 Error Processing56

2.3.3 Demonstration and Testing57

2.4 Coding the Life Functions62

2.5 Program Analysis and Comparison66

2.6 Conclusions and Preview68

2.6.1 The Game of Life68

2.6.2 Program Design70

2.6.3 C73

Pointers and Pitfalls75

Review Questions75

References for Further Study76

Stacks and Recursion77

3.1 Stacks78

3.1.1 Introduction78

3.1 2 First Example:Reversing a Line79

3 1 3 Information Hiding80

3.1.4 Specifications for a Stack81

3 1.5 Implementation of Stacks83

31.6 Linked Stacks85

3.2 Introduction to Recursion91

3.2.1 Stack Frames for Subprograms91

3.2 2 Tree of Subprogram Calls91

3.2.3 Factorials:A Recursive Definition93

3.2 4 Divide and Conquer:95

The Towers of Hanoi95

3.3 Backtracking:Postponing the Work101

3.3.2 Example:Four Queens102

3.3.1 Solving the Eight-Queens Puzzle102

3.3.3 Backtracking103

Choosing the Data Structures104

3.3.4 Refinement:104

3.3 5 Analysis of Backtracking107

3.4.1 Designing Recursive Algorithms110

3.4 Principles of Recursion110

3 4.2 How Recursion Works111

3.4.3 Tail Recursion115

3.4.4 When Not to Use Recursion116

3 4.5 Guidelines and Conclusions120

Pointers and Pitfalls122

Review Questions124

References for Further Study124

Queues and Linked Lists126

4.1 Definitions127

4.2 Implementations of Queues131

4.3 Circular Queues in C135

4.4 Application of Queues:Simulation139

4.4.1 Introduction139

4.4.2 Sirmulation of an Airport140

4.4.3 The Main Program142

4.4.4 Steps of the Simulation144

4.4.5 Pseudo-Random Numbers147

4.4.6 Sample Results149

4.5 Pointers and Linked Lists152

4.5.1 Introduction and Survey152

4.5.2 PointersandDynamicMemoryinC155

4.5.3 The Basics of Linked Lists159

4.6 Linked Queues161

4.71 PurposeoftheProject166

Polynomial Arithmetic166

4.7 Application:166

4.7.2 The Main Program166

Implementation171

4.7.3 Data Structures and Their171

4.7.4 Reading and Writing Polynomials172

4.7.5 Addition of Polynomials174

4.7.6 Completing the Project176

4.8.1 Introduction179

Their Implementations179

4.8 Abstract Data Types and179

4.8.2 General Definitions180

4.8.3 Refinement of Data Specification183

Review Questions185

Pointers and Pitfalls185

References for Further Study186

General Lists187

5.1 List Specifications188

5.2.1 Contiguous Implementation190

5.2 Implementation of Lists190

5.2.2 Simply Linked Implementation191

5.2.3 Variation:Keeping the CurrentPosition195

5.2.4 Doubly Linked Lists197

5.2.5 Comparison of Implementations200

5.3 Strings202

5.4 Application:A Text Editor205

5 4.1 Specifications205

5.4.2 Implementation207

5.5 Linked Lists in Atrays214

5.6 Generating Permutations223

Pointers and Pitfalls228

Review Questions229

References for Further Study230

Searching231

Introduction and Notation232

6.1 Searching:232

6.2 Sequential Search235

6.3.1 Introducton and Specification241

6.3 Coatrooms:A Project241

Programs244

6 3.2 Demonstration and Testing244

6.4 Binary Search248

6.4.1 Algorithm Development249

6.4.2 The Forgetful Version249

6.4.3 Recognizing Equality252

6.5 Comparison Trees254

6.5.1 Analysisfor n=10255

6.5.2 Generalizaton258

6.5.3 Comparison of Methods261

6.5.4 A General Relationship263

6.6 Lower Bounds264

6.7.1 Introducton269

6.7 Asymptotics269

6.7 2 The Big-O Notation270

6.7.3 Imprecision of the Big-O Notation273

6.7.4 Ordering of Cornmon Functions274

Pointers and Pitfalls275

Review Questions276

References for Further Study276

Sorting278

7.1 Introduction and Notation279

7.2 Insertion Sort280

7 2.1 Ordered Lists280

7 2.2 Sorting by Insertion281

7.2.3 Linked Version283

7 2.4 Analysis285

7.3 Selection Sort288

7.3.1 The Algorithm289

7.3.2 Contiguous Implementation290

7.3.4 Comparisons291

7.3.3 Analysis291

7.4 Shell Sort293

7.5 Lower Bounds295

7.6 Divide-and-Conquer Sorting298

7.6.1 The Main Ideas298

7.6.2 AnExample299

7.7 Mergesort for Linked Lists304

7.7.1 The Functions304

7.7.2 Analysis of Mergesort306

7.8 Quicksort for Contiguous Lists311

7.8.1 The Main Function311

7.8.2 Partitioning the List312

7.8.3 Analysis of Quicksort314

7.8 4 Average-Case Anialysis of Quicksort316

7.8 5 Comparison with Mergesort318

7.9 Heaps and Heapsort321

7.9.1 Two-Way Trees as Lists322

7.9.2 Heapsort323

7.9.3 Analysis of Heapsort327

7.9.4 Priority Queues328

7.10 Review:Comparison of Methods330

Pointers and Pitfalls333

Review Questions334

References for Further Study334

Tables and Information Retrieval336

8.1 Introduction:337

Breaking the lgn Barrier337

8.2 Rectangular Arrays337

8.3 Tables of Various Shapes340

8.3.1 Triangular Tables340

8.3.2 Jagged Tables342

8.3.3 Inverted Tables342

8.4 Tables:A New Abstract Data Type345

8.5 Application:Radix Sort348

8.5.1 The Idea348

8.5 2 Implementation349

8.5 3 Analysis352

8.6 Hashing353

8.6.1 Sparse Tables353

8 6.2 Choosing a Hash Function355

8.6 3 Collision Resolution with357

Open Addressing357

8.6.4 Collision Resolution by Chaining362

8.7 Analysis of Hashing367

8.8 Conclusions:373

Comparison of Methods373

8.9.2 Specification of Data Structures374

The Life Game Revisited374

8.9.1 Choice of Algorithm374

8.9 Application:374

8 9.3 The Main Program376

8.9.4 Functions377

Pointers and Pitfalls380

Review Questions381

References for Further Study382

Binary Trees383

9.1 Introduction to Binary Trees384

9.1.1 Definitions384

9.1.2 Traversal of Binary Trees386

Binary Trees391

9.1.3 Linked Implementation of391

9.2 Binary Search Tees396

9.2.1 Ordered Lists and Implementations397

9.2.2 Treesearch398

9.2.3 Insertion into a Binary Search Tree401

9.2.4 Treesort404

9.2.5 Deletion from a Binary Search Tree406

9.3 Building a Binary Search Tree414

9.3.1 Getting Started415

9.3.2 Declarations and the Main Function416

9.3.3 Inserting a Node417

9.3.4 Finishing the Task418

9.3.5 Evaluation419

9.3.6 Random Search Trees and419

Optimality419

9.4 Height Balance:AVL Trees422

9.4.1 Definition423

9.4.2 Insertion of a Node424

9.4.3 Deletion of a Node431

9.4.4 The Height of an AVL Tree433

9.5.1 Introduction438

9.5 Splay Trees:438

A Self-Adjusting Data Structure438

9.5.2 Splaying Steps439

9.5.3 Splaying Algorithm442

9.5.4 Amortized Algorithm Analysis:446

Introduction446

9.5.5 Amortized Analysis of Splaying449

Pointers and Pitfalls455

Review Questions456

References for Further Study458

Multiway Trees459

10.1 Orchards,Trees,and Binary Trees460

10.1.1 On the Classification of Species460

10.1.2 Ordered Trees461

10.1.3 Forests and Orchards463

10.1.4 The Formal Correspondence464

10.1.5 Rotations465

10.1.6 Summary466

10.2 Lexicographic Search Trees:Tries468

10.2.2 Searching for a Key468

10.2.1 Tries468

10.2.4 Insertion into a Trie470

10.2.3 CAlgorithm470

10.2.5 Deletion from a Trie472

10.2.6 Assessment of Tries472

10.3 Extemal Searching:B-Trees473

10.3.1 Access Time473

10.3.2 Multiway Search Trees474

10.3.3 Balanced Mutiway Trees474

10.3.4 Insertion into a B-tree475

10.3.5 CAlgorithms:477

Searching and Insertion477

10.3.6 Deletionfrom a B-tree483

10.4 Red-Black Trees492

10 4.1 Introcuction492

10.4.2 Definition and Analysis493

10.4.3 Insertion495

10.4.4 C Insertion496

10.5 Tree-Structured Programs:501

Look-Ahead in Games501

10.5.1 Game Trees501

10.5.2 The Minimax Method502

10.5.3 Algorithm Development503

10.5.4 Refinement504

Pointers and Pitfalls507

Review Questions507

References for Further Study508

Graphs510

11.1.1 Definitions and Examples511

11.1 Mathematical Background511

11.1.2 Undirected Graphs512

11.1.3 Directed Graphs512

11.2 Computer Representation513

11.3 Graph Traversal517

11.3.1 Methods517

11.3.2 Depth-First Algorithm518

11.3.3 Breadth-First Algorithm519

11.4 Topological Sorting520

11.4.1 The Problem520

11.4.2 Depth-First Algorithm522

11.4.3 Breadth-First Algorithm523

11.5 A Greedy Algorithm:525

Shortest Paths525

11.6 Graphs as Data Structures529

Pointers and Pitfalls531

Review Questions532

References for Further Study532

Case Study:The Polish Notation533

12.1 The Problem534

12.1.1 The Quadratic Formula534

12.2.1 Expression Trees536

12.2 The Idea536

12.2.2 Polish Notation538

12.2.3 C Method539

12.3 Evaluation of Polish Expressions540

12.3.1 Evaluation of an Expression inPrefix Form540

12.3.2 C Conventions541

12.3.3 C Function for Prefix Evaluation542

12.3.4 Evaluation of Postfix Expressions542

12.3.5 Proof of the Program:544

Counting Stack Entries544

12.3.6 Recursive Evaluafion of547

Postfix Expressions547

12.4 Translation from Infix Form to PolishForm551

12.5.1 Overall Structure558

12.5 An Interactive Expression558

Evaluator558

12 5.2 Representation of the Data560

12.5.3 Initialization and Auxiliary Tasks562

12.5.4 Translation of the Expression566

12.5.5 Evaluating the Expression574

12.5.6 Graphing the Expression576

References for Further Study578

APPENDIX A579

Mathematical Methods579

A.1 Sums of Powers of Integers580

A.2 Logarithms582

A.2.2 Simple Properties583

A.2.1 Definition of Logarithms583

A.2.3 Choice of Base584

A.2.4 Natural Logarithms584

A.2.5 Notation585

A.2.6 Change of Base586

A.2.7 Logarithmic Graphs586

A.2.8 Harmonic Numbers588

A.3 Permutations,Combinations,589

Factorials589

A.3.1 Permutatiors589

A.3.2 Combinations589

A.3.3 Factorials590

A.4 Fibonacci Numbers592

A.5.2 The Proof by One-to-One594

Correspondences594

A.5 Catalan Numbers594

A.5.1 The Main Result594

A.5.3 History596

A.5.4 Numerical Results597

References for Further Study598

APPiENDIX B600

Removal of Recursion600

B.1 General Methods for Removing601

Recursion601

B.1.1 Preliminary Assumptions601

B.1.2 General Rules602

B.1.3 Indirect Recursion603

B.1.4 Towers of Hanoi603

B.1.5 Further Simplifications605

B.2 Recursion Removal by Folding606

B.2.1 Program Schemata606

B.2.2 Proof of the Transformation607

B.2.3 Towers of Hanoi:609

The Final Version609

B.3 Nonrecursive Quicksort611

B.4 Stackless Recursion Removal:613

Mergesort613

B.5 Threaded Binary Trees617

B.5.1 Introduction617

B.5.2 Threads619

B.5.3 Inorder and Preorder Traversal620

B.5 4 Insertion in a Threaded Tree621

B.5.5 Postorder Traversal623

References for Further Study627

APPENDIX C628

An Introduction to C628

C.1 Introduction629

C.1.1 Overview of a C Program629

C.2 C Elements629

C.2.1 Reserved Words629

C.2.2 Constants629

C.3 Types and Declarations631

C.3.1 Basic Types631

C.3.2 Arrays631

C.3.3 Enumerations631

C.3.5 Unions632

C.3.4 Structures632

C.3.6 Type Definitions with typedef634

C.4 Operators635

C.5 Control Flow Statements636

C.5.1 If-Else636

C.5.2 Switch636

C.5 3 Loops637

C.5.4 Break and Continue637

C.5.5 Goto637

C.6 Pointers638

C.6.1 Pointer to a Simple Variable638

C.6.2 Pointer to an Array639

C.6 3 Array of Pointers640

C.6.4 Pointer to Structures641

C.7 Functions642

C.7.1 Arguments to Functions:642

Call by Value642

C.7.2 Arguments to Functions:643

Call by Reference643

C.7.3 Function Prototypes and IncludeFiles644

C.8 Pointers and Functions644

C.8.1 Pointer to a Function644

C.8.2 Functions that Return a Pointer645

C.8.3 Pointer to a Pointer as an646

Argument646

References for Further Study647

INDEX649