Object-Oriented Introduction to Data Structures Using Eiffel

RICHARD S. WIENER is also author of the companion text, An Object-Oriented Introduction to Computer Science 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.