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

by Tremblay, Jean-Paul; Cheston, Grant A.

• ISBN13: 9780137879465
• ISBN10: 0137879466
• Format: Paperback
• Copyright: 2001-01-01
• Publisher: Prentice Hall

Summary

For CS2/CS7 Data Structures courses. Also appropriate for first- and second-year Object Oriented Design courses where instructors also want to re-enforce data structures from an object-oriented perspective. Using a unique parallel-coverage approach, this text 1) presents the fundamentals of data structures from arrays and lists to balanced trees, graphs, and files (including their design, use, implementation, and analysis); and 2) gives an introduction to object-oriented software engineering using UML (including the context diagram, use cases, sequence diagrams, architectural and detailed design, implementation, and testing). It can be used (a) to mostly present data structures with little software engineering, (b) to present both topics in parallel, or (c) to review data structures from an object-oriented perspective and then concentrate on software engineering at the first or second year level. The text uses Eiffel as the implementation language, an object-oriented language particularly well-suited to the clean presentation of data structures and software engineering concepts. Two case studies are included to illustrate the steps followed in an object-oriented development process for the analysis and design of non-trivial systems.

Table of Contents

State of Software Development	1	(16)
Introduction	1	(1)
Software Development Process	2	(3)
Assessing Software Quality	5	(4)
Quality Factors in Software Products	5	(4)
Aspiring to Measure Software Quality	9	(1)
Principles of Software Design	9	(3)
Modularity and Localization	9	(1)
Abstraction and Information Hiding	10	(1)
Loose Coupling and High Cohesion	11	(1)
Approaches to Software Design	12	(4)
Top-Down Design	13	(2)
Compositional (Bottom-Up) Design	15	(1)
Object-Oriented Design	15	(1)
Concluding Remarks	16	(1)
Eiffel Basics	17	(30)
Introduction	18	(1)
Comments and White Space	18	(1)
Naming Conventions	18	(1)
Data Types	19	(1)
Expanded Types	19	(1)
Reference Types	19	(1)
Operations	19	(3)
Arithmetic Operations	19	(1)
Relational Operations	20	(1)
Boolean Operators	20	(1)
Object-Oriented Notation for Operations	20	(1)
String Operations	21	(1)
Basic Instructions	22	(5)
Assignment	23	(1)
I/O to Console	23	(1)
If-Then-Else Instruction	24	(1)
Loop Instruction	25	(1)
Inspect Instruction	26	(1)
Functions and Procedures	27	(1)
Class Declaration	28	(1)
Eiffel System	29	(1)
Objects	30	(4)
Printing Objects	31	(1)
Object Equality	31	(2)
The Current Object	33	(1)
Limitations of Objects Access	33	(1)
Inheritance	34	(3)
Argument Passing	37	(3)
Repairing Program Faults	40	(3)
Compile-Time Errors	40	(1)
Run-Time Errors	41	(1)
Debugging Techniques for Incorrect Output	42	(1)
I/O to Text Files	43	(1)
Concluding Remarks	44	(3)
Objects and Classes	47	(18)
Introduction	47	(1)
Models and Modeling	48	(1)
Objects	49	(6)
What Is an Object?	49	(2)
State	51	(1)
Behavior	52	(1)
Interface	53	(1)
Identity	54	(1)
Types of Objects	54	(1)
Classes and Instances	55	(2)
Relationships to Describe Class Interactions	57	(6)
Concluding Remarks	63	(2)
Arrays and Algorithm Analysis	65	(62)
An Array Application and Analysis of the Problem	66	(1)
Arrays in Eiffel	67	(2)
Problem Solution	69	(2)
Storage Structure, Assignment, and Copying for Reference Types	71	(4)
Dynamic Arrays	75	(1)
Algorithm Analysis	76	(22)
Analytical Timing Analysis	77	(18)
Experimental Timing Comparison	95	(2)
Space Comparison	97	(1)
Computer Science Applications	98	(24)
Searching	99	(5)
Sorting	104	(7)
Array Dictionaries	111	(10)
Strings	121	(1)
Concluding Remarks	122	(1)
New Eiffel Constructs	123	(4)
Abstract Data Types and Their Implementation	127	(28)
Introduction	127	(1)
Data Types	128	(2)
Specifying Abstract Data Types	130	(14)
Introduction	130	(1)
The Axiomatic Approach	131	(7)
The Constructive Approach	138	(3)
The Postcondition Approach	141	(3)
Implementation of ADTs in Eiffel	144	(9)
Using Classes to Represent Data Abstractions	144	(1)
Preconditions and Postconditions Support in Eiffel	145	(5)
Class Invariants in Eiffel	150	(1)
Specifying ADTs in Eiffel	150	(3)
Concluding Remarks	153	(1)
New Eiffel Constructs	154	(1)
Lists	155	(98)
A List Application	156	(4)
List Abstract Data Type	160	(4)
Implementations	164	(15)
Array Implementation	164	(5)
Linked Implementation	169	(8)
The Built-in Copy, Clone, and Equal Routines	177	(2)
Examples of Linked List Operations	179	(12)
Maximum Value in a List	179	(1)
Position of a Value in a List	179	(1)
Inserting a Value Prior to Another Value	180	(1)
Ordered Simple List	181	(7)
Object Comparison	188	(3)
List Variations	191	(6)
Last Reference	191	(1)
Doubly Linked Lists	192	(2)
List with a Head and Circular List	194	(3)
List Tools	197	(11)
Cursor	197	(1)
Iterator	198	(7)
Traverser	205	(3)
Design by Contract and Inheritance	208	(6)
Library of List Data Structures	214	(11)
Applications	225	(16)
Library Overdue Notices	225	(8)
Memory Management	233	(8)
Polymorphism and Heterogeneous Lists	241	(8)
Concluding Remarks	249	(1)
New Eiffel Constructs	250	(3)
Dispensers: Stacks, Queues, and Priority Queues	253	(62)
Stacks	255	(15)
Stack ADT	255	(2)
Implementations	257	(4)
Applications	261	(9)
Recursion	270	(18)
Recursive Definitions from Mathematics	270	(1)
Recursive Routines	271	(2)
Developing and Verifying Recursive Routines	273	(4)
Timing Analysis for Simple Recursive Routines	277	(3)
Recursive List Routines	280	(8)
Queues	288	(6)
Queue ADT	289	(1)
Implementations	290	(3)
Applications	293	(1)
Priority Queues	294	(19)
Priority Queue ADT	295	(1)
Implementations	295	(1)
Application: Discrete Simulation	296	(17)
Concluding Remarks	313	(1)
New Eiffel Constructs	313	(2)
Object-Oriented Development: An Example	315	(78)
Introduction	315	(1)
Object-Oriented Development Life Cycle	316	(1)
Various Stakeholders in Software Development	317	(1)
An Object-Oriented Development Approach	318	(5)
A Simplified Banking Example	323	(60)
Specify System Requirements	323	(2)
Determine the System Boundary	325	(6)
Identify Objects and Classes	331	(3)
Identify Class Interactions and Features	334	(21)
Group Classes into Subsystems	355	(3)
Determine High-Level System Architecture	358	(2)
Find More Detailed Design Classes and Perform Detailed Class Design	360	(5)
Write Code for First Working Prototype	365	(12)
Review System for Quality Considerations	377	(3)
Refine Coding for First Working Prototype and Perform Testing	380	(1)
Sample Output from the System	380	(3)
Design Caveat	383	(3)
Seamless Software Development	386	(1)
Benefits of the Object Model	387	(1)
Concluding Remarks	388	(5)
Trees	393	(78)
Introduction and Applications	394	(4)
Binary Tree Abstract Data Type	398	(4)
Binary Trees	402	(40)
Implementation	402	(6)
Traversals	408	(9)
Ordered Binary Trees	417	(10)
Tree Tools	427	(3)
Multiple Inheritance and Feature Adaptation	430	(8)
Binary Tree Data Structures in the UOS Library	438	(4)
General Trees	442	(4)
Applications	446	(18)
Better Dictionaries	446	(2)
Languages, Grammars, and Parsing	448	(15)
Expression Evaluation	463	(1)
Mathematical Induction	464	(5)
Concluding Remarks	469	(1)
New Eiffel Constructs	470	(1)
Elementary Problem Modeling and System Design	471	(72)
Introduction	471	(1)
Modeling Static System Structure	472	(29)
Generating a Context Model	473	(1)
How to Find Classes	474	(9)
Using Relationships to Describe Class Interactions	483	(12)
Subsystems (Packages)	495	(6)
Modeling System Behavior	501	(9)
Users, Actors, and use Cases	501	(1)
Events	502	(1)
Sequence Diagrams	503	(3)
Collaboration Diagrams	506	(4)
Using a Layered Architecture in System Design	510	(1)
Analysis and Architectural Design of a Student Registration System	511	(26)
Specify System Requirements	512	(3)
Determine the System Boundary	515	(7)
Identify Objects and Classes	522	(2)
Identify Class Interactions and Features	524	(5)
Group Classes into Subsystems	529	(3)
Determine High-Level System Architecture	532	(5)
Concluding Remarks	537	(6)
Principles of Software Design	543	(78)
Introduction	544	(1)
Design By Contract	545	(10)
Review	545	(1)
Client-Supplier Contract	546	(2)
Precondition Design	548	(1)
Other Types of Assertion Support in Eiffel	549	(4)
Monitoring Assertions in Eiffel	553	(1)
Purposes of Using Assertions	554	(1)
Exception Handling	555	(9)
Notions of Exception Handling	555	(1)
Exception Handling in Eiffel	556	(2)
Strategies for Handling Exceptions	558	(4)
Library Support for Advanced Exception Handling	562	(2)
Class Design	564	(8)
Class Life Cycle	564	(2)
State Space and Behavior of a Class	566	(1)
Side Effects in Functions	567	(1)
How Many Arguments in Routines?	568	(1)
Keeping Classes Simple	569	(1)
Dealing with Abnormal Cases: Class Robustness	570	(2)
Class-Level Design Guidelines	572	(1)
Building Inheritance Taxonomies	572	(7)
Overview of Some Categories of Inheritance	573	(1)
Inheritance versus Aggregation	573	(3)
Some Characteristics of Inheritance Taxonomies	576	(2)
Guidelines for Building Good Inheritance Taxonomies	578	(1)
Coupling and Cohesion in Object-Oriented Software	579	(12)
Coupling	579	(8)
Cohesion	587	(4)
Using Patterns in Software Design	591	(17)
Introduction	592	(3)
Review of Patterns Presented Earlier	595	(3)
Architectural Patterns	598	(3)
Design Patterns	601	(7)
Subsystem Design	608	(2)
Coupling and Cohesion	609	(1)
Boundary Classes for Subsystems	609	(1)
Detailed Design of a Student Registration System	610	(4)
Concluding Remarks	614	(7)
Software Testing	621	(44)
Fundamentals of Software Testing	622	(5)
Basic Terminology	622	(1)
Basic Notions of Testing	623	(1)
Determining Test Cases	624	(1)
Levels of Testing	625	(1)
Psychology of Testing	626	(1)
Testing Principles	627	(1)
Human Testing	627	(1)
Code Readings	627	(1)
Structured Walk-Throughs	628	(1)
Black Box Testing	628	(7)
Boundary Value Testing	629	(2)
Equivalence Class Testing	631	(4)
White Box (Program-Based) Testing	635	(5)
Object-Oriented Testing	640	(15)
Issues in Testing Object-Oriented Software	640	(1)
Method Testing	641	(2)
Testing Recursive Routines	643	(4)
State-Based Class Testing	647	(4)
The Effect of Inheritance on Testing	651	(2)
Object-Oriented Integration Testing	653	(1)
Object-Oriented System Testing	654	(1)
Locating and Repairing Dynamic Faults	655	(6)
Planning for Debugging	656	(1)
Debugging by Brute Force	657	(1)
Debugging by Backtracking	658	(1)
Debugging by Induction	658	(1)
Debugging by Deduction	659	(1)
Debugging Example	660	(1)
Concluding Remarks	661	(4)
Bags, Sets, and Dictionaries	665	(70)
Introduction	666	(4)
Bit Vector Implementation	670	(2)
Hash Tables	672	(17)
Introduction	672	(1)
Design of a Hash Function	673	(3)
Collision-Resolution Techniques	676	(13)
Specialized Search Trees	689	(44)
Introduction and Motivation	689	(1)
Height Balanced Trees	690	(15)
2-3 Trees	705	(18)
Data Structures for Good Expected Performance	723	(6)
Trie Trees	729	(4)
Better Priority Queues	733	(1)
Concluding Remarks	734	(1)
Sorting	735	(44)
Introduction	736	(1)
Review of Basic Sorts	736	(1)
Merge Sort	737	(1)
Quicksort	738	(5)
Use of Recurrence Relations for Time Requirements	743	(19)
Development of Recurrence Relations	743	(6)
Solving Recurrence Relations by Repeated Substitution	749	(4)
Solving Linear Homogeneous Recurrence Relations	753	(3)
Solving Divide-and-Conquer Recurrence Relations	756	(6)
Heap Sort	762	(7)
Radix Sort	769	(6)
Address-Calculation Sort	775	(1)
Concluding Remarks	776	(3)
Graphs	779	(88)
Introduction and Examples of Graph Modeling	780	(7)
Basic Definitions of Graph Theory	787	(6)
Graph ADT	793	(5)
Paths, Reachability, and Connectedness	798	(5)
Graph Representations	803	(17)
Adjacency Matrix Representation	806	(4)
Adjacency Lists Representation	810	(4)
Searchable Graph	814	(4)
New Graph Representation	818	(2)
Computing Paths from a Matrix Representation of Graphs	820	(11)
Computing the Path Matrix Using Matrix Multiplications	820	(3)
Warshall's Algorithm	823	(2)
Floyd's Algorithm	825	(6)
Traversals of Undirected Graphs	831	(12)
Breadth-First Search	831	(5)
Depth-First Search	836	(7)
Applications	843	(21)
Connectivity and Components	843	(2)
Spanning Trees	845	(5)
Topological Sorting	850	(3)
Scheduling Networks	853	(6)
Graphs in Testing	859	(5)
Concluding Remarks	864	(3)
Files	867	(44)
Introduction	868	(1)
External Storage Devices	869	(4)
Magnetic Tapes	869	(2)
Magnetic Disks	871	(2)
Definitions and Concepts	873	(2)
Persistent Storage Support in Eiffel	875	(5)
Text files	876	(1)
Binary Files	876	(4)
Sequential Files	880	(11)
The Structure of Sequential Files	880	(3)
Processing Sequential Files	883	(8)
Direct Files	891	(7)
Indexed Sequential Files	898	(1)
Notions of Indexed Sequential Files	898	(1)
Indexed Sequential File Implementation	898	(1)
B-Tree Files	899	(5)
B-Tree Implementation	900	(4)
Multiple-Key Access	904	(4)
Concluding Remarks	908	(3)
A Eiffel Appendix	911	(94)
A.1 Eiffel Syntax Charts	913	(2)
A.2 Names	915	(2)
A.2.1 Identifiers	915	(1)
A.2.2 Entities	915	(1)
A.2.3 Reserved Words	916	(1)
A.3 Data Types	917	(4)
A.3.1 Declarations	917	(1)
A.3.2 Expanded and Reference Types	918	(1)
A.3.3 Basic Types and Their Manifest Constants	918	(2)
A.3.4 Platform-Dependent Properties of Built-in Expanded Types	920	(1)
A.3.5 Built-in Reference Types	920	(1)
A.3.6 User-Defined Expanded Types	920	(1)
A.3.7 ANY and NONE Clasees	921	(1)
A.3.8 Void	921	(1)
A.4 Operators and Operations of Built-in Types	921	(12)
A.4.1 Relational and Arithmetic Operators	922	(2)
A.4.2 Boolean Operators	924	(1)
A.4.3 Bit Operators	924	(1)
A.4.4 Operator Precedence	925	(1)
A.4.5 Array Operations	925	(2)
A.4.6 String Operations	927	(1)
A.4.7 TUPLE	928	(2)
A.4.8 Copy, Clone, Equal, and Other Operations of ANY	930	(3)
A.4.9 Expression	933	(1)
A.5 Instructions	933	(14)
A.5.1 Instruction and Compound	933	(2)
A.5.2 Comments	935	(1)
A.5.3 Assignment Instruction	936	(1)
A.5.4 Conditional	937	(1)
A.5.5 Multi-Branch Choice Instruction	938	(1)
A.5.6 Loop Instruction	939	(2)
A.5.7 Call Instruction	941	(2)
A.5.8 Precursor	943	(1)
A.5.9 Create Instruction	943	(4)
A.5.10 Debug	947	(1)
A.6 Routines	947	(5)
A.6.1 Procedures	948	(1)
A.6.2 Functions	948	(1)
A.6.3 Formal Arguments	949	(1)
A.6.4 Infix and Prefix Functions	950	(1)
A.6.5 Synonyms and Frozen	951	(1)
A.6.6 Variable Number of Arguments	951	(1)
A.7 Details of Routine Declaration	952	(5)
A.7.1 Obsolete, Require, Ensure, and Rescue	952	(1)
A.7.2 Local Entities	953	(1)
A.7.3 Routine Body	954	(3)
A.8 Class Declaration	957	(10)
A.8.1 Scope	958	(2)
A.8.2 Creation Part	960	(1)
A.8.3 Feature Part	960	(2)
A.8.4 Formal Generic Part	962	(4)
A.8.5 Indexing, Deferred, and Obsolete	966	(1)
A.8.6 Short and Flat-Short Forms	966	(1)
A.9 Inheritance	967	(10)
A.9.1 Inheritance and Feature Adaptation	967	(1)
A.9.2 Rename	967	(1)
A.9.3 Export	968	(2)
A.9.4 Redefine	970	(2)
A.9.5 Repeated Inheritance	972	(1)
A.9.6 Select	973	(1)
A.9.7 Undefine	974	(1)
A.9.8 Joining Features	974	(2)
A.9.9 Nonconforming Inheritance	976	(1)
A.10 Input/Output	977	(5)
A.10.1 I/O to User's Terminal	978	(3)
A.10.2 I/O to Text Files	981	(1)
A.10.3 I/O to Raw Files	981	(1)
A.11 Assertions	982	(3)
A.11.1 Preconditions	982	(1)
A.11.2 Postconditions	983	(1)
A.11.3 Check	984	(1)
A.11.4 Class Invariants	984	(1)
A.11.5 Loop Invariants and Variants	984	(1)
A.12 Typing	985	(17)
A.12.1 Basics of Conformance	986	(2)
A.12.2 Overview of Typing	988	(6)
A.12.3 Simple Typing	994	(1)
A.12.4 Including Inheritance and User Expanded Types	994	(1)
A.12.5 Including Generics	995	(2)
A.12.6 Including Anchors	997	(2)
A.12.7 Type Checking	999	(3)
A.13 Clusters	1002	(1)
A.14 Exceptions	1002	(1)
A.15 Random Numbers	1003	(1)
A.16 Eiffel System	1003	(2)
B Math Primer	1005	(10)
B.1 Summation Nottation	1005	(5)
B.2 Logarithms	1010	(2)
B.3 Cross Product and Function Notation	1012	(3)
Bibliography	1015	(4)
Index	1019

Excerpts

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 studie