A Structured Programming Approach to Data

ISBN-13: 9781468479874 / Angielski / Miękka / 2012 / 222 str.

Opis

Much of current programming practice is basically empirical and ad hoc in approach. Each problem is tackled without relation to those that have gone before; experiences are made and stored as a series of fragments. Now, under the pressure of events, this unsatisfactory state of affairs is coming to an end. Programming is becoming a technology, a theory known as structured programming is developing. The purpose of a theory is to categorise and explain existing practice, thus enabling it to be improved through the development of new and sharper techniques. The resulting experiences have then to be fed back into the theory so that the process of enrichment may continue. This dialectical relationship between theory and practice is essential to a healthy programming technology. The lack of such a relationship in the 1950s and 60s and the accompanying software crisis certainly confirm the converse of this proposition. My aim in writing this book has been to explain the current state of the theory of structured programming, so that it may be used to improve the reader's practice. The book deals with two facets of programming - how to design a program in terms of abstract data structures and how to represent the data structures on real and bounded computers. The separation between program design and data structure representation leads to more reliable and flexible programs.

Spis treści

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.