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

by Michael B. Feldman (Author)

Editorial Reviews

Product Description
Using Ada as a language for data structures, Feldman offers a blend of the theoretical and applied. The reader comes away from this book equipped to understand and design data structures and their implementations.

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

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)
• Average Customer Review: 4.0 out of 5 stars See all reviews (1 customer review)
• Amazon.com Sales Rank: #150,371 in Books (See Bestsellers in Books)

  Popular in these categories: (What's this?)

  #1 in	Books > Computers & Internet > Programming > Languages & Tools > Ada
  #10 in	Books > Computers & Internet > Programming > Algorithms > Data Structures

Customer Reviews

Most Helpful Customer Reviews

4.0 out of 5 stars a good computer book, July 9, 2000

By	tanping wang (Washington,DC, DC United States) - See all my reviews

this book is a pretty good textbook. I bought this book because the author is my advisor of grduate school. After I looked over it, i feel that it's really good book for the first learners of computer science.