Object-Oriented Introduction to Data Structures Using Eiffel
Richard Wiener, Colorado Springs, CO

ISBN-10: 0131855883
ISBN-13: 9780131855885

Publisher: Prentice Hall
Copyright: 1997
Format: Paper; 528 pp
Available on Demand

Suggested retail price: $78.65
Buy from myPearsonStore

A text book directed at CS2, the second course is a computer science curriculum and comparison release to the author's object-oriented Introduction to Computer Science using Eiffel. It presents the basic principles of Data Structures from an object-oriented perspective using Eiffel, and relatively easy to learn object-oriented programming languages. As a data alternative to C and C++.

Learn an object-oriented approach to data structures --without the complexity of C++.

  • Introduces the basic principles of data structures from an object-oriented perspective, using Eiffel.
  • Presents detailed coverage of non-linear data structures, including binary trees, balanced search trees, and unordered collections.
  • A companion guide to the author's 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.

RICHARD S. WIENER is also author of the companion text, An Object-Oriented Introduction to Computer Science Using Eiffel.


18558-7

“Data structures and algorithms are at the core of any computing science education. Richard S. Wiener's An Object-Oriented Introduction to Data Structures Using Eiffel has the great distinction of combining the best in algorithms and data structures with the best in supporting software technology: object-oriented programming and Eiffel. The result, both for the students and their teachers, is the most exciting path available today for learning these fundamental topics.” —Bertrand Meyer, creator of the Eiffel Language and author of Object-Oriented Software Construction.

An object-oriented approach to data structures—without the complexity of C++.

Eiffel is the ideal language for introducing object-oriented concepts, because it is highly readable, supports safe programming, and does not require students to master a myriad of low-level details in order to program successfully. An Object-Oriented Introduction to Data Structures Using Eiffel serves as a complete second course in computer science, using Eiffel to introducing all the fundamentals of object-oriented data structures, including abstract data types, encapsulation, classes, external and internal views of classes, inheritance and polymorphism.

The book begins by introducing object-oriented problem solving and presenting an overview of the Eiffel language. Step-by-step, students are introduced to both fundamental concepts and their programming applications. Topics covered include:

  • ARRAY and STRING classes, and several classical sorting algorithms.
  • Stack and queue abstractions, in both static and dynamic implementations.
  • The basic concepts and mechanics of recursions.
  • Stack applications.
  • Discrete-event queueing.
  • Unordered collections and hash tables.

This book also includes a thorough introduction to binary trees and search trees, presenting important algorithms for balancing search trees, as well as two practical applications.

An Object-Oriented Introduction to Data Structures Using Eiffel is the companion book to Richard S. Wiener's complete first course, An Object-Oriented Introduction to Computer Science Using Eiffel. Together, both texts deliver a complete introduction to object-oriented computing that is friendly, consistent and easy to understand.

View a Sample Chapter PDF:

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students, contact your Pearson Higher Education representative for pricing and ordering information.

Pearson Higher Education offers special pricing when you choose to package your text with other student resources. If you're interested in creating a cost-saving package for your students contact your Pearson Higher Education representative.


Copyright ©2008 Pearson Education. All rights reserved. Legal Notice | Privacy Policy | Permissions