---

This textbook provides an in depth course on data structures in the context of object oriented development. Its main themes are abstraction, implementation, encapsulation, and measurement: that is, that the software process begins with abstraction of data types, which then lead to alternate representations and encapsulation, and finally to resource measurement. A clear object oriented approach, making use of Booch components, will provide readers with a useful library of data structure components and experience in software reuse. Students using this book are expected to have a reasonable understanding of the basic logical structures such as stacks and queues. Throughout, Ada 95 is used and the author takes full advantage of Ada´s encapsulation features and the ability to present specifications without implementational details. Ada code is supported by two suites available over the World Wide Web.

---

´1 Preliminaries.- 1.1 Object-Oriented Software Development.- 1.1.1 The Object-Oriented Concept.- 1.1.2 Objects and Their Attributes.- 1.1.3 Operations.- 1.2 Problem Analysis.- 1.3 Solution Design.- 1.4 Design to Implementation.- 1.5 Software Maintenance.- 1.6 Data Structures and Algorithms.- 1.7 Ada 95.- 1.8 Simple Static Types.- 1.8.1 Ordinal Objects.- 1.8.2 Access Types.- 1.8.3 Nonordinal Objects.- 1.9 Structured Data Types.- 1.9.1 Arrays.- 1.9.1.1 Constrained Arrays.- 1.9.1.2 Unconstrained (Generic) Arrays.- 1.9.2 Records.- 1.9.2.1 Simple Record Structure.- 1.9.2.2 Record Discriminants.- 1.9.2.3 Variant Records.- 1.9.2.4 Protected Types.- 1.9.3 Compound Structures.- 1.10 Explorations.- 2 Encapsulation.- 2.1 Concept.- 2.2 Packaging Fundamentals.- 2.2.1 Initialize/Finalize.- 2.2.2 Private Types and Safe Client/Package Interface.- 2.2.2.1 Private Types and Equality.- 2.2.2.2 Issues Surrounding Limited Private Types.- 2.3 Using Generic Packages.- 2.4 Object-Oriented Support.- 2.4.1 Tagged Types.- 2.4.2 Abstract Types.- 2.4.3 Abstract Subprograms.- 2.4.4 ´Class.- 2.4.5 Dynamic Dispatch.- 2.4.6 Controlled Types.- 2.5 Using Object-Oriented Packaging.- 2.5.1 Polymorphic Versus Generic Packaging.- 2.6 A Taxonomy of Client/Package Visibility.- 2.6.1 Safe Handling of User Objects.- 2.6.1.1 Private.- 2.6.1.2 Limited Private.- 2.6.1.3 Tagged.- 2.6.1.4 Controlled.- 2.6.2 Safe Encapsulation of Data Structures.- 2.6.2.1 Private.- 2.6.2.2 Limited Private.- 2.6.2.3 Controlled.- 2.6.2.4 Encapsulated.- 2.7 Composability.- 2.8 Child Units.- 2.8.1 Generic Child Units.- 2.9 Explorations.- 3 Stacks.- 3.1 Linear Structures.- 3.2 Elementary Stacks.- 3.2.1 Abstraction.- 3.2.2 Representation.- 3.2.2.1 Static.- 3.2.2.2 Dynamic.- 3.2.3 Encapsulation.- 3.2.3.1 Stack_Pt_Pt.- 3.2.3.2 Dynamic Representations.- 3.2.4 Measurement.- 3.3 Advanced Features.- 3.3.1 Abstraction.- 3.3.2 Representation.- 3.3.2.1 Static.- 3.3.2.2 Dynamic.- 3.3.3 Encapsulation.- 3.3.4 Measurement.- 3.4 Iterators.- 3.4.1 Abstraction.- 3.4.2 Representation.- 3.4.2.1 Static.- 3.4.2.2 Dynamic.- 3.4.3 Encapsulation.- 3.4.4 Measurement.- 3.5 Explorations.- 4 Queues.- 4.1 Elementary Queues.- 4.1.1 Abstraction.- 4.1.2 Representation.- 4.1.2.1 Static: First Thoughts.- 4.1.2.2 Static: Wraparound.- 4.1.2.3 Dynamic: Two-Pointer Queues.- 4.1.2.4 Dynamic: One-Pointer Queues.- 4.1.3 Encapsulation.- 4.2 Advanced Features.- 4.2.1 Abstraction.- 4.2.2 Representation.- 4.2.2.1 Static Wraparound.- 4.2.2.2 Dynamic: One-Pointer Queues.- 4.3 Iterators.- 4.3.1 Abstraction.- 4.3.2 Representation.- 4.3.2.1 Static.- 4.3.2.2 Dynamic.- 4.3.3 Measurement.- 4.4 Explorations.- 5 Lists.- 5.1 Recursive Paradigm.- 5.1.1 Abstraction.- 5.1.2 Representation.- 5.1.2.1 Static.- 5.1.2.2 Dynamic.- 5.1.3 Encapsulation.- 5.1.4 Advanced Support.- 5.1.5 Iterators.- 5.1.6 Measurement.- 5.2 Positional Paradigm.- 5.2.1 Abstraction.- 5.2.2 Representation.- 5.3 Explorations.- 6 Trees.- 6.1 Nonlinear Structures.- 6.2 Binary Trees, Positional Paradigm.- 6.2.1 Abstraction.- 6.2.2 Representation.- 6.3 Binary Trees, Recursive Paradigm.- 6.3.1 Abstraction.- 6.3.2 Representation.- 6.4 Tree Traversals.- 6.4.1 Depth-first.- 6.4.2 Breadth-first.- 6.4.3 Other Schema.- 6.5 Complete Trees.- 6.6 N-ary Trees.- 6.7 Measurement.- 6.8 Explorations.- 7 Tree Applications.- 7.1 Tree Restructuring.- 7.1.1 Binary Search Trees Revisited.- 7.1.2 AVL Trees.- 7.1.3 B-trees.- 7.2 Heaps.- 7.2.1 Heapsort.- 7.2.2 Priority Queues.- 7.2.3 Huffman Coding.- 7.3 Dictionary Trees.- 7.4 Explorations.- 8 Graphs.- 8.1 Graphs and Digraphs.- 8.2 Digraph Specifications.- 8.3 Matrix Representation.- 8.4 Table Representation.- 8.5 Dynamic Representation.- 8.6 Applications.- 8.7 Explorations.- 9 Sets.- 9.1 Specifications.- 9.2 Static Representation.- 9.3 Dynamic Representation.- 9.4 Hashing Representation.- 9.5 Hamming Codes.- 9.6 Bags.- 9.7 Explorations.- 10 Strings.- 10.1 Specific

---