Data structures and program design in C

목차 (Table of Contents)

• CONTENTS
• Preface = xi
• Synopsis = xii
• Course Structure = xiii
• Acknowledgments = xiv
• CHAPTER 1 Programming Principles = 1
• 1.1 Introduction = 2
• 1.2 The Game of Life = 3
• 1.2.1 Rules for the Game of Life = 4
• 1.2.2 Examples = 4
• 1.2.3 The Solution = 6
• 1.2.4 Life : The Main Program = 6
• 1.3 Programming Style = 9
• 1.3.1 Names = 9
• 1.3.2 Documentation and Format = 11
• 1.3.3 Refinement and Modularity = 12
• 1.4 Coding, Testing, and Further Refinement = 17
• 1.4.1 Stubs = 17
• 1.4.2 Counting Neighbors = 18
• 1.4.3 Input and Output = 19
• 1.4.4 Drivers = 21
• 1.4.5 Program Tracing = 22
• 1.4.6 Principles of Program Testing = 23
• Pointers and Pitfalls = 26
• Review Questions = 27
• References for Further Study = 28
• The C Language = 28
• Programming Principles = 28
• The Game of Life = 29
• CHAPTER 2 Introduction to Software Engineering = 30
• 2.1 Program Maintenance = 31
• 2.2 Lists in C = 35
• 2.3 Algorithm Development : A Second Version of Life = 37
• 2.3.1 The Main Program = 37
• 2.3.2 Refinement : Development of the Subprograms = 39
• 2.3.3 Coding the Functions = 40
• 2.4 Verification of Algorithms = 44
• 2.4.1 Proving the Program = 44
• 2.4.2 Invariants and Assertions = 46
• 2.4.3 Initialization = 47
• 2.5 Program Analysis and Comparison = 48
• 2.6 Conclusions and Preview = 51
• 2.6.1 The Game of Life = 51
• 2.6.2 Program Design = 53
• 2.6.3 The C Language = 55
• Pointers and Pitfalls = 57
• Review Questions = 57
• References for Further Study = 58
• CHAPTER 3 Lists = 59
• 3.1 Static and Dynamic Structures = 60
• 3.2 Stacks = 60
• 3.2.1 Definition and Operations = 60
• 3.2.2 Examples = 61
• 3.2.3 Array Implementation of Stacks = 64
• 3.3 Queues = 68
• 3.3.1 Definitions = 68
• 3.3.2 Implementations of Queues = 69
• 3.3.3 Circular Queues in C = 72
• 3.4 Application of Queues : Simulation = 77
• 3.4.1 Introduction = 77
• 3.4.2 Simulation of an Airport = 78
• 3.4.3 The Main Program = 80
• 3.4.4 Steps of the Simulation = 81
• 3.4.5 Random Numbers = 84
• 3.4.6 Sample Results = 85
• 3.5 Other Lists and their Implementation = 89
• Pointers and Pitfalls = 96
• Review Questions = 96
• Reverences for Further Study = 97
• CHAPTER 4 Linked Lists = 98
• 4.1 Dynamic Memory Allocation and Pointers = 99
• 4.1.1 The Problem of Overflow = 99
• 4.1.2 Pointers = 99
• 4.1.3 Further Remarks = 100
• 4.1.4 Dynamic Memory Allocation = 101
• 4.1.5 Pointers and Dynamic Memory in C = 101
• 4.2 Linked Stacks and Queues = 106
• 4.2.1 Declarations = 106
• 4.2.2 Linked Stacks = 107
• 4.2.3 Linked Queues = 111
• 4.3 Further Operations on Linked Lists = 114
• 4.3.1 Algorithms for Simply Linked Lists = 114
• 4.3.2 Comparison of Implementations = 120
• 4.3.3 Programming Hints = 121
• 4.4 Application : Polynomial Arithmetic = 123
• 4.4.1 Purpose of the Project = 123
• 4.4.2 The Main Program = 124
• 4.4.3 Data Structures and Their Implementation = 128
• 4.4.4 Reading and Writing Polynomials = 130
• 4.4.5 Addition of Polynomials = 131
• 4.4.6 Completing the Project = 132
• 4.5 Linked Listen in Arrays = 135
• 4.6 Abstract Data Types and Their Implementations = 140
• 4.6.1 Introduction = 140
• 4.6.2 General Definitions = 141
• 4.6.3 Refinement of Data Specification = 143
• Pointers and Pitfalls = 145
• Review Questions = 146
• References for Further Study = 146
• CHAPTER 5 Searching = 147
• 5.1 Searching : Introduction and Notation = 148
• 5.2 Sequential Search = 151
• 5.3 Binary Search = 154
• 5.3.1 The Forgetful Version = 155
• 5.3.2 Recognizing Equality = 156
• 5.4 comparison Trees = 157
• 5.4.1 Analysis for n 〓 10 = 158
• 5.4.2 Generalization = 161
• 5.4.3 Comparison of Methods = 164
• 5.4.4 A General Relationship = 165
• 5.5 Lower Bounds = 167
• 5.6 Asymptotics = 171
• Pointers and Pitfalls = 175
• Review Questions = 176
• References for Further Study = 177
• CHAPTER 6 Tables and Information Retrieval = 178
• 6.1 Introduction : Breaking the Ig n Barrier = 179
• 6.2 Rectangular Arrays = 179
• 6.3 Tables of Various Shapes = 182
• 6.3.1 Triangular Tables = 182
• 6.3.2 Jagged Tables = 184
• 6.3.3 Inverted Tables = 184
• 6.4 Tables : A New Abstract Data Type = 187
• 6.5 Hashing = 189
• 6.5.1 Sparse Tables = 189
• 6.5.2 Choosing a Hash Function = 191
• 6.5.3 Collision Resolution with Open Addressing = 193
• 6.5.4 Collision Resolution by Chaining = 197
• 6.6 Analysis of Hashing = 201
• 6.7 Conclusions : Comparison of Methods = 206
• 6.8 Application : The Life Game Revisited = 207
• 6.8.1 Choice of Algorithm = 207
• 6.8.2 Specification of data Structures = 207
• 6.8.3 The Main Program = 209
• 6.8.4 Functions = 210
• Pointers and Pitfalls = 213
• Review Questions = 214
• References for Further Study = 216
• CHAPTER 7 Sorting = 216
• 7.1 Introduction and Notation = 217
• 7.2 Insertion Sort = 218
• 7.2.1 Contiguous Version = 219
• 7.2.2 Linked Version = 220
• 7.2.3 Analysis = 222
• 7.3 Selection Sort = 225
• 7.4 Shell Sort = 228
• 7.5 Lower Bounds = 230
• 7.6 Divide and Conquer = 233
• 7.6.1 The Main Ideas = 233
• 7.6.2 An Example = 234
• 7.6.3 Recursion = 237
• 7.6.4 Tree of Subprogram Calls = 237
• 7.7 Mergesort for Linked Lists = 240
• 7.7.1 The Functions = 240
• 7.7.2 Analysis of Mergesort = 242
• 7.8 Quicksort for Contiguous Lists = 246
• 7.8.1 The Main Function = 247
• 7.8.2 Partitioning the List = 247
• 7.8.3 Analysis of Quicksort = 249
• 7.8.4 Average-Case Analysis of Quicksort = 251
• 7.8.5 Comparison with Mergesort = 253
• 7.9 Review : Comparison of Methods = 256
• Pointers and Pitfalls = 259
• Review Questions = 259
• References for Further Study = 260
• CHAPTER 8 Recursion = 262
• 8.1 Divide and Conquer = 263
• 8.1.1 The Towers of Hanoi = 263
• 8.1.2 The Solution = 264
• 8.1.3 Refinement = 264
• 8.1.4 Analysis = 265
• 8.2 Postponing the Work = 266
• 8.2.1 Generating Permutations = 266
• 8.2.2 Backtracking : Nonattacking Queens = 271
• 8.3 Tree-Structured Programs : Look-Ahead in Games = 278
• 8.3.1 Game Trees = 278
• 8.3.2 The Minimax Method = 279
• 8.3.3 Algorithm Development = 280
• 8.3.4 Refinement = 281
• 8.4 Compilation by Recursive Descent = 284
• 8.5 Principles of Recursion = 288
• 8.5.1 Guidelines for Using Recursion = 288
• 8.5.2 How Recursion Works = 288
• 8.5.3 Tail Recursion = 292
• 8.5.4 When Not to Use Recursion = 294
• 8.5.5 Guidelines and Conclusions = 299
• Pointers and Pitfalls = 300
• Review Questions = 301
• References for Further Study = 302
• CHAPTER 9 Binary Trees = 304
• 9.1 Definitions = 305
• 9.2 Treesearch = 308
• 9.3 Traversal of Binary Trees = 309
• 9.4 Treesort = 312
• 9.4.1 Insertion into a Search Tree = 313
• 9.4.2 The Treesort Algorithm = 314
• 9.4.3 Deletion from a Search Tree = 316
• 9.5 Building a Binary Search Tree = 321
• 9.5.1 Getting Started = 323
• 9.5.2 Declarations and the Main Program = 324
• 9.5.3 Inserting a Node = 325
• 9.5.4 Finishing the Task = 325
• 9.5.5 Evaluation = 326
• 9.5.6 Random Search Trees and Optimality = 327
• 9.6 Height Balance : AVL Trees = 330
• 9.6.1 Definition = 330
• 9.6.2 Insertion of a Node = 330
• 9.6.3 Deletion of a Node = 337
• 9.6.4 The Height of an AVL Tree = 338
• 9.7 Contiguous Representation of Binary Trees : Heaps = 343
• 9.7.1 Binary Trees in Contiguous Storage = 343
• 9.7.2 Heaps and Heapsort = 344
• 9.7.3 Analysis of Heapsort = 348
• 9.7.4 Priority Queues = 349
• Pointers and Pitfalls = 351
• Review Questions = 352
• References for Further Study = 353
• CHAPTER 10 Trees and Graphs = 354
• 10.1 Orchards, Trees, and Binary Trees = 355
• 10.1.1 On the Classification of Species = 355
• 10.1.2 Ordered Trees = 356
• 10.1.3 Forests and Orchards = 357
• 10.1.4 The Formal Correspondence = 359
• 10.1.5 Rotations = 360
• 10.1.6 Summary = 360
• 10.2 Lexicographic Search Trees : Tries = 362
• 10.2.1 Tries = 362
• 10.2.2 Searching for a Key = 363
• 10.2.3 C Algorithm = 364
• 10.2.4 Insertion into a Trie = 365
• 10.2.5 Deletion from a Trie = 365
• 10.2.6 Assessment of Tries = 366
• 10.3 External Searching : B-Trees = 367
• 10.3.1 Access Time = 367
• 10.3.2 Multiway Search Trees = 367
• 10.3.3 Balanced Multiway Trees = 367
• 10.3.4 Insertion into a B-tree = 368
• 10.3.5 C Algorithms : Searching and Insertion = 370
• 10.3.6 Deletion from a B-tree = 375
• 10.4 Graphs = 382
• 10.4.1 Mathematical Background = 382
• 10.4.2 Computer Representation = 384
• 10.4.3 Graph Traversal = 388
• 10.4.4 Topological Sorting = 391
• 10.4.5 A Greedy Algorithm :Shortest Paths = 395
• 10.4.6 Graphs as Data Structures = 399
• Pointers and Pitfalls = 401
• Review Questions = 402
• References for Further Study = 402
• CHAPTER 11 Case Study : The Polish Notation = 404
• 11.1 The Problem = 405
• 11.1.1 The Quadratic Formula = 405
• 11.1.2 Unary Operators and Priorities = 406
• 11.2 The Idea = 406
• 11.2.1 Expression Trees = 406
• 11.2.2 Polish Notation = 408
• 11.2.3 C Method = 410
• 11.3 Evaluation of Polish Expressions = 410
• 11.3.1 Evaluation of an Expression in Prefix Form = 410
• 11.3.2 C Conventions = 411
• 11.3.3. C Function for Prefix Evaluation = 412
• 11.3.4 Evaluation of Postfix Expressions = 413
• 11.3.5 Proof of the Program : Counting Stack Entries = 414
• 11.3.6 Recursive Evaluation of Postfix Expressions = 417
• 11.4 Translation from Infix Form to Polish Form = 421
• 11.5 An Interactive Expression Evaluator = 426
• 11.5.1 The Main Program = 426
• 11.5.2 Representation of the Data = 428
• 11.5.3 Predefined Tokens = 430
• 11.5.4 Translation of the Expression = 430
• 11.5.5 Evaluating the Expression = 439
• 11.5.6 Summary = 440
• References for Further Study = 442
• APPENDIX A Mathematical Methods = 443
• A.1 Sums of Powers of Integers = 443
• A.2 Logarithms = 446
• A.2.1 Definition of Logarithms = 446
• A.2.2 Simple Properties = 447
• A.2.3 Choice of Base = 448
• A.2.4 Natural Logarithms = 448
• A.2.5 Change of Base = 449
• A.2.6 Logarithmic Graphs = 450
• A.2.7 Harmonic Numbers = 450
• A.3 Permutations, Combinations, Factorials = 452
• A.3.1 Permutations = 452
• A.3.2 Combinations = 453
• A.3.3 Factorials = 453
• A.4 Fibonacci Numbers = 456
• A.5 Catalan Numbers = 456
• A.5.1 The Main Result = 456
• A.5.2 The Proof by One-to-One Correspondences = 457
• A.5.3 History = 460
• A.5.4 Numerical Results = 460
• References for Further Study = 460
• APPENDIX B Removal of Recursion = 462
• B.1 General Methods for Removing Recursion = 462
• B.1.1 Preliminary Assumptions = 463
• B.1.2 General Rules = 463
• B.1.3 Indirect Recursion = 464
• B.1.4 Towers of Hanoi = 465
• B.1.5 Further Simplifications = 467
• B.2 Recursion Removal by Folding = 467
• B.2.1 Program Schemata = 467
• B.2.2 Proof of the Transformation = 469
• B.2.3 Towers of Hanoi : The Final Version = 471
• B.3 Nonrecursive Quicksort = 472
• B.4 Stackless Recursion Removal :Mergesort = 474
• B.5 Threaded Binary Trees = 478
• B.5.1 Introduction = 478
• B.5.2 Threads = 480
• B.5.3 Inorder and Preorder Traversal = 481
• B.5.4 Insertion in a Threaded Tree = 482
• B.5.5 Postorder Traversal = 484
• References for Further Study = 488
• APPENDIX C An Introduction to C = 489
• C.1 Introduction = 489
• C.1.1 Overview of a C Program = 489
• C.2 C Elements = 490
• C.2.1 Reserved Words = 490
• C.2.2 Constants = 490
• C.3 Types and Declarations = 491
• C.3.1 Basic Types = 491
• C.3.2 Arrays = 492
• C.3.3 Enumerations = 492
• C.3.4 Structures = 492
• C.3.5 Unions = 493
• C.3.6 typedef = 494
• C.4 Operators = 495
• C.5 Control Flow Statements = 496
• C.5.1 If-Else = 496
• C.5.2 Switch = 497
• C.5.3 Loops = 497
• C.5.4 Break and Continue = 498
• C.5.5 Goto = 498
• C.6 Pointers = 498
• C.6.1 Pointer to a Simple Variable = 498
• C.6.2 Pointer to an Array = 499
• C.6.3 Array of Pointers = 500
• C.6.4 Pointer to Structures = 500
• C.7 Functions = 501
• C.7.1 Arguments to Functions : Call by Value = 502
• C.7.2 Arguments to Functions : Call by Reference = 502
• C.7.3 Function Prototypes and Include Files = 503
• C.8 Pointers and Functions = 504
• C.8.1 Pointer to a Function = 504
• C.8.2 Functions that Return a Pointer = 504
• C.8.3 Pointer to a Pointer as an Argument = 505
• References for Further Study = 506
• Index = 507