Fundamentals of Oop and Data Structures in Java

by Richard Wiener , Lewis J. Pinson

• ISBN13: 9780521662208
• ISBN10: 0521662206
• Format: Hardcover
• Copyright: 2000-06-05
• Publisher: Cambridge University Press

Summary

Fundamentals of OOP and Data Structures in Java is a text for an introductory course on classical data structures. Part One of the book presents the basic principles of Object-Oriented Programming (OOP) and Graphical User Interface (GUI) programming with Java as the example language. Part Two introduces each of the major data structures with supporting, GUI-based laboratory programs designed to reinforce the basic concepts and principles of the text. These laboratories allow the reader to explore and experiment with the properties of each data structure. All source code for the laboratories is available on the web. By integrating the principles of OOP and GUI programming, this book takes the unique path of presenting the fundamental issues of data structures within the context of paradigms that are essential to today's professional software developer. The authors assume the reader has only an elementary understanding of Java and no experience with OOP.

Table of Contents

Preface	xiii
PART ONE: FOUNDATIONS
Cornerstones of OOP	3	(19)
Data Abstraction	4	(1)
Encapsulation	5	(1)
Object	5	(1)
Message	6	(1)
Method	6	(1)
Class	7	(1)
Inheritance	8	(5)
Late Binding Polymorphism	13	(1)
Abstract Classes	13	(4)
Interface	17	(2)
Delegation	19	(1)
Generic Classes and Interfaces	19	(1)
Summary	20	(1)
Exercises	21	(1)
Objects	22	(29)
Reference Semantics and Creating Objects	22	(1)
Assigning, Aliasing, and Cloning Objects	23	(7)
Equality Testing	30	(1)
Scalar versus Reference Types	31	(1)
Scalar Types and Their Wrappers	31	(1)
Wrapping and Un wrapping--Conversion from Object to Scalar and Scalar to Object	32	(2)
Strings	34	(2)
Class StringBuffer	36	(1)
Arrays	36	(4)
Vector	40	(4)
Enumeration	44	(4)
Summary	48	(1)
Exercises	49	(2)
Class Construction	51	(13)
Responsibilities between a Class and Its Users - Design by Contract	51	(4)
Organization of a Class	55	(1)
Packages	56	(4)
Access Modifiers	60	(1)
Naming Conventions	61	(1)
Summary	62	(1)
Exercises	63	(1)
Relationships between Classes	64	(13)
Inheritance	64	(1)
Composition	65	(1)
Class Relationships in Action - A Case Study	66	(9)
Summary	75	(1)
Exercises	76	(1)
GUI: Basic Concepts	77	(18)
The Graphical Part of a GUI Application	77	(5)
Events - Making Communication Work	82	(7)
The MVC Design Pattern	89	(5)
Summary	94	(1)
Implementing Simple GUIs in Java	95	(24)
Containers and Essential Components - Building a GUI	95	(4)
Implementation of Event Handling in Java	99	(9)
Implementing MVC in Java	108	(7)
Summary	115	(1)
Exercises	115	(4)
Errors and Exceptions	119	(16)
Classification of Errors and Exceptions	120	(1)
Advertising Exceptions	121	(3)
Throwing an Exception	124	(1)
Creating Exception Classes	125	(1)
Handling Exceptions	126	(1)
The finally Clause	127	(1)
Putting It All Together - An Example	127	(4)
Catching Runtime Exceptions - An Example	131	(2)
Summary	133	(1)
Exercises	133	(2)
Recursion	135	(22)
Properties for a Well-Behaved Recursion	136	(2)
Iteration versus Recursion	138	(4)
Relative Complexity of a Recursion	142	(3)
Examples of Single and Double Recursion	145	(7)
Summary	152	(1)
Exercises	152	(5)
PART TWO: DATA STRUCTURES
Abstract Data Types	157	(13)
Counter ADT	158	(2)
General Properties of the Fraction ADT	160	(1)
Requirements for Class Fraction	160	(3)
Implementation Details for Selected Methods in Class Fraction	163	(3)
Building a Fraction Laboratory to Test Class Fraction	166	(2)
Documentation for Fraction - Generated by javadoc	168	(1)
Summary	168	(1)
Exercises	169	(1)
Containers as Abstract Data Types	170	(27)
The Container Hierarchy - Top Level	171	(2)
The Simplest Containers - Stack and Queue	173	(2)
Supporting Interface and Classes	175	(3)
The Container Hierarchy	178	(14)
UML Description of Container Hierarchy	192	(2)
Summary	194	(1)
Exercises	194	(3)
Stack and Queue	197	(17)
The Stack	197	(1)
ArrayStack	198	(3)
LinkedStack	201	(4)
Comparing the Efficiency of ArrayStack with LinkedStack	205	(2)
Queue	207	(1)
LinkedQueue	208	(2)
Stack/Queue Laboratory	210	(1)
Summary	211	(1)
Exercises	212	(2)
Application of Stack	214	(13)
Algebraic Expression Evaluation	214	(2)
Algorithm for Converting from Infix to Postfix Representation	216	(2)
Implementation of Algebraic Function Evaluation	218	(7)
Function Evaluation Laboratory	225	(1)
Summary	225	(1)
Exercises	226	(1)
Lists	227	(36)
Dequeue - An Implementation of List	227	(13)
Positionable List	240	(9)
Vector List	249	(3)
Ordered List	252	(4)
List Laboratory	256	(2)
Stack and Queue Revisited	258	(1)
Summary	259	(1)
Exercises	260	(3)
Trees, Heaps, and Priority Queues	263	(52)
Trees	263	(20)
Heaps	283	(17)
Priority Queues	300	(12)
Summary	312	(1)
Exercises	313	(2)
Search Trees	315	(52)
Review of Search Table Abstraction	315	(1)
Binary Search Tree	316	(1)
Searching for an Element in a Search Tree	317	(1)
Balance of Search Tree	318	(2)
Adding an Element to a Binary Search Tree	320	(1)
Removing an Element in a Binary Search Tree	320	(2)
Method add for Binary Search Tree	322	(1)
Method remove for Binary Search Tree	323	(7)
Performance of Binary Search Tree	330	(1)
AVL Tree	330	(1)
Tree Rotation	331	(2)
AVL add	333	(7)
AVL Deletion	340	(2)
Splay Tree	342	(2)
Implementation of Class Splay Tree	344	(4)
Skip List	348	(1)
Implementation of Skip List	349	(7)
Putting It All Together	356	(3)
Reusable Class Draw Tree	359	(5)
Summary	364	(1)
Exercises	364	(3)
Hashing and Sets	367	(28)
Hashing and Collision Resolution	367	(2)
Bit Operations	369	(2)
Perfect Hash Function	371	(2)
Collisions	373	(2)
Class Hashtable	375	(3)
Collision Resolution	378	(8)
Set	386	(6)
Summary	392	(1)
Exercises	393	(2)
Association and Dictionary	395	(32)
The Association Abstract Data Type	395	(4)
The Dictionary Interface	399	(3)
Implementing the Dictionary Interface	402	(11)
The Dictionary Laboratory	413	(2)
The Ordered Dictionary Interface	415	(3)
Implementing the Ordered Dictionary Interface	418	(4)
The Ordered Dictionary Laboratory	422	(2)
Summary	424	(1)
Exercises	424	(3)
Sorting	427	(10)
Simple and Inefficient Sorting Algorithms	427	(3)
Efficient Sorting Algorithms	430	(4)
Binary Search	434	(1)
Sort Laboratory	434	(1)
Summary	435	(1)
Exercises	435	(2)
Appendix A Unified Modeling Language Notation	437	(8)
A.1 Representing Classes in UML	437	(2)
A.2 Representing Relationships among Classes in UML	439	(2)
A.3 Representing Packages in UML	441	(1)
A.4 Representing Objects in UML	442	(1)
A.5 Representing Interactions among Objects in UML	442	(3)
Appendix B Complexity of Algorithms	445	(5)
Appendix C Installing and Using Foundations Classes	450	(5)
C.1 Installing the Foundations Classes	450	(1)
C.2 Using foundations jar with the Java 2 Platform	450	(2)
C.3 Using foundations.jar with JBuilder	452	(3)
Index	455