Software Construction and Data Structures with Ada 95 (2nd Edition) [Paperback]

Michael B. Feldman (Author)

Book Description

ISBN-10: 0201887959 | ISBN-13: 978-0201887952 | Publication Date: June 23, 1996 | Edition: 2

Using Ada 95, this book covers classical data structures and algorithms in a software engineering context. Through the use of generic abstract data types (ADT) packages, this text gives a realistic view of system development using reusable components. The book contains over 200 complete and compilable package specifications, implementations, and programs, which are compatible with any Ada compiler.

Editorial Reviews

From the Inside Flap

This text is the first in its field to use Ada 95 throughout as the language of instruction. It is intended for use in a second orthird course at the undergraduate level; it is also suitable forself-study. I assume a basic knowledge of Ada--equivalent to the first eight chapters of Feldman/Koffman, Ada 95: Problem Solving and Program Design, Second Edition, Addison-Wesley, 1996. I also present a summary of the Ada type system in Chapter 1, and a synopsis of other features, oriented to readers with Pascal experience, in Appendix I. Because many readers may have experience with Ada 83but not with Ada 95, I point out new features whereverappropriate.Basic Principles

As the title indicates, this book is about software constructionand data structures. It presents most of the classical datastructures, together with many algorithms, in a framework basedon software construction using the encapsulation principle.Attention is paid to "object thinking" through heavy emphasis onthe state and behavior of objects, on the use of private typesto achieve encapsulation and tight control over operations, andon the use of generic templates to achieve flexibility andreusability.

Performance prediction ("big O" notation) is introduced early inChapter 3 and pervades the remaining chapters; the notion oftrade-offs--for example, time vs. space and speed vs.abstraction--is emphasized throughout. The presentation of "bigO" is correct but rather informal, avoiding heavy mathematicalnotation that might intimidate some readers.

Inheritance and dynamic dispatching are introduced in the middleof the book. However, these important techniques are kept underrather tight control, because over-use of inheritance is nowseen by industry as potentially creating large and unmanageablehierarchies of classes. Indeed, the growing popularity of theStandard Template Library in the C++ community indicates thatgeneric templates are at least as important as inheritancestructures in building understandable and maintainable software.We have endeavored to achieve a balanced presentation, with apreference for generics but due regard for the role ofinheritance.

Packages and application programs--about 200 in all--are presentedin complete and compilable form; we have an aversion to programfragments. However, not all programs are fully functional.Sometimes only a package interface is given, so the studentcan write the implementation as an exercise.Sometimes the implementation is provided, but some or allof the operations are "stubbed out" so as to be compilable butnonfunctional. The intention is to direct the student to fill inthe code for the stubs.General Organization

Each chapter introduces some data structures concepts, a fewADTs, and one or more applications thereof, all in the contextof an integrated approach to Ada 95.

The first chapter is a general introduction to abstraction, witha brief survey of the Ada type system and how it is described inthe Ada standard. Also presented are a few basic Ada 95 topics,describing the changes to the names of standard packages,generalized declaration order, and removal of the write-onlyrestriction on OUT parameters.

The second chapter introduces five simple but very useful ADTs:Rational numbers;Currency (dollars and cents);Calendar dates;Simple video-screen control using ANSI escape sequences;Simple window management.

Recurring use is made of these in later chapters.

Chapter 3 discusses recursion and "big O," with emphasis oninformal estimation of the performance of an algorithm. "Big O"comparison is done using a keyed-table example, with the tableimplemented as an unordered array, and then as an ordered one.This example lays the groundwork for the recurring generickeyed-table introduced in Chapter 5 and reimplemented in laterchapters as appropriate data structures (linked lists, binarysearch trees, hash tables) are brought into play.

A discussion of the relationship between performance predictionand performance measurement is given in Section 3.6, along witha package for measuring elapsed CPU time and some suggestionsfor implementing it on timeshared computers.

Ada's standard time services provide only time-of-day, which isfine for personal computers but useless for measuring CPU timeon a shared system. Therefore one must resort to usingoperating-system services. The example in this section suggestshow to do this and some code is given in an appendix forimplementing it under Unix.

Chapter 4 introduces multidimensional and unconstrained arrays,with examples from vectors and matrices, as well a generaldiscussion of storage mappings for multidimensional arrays.

Chapter 5 introduces generics, including a generic sort and ageneric binary search, and generic ADTs for bit-mapped sets,vectors, and keyed tables.

Chapter 6 introduces variant records, with examples taken frompersonnel records, geometric shapes, variable-length strings,and metric (dimensioned) quantities. Also introduced here areAda 95 tagged types, with a revision of the personnel example toshow type extension as a much more dynamic kind of variantrecord.

Chapter 7 introduces queues and stacks, with differentimplementations, all as generic ADTs, of course. Stacks are usedto implement several simple expression-to-RPN translators;queues are applied in a discrete simulation of a supermarket.

Chapters 8 and 9 present dynamic linear linked structures. Thefirst chapter introduces the basics, the second presents someinteresting generic applications--including a reimplementation ofthe keyed table--as well as introducing Ada 95 unbounded strings,general access types and heterogeneous lists.

Chapter 10 introduces directed graphs, with an application tostate graphs.

Chapter 11 presents the basics of binary trees, using expressiontrees and binary search trees as the main examples. The chapterconcludes with an extended example of a cross-referencer,including an example of Ada 95 subprogram pointers to implementfinite state machines and other table-driven programming.

Chapter 12 presents some "advanced" examples of trees: threadedbinary trees, heaps, AVL trees, and general (non-binary) trees.The heap is presented as a data structure in its own right,which operations provided in a generic package. An example isgiven of using this heap package to implement priority queues;the same generic heap package is reused in Chapter 14 toimplement heap sort.

Chapter 13 gives a brief introduction to hash tables; Chapter 14presents a collection of sorting algorithms, classified by their"big O."

Finally, Chapter 15 gives a brief introduction to concurrentprogramming; Ada task types and protected types are presentedthrough a series of small examples, followed by two majorapplications: a bank simulation and the famous DiningPhilosophers.Acknowledgements

The programs in this book have been tested with the GNATcompiler runnning on a Sun Sparc server under Solaris; weacknowledge the School of Engineering and Applied ScienceComputing Facilty (SEASCF) at The George Washington Universityfor providing the computer resources. We have also tested theprograms under DOS on an IBM-PC compatible.

Michael B. Feldman
Bethesda, MD 0201887959P04062001

From the Back Cover

Ideal for large-scale software system development, Ada 95 is the first fully object-oriented language to be internationally standardized by the ISO and the ANSI. Michael B. Feldman's Software Construction and Data Structures with Ada 95 introduces data structures concepts and their applications using this powerful, yet flexible language. Through the use of generic abstract data type (ADT) packages, this text gives a realistic view of system development using reusable components. With an informal writing style, Michael B.Feldman leads students from subject to subject finding effective, maintainable, and portable solutions to programming problems.

Highlights:

• Covers Ada 95 object-oriented programming concepts.
• Introduces algorithm performance evaluation and "big O" notation in Chapter 3 and expands on the concepts throughout the book.
• Uses real-world applications in each chapter for students to put data structures and ADTs into practice.
• Provides over 200 executable programs and packages that are portable to any Ada 95 compiler on any computer.

See all Editorial Reviews

Product Details

• Paperback: 648 pages
• Publisher: Addison Wesley; 2 edition (June 23, 1996)
• Language: English
• ISBN-10: 0201887959
• ISBN-13: 978-0201887952
• Product Dimensions: 9.2 x 7.4 x 1 inches
• Shipping Weight: 2.1 pounds (View shipping rates and policies)
• Amazon Best Sellers Rank: #2,100,408 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.