Register your product to gain access to bonus material or receive a coupon.
Object-Oriented Introduction to Data Structures Using Eiffel
- By Richard Wiener
- Published Feb 4, 1997 by Pearson.
Book
- Sorry, this book is no longer in print.
About
Features
“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 gre
Description
- Copyright 1997
- Dimensions: 7" x 9-1/4"
- Pages: 528
- Edition: 1st
- Book
- ISBN-10: 0-13-185588-3
- ISBN-13: 978-0-13-185588-5
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.
Sample Content
Table of Contents
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.
Preface
There is a strong need for a CS 2 book that from the very beginning presents the basic principles of data structures from an object- oriented perspective and is supported by a friendly, consistent, and relatively easy-to-learn object-oriented programming language. This book is directed at meeting this need. It is aimed at computer science students enrolled in a rigorous computer science curriculum taking CS 2. It is also aimed at practicing software development professionals new to the subject of data structures, Eiffel, and object-oriented problem solving.
Some computer science departments have been moving towards C++ to support CS 2. This author believes that this is a serious error. Although C++ is commercially important and widely used outside of the university, which probably accounts for its adoption as a CS 2 language, it is a poor choice to support CS 2. The C++ language is quite complex, is hard to read, and provides relatively little safety to the beginning programmer. C++ requires beginning students to master a myriad of low-level details while at the same time developing a high-level vision and sensitivity concerning the safe construction of data structures. The Eiffel language is much better suited for this task. In addition to being a viable and important language, it provides a wonderful platform for teaching the basic concepts of data structures and safe programming. Its high degree of readability, its support for generic class parameters, its assertion handling and emphasis on program correctness, and it powerful but understandable inheritance mechanisms provide a notation and foundation upon which to introduce the important data abstractions that comprise CS 2.
Chapter 1 presents a summary of an object-oriented approach to problem solving. The notions of abstract data types, encapsulation, class, external versus internal views of a class, inheritance, and polymorphism are introduced. This chapter is especially important for those readers with little or no object-oriented programming background.
Chapter 2 presents an overview of the Eiffel programming language. The major features of the language are presented and illustrated with short examples. This chapter is aimed at readers with no prior programming experience with Eiffel.
Chapter 3 presents the ARRAY and STRING classes and discusses some classical sorting algorithms. Included are selection-sort, bubble- sort, comb-sort, and quick sort.
Chapter 4 introduces the stack and queue abstractions and several of their implementations. Both static and dynamic implementations are included.
Chapter 5 presents several basic list implementations: unordered list without duplicates, unordered list with duplicates, ordered list without duplicates, and ordered list. The stack, queue, priority queue and deque are implemented in terms of a list. Portions of a doubly- linked list are shown.
Chapter 6, introduces the basic concepts of recursion. The mechanics of recursion are illustrated with several examples including the generation of permutations of an arbitrary group of objects.
Chapter 7 presents three applications of the stack. The first application demonstrates how a recursive algorithm can be implemented iteratively using a stack. The second application presents the classic infix to postfix conversion and algebraic function evaluation using stacks as the central computation engine. The third application uses a stack as a major component of a Las Vegas Solitaire simulation.
Chapter 8 presents a discrete-event queuing application. A random number class is constructed to support the queuing application.
Chapter 9 presents two applications of lists. The first application involves the partial construction of a class that manipulates extended precision integers. The second application involves the construction of a class to encapsulate the polynomial abstraction.
Chapter 10 introduces the binary tree with a focus on search trees. The need for tree balancing is explored.
Chapter 11 presents two important algorithms for balancing search trees: the AVL and weight-balanced algorithms.
Chapter 12 introduces unordered collections. The BIT data type is explored and used to implement the set abstraction. The concepts associated with hash tables are introduced. A common and important hash function is implemented using the BIT data type. Collision resolution is explored with a focus on linear and coalesced chaining. A simulation is presented that compares the efficiency of these two collision resolution algorithms.
Chapter 13 presents two applications of binary trees: heap sorting and a “learning tree” game.
Acknowledgments
I wish to acknowledge the monumental contributions of Bertrand Meyer to the intellectual foundations of object-oriented software development. Many of the seminal ideas associated with object-oriented software construction are embodied in the elegant and powerful Eiffel language and its libraries that Bertrand is the creator of. I strongly recommend that readers of this book obtain the soon to be published Second Edition of Object-Oriented Software Construction. This book, like the original edition published by Prentice-Hall in 1988, is destined to become an important classic.
Most importantly I wish to thank Bertrand personally for his friendship and support. This has meant a great deal to me, particularly with this project. I also thank Annie Meyer for her tremendous support.
My thanks also go to Madison Cloutier and Rock Howard of Tower Technology. This company, along with ISE, has made significant contributions to making outstanding quality Eiffel systems widely available at an affordable price. The examples developed in this book were tested with one or both of these Eiffel systems.
I would like to thank Jim McKim of the Hartford Graduate Center, my good friend and occasional Eiffel mentor, for his inspiration and help in all of my Eiffel projects.
Finally I wish to thank my wife Hanne for her tremendous help in all of my work and for her love.
More Information
Other Things You Might Like
- eBook $30.39