Object-oriented Data Structures Using Java

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

• ISBN13: 9780763737467
• ISBN10: 0763737461
• Edition: 2nd
• Format: Hardcover
• Copyright: 2006-02-27
• Publisher: Jones & Bartlett

Summary

Thoroughly revised and updated, Object-Oriented Data Structures Using, Java, Second Edition presents traditional data structures and object-oriented topics with an emphasis on problem solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors introduce and expand upon the use of many Java features including packages, interfaces, abstract classes, inheritance, and exceptions. Numerous case studies provide readers with real-world scenarios and demonstrate possible solutions to interesting problems. Object-Oriented Data Structures Using Java, Second Edition guides the reader through the rigor of standard data structures by presenting essential concepts from the logical, application, and implementation levels. With a focus on abstract data types, this book provides a rich introduction to encapsulation, inheritance, and polymorphism.

Table of Contents

1 Gettng Organized	1	(60)
1.1 Software Engineering	2	(6)
Software Life Cycles	3	(2)
Agile Methods	5	(1)
Goals of Quality Software	6	(2)
1.2 Object Orientation	8	(2)
Benefits	9	(1)
The Unified Method	9	(1)
1.3 Classes, Objects, and Applications	10	(42)
Classes	10	(6)
Objects	16	(2)
Applications	18	(3)
1.4 Organizing Classes 20 inheritance	21	(7)
Packages	26	(2)
1.5 Data Structures	28	(5)
Implementation-Dependent Structures	29	(1)
Implementation-Independent Structures	30	(3)
What is a Data Structure?	33	(1)
1.6 Basic Structuring Mechanisms	33	(8)
References	33	(4)
Arrays	37	(4)
1.7 Comparing Algorithms: Big-O Analysis	41	(10)
Big-O Notation	44	(2)
Common Orders of Magnitude	46	(1)
Example 1: Sum of Consecutive Integers	47	(2)
Example 2: Finding a Number in a Phone Book	49	(2)
Summary	51	(1)
Exercises	52	(9)
2 Abstract Data Types	61	(94)
2.1 Abstraction	62	(8)
Information Hiding	62	(1)
Data Abstraction	63	(1)
Data Levels	64	(1)
Preconditions and Postconditions	65	(1)
Java interfaces	66	(4)
2.2 The StringLog ADT Specification	70	(5)
Constructors	70	(1)
Transformers	71	(1)
Observers	71	(1)
The StringLogInterface	71	(2)
Using the StringLoglnterface	73	(2)
2.3 Array-Based StringLog ADT Implementation	75	(14)
Instance Variables	75	(2)
Constructors	77	(1)
Transformers	78	(2)
Observers	80	(9)
2.4 Software Testing	89	(11)
Identifying Test Cases	90	(2)
Test Plans	92	(1)
Testing ADT Implementations	92	(8)
2.5 Introduction to Linked Lists	100	(44)
Array versus Linked Lists	100	(1)
The LLStringNode Class	101	(4)
Operations on Linked Lists	105	(6)
2.6 Linked List StringLog ADT Implementation	111	(11)
Instance Variables	113	(1)
Constructors	113	(1)
Transformers	114	(3)
Observers	117	(5)
2.7 Software Design: Identification of Classes	122	(4)
Brainstorm	122	(1)
Filter	123	(1)
Scenario Analysis	123	(1)
Nouns and Verbs	123	(1)
Cohesive Designs	124	(1)
Summation of Our Approach	124	(2)
Design Choices	126	(1)
2.8 Case Study: A Trivia Game	126	(18)
The Source of the Trivia Game	127	(2)
Identifying Support Classes	129	(2)
Implementing the Support Classes	131	(7)
The Trivia Game Application	138	(5)
Case Study Summation	143	(1)
Summary	144	(1)
Exercises	144	(11)
3 The Stack ADT	155	(80)
3.1 Stacks	156	(66)
Operations on Stacks	157	(1)
Using Stacks	157	(2)
3.2 Collection Elements	159	(4)
Generally Usable Collections	160	(3)
3.3 Exceptional Situations	163	(8)
Handling Exceptional Situations	163	(1)
Exceptions and ADTs: An Example	164	(5)
Error Situations and ADTs	169	(2)
3.4 Formal Specification	171	(8)
Exceptional Situations	172	(3)
The Interfaces	175	(4)
3.5 Application: Well-Formed Expressions	179	(9)
The Balanced Class	180	(5)
The Application	185	(3)
3.6 Array-Based Implementations	188	(7)
The ArrayStack Class	188	(2)
Definitions of Stack Operations	190	(2)
Test Plan	192	(3)
3.7 Link-Based Implementation	195	(12)
The LLObject Node Class	196	(1)
The LinkedStack Class	197	(1)
The push Operation	198	(4)
The pop Operation	202	(2)
The Other Stack Operations	204	(2)
Comparing Stack Implementations	206	(1)
3.8 Case Study: Postfix Expression Evaluator	207	(15)
Discussion	207	(1)
Evaluating Postfix Expressions	208	(2)
Postfix Expression Evaluation Algorithm	210	(2)
Specification: Program Postfix Evaluation	212	(2)
Brainstorming and Filtering	214	(1)
The PostFixEvaluator Class	215	(3)
The PFixConsole Class	218	(2)
Testing the Postfix Evaluator	220	(2)
Summary	222	(1)
Exercises	222	(13)
4 Recursion	235	(54)
4.1 Recursive Definitions, Algorithms, and Programs	236	(7)
Recursive Definitions	236	(1)
Recursive Algorithms	237	(3)
Recursive Programs	240	(3)
4.2 The Three Questions	243	(3)
Verifying Recursive Algorithms	243	(2)
Writing Recursive Methods	245	(1)
Debugging Recursive Methods	245	(1)
4.3 Towers of Hanoi	246	(158)
The Algorithm	246	(2)
The Method	248	(1)
The Program	249	(3)
4.4 Counting Blobs	252	(9)
Generating Blobs	253	(1)
The Counting Algorithm	254	(1)
The Marking Algorithm	255	(1)
The Grid Class	256	(3)
The Program	259	(2)
4.5 Recursive Linked-List Processing	261	(4)
Reverse Printing	261	(4)
4.6 Removing Recursion	265	(8)
How Recursion Works	266	(4)
Iteration	270	(1)
Stacking	271	(2)
4.7 Deciding Whether to Use a Recursive Solution	273	(4)
Recursion Overhead	274	(1)
Inefficient Algorithms	274	(3)
Clarity	277	(1)
Summary	277	(1)
Exercises	278	(11)
5 The Queue ADT	289	(68)
5.1 Queues	290	(2)
Operations on the Queues	291	(1)
Using Queues	291	(1)
5.2 Formal Specification	292	(4)
5.3 Application: Palindromes	296	(5)
The Palindrome Class	296	(3)
The Application	299	(2)
5.4 Array-Based Implementations	301	(10)
The ArrayBndQueue Class	301	(7)
The ArrayUnbndQueue Class	308	(3)
5.5 Application: The Card Game of War	311	(10)
The RankCardDeck Class	312	(1)
The WarGame Class	313	(5)
The WarGameApp Class	318	(3)
5.6 Link-Based Implementations	321	(9)
The Enqueue Operation	323	(1)
The Dequeue Operation	324	(2)
The Queue implementation	326	(1)
A Circular Linked Queue Design	327	(1)
Comparing Queue implementations	328	(2)
5.7 Case Study: Average Waiting Time	330	(17)
Problem Discussion	331	(2)
Program Design	333	(3)
Program Details	336	(10)
Testing Considerations	346	(1)
Summary	347	(2)
Exercises	349	(8)
6 The List ADT	357	(98)
6.1 Comparing Objects Revisited	358	(4)
The equals Method	358	(2)
The Comparable Interface	360	(2)
6.2 Lists	362	(2)
Varieties of Lists	363	(1)
Assumptions for Our Lists	364	(1)
6.3 Formal Specification	364	(9)
The Listinterface	364	(3)
The Specialized Interfaces	367	(3)
Example Use	370	(3)
6.4 Array-Based Implementations	373	(20)
The List Class	374	(5)
The ArrayUnsortedList Class	379	(3)
The ArraySortedList Class	382	(7)
The ArrayIndexedList Class	389	(4)
6.5 Applications: Poker, Golf, and Music	393	(11)
Poker	394	(3)
Golf	397	(3)
Music	400	(4)
6.6 The Binary Search Algorithm	404	(37)
Improving Linear Search in a Sorted List	405	(1)
Binary Search Algorithm	405	(5)
Recursive Binary Search	410	(3)
Efficiency Analysis	413	(1)
6.7 Reference-Based Implementations	414	(13)
The RefList Class	414	(7)
The RefUnsortedList Class	421	(1)
The RefSortedList Class	422	(5)
6.8 Storing Objects and Structures in Files	427	(14)
Saving Object Data in Text Files	428	(1)
Serialization of Objects	429	(4)
Serializing Structures	433	(1)
Application: Song Lists	433	(8)
Summary	441	(1)
Exercises	441	(14)
7 More Lists	455	(60)
7.1 Circular Linked Lists	456	(10)
An Unsorted Circular List	457	(2)
The CrefList Class	459	(5)
The CrefUnsorted List Class	464	(1)
Circular versus Linear Linked Lists	465	(1)
7.2 Doubly Linked Lists	466	(14)
The Add and Remove Operations	468	(2)
7.3 Linked Lists with Headers and Trailers	470	(1)
7.4 A Linked List as an Array of Nodes	471	(9)
Why Use an Array?	472	(1)
Flow Is an Array Used?	472	(8)
7.5 A Specialized List ADT	480	(26)
The Specification	481	(1)
The implementation	482	(5)
7.6 Case Study: Large Integers	487	(95)
The LargeInt Class	491	(2)
Addition and Subtraction	493	(8)
Test Plan	501	(1)
The LargeIntApp Program	502	(4)
Summary	506	(1)
Exercises	506	(9)
8 Binary Search Trees	515	(138)
8.1 Trees	516	(8)
Binary Trees	518	(2)
Binary Search Trees	520	(2)
Binary Tree Traversals	522	(2)
8.2 The Logical Level	524	(3)
Tree Elements	524	(1)
The Binary Search Tree Specification	525	(2)
8.3 The Application Level	527	(2)
8.4 The Implementation Level: Basics	529	(3)
8.5 Iterative versus Recursive Method Implementations	532	(7)
Recursive Approach to the size Method	533	(4)
Iterative Approach to the size Method	537	(2)
Recursion or iteration?	539	(1)
8.6 The Implementation Level: Remaining Operations	539	(22)
The contains and get Operations	539	(4)
The add Operation	543	(5)
The remove Operation	548	(7)
Iteration	555	(4)
Testing Binary Search Tree Operations	559	(2)
8.7 Comparing Binary Search. Tree and Linear Lists	561	(1)
Big-O Comparisons	561	(1)
8.8 Balancing a Binary Search Tree	562	(6)
8.9 A Nonlinked Representation of Binary Trees	568	(4)
8.10 Case Study: Word Frequency Generator	572	(10)
Problem	572	(1)
Discussion	572	(1)
Brainstorming	572	(1)
Filtering	573	(1)
The User interface	573	(1)
Error Handling	574	(1)
Scenario Analysis	574	(2)
The WordFreq Class	576	(2)
The Word Frequency Generator Program	578	(2)
Testing	580	(2)
Summary	582	(1)
Exercises	582	(15)
9 Priority, Queues, Heaps, and Graphs	597	(56)
9.1 Priority Queues	598	(3)
Logical Level	598	(2)
Application Level	600	(1)
Implementation Level	600	(1)
9.2 Heaps	601	(14)
Heap Implementation	605	(2)
The enqueue Method	607	(3)
The dequeue Method	610	(4)
Heaps versus Other Representations of Priority Queues	614	(1)
9.3 Introduction to Graphs	615	(5)
9.4 Formal Specification of a Graph ADT	620	(2)
9.5 Graph Applications	622	(13)
Depth-First Searching	622	(4)
Breadth-First Searching	626	(3)
The Single-Source Shortest-Paths Problem	629	(6)
9.6 Implementations of Graphs	635	(7)
Array-Based Implementation	635	(5)
Linked Implementation	640	(2)
Summary	642	(1)
Exercises	643	(10)
10 Sorting and Searching Algorithms	653	(76)
10.1 Sorting	654	(4)
A Test Harness	655	(3)
10.2 Simple Sorts	658	(14)
Straight Selection Sort	658	(6)
Bubble Sort	664	(4)
Insertion Sort	668	(4)
10.3 O(N log2N) Sorts	672	(20)
Merge Sort	672	(8)
Quick Sort	680	(6)
Heap Sort	686	(6)
10.4 More Sorting Considerations	692	(10)
Testing	692	(1)
Efficiency	692	(2)
Objects and References	694	(1)
Using the Comparable interface	694	(1)
Using the Comparator interface	695	(6)
Stability	701	(1)
10.5 Searching	702	(2)
Linear Searching	702	(1)
High Probability Ordering	703	(1)
Sorted Lists	704	(1)
10.6 Hashing	704	(15)
Collisions	707	(9)
Choosing a Good Hash Function	716	(3)
Complexity	719	(1)
Summary	719	(1)
Exercises	720	(9)
Appendix A Java Reserved Words	729	(1)
Appendix B Operator Precedence	730	(1)
Appendix C Primitive Data Types	731	(1)
Appendix D ASCII Subset of Unicode	732	(1)
Appendix E Application of Programmer Interfaces for the Java Classes and Interfaces Used in This Book	733	(16)
Appendix F A Generic Stack	749	(8)
F.1 The Bounded Stack 'Interface	750	(1)
F.2 The Bounded Stack Class	751	(3)
F.3 The SampleApp Class	754	(3)
Index	757