A Structured Programming Approach to Data (Computer Science Series)

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. vi 4.3 Use of Structured Types 4.4 Variant Types I owe a great deal to Professor J. S. Rohl of the University of Western Australia, who first encouraged me to set my ideas down in book form. I would also like to thank Geoff King and the many other UMIST students who have contributed to this book in numerous ways. David Watt, Clive Coleman, Ronan Sleep and John Reynolds all read the draft manuscript and made many helpful comments and suggestions. I have also received much advice and assistance from my colleagues at UMIST, and for this I am extremely grateful. Special thanks go to Mrs I. Betton, Miss M. O'Brien and Mrs B. Sharples, who had the unenviable task of typing the manuscript. Finally I would like to thank Joan, Abra and Robert Coleman for all their support while this book was in preparation. ## DEREK COLEMAN Record types were proposed in a paper entitled 'Record Handling' by Hoare (1968). Textbooks on Pascal contain many examples of their use, for example, Jensen and Wirth (1975) or Wirth (1973). Front Matter....Pages i-xi An Overview of Program Design....Pages 1-5 Program Design Notation....Pages 6-20 Arrays....Pages 21-26 Simple Data Structuring....Pages 27-35 On Program Design....Pages 36-52 Set Structures....Pages 53-65 The Class Construct....Pages 66-79 Dynamic Data Structures....Pages 80-94 Sequences....Pages 95-115 Simple Searching Techniques....Pages 116-127 Hashing Techniques....Pages 128-140 Recursion and Recursive Algorithms....Pages 141-157 Binary Search Trees....Pages 158-186 Designing Programs from Data Structures....Pages 187-216 Back Matter....Pages 217-222