ISBN-10:
0137879466
ISBN-13:
9780137879465
Pub. Date:
02/26/2001
Publisher:
Prentice Hall
Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition / Edition 1

Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition / Edition 1

by Jean-Paul Tremblay, Grant A. Cheston

Other Format

Current price is , Original price is $109.0. You
Select a Purchase Option (EIFFEL ED.)
  • purchase options

Overview

Data Structures and Software Development in an Object Oriented Domain, Eiffel Edition / Edition 1

FEATURES

  • Use of a subset of the UML—Shows how to use UML for analysis and modeling.
  • CD-ROM included—CD contains an Eiffel compiler and development environment, all the code for the text, and the data structures library.
  • Modeling of the Problem Domain—Absent in other texts, this book models the problem domain that an object-oriented project must begin with.
  • Two case studies—Illustrates the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.
  • Extensive Data Structures Library—Consists of the standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files.
  • Extensive Reference for the Eiffel language—A full-featured object-oriented language, Eiffel, specifically developed for large object-oriented systems.

Product Details

ISBN-13: 9780137879465
Publisher: Prentice Hall
Publication date: 02/26/2001
Series: Object and Component Technology Ser.
Edition description: EIFFEL ED.
Pages: 1071
Product dimensions: 7.68(w) x 9.94(h) x 2.07(d)

Read an Excerpt

PREFACE:

Preface

Most computer-science curricula have at least one course in data structures. Such a course s usually taken by all majors, since its contents are used in subsequent courses. Historically, his course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CSl and CS2 of the ACM88 Curriculum). However, in recent years such a course is also expected to give students a good object-oriented programming background, and, increasingly, an introductory background in software development. This is in keeping with the ACM/IEEE-CS Computing Curricula 1991 report, which emphasizes, among other things, software engineering and software design, rather than merely implementing the data structures in an object-oriented language.

Whereas this book is designed for our present second-year course taken by all our majors, it is also appropriate for the second term of first year (i.e., CS2) in some situations. In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more on application-level software development to their students. To fit at the CS2 level, the book includes all the material on the basic data structures arrays and linked lists-before treating more advanced data structures. The amount of the advanced material that can be covered in a second-term first-year course will depend on the background of the students and the pace of the course. However, the book has more material than can typically be covered in a CS2 course. As a result, it can also be used in a subsequent course to develop more depth in data structures and softwareengineering. Alternately, if first year uses a breadth-first approach, this book will be suitable for a strong second-year course that integrates data structures and software engineering.

Our presentation is from an object-oriented perspective and includes many of the recent software engineering techniques for an object-oriented development of a system. For our implementation language, we have chosen Eiffel, a language specifically designed for developing large object-oriented systems. It is a full-featured object-oriented language that includes abstract classes, assertions such as preconditions, postconditions, and class invariants, multiple inheritance, generic classes, exception handling, automatic garbage collection, and GUI interfaces. In particular, preconditions and postconditions were designed to support the software engineering approach of Design by Contract. Also, the simple concepts can be expressed in a clean and simple syntax without being clouded by a multitude of alternatives, options, and exception handling. Even for more complex concepts, the syntax is still simple, although the semantics necessarily increase in complexity. Although Eiffel is the language of implementation, we only use moderate amounts of code.

Like in most other recent data structure books, abstract data types (ADTs) are discussed early. ADTs offer several advantages that include encapsulation and information hiding. In any object-oriented programming language, a deferred/abstract class provides a clean implementation of an abstract data type. Also, the use of inheritance facilitates the design of modular, extendible, and reusable systems. The existence of multiple and repeated inheritance in Eiffel opens up more possibilities for the system design implementation.

But using ADTs and inheritance in developing software does not by themselves guarantee quality software. One of the primary goals is to integrate several software-engineering principles with the data structures content of the course. Students at the first- or second-year level should be introduced to the principles of software engineering, but they do not have the programming experience to understand the problems or complexities of writing large projects. Often, if these software principles are studied in isolation, they can be beyond their comprehension and are viewed as just requiring more work. They do see the need for data structures, and, with a library of data structures, they can design and build much larger applications. Thus, the book integrates data structures, library design, and the software principles into one package. Obviously at the first- or second-year level, software engineering cannot be presented to the depth of a third-year or fourth-year/graduate course. However, by gradually introducing more and more software design concepts when building up a data structures library, students can obtain a surprisingly good background in the analysis and design of software systems.

However, our discussion of software development is not limited to the data structures library context. We begin with simple software engineering concepts and repeatedly use them to develop applications throughout the book. After students have developed a working knowledge of the software basics, the more advanced concepts are introduced throughout the remainder of the book. The students absorb the software engineering material while working with concrete techniques and data structures.

An important part of this book not found in most other texts is the modeling of the problem domain. Any nontrivial object-oriented project must begin with problem modeling, and even at the first- or second-year level, students need exposure to modeling concepts. The static structure is modeled using types of relationships such as inheritance, aggregation, and association. The dynamic structure is modeled with events, users (and actors), use cases, and object-interaction diagrams. We develop and present a simplified methodology for system development. Included with it is the use of appropriate diagrams using the Unified Modeling Language (UML) to portray the key aspects of the system design. We use the methodology to develop significant applications that use the data structures being developed in parallel.

Some important aspects of this book are:

  • The presentation of basic software engineering concepts at a level suitable for advanced first- or second-year students, including the use of a subset of the UML to present the results of analysis and modeling. Also, there is extensive use of diagrams to portray software relationships, which includes using the following types of diagrams: inheritance, context, sequence, collaboration, class, high-level architecture, and subsystem.
  • The' standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files, are developed, analyzed, applied, and placed in an extensive data structures library. Most of these data structures have iterators for traversing the data structures. The library also has a number of implementations of keyed and non-keyed dictionaries.
  • The discussion of software engineering includes the concepts of Design by Contract, cohesion, and coupling.
  • The object-oriented techniques of inheritance and polymorphism are used. Single inheritance is introduced in Chapter 2 and frequently used thereafter. Multiple inheritance is presented in Chapter 6 and used to define many of the data structures of the library. Polymorphism is introduced in Chapter 6 and used in both the data structures library and applications.
  • Two case studies illustrate the steps followed in an object-oriented development process for the analysis and design of nontrivial systems.
  • Timing analysis is extensively studied and used throughout. This includes the analysis of recursive algorithms, first by counting the number of calls and then by recurrence relations.
  • A full chapter is included on software testing, which deals with traditional black box and white box test-case generation techniques, as well as testing techniques for object-oriented software.
  • Abstract Data Types are presented from both the constructive and the axiomatic approaches using an object-oriented notation.
  • Eiffel, the language used for implementation, is a full-featured object-oriented language. It has automatic garbage collection, polymorphism, multiple inheritance, generic classes, assertions for the support of the Design-by-Contract approach, and exception raising and handling. Eiffel was designed with a clean and simple syntax so that more advanced concepts, like exceptions, don't clutter the simple concepts.
  • An extensive reference for the Eiffel language is included in an appendix.
  • Some of the concepts and techniques are introduced on an as-needed basis rather than overwhelming the student with a full treatment of the topic in a single chapter. For example, the basics of the language Eiffel are presented in Chapter 2, and most of the subsequent chapters add various constructs, as they are needed for specific purposes. This approach is also used for timing analysis and UML notation.
  • An appendix reviews basic mathematics for handling summations, logarithms, and functions.
  • An extensive collection of problems is included. Also, there are a number of case studies that are suitable for student projects.
  • A CD is included with the book that contains all code for the text, the data structures library, and an Eiffel compiler with its associated environment.

Summary by Chapters

Chapter 1 examines the phases present in most software development processes. This chapter explores briefly factors that are important in assessing the quality of software systems. The chapter also examines some fundamental principles of software design that have been used in the production of quality software. It concludes with an overview of three approaches to software design.

Chapter 2 presents the basics of the Eiffel language. The main goal of this chapter is to cover Eiffel's elementary constructs so that a student can write simple programs.

Chapter 3 introduces the elements and mechanisms that constitute the object model. The model is based on data abstraction, encapsulation, and hierarchy.

Chapter 4 introduces the concept of the array. Processing of single-dimensional arrays, or vectors, is discussed first. The notions of time and space analysis are then introduced. Some typical applications of arrays are described; among these are the important applications of searching and sorting.

Chapter 5 promotes ADTs as part of a good design strategy that can lead to the production of good reusable components. This chapter presents three approaches to specifying ADTs, and it concludes with a discussion of how ADTs can be implemented in Eiffel.

Chapter 6 deals first with basic list structures and their sequential storage representations. Several list variations are explored. This chapter introduces list-manipulation tools such as cursors, iterators, and traversers. Design by Contract and its effects on inheritance is introduced. Certain design issues of the data structures library dealing with list structures are discussed, and two applications of list structures are given. This chapter includes the notion of polymorphism and its application to heterogeneous lists.

Chapter 7 begins with a discussion of stack structures. Recursion (and its implementation) is dealt with in some detail. A discussion of queue structures with their implementations and applications follows. The chapter then presents priority queues with associated implementation considerations and their use in discreteevent simulations.

Chapter 8 illustrates an object-oriented life cycle in which a system for a simple banking application is developed. The development begins with a specification of the problem and concludes with a presentation of implementation fragments with sample outputs. Some elements of the Unified Modeling Language (UML) are introduced and used in the development of the banking system. Design patterns used in the design of the banking system are overviewed. This chapter discusses the benefits of the object model and the advantages of dealing with objects throughout the development life cycle.

Chapter 9 deals with the most important nonlinear data structure - the tree. The chapter presents binary trees in detail, including their manipulations, representations, and associated tools. The design issues of incorporating trees in the data structures library are discussed. Multiple inheritance and feature adaptation are described; the chapter then extends binary trees to more general trees. Three applications of trees are given. The chapter also introduces mathematical induction as a way to prove properties of tree structures.

Chapter 10 investigates further the modeling concepts introduced in earlier chapters. The emphasis is primarily on the analysis and architectural design phases of development. It concludes with the presentation of these phases for a student registration system.

Chapter 11 focuses on software design issues. The chapter discusses more fully the Design by Contract principle, which was introduced earlier. The handling of exceptions arising from contract violations is then presented. This chapter presents several aspects of class design. Various kinds of inheritance are introduced. The choice between inheritance and aggregation relationships is analyzed and compared. Some characteristics of inheritance hierarchies are introduced, as well as guidelines for their construction. Coupling and cohesion in object-oriented software are discussed in detail. Software patterns are revisited and extended. It concludes with a brief overview of the detailed design of the student registration system.

Chapter 12 outlines software testing. It first introduces some fundamentals of software testing. Human testing approaches are outlined. Two approaches used to generate test cases are introduced: black-box testing and white-box testing. It then deals with the issues which arise in testing object-oriented software. It concludes with an examination of how to locate and repair dynamic errors that have caused a system to fail.

Chapter 13 surveys specialized data structures for searching. In particular, searching methods based on hashing, height-balanced trees, 2-3 trees, and trie trees are examined. Priority queues are revisited and extended.

Chapter 14 describes sorting techniques. In addition to reviewing the basic sorting techniques introduced in Chapter 4, more advanced techniques such as Quicksort, Heapsort, and Radix sort are described in detail. Recurrence relations are introduced as a tool to analyze the time requirements of recursive sorting methods. A comparison of sorting methods indicates that the performance of certain methods can be significantly improved by choosing an appropriate data structure.

Chapter 15 describes graph structures. The chapter first gives examples of graph modeling and introduces basic graph terminology. More advanced terminology involving the notions of reachability and connectedness is given. Several graph representations are illustrated. Algorithms for computing and traversing graphs based on these representations follow. The chapter concludes with the presentation of several applications of graphs.

Finally, Chapter 16 contains an introduction to external files. External storage devices are described, since the characteristics are important in file design and manipulation. ISE's Eiffel environment support for files is discussed. A number of file organizations such as sequential, direct, and index sequential is introduced. B-tree files and multi-key files are outlined.

The book also contains two appendices. Appendix A gives a reasonably comprehensive summary of the Eiffel language. Appendix B is a mathematics primer that contains basic terminology and results, which are used throughout the book.

Extensive sets of exercises conclude most chapters and sections. The exercises have been designed for self study as well as classroom study. For the reader's convenience, the exercises have been graded and given a level of difficulty. The ratings are as follows:

An exercise which can be answered easily.
* An average exercise that tests basic understanding of the material.
** An exercise of moderate difficulty that can take some time.

The book includes two significant case studies: a simple banking system and a student registration system. Also, many problems and case studies are included as assignments or as projects suitable for a group of two to three students. The focus of each case study is on analysis and design.

The exercises deal with the following issues:

  • programming
  • analysis and design
  • testing
  • timing/space analysis of algorithms
  • algorithms to manipulate various data structures
  • using mathematical induction to prove properties of certain data structures such as trees

The solutions to the case studies and exercises are in the accompanying Instructor's Manual.

How to Use This Book

As background for this book, the reader is expected to already know the fundamentals of programming. This includes the use of declarations and the development of procedures and functions. Also, the reader will usually know how to use arrays, including the basic techniques for sorting and searching an array. This programming background might have been gained by using an object-oriented language, but this is not necessary. We certainly do not assume experience using the language Eiffel.

This book was written with the following three broad objectives in mind:

  • The reader should obtain a good grasp of object-oriented programming through a powerful, cleanly structured language.
  • The reader should learn all the standard data structures and the fundamentals of algorithm analysis for algorithm and data structure comparisons.
  • The reader should learn the basics of the object-oriented development of a large information system (software engineering).

As this is not a programming book, object-oriented programming is not an explicit topic of any one chapter of the book. Object-oriented programming is just a means to implement data structures and software systems. Nevertheless, object-oriented programming pervades the entire book. The degree to which the other two objectives are emphasized is dependent upon the objectives of the instructor. However, data structures and software engineering are included together in this book, as we feel that there are benefits to at least a moderate exposure to both topics. In particular, basic software engineering approaches should not be delayed until the third year.

Figure 1 has a prerequisite chart for the chapters of this book. Each box has a chapter number and a short description of its contents. Solid arrows from a box are directed to chapters that need to be covered before the current chapter. Dashed arrows are directed to chapters that ideally would be covered first, but it is not essential that they are.

In the diagram, the two streams can be clearly seen. The software engineering stream includes Chapters 3, 8, 10, 11, and 12. The data structures stream has Chapters 4, 6, 7, 9, 13, 15, and 16. As we have indicated, it is important not to do just one stream. By intermingling the two streams, a concept in one stream can be presented in class, while by means of an assignment, students are developing a familiarity with the previous concept in the other stream. In particular, it is important to cover Chapter 8 in detail to obtain exposure to modern software engineering. If this is not done, students may merely view computing as programming.

There is more material here than can be completed in one undergraduate semester course. However, the amount of material allows the book to be used in a variety of ways:

Second-year course, which re-enforces data structures and introduces software engineering techniques. Such a course can be particularly useful in programs that take a breadth-first approach in first year. Topics in the book might be covered as follows:

  • With a first-year programming background, Chapter 2 can be covered quickly.
  • Most of Chapter 4 should already be known, but some coverage of timing analysis may be needed. Also, dictionaries are introduced in this chapter.
  • Depending upon the background of students and the instructor's objectives, the Abstract Data Type chapter can be omitted, covered informally, or covered in detail.
  • Most students will already be familiar with linked lists, so in Chapter 6, it will only be necessary to cover iterators, Design by Contract, the data structures library, and heterogeneous lists. Many students will also know stacks and queues. Consequently Chapter 7 can largely be ignored. Students weak in recursion will benefit from that subsection.
  • For students to obtain an introduction to software engineering, Chapter 8 needs to be covered in detail. Also, it should not be covered late in the course, as students need to do a significant assignment to fully appreciate the topic.
  • The remainder of the course can go in different directions:
    1. Emphasize data structures from Chapters 9 (trees), 13 (better dictionaries), 15 (graphs), and 16 (files);
    2. Emphasize software engineering from Chapters 10 (modeling and high-level design), 11 (detailed design), and 12 (testing);
    3. A combination of data structures and software engineering.

Background graduate course, which takes graduate students from other fields, and gives them the fundamentals of computer science in an intense, fast-paced course. In such a course, most of the book can be covered, which will provide the background for study in a number of more specialized areas.

Advanced first-year course, for students with a strong background. If students enter university with programming experience, and program in an object-oriented language during their first term, by second term of first year, they are ready for a course based on this book. The chapters covered would be similar to that described above for a second-year course, except that more time would likely be needed for lists, stacks, recursion, and queues. Perhaps Chapter 8 might be covered before Chapter 7 to ensure that there is enough time for a significant assignment on Chapter 8. Of the more advanced chapters, there might only be enough time for a couple of chapters, say 9 on trees and 12 on testing.

We advocate a laboratory environment of some sort for the parallel presentation of the issues relating to the actual problem modeling and computing components of the course. The instructor may wish, on occasion, to deal in class with particularly difficult notions related to assignment issues, but too much of this detracts from continuity of presentation. Students should not view the course as a course on programming. The laboratory also provides the student with the opportunity to develop solutions to problems, with assistance readily available when needed. Also, to learn the most from the software engineering topics, students should work in teams on a significant problem. It is not necessary for students to implement their solution, as much is gained by just doing the analysis and detailed design.

Acknowledgments

We are grateful to the many people who assisted us in the preparation of this book. We owe a large debt of thanks to Jeremy Pfeifer, who assisted in the preparation of the manuscript, read most of the manuscript, created all the diagrams, helped to pick out many errors, and made the final copy-editing changes. Reid van Melle was the first to work on the manuscript and assisted in the initial development of the data structures library. Kevin Lechler assisted in the preparation of Chapter 2. Peter Christensen worked on Chapter 2 and the Eiffel Appendix. Bryce Coutts assisted in the refinement of the data structures library and solved exercises. Carl Norum solved many of the exercises. Miso Cilimdzic worked on various parts of the manuscript. Chris Worman implemented and tested the two case studies, and worked on the files part of the data structures library. Deanna Tremblay proofread several versions of the manuscript. Paul Sorenson assisted in the preparation of the first eight chapters. Julita Vassileva and Carl Gutwin made valuable comments and class tested the manuscript. Ralph Deters read and suggested improvements to Chapters 8, 10, 11, and 12. We are grateful for the support of the Department of Computer Science at the University of Saskatchewan. We also wish to thank the reviewers of the manuscript: Glen Blank (Lehigh University), Roger Browne (Everything Eiffel), Cynthia Cicalese (Marymount University), Edward Gehringer (North Carolina State), Jim Grundy (Australian National University), and David Riley (University of Wisconsin-La Crosse).

Table of Contents

1. State of Software Development.
Introduction. Software Development Process. Assessing Software Quality. Principles of Software Design. Approaches to Software Design. Concluding Remarks.

2. Eiffel Basics.
Introduction. Comments and White Space. Naming Conventions. Data Types. Operations. Basic Instructions. Functions and Procedures. Class Declaration. Eiffel System. Objects. Inheritance. Argument Passing. Preparing Program Faults. I/O to Text Files. Concluding Remarks.

3. Objects and Classes.
Introduction. Models and Modeling. Objects. Classes and Instances. Relationships to Describe Class Interactions. Concluding Remarks.

4. Arrays and Algorithm Analysis.
An Array Application and Analysis of the Problem. Arrays in Eiffel. Problem Solution. Storage Structure, Assignment, and Copying for Reference Types. Dynamic Arrays. Algorithm Analysis. Computer Science Applications. Concluding Remarks. New Eiffel Constructs.

5. Abstract Data Types and Their Implementation.
Introduction. Data Types. Specifying Abstract Data Types. Implementation of ADTs in Eiffel. Concluding Remarks. New Eiffel Constructs.

6. Lists.
A List Application. List Abstract Data Type. Implementations. Examples of Linked List Operations. List Variations. List Tools. Design by Contract and Inheritance. Library of List Data Structures.Applications. Polymorphism and Heterogeneous Lists. Concluding Remarks. New Eiffel Constructs.

7. Dispensers: Stacks, Queues, and Priority Queues.
Stacks. Recursion. Queues. Priority Queues. Concluding Remarks. New Eiffel Constructs.

8. Object-Oriented Development: An Example.
Introduction. Object-Oriented Development Life Cycle. Various Stakeholders in Software Development. An Object-Oriented Development Approach. A Simplified Banking Example. Design Caveat. Seamless Software Development. Benefits of the Object Model. Concluding Remarks.

9. Trees.
Introduction and Applications. Binary Tree Abstract Data Type. Binary Trees. General Trees. Applications. Mathematical Induction. Concluding Remarks. New Eiffel Constructs.

10. Elementary Problem Modeling and System Design.
Introduction. Modeling Static System Structure. Modeling System Behavior. Using a Layered Architecture in System Design. Analysis and Architectural Design of a Student Registration System. Concluding Remarks.

11. Principles of Software Design.
Introduction. Design By Contract. Exception Handling. Class Design. Building Inheritance taxonomies. Coupling and Cohesion in Object-Oriented Software. Using Patterns in Software Design. Subsystem Design. Detailed Design of a Student Registration System. Concluding Remarks.

12. Software Testing.
Fundamentals of Software Testing. Human Testing. Black Box Testing. White Box (Program-Based)Testing. Object-Oriented Testing. Locating and Repairing Dynamic Faults. Concluding Remarks.

13. Bags, Sets, and Dictionaries.
Introduction. Bit Vector Implementation. Hash Tables. Specialized Search Trees. Better Priority Queues. Concluding Remarks.

14. Sorting.
Introduction. Review of Basic Sorts. Merge Sort. Quicksort. Use of Recurrence Relations for Time Requirements. Heap Sort. Radix Sort. Address-Calculation Sort. Concluding Remarks.

15. Graphs.
Introduction and Examples of Graph Modeling. Basic Definitions of Graph Modeling. Basic Definitions of Graph Theory. Graph ADT. Paths, Reachability, and Connectedness. Graph Representations. Computing Paths from a Matrix Representation of Graphs. Traversals of Undirected Graphs. Applications. Concluding Remarks.

16. Files.
Introduction. External Storage Devices. Definitions and Concepts. Persistent Storage Support in Eiffel. Sequential Files. Direct Files. Indexed Sequential Files. B-Tree Files. Multiple-Key Access. Concluding Remarks.

A. Eiffel Appendix.
Eiffel Syntax Charts. Names. Data Types. Operators and Operations of Built-in Types. Instructions. Routines. Details of Routine Declaration. Class Declaration. Inheritance. Input/Output. Assertions. Typing. Clusters. Exceptions. Random Numbers. Eiffel System.

B. Math Primer.
Summation Notation. Logarithms. Cross Product and Function Notation.

Bibliography.
Index.

Preface

Most computer-science curricula have at least one course in data structures. Such a course s usually taken by all majors, since its contents are used in subsequent courses. Historically, his course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CSl and CS2 of the ACM88 Curriculum). However, in recent years such a course is also expected to give students a good object-oriented programming background, and, increasingly, an introductory background in software development. This is in keeping with the ACM/IEEE-CS Computing Curricula 1991 report, which emphasizes, among other things, software engineering and software design, rather than merely implementing the data structures in an object-oriented language.

Whereas this book is designed for our present second-year course taken by all our majors, it is also appropriate for the second term of first year (i.e., CS2) in some situations. In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more on application-level software development to their students. To fit at the CS2 level, the book includes all the material on the basic data structures arrays and linked lists-before treating more advanced data structures. The amount of the advanced material that can be covered in a second-term first-year course will depend on the background of the students and the pace of the course. However, the book has more material than can typically be covered in a CS2 course. As a result, it can also be used in a subsequent course to develop more depth in data structures and software engineering. Alternately, if first year uses a breadth-first approach, this book will be suitable for a strong second-year course that integrates data structures and software engineering.

Our presentation is from an object-oriented perspective and includes many of the recent software engineering techniques for an object-oriented development of a system. For our implementation language, we have chosen Eiffel, a language specifically designed for developing large object-oriented systems. It is a full-featured object-oriented language that includes abstract classes, assertions such as preconditions, postconditions, and class invariants, multiple inheritance, generic classes, exception handling, automatic garbage collection, and GUI interfaces. In particular, preconditions and postconditions were designed to support the software engineering approach of Design by Contract. Also, the simple concepts can be expressed in a clean and simple syntax without being clouded by a multitude of alternatives, options, and exception handling. Even for more complex concepts, the syntax is still simple, although the semantics necessarily increase in complexity. Although Eiffel is the language of implementation, we only use moderate amounts of code.

Like in most other recent data structure books, abstract data types (ADTs) are discussed early. ADTs offer several advantages that include encapsulation and information hiding. In any object-oriented programming language, a deferred/abstract class provides a clean implementation of an abstract data type. Also, the use of inheritance facilitates the design of modular, extendible, and reusable systems. The existence of multiple and repeated inheritance in Eiffel opens up more possibilities for the system design implementation.

But using ADTs and inheritance in developing software does not by themselves guarantee quality software. One of the primary goals is to integrate several software-engineering principles with the data structures content of the course. Students at the first- or second-year level should be introduced to the principles of software engineering, but they do not have the programming experience to understand the problems or complexities of writing large projects. Often, if these software principles are studied in isolation, they can be beyond their comprehension and are viewed as just requiring more work. They do see the need for data structures, and, with a library of data structures, they can design and build much larger applications. Thus, the book integrates data structures, library design, and the software principles into one package. Obviously at the first- or second-year level, software engineering cannot be presented to the depth of a third-year or fourth-year/graduate course. However, by gradually introducing more and more software design concepts when building up a data structures library, students can obtain a surprisingly good background in the analysis and design of software systems.

However, our discussion of software development is not limited to the data structures library context. We begin with simple software engineering concepts and repeatedly use them to develop applications throughout the book. After students have developed a working knowledge of the software basics, the more advanced concepts are introduced throughout the remainder of the book. The students absorb the software engineering material while working with concrete techniques and data structures.

An important part of this book not found in most other texts is the modeling of the problem domain. Any nontrivial object-oriented project must begin with problem modeling, and even at the first- or second-year level, students need exposure to modeling concepts. The static structure is modeled using types of relationships such as inheritance, aggregation, and association. The dynamic structure is modeled with events, users (and actors), use cases, and object-interaction diagrams. We develop and present a simplified methodology for system development. Included with it is the use of appropriate diagrams using the Unified Modeling Language (UML) to portray the key aspects of the system design. We use the methodology to develop significant applications that use the data structures being developed in parallel.

Some important aspects of this book are:

  • The presentation of basic software engineering concepts at a level suitable for advanced first- or second-year students, including the use of a subset of the UML to present the results of analysis and modeling. Also, there is extensive use of diagrams to portray software relationships, which includes using the following types of diagrams: inheritance, context, sequence, collaboration, class, high-level architecture, and subsystem.
  • The' standard data structures, including lists, stacks, queues, trees, balanced trees, graphs, and files, are developed, analyzed, applied, and placed in an extensive data structures library. Most of these data structures have iterators for traversing the data structures. The library also has a number of implementations of keyed and non-keyed dictionaries.
  • The discussion of software engineering includes the concepts of Design by Contract, cohesion, and coupling.
  • The object-oriented techniques of inheritance and polymorphism are used. Single inheritance is introduced in Chapter 2 and frequently used thereafter. Multiple inheritance is presented in Chapter 6 and used to define many of the data structures of the library. Polymorphism is introduced in Chapter 6 and used in both the data structures library and applications.
  • Two case studies illustrate the steps followed in an object-oriented development process for the analysis and design of nontrivial systems.
  • Timing analysis is extensively studied and used throughout. This includes the analysis of recursive algorithms, first by counting the number of calls and then by recurrence relations.
  • A full chapter is included on software testing, which deals with traditional black box and white box test-case generation techniques, as well as testing techniques for object-oriented software.
  • Abstract Data Types are presented from both the constructive and the axiomatic approaches using an object-oriented notation.
  • Eiffel, the language used for implementation, is a full-featured object-oriented language. It has automatic garbage collection, polymorphism, multiple inheritance, generic classes, assertions for the support of the Design-by-Contract approach, and exception raising and handling. Eiffel was designed with a clean and simple syntax so that more advanced concepts, like exceptions, don't clutter the simple concepts.
  • An extensive reference for the Eiffel language is included in an appendix.
  • Some of the concepts and techniques are introduced on an as-needed basis rather than overwhelming the student with a full treatment of the topic in a single chapter. For example, the basics of the language Eiffel are presented in Chapter 2, and most of the subsequent chapters add various constructs, as they are needed for specific purposes. This approach is also used for timing analysis and UML notation.
  • An appendix reviews basic mathematics for handling summations, logarithms, and functions.
  • An extensive collection of problems is included. Also, there are a number of case studies that are suitable for student projects.
  • A CD is included with the book that contains all code for the text, the data structures library, and an Eiffel compiler with its associated environment.

Summary by Chapters

Chapter 1 examines the phases present in most software development processes. This chapter explores briefly factors that are important in assessing the quality of software systems. The chapter also examines some fundamental principles of software design that have been used in the production of quality software. It concludes with an overview of three approaches to software design.

Chapter 2 presents the basics of the Eiffel language. The main goal of this chapter is to cover Eiffel's elementary constructs so that a student can write simple programs.

Chapter 3 introduces the elements and mechanisms that constitute the object model. The model is based on data abstraction, encapsulation, and hierarchy.

Chapter 4 introduces the concept of the array. Processing of single-dimensional arrays, or vectors, is discussed first. The notions of time and space analysis are then introduced. Some typical applications of arrays are described; among these are the important applications of searching and sorting.

Chapter 5 promotes ADTs as part of a good design strategy that can lead to the production of good reusable components. This chapter presents three approaches to specifying ADTs, and it concludes with a discussion of how ADTs can be implemented in Eiffel.

Chapter 6 deals first with basic list structures and their sequential storage representations. Several list variations are explored. This chapter introduces list-manipulation tools such as cursors, iterators, and traversers. Design by Contract and its effects on inheritance is introduced. Certain design issues of the data structures library dealing with list structures are discussed, and two applications of list structures are given. This chapter includes the notion of polymorphism and its application to heterogeneous lists.

Chapter 7 begins with a discussion of stack structures. Recursion (and its implementation) is dealt with in some detail. A discussion of queue structures with their implementations and applications follows. The chapter then presents priority queues with associated implementation considerations and their use in discreteevent simulations.

Chapter 8 illustrates an object-oriented life cycle in which a system for a simple banking application is developed. The development begins with a specification of the problem and concludes with a presentation of implementation fragments with sample outputs. Some elements of the Unified Modeling Language (UML) are introduced and used in the development of the banking system. Design patterns used in the design of the banking system are overviewed. This chapter discusses the benefits of the object model and the advantages of dealing with objects throughout the development life cycle.

Chapter 9 deals with the most important nonlinear data structure - the tree. The chapter presents binary trees in detail, including their manipulations, representations, and associated tools. The design issues of incorporating trees in the data structures library are discussed. Multiple inheritance and feature adaptation are described; the chapter then extends binary trees to more general trees. Three applications of trees are given. The chapter also introduces mathematical induction as a way to prove properties of tree structures.

Chapter 10 investigates further the modeling concepts introduced in earlier chapters. The emphasis is primarily on the analysis and architectural design phases of development. It concludes with the presentation of these phases for a student registration system.

Chapter 11 focuses on software design issues. The chapter discusses more fully the Design by Contract principle, which was introduced earlier. The handling of exceptions arising from contract violations is then presented. This chapter presents several aspects of class design. Various kinds of inheritance are introduced. The choice between inheritance and aggregation relationships is analyzed and compared. Some characteristics of inheritance hierarchies are introduced, as well as guidelines for their construction. Coupling and cohesion in object-oriented software are discussed in detail. Software patterns are revisited and extended. It concludes with a brief overview of the detailed design of the student registration system.

Chapter 12 outlines software testing. It first introduces some fundamentals of software testing. Human testing approaches are outlined. Two approaches used to generate test cases are introduced: black-box testing and white-box testing. It then deals with the issues which arise in testing object-oriented software. It concludes with an examination of how to locate and repair dynamic errors that have caused a system to fail.

Chapter 13 surveys specialized data structures for searching. In particular, searching methods based on hashing, height-balanced trees, 2-3 trees, and trie trees are examined. Priority queues are revisited and extended.

Chapter 14 describes sorting techniques. In addition to reviewing the basic sorting techniques introduced in Chapter 4, more advanced techniques such as Quicksort, Heapsort, and Radix sort are described in detail. Recurrence relations are introduced as a tool to analyze the time requirements of recursive sorting methods. A comparison of sorting methods indicates that the performance of certain methods can be significantly improved by choosing an appropriate data structure.

Chapter 15 describes graph structures. The chapter first gives examples of graph modeling and introduces basic graph terminology. More advanced terminology involving the notions of reachability and connectedness is given. Several graph representations are illustrated. Algorithms for computing and traversing graphs based on these representations follow. The chapter concludes with the presentation of several applications of graphs.

Finally, Chapter 16 contains an introduction to external files. External storage devices are described, since the characteristics are important in file design and manipulation. ISE's Eiffel environment support for files is discussed. A number of file organizations such as sequential, direct, and index sequential is introduced. B-tree files and multi-key files are outlined.

The book also contains two appendices. Appendix A gives a reasonably comprehensive summary of the Eiffel language. Appendix B is a mathematics primer that contains basic terminology and results, which are used throughout the book.

Extensive sets of exercises conclude most chapters and sections. The exercises have been designed for self study as well as classroom study. For the reader's convenience, the exercises have been graded and given a level of difficulty. The ratings are as follows:

An exercise which can be answered easily.
* An average exercise that tests basic understanding of the material.
** An exercise of moderate difficulty that can take some time.

The book includes two significant case studies: a simple banking system and a student registration system. Also, many problems and case studies are included as assignments or as projects suitable for a group of two to three students. The focus of each case study is on analysis and design.

The exercises deal with the following issues:

  • programming
  • analysis and design
  • testing
  • timing/space analysis of algorithms
  • algorithms to manipulate various data structures
  • using mathematical induction to prove properties of certain data structures such as trees

The solutions to the case studies and exercises are in the accompanying Instructor's Manual.

How to Use This Book

As background for this book, the reader is expected to already know the fundamentals of programming. This includes the use of declarations and the development of procedures and functions. Also, the reader will usually know how to use arrays, including the basic techniques for sorting and searching an array. This programming background might have been gained by using an object-oriented language, but this is not necessary. We certainly do not assume experience using the language Eiffel.

This book was written with the following three broad objectives in mind:

  • The reader should obtain a good grasp of object-oriented programming through a powerful, cleanly structured language.
  • The reader should learn all the standard data structures and the fundamentals of algorithm analysis for algorithm and data structure comparisons.
  • The reader should learn the basics of the object-oriented development of a large information system (software engineering).

As this is not a programming book, object-oriented programming is not an explicit topic of any one chapter of the book. Object-oriented programming is just a means to implement data structures and software systems. Nevertheless, object-oriented programming pervades the entire book. The degree to which the other two objectives are emphasized is dependent upon the objectives of the instructor. However, data structures and software engineering are included together in this book, as we feel that there are benefits to at least a moderate exposure to both topics. In particular, basic software engineering approaches should not be delayed until the third year.

Figure 1 has a prerequisite chart for the chapters of this book. Each box has a chapter number and a short description of its contents. Solid arrows from a box are directed to chapters that need to be covered before the current chapter. Dashed arrows are directed to chapters that ideally would be covered first, but it is not essential that they are.

In the diagram, the two streams can be clearly seen. The software engineering stream includes Chapters 3, 8, 10, 11, and 12. The data structures stream has Chapters 4, 6, 7, 9, 13, 15, and 16. As we have indicated, it is important not to do just one stream. By intermingling the two streams, a concept in one stream can be presented in class, while by means of an assignment, students are developing a familiarity with the previous concept in the other stream. In particular, it is important to cover Chapter 8 in detail to obtain exposure to modern software engineering. If this is not done, students may merely view computing as programming.

There is more material here than can be completed in one undergraduate semester course. However, the amount of material allows the book to be used in a variety of ways:

Second-year course, which re-enforces data structures and introduces software engineering techniques. Such a course can be particularly useful in programs that take a breadth-first approach in first year. Topics in the book might be covered as follows:

  • With a first-year programming background, Chapter 2 can be covered quickly.
  • Most of Chapter 4 should already be known, but some coverage of timing analysis may be needed. Also, dictionaries are introduced in this chapter.
  • Depending upon the background of students and the instructor's objectives, the Abstract Data Type chapter can be omitted, covered informally, or covered in detail.
  • Most students will already be familiar with linked lists, so in Chapter 6, it will only be necessary to cover iterators, Design by Contract, the data structures library, and heterogeneous lists. Many students will also know stacks and queues. Consequently Chapter 7 can largely be ignored. Students weak in recursion will benefit from that subsection.
  • For students to obtain an introduction to software engineering, Chapter 8 needs to be covered in detail. Also, it should not be covered late in the course, as students need to do a significant assignment to fully appreciate the topic.
  • The remainder of the course can go in different directions:
    1. Emphasize data structures from Chapters 9 (trees), 13 (better dictionaries), 15 (graphs), and 16 (files);
    2. Emphasize software engineering from Chapters 10 (modeling and high-level design), 11 (detailed design), and 12 (testing);
    3. A combination of data structures and software engineering.

Background graduate course, which takes graduate students from other fields, and gives them the fundamentals of computer science in an intense, fast-paced course. In such a course, most of the book can be covered, which will provide the background for study in a number of more specialized areas.

Advanced first-year course, for students with a strong background. If students enter university with programming experience, and program in an object-oriented language during their first term, by second term of first year, they are ready for a course based on this book. The chapters covered would be similar to that described above for a second-year course, except that more time would likely be needed for lists, stacks, recursion, and queues. Perhaps Chapter 8 might be covered before Chapter 7 to ensure that there is enough time for a significant assignment on Chapter 8. Of the more advanced chapters, there might only be enough time for a couple of chapters, say 9 on trees and 12 on testing.

We advocate a laboratory environment of some sort for the parallel presentation of the issues relating to the actual problem modeling and computing components of the course. The instructor may wish, on occasion, to deal in class with particularly difficult notions related to assignment issues, but too much of this detracts from continuity of presentation. Students should not view the course as a course on programming. The laboratory also provides the student with the opportunity to develop solutions to problems, with assistance readily available when needed. Also, to learn the most from the software engineering topics, students should work in teams on a significant problem. It is not necessary for students to implement their solution, as much is gained by just doing the analysis and detailed design.

Acknowledgments

We are grateful to the many people who assisted us in the preparation of this book. We owe a large debt of thanks to Jeremy Pfeifer, who assisted in the preparation of the manuscript, read most of the manuscript, created all the diagrams, helped to pick out many errors, and made the final copy-editing changes. Reid van Melle was the first to work on the manuscript and assisted in the initial development of the data structures library. Kevin Lechler assisted in the preparation of Chapter 2. Peter Christensen worked on Chapter 2 and the Eiffel Appendix. Bryce Coutts assisted in the refinement of the data structures library and solved exercises. Carl Norum solved many of the exercises. Miso Cilimdzic worked on various parts of the manuscript. Chris Worman implemented and tested the two case studies, and worked on the files part of the data structures library. Deanna Tremblay proofread several versions of the manuscript. Paul Sorenson assisted in the preparation of the first eight chapters. Julita Vassileva and Carl Gutwin made valuable comments and class tested the manuscript. Ralph Deters read and suggested improvements to Chapters 8, 10, 11, and 12. We are grateful for the support of the Department of Computer Science at the University of Saskatchewan. We also wish to thank the reviewers of the manuscript: Glen Blank (Lehigh University), Roger Browne (Everything Eiffel), Cynthia Cicalese (Marymount University), Edward Gehringer (North Carolina State), Jim Grundy (Australian National University), and David Riley (University of Wisconsin-La Crosse).

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews