Dijkstra's Notes on Structured Programming opened a new view of programming as a scientific subject and intellectual challenge, and it coined the title for a "revolution" in programming. The initial outstanding contributions toward this development were made by E.W. It has advanced from a craft to an academic discipline. Preface In recent years the subject of computer programming has been recognized as a discipline whose mastery is fundamental and crucial to the success of many engineering projects and which is amenable to scientific treatement and presentation. Wirth 1985 (Oberon version: August 2004)Ĭontents Preface 1 Fundamental Data Structures 1.1 Introduction 1.2 The Concept of Data Type 1.3 Primitive Data Types 1.4 Standard Primitive Typesġ.4.1 Integer types 1.4.2 The type REAL 1.4.3 The type BOOLEAN 1.4.4 The type CHAR 1.4.5 The type SETġ.5 The Array Structure 1.6 The Record Structure 1.7 Representation of Arrays, Records, and Setsġ.7.1 Representation of Arrays 1.7.2 Representation of Recors 1.7.3 Representation of Setsġ.8 The File (Sequence) 1.8.1 Elementary File Operators 1.8.2 Buffering Sequences 1.8.3 Buffering between Concurrent Processes 1.8.4 Textual Input and Outputġ.9 Searching 1.9.1 Linear Search 1.9.2 Binary Search 1.9.3 Table Search 1.9.4 Straight String Search 1.9.5 The Knuth-Morris-Pratt String Search 1.9.6 The Boyer-Moore String SearchĮxercises 2 Sorting 2.1 Introduction 2.2 Sorting ArraysĢ.2.1 Sorting by Straight Insertion 2.2.2 Sorting by Straight Selection 2.2.3 Sorting by Straight ExchangeĢ.3 Advanced Sorting Methods 2.3.1 Insertion Sort by Diminishing Increment 2.3.2 Tree Sort 2.3.3 Partition Sort 2.3.4 Finding the Median 2.3.5 A Comparison of Array Sorting MethodsĢ.4 Sorting Sequences 2.4.1 Straight Merging 2.4.2 Natural Merging 2.4.3 Balanced Multiway Merging 2.4.4 Polyphase Sort 2.4.5 Distribution of Initial Runsģ Recursive Algorithms 3.1 Introduction 3.2 When Not to Use Recursion 3.3 Two Examples of Recursive Programs 3.4 Backtracking Algorithms 3.5 The Eight Queens Problem 3.6 The Stable Marriage Problem 3.7 The Optimal Selection Problem Exercises 4 Dynamic Information Structures 4.1 Recursive Data Types 4.2 Pointers 4.3 Linear ListsĤ.3.1 Basic Operations 4.3.2 Ordered Lists and Reorganizing Lists 4.3.3 An Application: Topological SortingĤ.4 Tree Structures 4.4.1 Basic Concepts and Definitions 4.4.2 Basic Operations on Binary Trees 4.4.3 Tree Search and Insertion 4.4.4 Tree Deletion 4.4.5 Analysis of Tree Search and InsertionĤ.5 Balanced Trees 4.5.1 Balanced Tree Insertion 4.5.2 Balanced Tree DeletionĤ.7.1 Multiway B-Trees 4.7.2 Binary B-TreesĤ.8 Priority Search Trees Exercises 5 Key Transformations (Hashing) 5.1 Introduction 5.2 Choice of a Hash Function 5.3 Collision handling 5.4 Analysis of Key Transformation Exercises Appendices A The ASCII Character Set B The Syntax of Oberon Index