Object-Oriented Introduction to Data Structures Using Eiffel - Softcover

Wiener, Richard

Softcover

ISBN 10: 0131855883 ISBN 13: 9780131855885

Publisher: Pearson, 2008

Synopsis

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++.

About this title

About the Author

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

From the Back Cover

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.

From the Inside Flap

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.

Edition details

• Publisher: Pearson
• Publication date: 2008
• Language: English
• ISBN 10: 0131855883
• ISBN 13: 9780131855885
• Binding: Paperback
• Edition number: 1
• Number of pages: 520