Data Structures and Software Development in an Object Oriented Domain : Java Edition

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

• ISBN13: 9780137879533
• ISBN10: 0137879539
• Edition: 1st
• Format: Hardcover
• Copyright: 2003-01-01
• Publisher: Prentice Hall

Summary

This Java data structures book provides a strong introduction to object-oriented programming. It features a comprehensive presentation of the fundamentals of algorithm analysis foralgorithm and data structure comparisons, along with basic software engineering principles for the object-oriented analysis and design of a large information system. It is the first data structures book to present an introduction to software design and development at an intermediate level. Key Features bull; bull;Data structure library: Lists, stacks, queues, trees, balanced trees, graphs, and files are discussed in detail and implemented in Java. bull;UML: Software analysis and modeling are presented using a subset of UML at a level accessible to second- or third-year students. bull;Timing analysis: Timing is extensively studied and used throughout. bull;Two case studies: Real examples illustrate the object-oriented development process for the analysis and design of a non-trivial system. bull;Electronic materials: All of the code included in the text and an example of a well-designed data structure library with implementations of all the standard data structures is provided for downloading.

Table of Contents

State of Software Development	1	(17)
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)
Java Basics	17	(38)
Introduction	18	(1)
Comments and White Space	19	(1)
Naming Conventions	19	(1)
Data Types	19	(2)
Primitive Types	19	(1)
Reference Types	20	(1)
Literals and Constants	21	(1)
Operators	21	(4)
Arithmetic Operators	21	(1)
Increment and Decrement Operators	21	(1)
Relational Operators	22	(1)
Boolean Operators	22	(1)
Object-Oriented Notation for Operations	23	(1)
String Operations	23	(2)
Basic Statements	25	(7)
Assignment Statement	25	(1)
Statements for Input and Output to the Console	26	(1)
Declaration Statement	27	(1)
Compound Statement or Block	27	(1)
If Statement	28	(1)
While Statement	29	(1)
For Statement	30	(1)
Switch Statement	30	(2)
Methods	32	(2)
Class Declaration	34	(2)
Java Program	36	(1)
Objects	36	(4)
Printing Objects	37	(1)
Object Equality	38	(1)
The this Object	39	(1)
Accessibility	39	(1)
Inheritance	40	(4)
Argument Passing	44	(2)
Repairing Program Faults	46	(2)
Compile-Time Errors	46	(1)
Run-Time Errors	47	(1)
Debugging Techniques for Incorrect Output	47	(1)
I/O to Text Files	48	(2)
Java Virtual Machine (JVM)	50	(1)
Graphical User I/O	50	(2)
Concluding Remarks	52	(3)
Objects and Classes	55	(18)
Introduction	55	(1)
Models and Modeling	56	(1)
Objects	57	(6)
What Is an Object?	57	(2)
State	59	(1)
Behavior	60	(1)
Interface	61	(1)
Identity	62	(1)
Types of Objects	62	(1)
Classes and Instances	63	(2)
Relationships to Describe Class Interactions	65	(7)
Concluding Remarks	72	(1)
Arrays and Strings	73	(16)
An Array Application and Analysis of the Problem	73	(1)
Arrays in Java	74	(3)
Problem Solution	77	(2)
Storage Structure, Assignment, 'and Equality for Reference Types	79	(4)
Strings	83	(1)
String Buffer Class	84	(1)
Concluding Remarks	85	(1)
New Java Constructs	85	(4)
Array Algorithms and Their Analysis	89	(54)
Algorithm Analysis	90	(20)
Analytical Timing Analysis	91	(17)
Experimental Timing Comparison	108	(1)
Space Comparison	109	(1)
Searching	110	(5)
Linear Search	111	(2)
Binary Search	113	(2)
Sorting	115	(7)
Bubble Sort	115	(1)
Merge Sort	116	(6)
Introduction to Object Comparison, Interfaces, and the Object Class	122	(4)
Array Dictionaries	126	(15)
Basic Dictionary	127	(8)
Basic Keyed Dictionary	135	(6)
Concluding Remarks	141	(1)
New Java Constructs	141	(2)
Abstract Data Types and Their Implementation	143	(44)
Introduction	143	(1)
Data Types	144	(2)
Specifying Abstract Data Types	146	(15)
Introduction	146	(1)
The Axiomatic Approach	147	(7)
The Constructive Approach	154	(4)
The Postcondition Approach	158	(3)
Specifying and Implementing ADTs in Java	161	(10)
ADT Syntax Specification in Java	162	(2)
ADT Semantics Specification in Java	164	(2)
ADT Implementation in Java	166	(5)
Assertion Checking and Exceptions	171	(8)
Visibility of Classes and Class Members	179	(3)
Introduction to Design by Contract	182	(1)
Concluding Remarks	183	(2)
New Java Constructs	185	(2)
List Fundamentals	187	(42)
A Simple List Application	188	(1)
List Abstract Data Type	189	(3)
Implementations	192	(16)
Array Implementation	192	(5)
Linked Implementation	197	(8)
Handling Exceptions	205	(3)
Examples of Linked Operations	208	(7)
Maximum Value in a List	208	(1)
Position of a Value in a List	209	(1)
Inserting a Value Prior to Another Value	210	(1)
The toString(), equals(), and clone() Methods	211	(4)
Ordered Simple List	215	(6)
List Variations	221	(5)
Last Reference	221	(2)
Doubly Linked Lists	223	(3)
List with a Head and Circular List	226	(1)
Concluding Remarks	226	(1)
New Java Constructs	227	(2)
Advanced List Concepts and the Uos Data Structure Library	229	(54)
List Tools	230	(12)
Cursor	230	(1)
Iterator	230	(9)
Traverser	239	(3)
Library of Dictionaries and List Data Structures	242	(13)
Applications	255	(18)
A University Library Application	255	(11)
Memory Management	266	(7)
Polymorphism and Heterogeneous Lists	273	(8)
Concluding Remarks	281	(1)
New Java Constructs	281	(2)
Stacks	283	(22)
Introduction	284	(1)
Stack ADT	285	(1)
Implementations	286	(5)
Applications	291	(12)
Parentheses Matching	292	(1)
Java Dynamic Model	293	(10)
Concluding Remarks	303	(2)
Recursion	305	(22)
Recursive Definitions from Mathematics	305	(2)
Recursive Methods	307	(2)
Developing and Verifying Recursive Methods	309	(4)
Timing Analysis for Simple Recursive Methods	313	(3)
Recursive List Methods	316	(8)
Concluding Remarks	324	(1)
New Java Constructs	324	(3)
Queues and Priority Queues	327	(32)
Queues	328	(3)
Queue ADT	328	(2)
Implementations	330	(1)
Applications	331	(1)
Priority Queues	331	(6)
Priority Queue ADT	335	(1)
Implementations	335	(2)
Application: Discrete Simulations	337	(21)
Concluding Remarks	358	(1)
New Java Constructs	358	(1)
Object-Oriented Development: An Example	359	(86)
Introduction	360	(1)
Object-Oriented Development Life Cycle	360	(1)
Various Stakeholders in Software Development	361	(1)
An Object-Oriented Development Approach	362	(5)
A Simplified Banking Example	367	(68)
Specify System Requirements	367	(2)
Determine the System Boundary	369	(6)
Identify Objects and Classes	375	(3)
Identify Class Interactions and Features	378	(22)
Group Classes into Subsystems	400	(3)
Determine High-Level System Architecture	403	(5)
Find More Detailed Design Classes and Perform Detailed Class Design	408	(5)
Write Code for First Working Prototype	413	(13)
Review System for Quality Considerations	426	(5)
Refine Coding for First Working Prototype and Perform Testing	431	(1)
Sample Output from the System	432	(3)
Design Caveat	435	(3)
Seamless Software Development	438	(1)
Benefits of the Object Model	439	(1)
Concluding Remarks	440	(1)
New Java Constructs	440	(5)
Trees	445	(70)
Introduction and Applications	446	(4)
Binary Tree Abstract Data Type	450	(3)
Binary Trees	453	(37)
Implementation	453	(9)
Traversals	462	(9)
Ordered Binary Trees	471	(12)
Tree Tools	483	(4)
Binary Tree Data Structures in the Uos Library	487	(3)
General Trees	490	(4)
Applications	494	(19)
Better Dictionaries	494	(2)
Languages, Grammars, and Parsing	496	(15)
Expression Evaluation	511	(2)
Concluding Remarks	513	(2)
Elementary Problem Modeling and System Design	515	(72)
Introduction	515	(1)
Modeling Static System Structure	516	(31)
Generating a Context Model	517	(1)
How to Find Classes	518	(9)
Using Relationships to Describe Class Interactions	527	(13)
Subsystems (Packages)	540	(5)
Using a Layered Architecture in System Design	545	(2)
Modeling System Behavior	547	(9)
Users, Actors, and Use Cases	548	(1)
Events	548	(2)
Sequence Diagrams	550	(3)
Collaboration Diagrams	553	(3)
Analysis and Architectural Design of a Student Registration System	556	(24)
Specify System Requirements	556	(3)
Determine the System Boundary	559	(7)
Identify Objects and Classes	566	(2)
Identify Class Interactions and Features	568	(5)
Group Classes into Subsystems	573	(2)
Determine High-Level System Architecture	575	(5)
Concluding Remarks	580	(7)
Principles of Software Design	587	(84)
Introduction	588	(1)
Design by Contract	589	(11)
Review	589	(1)
Client-Supplier Contract	590	(2)
Subcontracting and Inheritance	592	(4)
Precondition Design	596	(1)
Other Types of Assertion Support	597	(2)
Purposes of Using Assertions	599	(1)
Exception Handling	600	(18)
Notions of Exception Handling	600	(2)
Basic Exception Handling	602	(7)
Predefined Exception Classes	609	(2)
Defining and Throwing Your Own Exceptions	611	(2)
Strategies for Exception Handling	613	(3)
The Effect of Inheritance on Exception Handling	616	(1)
Summary and Exception Guidelines	617	(1)
Class Design	618	(8)
Class Life Cycle	618	(2)
State Space and Behavior of a Class	620	(1)
Side Effects in Functions	621	(1)
How Many Parameters in Methods?	622	(1)
Keeping Classes Simple	623	(1)
Dealing with Abnormal Cases: Class Robustness	624	(1)
Class-Level Design Guidelines	625	(1)
Building Inheritance Taxonomies	626	(7)
Overview of Some Categories of Inheritance	626	(1)
Inheritance versus Aggregation	627	(2)
Some Characteristics of Inheritance Taxonomies	629	(3)
Guidelines for Building Good Inheritance Taxonomies	632	(1)
Coupling and Cohesion in Object-Oriented Software	633	(12)
Coupling	633	(7)
Cohesion	640	(5)
Using Patterns in Software Design	645	(17)
Introduction	645	(3)
Review of Patterns Presented Earlier	648	(4)
Architectural Patterns	652	(3)
Design Patterns	655	(7)
Subsystem Design	662	(1)
Coupling and Cohesion	663	(1)
Boundary Classes for Subsystems	663	(1)
Detailed Design of a Student Registration System	663	(3)
Concluding Remarks	666	(5)
Software Testing	671	(42)
Fundamentals of Software Testing	672	(5)
Basic Terminology	672	(1)
Basic Notions of Testing	673	(1)
Determining Test Cases	674	(1)
Levels of Testing	675	(1)
Psychology of Testing	675	(2)
Testing Principles	677	(1)
Human Testing	677	(1)
Code Readings	677	(1)
Structured Walk-Throughs	678	(1)
Black-Box Testing	678	(7)
Boundary Value Testing	679	(2)
Equivalence Class Testing	681	(4)
White-Box (Program-Based) Testing	685	(5)
Object-Oriented Testing	690	(14)
Issues in Testing Object-Oriented Software	690	(1)
Method Testing	691	(3)
Testing Recursive Methods	694	(2)
State-Based Class Testing	696	(4)
The Effect of Inheritance on Testing	700	(1)
Object-Oriented Integration Testing	701	(2)
Object-Oriented System Testing	703	(1)
Locating and Repairing Dynamic Faults	704	(6)
Planning for Debugging	704	(1)
Debugging by Brute Force	705	(1)
Debugging by Backtracking	706	(1)
Debugging by Induction	706	(2)
Debugging by Deduction	708	(1)
Debugging Example	708	(2)
Concluding Remarks	710	(3)
Bags, Sets, and Dictionaries	713	(74)
Introduction	714	(4)
Bit Vector Implementation	718	(2)
Hash Tables	720	(17)
Introduction	721	(1)
Design of a Hash Function	721	(3)
Collision-Resolution Techniques	724	(13)
Specialized Search Trees	737	(47)
Introduction and Motivation	737	(2)
Height-Balanced Trees	739	(15)
2-3 Trees	754	(20)
Data Structures for Good Expected Performance	774	(6)
Tree Trees	780	(4)
Better Priority Queues	784	(1)
Concluding Remarks	785	(2)
Sorting	787	(38)
Introduction	788	(1)
Review of Basic Sorts	788	(1)
Recursive Merge Sort	789	(1)
Quick sort	790	(5)
Use of Recurrence Relations for Time Requirements	795	(13)
Development of Recurrence Relations	795	(6)
Solving Recurrence Relations by Repeated Substitution	801	(3)
Solving Divide-and-Conquer Recurrence Relations	804	(4)
Heap Sort	808	(8)
Radix Sort	816	(5)
Address-Calculation Sort	821	(1)
Concluding Remarks	822	(3)
Graphs	825	(96)
Introduction and Examples of Graph Modeling	826	(7)
Basic Definitions of Graph Theory	833	(6)
Graph ADT	839	(6)
Paths, Reachability, and Connectedness	845	(4)
Graph Representations	849	(20)
Adjacency Matrix Representation	852	(8)
Adjacency Lists Representation	860	(3)
Searchable Graph	863	(6)
Computing Paths from a Matrix Representation of Graphs	869	(14)
Computing Reachability, Using Matrix Multiplications	869	(2)
Efficient Reachability Algorithm	871	(3)
All Pairs Shortest Paths Algorithm	874	(3)
Single Source Shortest Paths Algorithm	877	(6)
Traversals of Undirected Graphs	883	(13)
Breadth-First Search	883	(5)
Depth-First Search	888	(8)
Applications	896	(23)
Connectivity and Components	896	(3)
Spanning Trees	899	(4)
Topological Sorting	903	(4)
Scheduling Networks	907	(5)
Graphs in Testing	912	(7)
Concluding Remarks	919	(2)
Files	921	(58)
Introduction	922	(1)
External Storage Devices	923	(4)
Magnetic Tapes	923	(1)
Magnetic Disks	924	(3)
Definitions and Concepts	927	(2)
Persistent Storage Support in Java	929	(21)
Introduction	929	(2)
Basic Byte I/O	931	(1)
Overview of the I/O Streams	932	(1)
Object Serialization	933	(5)
Random Access Files	938	(4)
An Overview of Buffered Streams in Java	942	(3)
The ObjectFileUos Class	945	(5)
Sequential Files	950	(10)
The Structure of Sequential Files	950	(3)
Processing Sequential Files	953	(7)
Direct Files	960	(7)
Indexed Sequential Files	967	(1)
Notions of Indexed Sequential Files	967	(1)
Indexed Sequential File Implementation	968	(1)
B-Tree Files	968	(6)
B-Tree Implementation	969	(5)
Multiple-Key Access	974	(4)
Concluding Remarks	978	(1)
A Java Appendix	979	(122)
Java Syntax Charts	981	(2)
Comments and White Space	983	(2)
JavaDoc Tags	984	(1)
Names	985	(2)
Naming Conventions	985	(2)
Self Reference	987	(1)
Java Keywords	987	(1)
Data Types and Declarations	987	(14)
Primitive Types	988	(3)
Reference Types	991	(1)
The Object Class	991	(3)
Arrays	994	(2)
String	996	(3)
Wrapper Classes	999	(1)
Summary of Variable Declarations and Types	1000	(1)
Expressions	1001	(14)
Numeric Expression	1003	(1)
Typecasting and the Casting Expression	1004	(4)
Bit Expression	1008	(1)
Logical Expression	1009	(2)
Conditional Expression	1011	(1)
Assignment Expression	1012	(2)
Review of Operator Precedence and Order of Evaluation	1014	(1)
Primary	1015	(6)
Literal	1016	(1)
this	1016	(1)
Parenthesized Expressions	1017	(1)
Variable Access	1017	(1)
Function Invocation	1018	(1)
Array Access	1019	(1)
Class Instance Creation	1019	(1)
Array Creation	1020	(1)
Blocks and Statements	1021	(14)
Variable Declarations	1022	(1)
Statement	1023	(1)
Expression Statement	1024	(1)
Procedure Invocation	1025	(1)
Assert Statement	1025	(1)
If Statement	1026	(1)
Switch Statement	1027	(3)
For Statement	1030	(1)
While Statement	1031	(1)
Do Statement	1032	(1)
Break Statement	1032	(1)
Continue Statement	1033	(1)
Return Statement	1034	(1)
Throw Statement	1034	(1)
Try Statement	1034	(1)
Synchronized Statement	1035	(1)
Methods	1035	(4)
Procedures and Functions	1035	(1)
Method Body	1036	(1)
Local Variables	1036	(1)
Parameter List	1036	(1)
Method Signature	1037	(1)
Method Modifiers	1037	(2)
Constructors	1039	(2)
Constructor Body	1040	(1)
Default Constructor	1041	(1)
Creation Sequence	1041	(1)
Interfaces	1041	(5)
Interface Modifiers	1043	(1)
Interface Members	1043	(2)
Interface Inheritance	1045	(1)
Classes	1046	(12)
Class Modifiers	1046	(2)
Field Declarations	1048	(2)
Class Initializers	1050	(1)
Constructor Declarations	1051	(1)
Method Declarations	1052	(1)
Inheritance	1052	(2)
Method Overriding	1054	(1)
Multiple Fields with the Same Name	1055	(2)
Multiple Methods with the Same Signature	1057	(1)
Multiple Types with the Same Name	1057	(1)
Packages and Access Modifiers	1058	(3)
Access Modifiers	1060	(1)
Input/Output	1061	(5)
Console	1061	(1)
Files	1062	(4)
Exception Handling	1066	(7)
Throwable Classes	1066	(2)
Throws Clause	1068	(1)
Catching Exceptions	1069	(1)
Creating and Throwing Your Own Exceptions	1070	(1)
The Effect of Inheritance on Exception Handling	1071	(2)
Nested Types	1073	(10)
Static Member Types	1075	(1)
Inner Classes	1075	(8)
Multithreading	1083	(10)
Thread Class Versus Runnable Interface	1083	(2)
Synchronization	1085	(3)
Thread Fields	1088	(1)
Thread Methods	1089	(3)
Interthread Communication	1092	(1)
Deadlock	1093	(1)
Miscellaneous	1093	(8)
Random Numbers	1093	(1)
Timing	1093	(1)
Java Virtual Machine	1094	(1)
Graphical User Interfaces (AWT)	1094	(3)
Applets	1097	(4)
B The Java Data Structure Library	1101	(20)
Maps	1103	(6)
HashMaps	1106	(1)
TreeMap	1107	(2)
Sets	1109	(4)
HashSets	1111	(1)
TreeSet	1112	(1)
Lists	1113	(4)
ArrayList	1116	(1)
LinkedList	1116	(1)
Vector	1117	(1)
Arrays and Collections Classes	1117	(1)
BitSet	1118	(1)
BigInteger and BigDecimal	1118	(3)
C Math Primer	1121	(20)
Summation Notation	1121	(5)
Logarithms	1126	(2)
Cross Product and Function Notation	1128	(1)
Mathematical Induction	1129	(5)
Further Techniques for Recurrence Relations	1134	(7)
Verifying Recurrence Relation Solutions	1134	(2)
Solving Linear Homogeneous Recurrence Relations	1136	(5)
Bibliography	1141	(4)
Index	1145

Excerpts

Most computer-science curricula have at least one course in data structures. Such a course is usually taken by all majors since its contents are used in subsequent courses. Historically, this course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CS1 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 reflected in the ACM/IEEE report, "Computing Curricula 2001: Computer Science." The report recommends that one half of the .SE1 knowledge unit--software design--be covered in first year. The topics to be covered include fundamental design concepts and principles, object-oriented analysis and design, and design for reuse. This book was written to provide a strong introduction to these software design topics at the first- or second-year level. The material is integrated with the coverage of data structures in keeping with the recommendations of Curricula 2001. This book was originally designed for a second-year course taken by all our majors to reinforce data structures from first year and introduce software design. With the evolution of more software design into first year, in some situations it is also appropriate for the second term of first year (i.e., CS2). In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more application-level software development to their students. For example, the book covers almost all the material of courses CS102 O , CS103 O , and CS112 O of Curricula 2001. 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 advanced material that can be covered in a second-term first-year course depends 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 is 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 Java. It is an object-oriented language that includes interfaces, abstract classes, multiple interface inheritance, exception handling, automatic garbage collection, and GUI interfaces. In addition, it is extremely portable as it runs in a Web browser on almost every machine. Although Java 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. ADTs are discussed both formally (that can largely be ignored) and in terms of their Java implementation. In any object-oriented programming language, a concrete class provides a clean implementation of an ADT. The use of inheritance facilitates the design of modular, extendable, and reusable systems. The existence of multiple interface inheritance in Java opens up the possibilities for more modular systems. Yet using ADTs and inheritance in developing software does not 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 en