Object-Oriented Data Structures Using Java

by Dale, Nell B.; Joyce, Daniel T.; Weems, Chip

• ISBN13: 9780763710798
• ISBN10: 0763710792
• Edition: CD
• Format: Hardcover
• Copyright: 2001-12-01
• Publisher: Jones & Bartlett

Summary

Thoroughly revised and updated, Object Oriented Data Structures using Java, Second Edition presents classic data structure topics with an emphasis on problem solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors carefully introduce and expand on the use of many Java features such as packages, interfaces, abstract classes, inheritance, and exceptions. Chapters have been rearranged to get to the heart of the textbook material more quickly and additional exercises and example applications are included throughout.

Table of Contents

Software Engineering	1	(68)
The Software Process	2	(6)
Goals of Quality Software	4	(2)
Specification: Understanding the Problem	6	(2)
Program Design	8	(22)
Tools	9	(5)
Object-Oriented Design	14	(16)
Verification of Software Correctness	30	(39)
Origin of Bugs	33	(3)
Designing for Corectness	36	(5)
Program Testing	41	(5)
Testing Java Data Structures	46	(13)
Practical Considerations	59	(1)
Summary	60	(2)
Summary of Classes and Support Files	62	(2)
Exercises	64	(5)
Data Design and Implementation	69	(70)
Different Views of Data	70	(9)
Data Types	70	(1)
Data Abstraction	71	(3)
Data Structures	74	(1)
Data Levels	75	(1)
An Analogy	75	(4)
Java's Built-In Types	79	(19)
Primitive Data Types	80	(1)
The Class Type	81	(7)
Interfaces	88	(2)
Arrays	90	(2)
Type Hierarchies	92	(6)
Class-Based Types	98	(41)
Using Classes in Our Programs	100	(3)
Sources for Classes	103	(3)
The Java Class Library	106	(12)
Building Our Own ADTs	118	(13)
Summary	131	(2)
Summary of Classes and Support Files	133	(1)
Exercises	133	(6)
ADTs Unsorted List and Sorted List	139	(110)
Lists	140	(1)
Abstract Data Type Unsorted List	141	(21)
Logical Level	141	(5)
Application Level	146	(1)
Implementation Level	147	(15)
Abstract Classes	162	(7)
Relationship between Unsorted and Sorted Lists	162	(1)
Reuse Options	163	(1)
An Abstract List Class	164	(2)
Extending the Abstract Class	166	(3)
Abstract Data Type Sorted List	169	(12)
Logical Level	169	(1)
Application Level	170	(1)
Implementation Level	170	(11)
Comparison of Algorithms	181	(8)
Big-O	183	(1)
Common Orders of Magnitude	184	(5)
Comparison of Unsorted and Sorted List ADT Algorithms	189	(4)
Unsorted List ADT	189	(1)
Sorted List ADT	190	(3)
Generic ADTs	193	(56)
Lists of Objects	193	(1)
The Listable Interface	194	(2)
A Generic Abstract List Class	196	(4)
A Generic Sorted List ADT	200	(4)
A Listable Class	204	(1)
Using the Generic List	205	(1)
Case Study: Real Estate Listings	206	(31)
Summary	237	(1)
Summary of Classes and Support Files	238	(3)
Exercises	241	(8)
ADTs Stack and Queue	249	(92)
Formal ADT Specifications	250	(5)
Stacks	255	(26)
Logical Level	255	(9)
Application Level	264	(8)
Implementation Level	272	(9)
The Java Collections Framework	281	(5)
Properties of Collections Framework Classes	281	(1)
The Legacy Classes	282	(1)
Java 2 Collections Framework Interfaces	283	(1)
The AbstractCollection Class	284	(1)
What Next?	285	(1)
Queues	286	(55)
Logical Level	286	(3)
Application Level	289	(8)
Implementation Level	297	(7)
Case Study: Postfix Expression Evaluator	304	(21)
Summary	325	(1)
Summary of Classes and Support Files	325	(2)
Exercises	327	(14)
Linked Structures	341	(64)
Implementing a Stack as a Linked Structure	342	(14)
Self Referential Structures	342	(5)
The LinkedStack Class	347	(1)
The push Operation	348	(2)
The pop Operation	350	(3)
The Other Stack Operations	353	(2)
Comparing Stack Implementations	355	(1)
Implementing a Queue as a Linked Structure	356	(10)
The Enqueue Operation	358	(2)
The Dequeue Operation	360	(2)
The Queue Implementation	362	(1)
A Circular Linked Queue Design	363	(1)
Comparing Queue Implementations	364	(2)
An Abstract Linked List Class	366	(14)
Overview	366	(3)
The LinkedList Class	369	(11)
Implementing the Unsorted List as a Linked Structure	380	(6)
Comparing Unsorted List Implementations	384	(2)
Implementing the Sorted List as a Linked Structure	386	(9)
Comparing Sorted List Implementations	394	(1)
Our List Framework	395	(10)
Summary	398	(1)
Summary of Classes and Support Files	398	(1)
Exercises	399	(6)
Lists Plus	405	(70)
Circular Linked Lists	406	(11)
The CircularSortedLinkedList Class	407	(2)
The Iterator Methods	409	(1)
The is There Method	410	(1)
Deleting from a Circular List	411	(2)
The insert Method	413	(4)
Circular Versus Linear	417	(1)
Doubly Linked Lists	417	(5)
The Insert and Delete Operations	418	(2)
The List Framework	420	(2)
Linked Lists with Headers and Trailers	422	(1)
A Linked List as an Array of Nodes	423	(11)
Why Use an Array?	423	(2)
How Is an Array Used?	425	(9)
A Specialized List ADT	434	(41)
The Specification	434	(2)
The Implementation	436	(5)
Case Study: Large Integers	441	(21)
Summary	462	(1)
Summary of Classes and Support Files	462	(3)
Exercises	465	(10)
Programming with Recursion	475	(54)
What is Recursion?	476	(4)
A Classic Example of Recursion	477	(3)
Programming Recursively	480	(3)
Coding the Factorial Function	480	(2)
Comparison to the Iterative Solution	482	(1)
Verifying Recursive Methods	483	(1)
The Three-Question Method	483	(1)
Writing Recursive Methods	484	(4)
A Recursive Version of is There	485	(3)
Debugging Recursive Methods	488	(1)
Using Recursion to Simplify Solutions-Two Examples	488	(8)
Combinations	489	(2)
Towers of Hanoi	491	(5)
A Recursive Version of Binary Search	496	(2)
Recursive Linked-List Processing	498	(7)
Reverse Printing	498	(3)
The Insert Operation	501	(4)
How Recursion Works	505	(9)
Static Storage Allocation	505	(3)
Dynamic Storage Allocation	508	(6)
Removing Recursion	514	(4)
Iteration	514	(2)
Stacking	516	(2)
Deciding Whether to Use a Recursive Solution	518	(11)
Summary	520	(1)
Summary of Classes and Support Files	521	(1)
Exercises	522	(7)
Binary Search Trees	529	(82)
Trees	530	(8)
Binary Trees	532	(2)
Binary Search Trees	534	(2)
Binary Tree Traversals	536	(2)
The Logical level	538	(4)
The Comparable Interface	538	(2)
The Binary Search Tree Specification	540	(2)
The Application Level	542	(2)
A printTree Operation	543	(1)
The Implementation Level-Declarations and Simple Operations	544	(2)
Iterative Versus Recursive Method Implementations	546	(7)
Recursive numberOfNodes	546	(4)
Iterative numberOfNodes	550	(2)
Recursion or Iteration?	552	(1)
The Implementation Level-More Operations	553	(21)
The isThere and retrieve Operations	553	(3)
The insert Operation	556	(6)
The delete Operation	562	(6)
Iteration	568	(4)
Testing Binary Search Tree Operations	572	(2)
Comparing Binary Search Trees to Linear Lists	574	(2)
Big-O Comparisons	574	(2)
Balancing a Binary Search Tree	576	(5)
A Nonlinked Representation of Binary Trees	581	(30)
Case Study: Word Frequency Generator	585	(12)
Summary	597	(1)
Summary of Classes and Support Files	597	(1)
Exercises	598	(13)
Priority Queues, Heaps, and Graphs	611	(62)
Priority Queues	612	(3)
Logical Level	612	(2)
Application Level	614	(1)
Implementation Level	614	(1)
Heaps	615	(14)
Heap Implementation	619	(2)
The enqueue Method	621	(3)
The dequeue Method	624	(4)
Heaps Versus Other Representations of Priority Queues	628	(1)
Introduction to Graphs	629	(25)
Logical Level	633	(2)
Application Level	635	(12)
Implementation Level	647	(7)
Storing Objects/Structures in Files	654	(19)
Saving Object Data in Text Files	655	(3)
Saving Structures in Text Files	658	(2)
Serialization of Objects	660	(3)
Summary	663	(1)
Summary of Classes and Support Files	663	(2)
Exercises	665	(8)
Sorting and Searching Algorithms	673	(76)
Sorting	674	(3)
A Test Harness	675	(2)
Simple Sorts	677	(12)
Straight Selection Sort	678	(4)
Bubble Sort	682	(5)
Insertion Sort	687	(2)
O(N log2N) Sorts	689	(21)
Merge Sort	690	(8)
Quick Sort	698	(6)
Heap Sort	704	(6)
More Sorting Considerations	710	(10)
Testing	710	(1)
Efficiency	710	(2)
Sorting Objects	712	(8)
Searching	720	(3)
Linear Searching	721	(1)
High-Probablity Ordering	722	(1)
Key Ordering	722	(1)
Binary Searching	723	(1)
Hashing	723	(26)
Collisions	727	(7)
Choosing a Good Hash Function	734	(4)
Complexity	738	(1)
Summary	738	(1)
Summary of Classes and Support Files	739	(1)
Exercises	740	(9)
Appendix A Java Reserved Words	749	(1)
Appendix B Operator Precedence	750	(1)
Appendix C Primitive Data Types	751	(1)
Appendix D ASCII Subset of Unicode	752	(1)
Answers to Selected Exercises	753	(40)
Index	793