Algorithms + data structures=programs

Algorithms + Data Structures = Programs - Niklaus Wirth (0130224189) ......Page 1
Table of Contents ......Page 8
Preface ......Page 11
Declaration ......Page 16
1.1 Introduction ......Page 17
1.2 The Concept of Data Type ......Page 20
1.3 Primitive Data Types ......Page 22
1.4 Standard Primitive Types ......Page 24
1.5 Subrange Types ......Page 26
1.6 The Array Structure ......Page 27
1.7 The Record Structure ......Page 32
1.8 Variants of Record Structures ......Page 36
1.9 The Set Structure ......Page 39
1.10 Representation of Array, Record, and Set Structures ......Page 45
1.10.1 Representation of Arrays ......Page 46
1.10.2 Representation of Record Structures ......Page 48
1.10.3 Representation of Sets ......Page 49
1.11 The Sequential File Structure ......Page 50
1.11.1 Elementary File Operators ......Page 53
1.11.2 Files with Substructure ......Page 55
1.11.3 Texts ......Page 57
1.11.4 A File Editing Program ......Page 65
2.1 Introduction ......Page 72
2.2 Sorting Arrays ......Page 75
2.2.1 Sorting by Straight Insertion ......Page 76
2.2.2 Sorting by Straight Selection ......Page 79
2.2.3 Sorting by Straight Exchange ......Page 81
2.2.4 Insertion Sort by Diminishing Increment ......Page 84
2.2.5 Tree Sort ......Page 86
2.2.6 Partition Sort ......Page 92
2.2.7 Finding the Median ......Page 98
2.2.8 A Comparison of Array Sorting Methods ......Page 100
2.3.1 Straight Merging ......Page 103
2.3.2 Natural Merging ......Page 108
2.3.3 Balanced Multiway Merging ......Page 115
2.3.4 Polyphase Sort ......Page 120
2.3.5 Distribution of Initial Runs ......Page 132
3.1 Introduction ......Page 141
3.2 When Not to Use Recursion ......Page 143
3.3 Two Examples of Recursive Programs ......Page 146
3.4 Backtracking Algorithms ......Page 153
3.5 The Eight Queens Problem ......Page 159
3.6 The Stable Marriage Problem ......Page 164
3.7 The Optimal Selection Problem ......Page 170
4.1 Recursive Data Types ......Page 178
4.2 Pointers or References ......Page 182
4.3.1 Basic Operations ......Page 187
4.3.2 Ordered Lists and Re-organizing Lists ......Page 190
4.3.3 An Application: Topological Sorting ......Page 198
4.4.1 Basic Concepts and Definitions ......Page 205
4.4.2 Basic Operations on Binary Trees ......Page 214
4.4.3 Tree Search and Insertion ......Page 217
4.4.4 Tree Deletion ......Page 226
4.4.5 Analysis of Tree Search and Insertion ......Page 227
4.4.6 Balanced Trees ......Page 231
4.4.7 Balanced Tree Insertion ......Page 232
4.4.8 Balanced Tree Deletion ......Page 238
4.4.9 Optimal Search Trees ......Page 242
4.4.10 Displaying a Tree Structure ......Page 248
4.5 Multiway Trees ......Page 258
4.5.1 B-Trees ......Page 261
4.5.2 Binary B-Trees ......Page 273
4.6 Key Transformations (Hashing) ......Page 280
4.6.2 Collision Handling ......Page 282
4.6.3 Analysis of Key Transformation ......Page 287
5.1 Language Definition and Structure ......Page 296
5.2 Sentence Analysis ......Page 299
5.3 Constructing a Syntax Graph ......Page 304
5.4 Constructing a Parser for a Given Syntax ......Page 307
5.5 Constructing a Table-Driven Parsing Program ......Page 311
5.6 A Translator from BNF into Parser-Driving Data Structures ......Page 315
5.7 The Programming Language PL/0 ......Page 323
5.8 A Parser for PL/0 ......Page 327
5.9 Recovering from Syntactic Errors ......Page 336
5.10 A PL/0 Processor ......Page 347
5.11 Code Generation ......Page 360
Appendix A THE ASCII CHARACTER SET ......Page 366
Appendix B PASCAL SYNTAX DIAGRAMS ......Page 367
SUBJECT INDEX ......Page 374
INDEX OF PROGRAMS ......Page 379