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

CHAPTER 1

Programming Principles 1

1.1 Introduction 2

CHAPTER 2

CHAPTER 3

1.2 The Game of Life 4

1.2.1 Rules for the Gane of Life 4

CHAPTER 4

1.2.2 Examples 5

CHAPTER 5

1.2.3 The Solution 6

CHAPTER 6

1.2.4 Life:The Main Program 7

CHAPTER 7

CHAPTER 8

CHAPTER 9

1.3.1 Names 10

1.3 Programming Style 10

CHAPTER 10

Contents 11

PREFACE 11

CHAPTER 11

Synopsis 12

1.3.2 Documentation and Format 12

CHAPTER 12

Changes in the Second Edition 13

Course Structure 14

1.3.3 Refinement and Modularity 14

Book Production 15

Acknowledgments 16

1.4 Coding,Testing,and 19

Further Refinement 19

1.4.1 Stubs 19

1.4.2 Counting Neighbors 20

1.4.3 Input and Output 21

1.4.4 Drivers 24

1.4.5 Program Tracing 25

1.4.6 Principles of Program Testing 26

Pointers and Pitfalls 30

Review Questions 32

References for Further Study 32

C 32

Programming Principles 33

The Game of Life 33

Introduction to 34

Software Engineering 34

2.1 Program Maintenance 35

2.1.1 Review of the Life Program 35

2.1.2 A Fresh Start and a New Method forLife 37

2.2 Algorithm Development: 40

2.2.1 Lists:Specifications for a 40

Data Structure 40

A Second Version of Life 40

2.2.2 The Main Program 45

2.2.3 Information Hiding 47

Subprograms 48

2.2.4 Refinement:Development of the 48

2.2.5 Verification of Algorithms 50

2.3 Coding 55

2.3.1 The List Functions 55

2.3.2 Error Processing 56

2.3.3 Demonstration and Testing 57

2.4 Coding the Life Functions 62

2.5 Program Analysis and Comparison 66

2.6 Conclusions and Preview 68

2.6.1 The Game of Life 68

2.6.2 Program Design 70

2.6.3 C 73

Pointers and Pitfalls 75

Review Questions 75

References for Further Study 76

Stacks and Recursion 77

3.1 Stacks 78

3.1.1 Introduction 78

3.1 2 First Example:Reversing a Line 79

3 1 3 Information Hiding 80

3.1.4 Specifications for a Stack 81

3 1.5 Implementation of Stacks 83

31.6 Linked Stacks 85

3.2 Introduction to Recursion 91

3.2.1 Stack Frames for Subprograms 91

3.2 2 Tree of Subprogram Calls 91

3.2.3 Factorials:A Recursive Definition 93

3.2 4 Divide and Conquer: 95

The Towers of Hanoi 95

3.3 Backtracking:Postponing the Work 101

3.3.2 Example:Four Queens 102

3.3.1 Solving the Eight-Queens Puzzle 102

3.3.3 Backtracking 103

Choosing the Data Structures 104

3.3.4 Refinement: 104

3.3 5 Analysis of Backtracking 107

3.4.1 Designing Recursive Algorithms 110

3.4 Principles of Recursion 110

3 4.2 How Recursion Works 111

3.4.3 Tail Recursion 115

3.4.4 When Not to Use Recursion 116

3 4.5 Guidelines and Conclusions 120

Pointers and Pitfalls 122

Review Questions 124

References for Further Study 124

Queues and Linked Lists 126

4.1 Definitions 127

4.2 Implementations of Queues 131

4.3 Circular Queues in C 135

4.4 Application of Queues:Simulation 139

4.4.1 Introduction 139

4.4.2 Sirmulation of an Airport 140

4.4.3 The Main Program 142

4.4.4 Steps of the Simulation 144

4.4.5 Pseudo-Random Numbers 147

4.4.6 Sample Results 149

4.5 Pointers and Linked Lists 152

4.5.1 Introduction and Survey 152

4.5.2 PointersandDynamicMemoryinC 155

4.5.3 The Basics of Linked Lists 159

4.6 Linked Queues 161

4.71 PurposeoftheProject 166

Polynomial Arithmetic 166

4.7 Application: 166

4.7.2 The Main Program 166

Implementation 171

4.7.3 Data Structures and Their 171

4.7.4 Reading and Writing Polynomials 172

4.7.5 Addition of Polynomials 174

4.7.6 Completing the Project 176

4.8.1 Introduction 179

Their Implementations 179

4.8 Abstract Data Types and 179

4.8.2 General Definitions 180

4.8.3 Refinement of Data Specification 183

Review Questions 185

Pointers and Pitfalls 185

References for Further Study 186

General Lists 187

5.1 List Specifications 188

5.2.1 Contiguous Implementation 190

5.2 Implementation of Lists 190

5.2.2 Simply Linked Implementation 191

5.2.3 Variation:Keeping the CurrentPosition 195

5.2.4 Doubly Linked Lists 197

5.2.5 Comparison of Implementations 200

5.3 Strings 202

5.4 Application:A Text Editor 205

5 4.1 Specifications 205

5.4.2 Implementation 207

5.5 Linked Lists in Atrays 214

5.6 Generating Permutations 223

Pointers and Pitfalls 228

Review Questions 229

References for Further Study 230

Searching 231

Introduction and Notation 232

6.1 Searching: 232

6.2 Sequential Search 235

6.3.1 Introducton and Specification 241

6.3 Coatrooms:A Project 241

Programs 244

6 3.2 Demonstration and Testing 244

6.4 Binary Search 248

6.4.1 Algorithm Development 249

6.4.2 The Forgetful Version 249

6.4.3 Recognizing Equality 252

6.5 Comparison Trees 254

6.5.1 Analysisfor n=10 255

6.5.2 Generalizaton 258

6.5.3 Comparison of Methods 261

6.5.4 A General Relationship 263

6.6 Lower Bounds 264

6.7.1 Introducton 269

6.7 Asymptotics 269

6.7 2 The Big-O Notation 270

6.7.3 Imprecision of the Big-O Notation 273

6.7.4 Ordering of Cornmon Functions 274

Pointers and Pitfalls 275

Review Questions 276

References for Further Study 276

Sorting 278

7.1 Introduction and Notation 279

7.2 Insertion Sort 280

7 2.1 Ordered Lists 280

7 2.2 Sorting by Insertion 281

7.2.3 Linked Version 283

7 2.4 Analysis 285

7.3 Selection Sort 288

7.3.1 The Algorithm 289

7.3.2 Contiguous Implementation 290

7.3.4 Comparisons 291

7.3.3 Analysis 291

7.4 Shell Sort 293

7.5 Lower Bounds 295

7.6 Divide-and-Conquer Sorting 298

7.6.1 The Main Ideas 298

7.6.2 AnExample 299

7.7 Mergesort for Linked Lists 304

7.7.1 The Functions 304

7.7.2 Analysis of Mergesort 306

7.8 Quicksort for Contiguous Lists 311

7.8.1 The Main Function 311

7.8.2 Partitioning the List 312

7.8.3 Analysis of Quicksort 314

7.8 4 Average-Case Anialysis of Quicksort 316

7.8 5 Comparison with Mergesort 318

7.9 Heaps and Heapsort 321

7.9.1 Two-Way Trees as Lists 322

7.9.2 Heapsort 323

7.9.3 Analysis of Heapsort 327

7.9.4 Priority Queues 328

7.10 Review:Comparison of Methods 330

Pointers and Pitfalls 333

Review Questions 334

References for Further Study 334

Tables and Information Retrieval 336

8.1 Introduction: 337

Breaking the lgn Barrier 337

8.2 Rectangular Arrays 337

8.3 Tables of Various Shapes 340

8.3.1 Triangular Tables 340

8.3.2 Jagged Tables 342

8.3.3 Inverted Tables 342

8.4 Tables:A New Abstract Data Type 345

8.5 Application:Radix Sort 348

8.5.1 The Idea 348

8.5 2 Implementation 349

8.5 3 Analysis 352

8.6 Hashing 353

8.6.1 Sparse Tables 353

8 6.2 Choosing a Hash Function 355

8.6 3 Collision Resolution with 357

Open Addressing 357

8.6.4 Collision Resolution by Chaining 362

8.7 Analysis of Hashing 367

8.8 Conclusions: 373

Comparison of Methods 373

8.9.2 Specification of Data Structures 374

The Life Game Revisited 374

8.9.1 Choice of Algorithm 374

8.9 Application: 374

8 9.3 The Main Program 376

8.9.4 Functions 377

Pointers and Pitfalls 380

Review Questions 381

References for Further Study 382

Binary Trees 383

9.1 Introduction to Binary Trees 384

9.1.1 Definitions 384

9.1.2 Traversal of Binary Trees 386

Binary Trees 391

9.1.3 Linked Implementation of 391

9.2 Binary Search Tees 396

9.2.1 Ordered Lists and Implementations 397

9.2.2 Treesearch 398

9.2.3 Insertion into a Binary Search Tree 401

9.2.4 Treesort 404

9.2.5 Deletion from a Binary Search Tree 406

9.3 Building a Binary Search Tree 414

9.3.1 Getting Started 415

9.3.2 Declarations and the Main Function 416

9.3.3 Inserting a Node 417

9.3.4 Finishing the Task 418

9.3.5 Evaluation 419

9.3.6 Random Search Trees and 419

Optimality 419

9.4 Height Balance:AVL Trees 422

9.4.1 Definition 423

9.4.2 Insertion of a Node 424

9.4.3 Deletion of a Node 431

9.4.4 The Height of an AVL Tree 433

9.5.1 Introduction 438

9.5 Splay Trees: 438

A Self-Adjusting Data Structure 438

9.5.2 Splaying Steps 439

9.5.3 Splaying Algorithm 442

9.5.4 Amortized Algorithm Analysis: 446

Introduction 446

9.5.5 Amortized Analysis of Splaying 449

Pointers and Pitfalls 455

Review Questions 456

References for Further Study 458

Multiway Trees 459

10.1 Orchards,Trees,and Binary Trees 460

10.1.1 On the Classification of Species 460

10.1.2 Ordered Trees 461

10.1.3 Forests and Orchards 463

10.1.4 The Formal Correspondence 464

10.1.5 Rotations 465

10.1.6 Summary 466

10.2 Lexicographic Search Trees:Tries 468

10.2.2 Searching for a Key 468

10.2.1 Tries 468

10.2.4 Insertion into a Trie 470

10.2.3 CAlgorithm 470

10.2.5 Deletion from a Trie 472

10.2.6 Assessment of Tries 472

10.3 Extemal Searching:B-Trees 473

10.3.1 Access Time 473

10.3.2 Multiway Search Trees 474

10.3.3 Balanced Mutiway Trees 474

10.3.4 Insertion into a B-tree 475

10.3.5 CAlgorithms: 477

Searching and Insertion 477

10.3.6 Deletionfrom a B-tree 483

10.4 Red-Black Trees 492

10 4.1 Introcuction 492

10.4.2 Definition and Analysis 493

10.4.3 Insertion 495

10.4.4 C Insertion 496

10.5 Tree-Structured Programs: 501

Look-Ahead in Games 501

10.5.1 Game Trees 501

10.5.2 The Minimax Method 502

10.5.3 Algorithm Development 503

10.5.4 Refinement 504

Pointers and Pitfalls 507

Review Questions 507

References for Further Study 508

Graphs 510

11.1.1 Definitions and Examples 511

11.1 Mathematical Background 511

11.1.2 Undirected Graphs 512

11.1.3 Directed Graphs 512

11.2 Computer Representation 513

11.3 Graph Traversal 517

11.3.1 Methods 517

11.3.2 Depth-First Algorithm 518

11.3.3 Breadth-First Algorithm 519

11.4 Topological Sorting 520

11.4.1 The Problem 520

11.4.2 Depth-First Algorithm 522

11.4.3 Breadth-First Algorithm 523

11.5 A Greedy Algorithm: 525

Shortest Paths 525

11.6 Graphs as Data Structures 529

Pointers and Pitfalls 531

Review Questions 532

References for Further Study 532

Case Study:The Polish Notation 533

12.1 The Problem 534

12.1.1 The Quadratic Formula 534

12.2.1 Expression Trees 536

12.2 The Idea 536

12.2.2 Polish Notation 538

12.2.3 C Method 539

12.3 Evaluation of Polish Expressions 540

12.3.1 Evaluation of an Expression inPrefix Form 540

12.3.2 C Conventions 541

12.3.3 C Function for Prefix Evaluation 542

12.3.4 Evaluation of Postfix Expressions 542

12.3.5 Proof of the Program: 544

Counting Stack Entries 544

12.3.6 Recursive Evaluafion of 547

Postfix Expressions 547

12.4 Translation from Infix Form to PolishForm 551

12.5.1 Overall Structure 558

12.5 An Interactive Expression 558

Evaluator 558

12 5.2 Representation of the Data 560

12.5.3 Initialization and Auxiliary Tasks 562

12.5.4 Translation of the Expression 566

12.5.5 Evaluating the Expression 574

12.5.6 Graphing the Expression 576

References for Further Study 578

APPENDIX A 579

Mathematical Methods 579

A.1 Sums of Powers of Integers 580

A.2 Logarithms 582

A.2.2 Simple Properties 583

A.2.1 Definition of Logarithms 583

A.2.3 Choice of Base 584

A.2.4 Natural Logarithms 584

A.2.5 Notation 585

A.2.6 Change of Base 586

A.2.7 Logarithmic Graphs 586

A.2.8 Harmonic Numbers 588

A.3 Permutations,Combinations, 589

Factorials 589

A.3.1 Permutatiors 589

A.3.2 Combinations 589

A.3.3 Factorials 590

A.4 Fibonacci Numbers 592

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

Correspondences 594

A.5 Catalan Numbers 594

A.5.1 The Main Result 594

A.5.3 History 596

A.5.4 Numerical Results 597

References for Further Study 598

APPiENDIX B 600

Removal of Recursion 600

B.1 General Methods for Removing 601

Recursion 601

B.1.1 Preliminary Assumptions 601

B.1.2 General Rules 602

B.1.3 Indirect Recursion 603

B.1.4 Towers of Hanoi 603

B.1.5 Further Simplifications 605

B.2 Recursion Removal by Folding 606

B.2.1 Program Schemata 606

B.2.2 Proof of the Transformation 607

B.2.3 Towers of Hanoi: 609

The Final Version 609

B.3 Nonrecursive Quicksort 611

B.4 Stackless Recursion Removal: 613

Mergesort 613

B.5 Threaded Binary Trees 617

B.5.1 Introduction 617

B.5.2 Threads 619

B.5.3 Inorder and Preorder Traversal 620

B.5 4 Insertion in a Threaded Tree 621

B.5.5 Postorder Traversal 623

References for Further Study 627

APPENDIX C 628

An Introduction to C 628

C.1 Introduction 629

C.1.1 Overview of a C Program 629

C.2 C Elements 629

C.2.1 Reserved Words 629

C.2.2 Constants 629

C.3 Types and Declarations 631

C.3.1 Basic Types 631

C.3.2 Arrays 631

C.3.3 Enumerations 631

C.3.5 Unions 632

C.3.4 Structures 632

C.3.6 Type Definitions with typedef 634

C.4 Operators 635

C.5 Control Flow Statements 636

C.5.1 If-Else 636

C.5.2 Switch 636

C.5 3 Loops 637

C.5.4 Break and Continue 637

C.5.5 Goto 637

C.6 Pointers 638

C.6.1 Pointer to a Simple Variable 638

C.6.2 Pointer to an Array 639

C.6 3 Array of Pointers 640

C.6.4 Pointer to Structures 641

C.7 Functions 642

C.7.1 Arguments to Functions: 642

Call by Value 642

C.7.2 Arguments to Functions: 643

Call by Reference 643

C.7.3 Function Prototypes and IncludeFiles 644

C.8 Pointers and Functions 644

C.8.1 Pointer to a Function 644

C.8.2 Functions that Return a Pointer 645

C.8.3 Pointer to a Pointer as an 646

Argument 646

References for Further Study 647

INDEX 649