An object-oriented introduction to data structures using Eiffel

Preface. 1. An Object-Oriented Approach To Problem Solving. Abstract data types and classes. Encapsulation-attributes and routines. External and internal views of class. Inheritance. A more technical example of inheritance-a preview of data structures and the Eiffel programming language. Generic classes. Polymorphism and late-binding. Application that features late binding-Specification- Analysis-Design-Eiffel implementation-A final look at polymorphism in this application. Summary. Exercises. References. 2. An Overview of Eiffel. Programming in Eiffel. Creating and destroying objects-Basic types-Reference semantics versus value semantics-Assigning objects-Copying objects --Cloning-Basic operators-Branching-Iteration (loop) -Routines. Basic input and output. Arrays. An overview of the components of an Eiffel class. Creation. Subclass creation-More advanced subclass creation. Inheritance. Extension-Specialization - The redefine subclause- Selective export-the export subclause-Renaming inherited routines-the rename subclause-The select subclause. Abstract classes using Eiffel's deferred class facility. Storage versus computation: attributes versus routines. Protecting and documenting routines-assertions and programming by contract. Account classes revisited with assertions-Propagation of assertions through inheritance. Summary. Exercises. 3. Arrays, Sorting and Strings. ARRAY class. Sorting. Sorting problems versus their instances-Selection-sort algorithm-More on the efficiency of sorting algorithms-Bubble sort-Comb-sort-a magic number and a fast variant of bubble- sort-Insertion-sort-Quick-sort-Partition algorithm. Strings. String searching-simple algorithm. Summary. Exercises. 4. Stacks and Queues. Container classes. Stack. Static implementation of STACK-Dynamic implementation. Queue. Summary. Exercises. 5. Lists. Types of lists. Dynamic unordered list without duplicates. The UNORDERED_LIST data abstraction-Interface to UNORDERED_LIST-Implementation of class UNORDERED_LIST-Discussion of class LIST_TYPE-Details of UNORDERED_LIST-Discussion of UNORDERED_LIST. Unordered list with duplicates. Discussion of class UNORDERED_LIST_D. Ordered list. Doubly-linked list. Stack revisited. The queue revisited. The Deque. Priority queue. Summary. Exercises. 6. Recursion. The mechanics of recursion. First example of recursion-Second example of recursion- Third example of recursion-Final example of recursion-permutation group. Recursion used in design. Binary Search of Sorted Arrays. Summary. Exercises. 7. Applications of Stacks. Permutation iterator. Infix to postfix conversion and function evaluation. Evaluation of postfix expressions-Conversion from infix to postfix-Implementation of system that evaluates algebraic expressions. Las Vegas Solitaire. Specifications-Analysis and Implementation. Summary. Exercises. 8. Application of Queues. Queuing theory. Random number generator. Simple queuing application. Summary. Exercises. 9. Applications of Lists. Long integers. The internal representation of LONG_INTEGER-Addition of long integers-Construction of class LONG_INTEGER-Implementation of creation routine make-Implementation of the addition operation- Implementation of as_string command. Polynomials. Class POLYNOMIAL-Creation routine for POLYNOMIAL-The 169>+170> query-The differentiate query-The integrate query. Conclusions. Exercises. 10. Binary Trees What is a binary tree? Tree traversal. Path length. Implementation of binary tree. The constrained generic parameter in BINARY_T-Implementation of commands preorder, inorder, and postorder-Implementation of average_internal_path_length. Search trees. Insertion-Deletion-Search tree implementation. The need for tree balancing. Summary. Exercises. 11. Balanced Search Trees. Rotations. AVL trees. AVL insertion-Pattern 1-Pattern 2-Insertion algorithm-Explanation of insertion algorithm-Deletion algorithm. Weight-balanced trees. Conceptual framework-Implementation of insertion. Summary. Exercises. Reference. 12. Unordered Collections. The BIT data type. Summary of BIT_REF features. The Set abstraction. Set of integers using BIT type. Discussion of Listing 12.3. Hash functions and tables. Design of a good hash function-Implementation of hash function-Collision-resolution algorithms-Simulation that compares linear with coalesced chaining. Summary. Exercises. 13. Applications of Binary Trees Heap sorting. The heap data structure-Overview of heapsort algorithm- The procedure formheap-The procedure rebuildheap-Speed of heapsort versus quicksort-Concluding remarks about heapsort. A "learning"tree. Summary. Exercises. Interface to String Class.