"Lucid, systematic, and penetrating treatment of basic and dynamic data structures, sorting, recursive algorithms, language structures, and compiling."
Author(s): Niklaus Wirth
Series: Automatic Computation
Edition: 1
Publisher: Prentice Hall
Year: 1976
Language: English
Pages: 381
Title Page......Page 2
Table of Contents......Page 6
Preface......Page 9
Declaration......Page 14
1.1 Introduction......Page 16
1.2 The Concept of Data Type......Page 19
1.3 Primitive Data Types......Page 21
1.4 Standard Primitive Types......Page 23
1.5 Subrange Types......Page 25
1.6 The Array Structure......Page 26
1.7 The Record Structure......Page 31
1.8 Variants of Record Structures......Page 35
1.9 The Set Structure......Page 38
1.10 Representation of Array, Record, and Set Structures......Page 44
1.10.1 Representation of Arrays......Page 45
1.10.2 Representation of Record Structures......Page 47
1.10.3 Representation of Sets......Page 48
1.11 The Sequential File Structure......Page 49
1.11.1 Elementary File Operators......Page 52
1.11.2 Files with Substructure......Page 54
1.11.3 Texts......Page 56
1.11.4 A File Editing Program......Page 64
2.1 Introduction......Page 71
2.2 Sorting Arrays......Page 74
2.2.1 Sorting by Straight Insertion......Page 75
2.2.2 Sorting by Straight Selection......Page 78
2.2.3 Sorting by Straight Exchange......Page 80
2.2.4 Insertion Sort by Diminishing Increment......Page 83
2.2.5 Tree Sort......Page 85
2.2.6 Partition Sort......Page 91
2.2.7 Finding the Median......Page 97
2.2.8 A Comparison of Array Sorting Methods......Page 99
2.3.1 Straight Merging......Page 102
2.3.2 Natural Merging......Page 107
2.3.3 Balanced Multiway Merging......Page 114
2.3.4 Polyphase Sort......Page 119
2.3.5 Distribution of Initial Runs......Page 131
3.1 Introduction......Page 140
3.2 When Not to Use Recursion......Page 142
3.3 Two Examples of Recursive Programs......Page 145
3.4 Backtracking Algorithms......Page 152
3.5 The Eight Queens Problem......Page 158
3.6 The Stable Marriage Problem......Page 163
3.7 The Optimal Selection Problem......Page 169
4.1 Recursive Data Types......Page 177
4.2 Pointers or References......Page 181
4.3.1 Basic Operations......Page 186
4.3.2 Ordered Lists and Re-organizing Lists......Page 189
4.3.3 An Application: Topological Sorting......Page 197
4.4.1 Basic Concepts and Definitions......Page 204
4.4.2 Basic Operations on Binary Trees......Page 213
4.4.3 Tree Search and Insertion......Page 216
4.4.4 Tree Deletion......Page 225
4.4.5 Analysis of Tree Search and Insertion......Page 226
4.4.6 Balanced Trees......Page 230
4.4.7 Balanced Tree Insertion......Page 231
4.4.8 Balanced Tree Deletion......Page 237
4.4.9 Optimal Search Trees......Page 241
4.4.10 Displaying a Tree Structure......Page 247
4.5 Multiway Trees......Page 257
4.5.1 B-Trees......Page 260
4.5.2 Binary B-Trees......Page 272
4.6 Key Transformations (Hashing)......Page 279
4.6.2 Collision Handling......Page 281
4.6.3 Analysis of Key Transformation......Page 286
5.1 Language Definition and Structure......Page 295
5.2 Sentence Analysis......Page 298
5.3 Constructing a Syntax Graph......Page 303
5.4 Constructing a Parser for a Given Syntax......Page 306
5.5 Constructing a Table-Driven Parsing Program......Page 310
5.6 A Translator from BNF into Parser-Driving Data Structures......Page 314
5.7 The Programming Language PL/0......Page 322
5.8 A Parser for PL/0......Page 326
5.9 Recovering from Syntactic Errors......Page 335
5.10 A PL/0 Processor......Page 346
5.11 Code Generation......Page 359
Appendix A - The ASCII Character Set......Page 366
Appendix B - Pascal Syntax Diagrams......Page 367
Subject Index......Page 374
Index of Programs......Page 380
