A Structured Programming Approach to Data

1. An Overview of Program Design.- 1.1 Introduction - The Software Crisis.- 1.2 Objectives of Program Design.- 1.3 The Heart of the Problem.- 1.4 Stepwise Refinement.- 1.5 What Do We Mean When We Say a Program 'Works'?.- 1.6 Summary.- 1.7 Bibliographical Notes.- 2. Program Design Notation.- 2.1 An Abstract Programming Language.- 2.2 Structuring Control.- 2.3 Structuring Data.- 2.4 What is a Data Structure?.- 2.5 Unstructured Data Types.- 2.6 Implementation of Unstructured Types.- 2.7 Summary.- 2.8 Bibliographical Notes.- 3. Arrays.- 3.1 Array Structures.- 3.2 Arrays and Functions.- 3.3 Implementation of Arrays.- 3.4 Summary.- 3.5 Bibliographical Notes.- 4. Simple Data Structuring.- 4.1 Record Types.- 4.2 Implementation of Record Types.- 4.3 Use of Structured Types.- 4.4 Variant Types.- 4.5 Implementation of Variant Types.- 4.6 Summary.- 4.7 Bibliographical Notes.- 5. On Program Design.- 5.1 Stepwise Refinement of Programs.- 5.2 Two Examples.- 5.3 Summary.- 5.4 Bibliographical Notes.- Exercises 1.- 6. Set Structures.- 6.1 Introduction.- 6.2 Set Operations.- 6.3 Use of Set Structures.- 6.4 Implementation of Set Structures.- 6.5 Summary.- 6.6 Bibliographical Notes.- 7. The Class Construct.- 7.1 Using and Implementing Data Structures.- 7.2 Classes.- 7.3 Implementation of Classes.- 7.4 Summary.- 7.5 Bibliographical Notes.- 8. Dynamic Data Structures.- 8.1 Introduction.- 8.2 Basic Implementation Techniques for Dynamic Data Structures.- 8.3 Linear Linked Lists.- 8.4 Storage Management for Dynamic Data Structures.- 8.5 Linear Linked List Implementation of Integersets.- 8.6 Summary.- 8.7 Bibliographical Notes.- 9. Sequences.- 9.1 Introduction.- 9.2 Operations on Sequences.- 9.3 Storage Structures for Sequences.- 9.4 Queues.- 9.5 Summary.- 9.6 Bibliographical Notes.- Exercises 2.- 10. Simple Searching Techniques.- 10.1 Sparse Mappings.- 10.2 Sparsity and Searching.- 10.3 Linear Search.- 10.4 Merge Search.- 10.5 Binary Search.- 10.6 Properties of Binary Searching.- 10.7 Summary.- 10.8 Bibliographical Notes.- 11. Hashing Techniques.- 11.1 Introduction.- 11.2 Choice of a Hashing Function.- 11.3 Collision Handling by Open Addressing.- 11.4 Ordered Hashing.- 11.5 Chained Hashing.- 11.6 Efficiency of Hashing Methods.- 11.7 Summary.- 11.8 Bibliographical Notes.- 12. Recursion and Recursive Algorithms.- 12.1 Recursion.- 12.2 Mechanics of Recursion.- 12.3 Removal of Recursion.- 12.4 Recursion in the Design of Algorithms.- 12.5 Conclusion.- 12.6 Summary.- 12.7 Bibliographical Notes.- 13. Binary Search Trees.- 13.1 Introduction.- 13.2 Operations on Binary Trees.- 13.3 Binary Search Trees.- 13.4 The Shape of Binary Search Trees.- 13.5 Implementation of Binary Trees.- 13.6 Conclusion.- 13.7 Summary.- 13.8 Bibliographical Notes.- Exercises 3.- 14. Designing Programs From Data Structures.- 14.1 Introduction.- 14.2 Traversing Binary Trees.- 14.3 Input of Advanced Data Structures.- 14.4 Program Construction Rules.- 14.5 Systematic Design of File Processing Programs.- 14.6 Conclusion.- 14.7 Summary.- 14.8 Bibliographical Notes.- Exercises 4.- References.