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