数据结构和编程设计 应用C语言 英文PDF电子书下载

CHAPTER 1 Programming Principles 1

1.1 Introduction 2

1.2 The Game of Life 4

1.2.1 Rules for the Game of Life 4

1.2.2 Examples 5

1.2.3 The Solution 6

1.2.4 Life:The Main Program 7

1.3 Programming Style 10

1.3.1 Names 10

1.3.2 Documentation and Format 12

1.3.3 Refinement and Modularity 14

1.4 Coding,Testing,and 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

CHAPTER 2 Introduction to 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 for Life 37

2.2 Algorithm Development:A Second Version of Life 40

2.2.1 Lists:Specifications for a Data Structure 40

2.2.2 The Main Program 45

2.2.3 Information Hiding 47

2.2.4 Refinement:Development of the Subprograms 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

CHAPTER 3 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

3.1.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:The Towers of Hanoi 95

3.3 Backtracking:Postponing the Work 101

3.3.1 Solving the Eight-Queens Puzzle 102

3.3.2 Example:Four Queens 102

3.3.3 Backtracking 103

3.3.4 Refinement:Choosing the Data Structures 104

3.3.5 Analysis of Backtracking 107

3.4 Principles of Recursion 110

3.4.1 Designing Recursive Algorithms 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

CHAPTER 4 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 Simulation 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 Pointers and Dynamic Memory in C 155

4.5.3 The Basics of Linked Lists 159

4.6 Linked Queues 161

4.7 Application:Polynomial Arithmetic 166

4.7.1 Purpose of the Project 166

4.7.2 The Main Program 166

4.7.3 Data Structures and Their Implementation 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 Abstract Data Types and Their Implementations 179

4.8.1 Introduction 179

4.8.2 General Definitions 180

4.8.3 Refinement of Data Specification 183

Pointers and Pitfalls 185

Review Questions 185

References for Further Study 186

CHAPTER 5 General Lists 187

5.1 List Specifications 188

5.2 Implementation of Lists 190

5.2.1 Contiguous Implementation 190

5.2.2 Simply Linked Implementation 191

5.2.3 Variation:Keeping the Current Position 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 Arrays 214

5.6 Generating Permutations 223

Pointers and Pitfalls 228

Review Questions 229

References for Further Study 230

CHAPTER 6 Searching 231

6.1 Searching:Introduction and Notation 232

6.2 Sequential Search 235

6.3 Coatrooms:A Project 241

6.3.1 Introduction and Specification 241

6.3.2 Demonstration and Testing Programs 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 Analysis for n=10 255

6.5.2 Generalization 258

6.5.3 Comparison of Methods 261

6.5.4 A General Relationship 263

6.6 Lower Bounds 264

6.7 Asymptotics 269

6.7.1 Introduction 269

6.7.2 The Big-O Notation 270

6.7.3 Imprecision of the Big-O Notation 273

6.7.4 Ordering of Common Functions 274

Pointers and Pitfalls 275

Review Questions 276

References for Further Study 276

CHAPTER 7 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.3 Analysis 291

7.3.4 Comparisons 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 An Example 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 Quicksoft 314

7.8.4 Average-Case Analysis 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

CHAPTER 8 Tables and Information Retrieval 336

8.1 Introduction:Breaking the lg n 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 Open Addressing 357

8.6.4 Collision Resolution by Chaining 362

8.7 Analysis of Hashing 367

8.8 Conclusions:Comparison of Methods 373

8.9 Application:The Life Game Revisited 374

8.9.1 Choice of Algorithm 374

8.9.2 Specification of Data Structures 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

CHAPTER 9 Binary Trees 383

9.1 Introduction to Binary Trees 384

9.1.1 Definitions 384

9.1.2 Traversal of Binary Trees 386

9.1.3 Linked Implementation of Binary Trees 391

9.2 Binary Search Trees 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 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 Splay Trees:A Self-Adjusting Data Structure 438

9.5.1 Introduction 438

9.5.2 Splaying Steps 439

9.5.3 Splaying Algorithm 442

9.5.4 Amortized Algorithm Analysis:Introduction 446

9.5.5 Amortized Analysis of Splaying 449

Pointers and Pitfalls 455

Review Questions 456

References for Further Study 458

CHAPTER 10 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.1 Tries 468

10.2.2 Searching for a Key 468

10.2.3 C Algorithm 470

10.2.4 Insertion into a Trie 470

10.2.5 Deletion from a Trie 472

10.2.6 Assessment of Tries 472

10.3 External Searching:B-Trees 473

10.3.1 Access Time 473

10.3.2 Multiway Search Trees 474

10.3.3 Balanced Multiway Trees 474

10.3.4 Insertion into a B-tree 475

10.3.5 C Algorithms:Searching and Insertion 477

10.3.6 Deletion from a B-tree 483

10.4 Red-Black Trees 492

10.4.1 Introduction 492

10.4.2 Definition and Analysis 493

10.4.3 Insertion 495

10.4.4 C Insertion 496

10.5 Tree-Structured Programs: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

CHAPTER 11 Graphs 510

11.1 Mathematical Background 511

11.1.1 Definitions and Examples 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:Shortest Paths 525

11.6 Graphs as Data Structures 529

Pointers and Pitfalls 531

Review Questions 532

References for Further Study 532

CHAPTER 12 Case Study:The Polish Notation 533

12.1 The Problem 534

12.1.1 The Quadratic Formula 534

12.2 The Idea 536

12.2.1 Expression Trees 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 in Prefix 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:Counting Stack Entries 544

12.3.6 Recursive Evaluation of Postfix Expressions 547

12.4 Translation from Infix Form to Polish Form 551

12.5 An Interactive Expression Evaluator 558

12.5.1 Overall Structure 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 Mathematical Methods 579

A.1 Sums of Powers of Integers 580

A.2 Logarithms 582

A.2.1 Definition of Logarithms 583

A.2.2 Simple Properties 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,Factorials 589

A.3.1 Permutations 589

A.3.2 Combinations 589

A.3.3 Factorials 590

A.4 Fibonacci Numbers 592

A.5 Catalan Numbers 594

A.5.1 The Main Result 594

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

A.5.3 History 596

A.5.4 Numerical Results 597

References for Further Study 598

APPENDIX B Removal of Recursion 600

B.1 General Methods for Removing 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:The Final Version 609

B.3 Nonrecursive Quicksort 611

B.4 Stackless Recursion Removal: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 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.4 Structures 632

C.3.5 Unions 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:Call by Value 642

C.7.2 Arguments to Functions:Call by Reference 643

C.7.3 Function Prototypes and Include Files 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 Argument 646

References for Further Study 647

INDEX 649