Absolutely Australia's Lowest Prices

We won't be beaten by anyone. Guaranteed

New or Used: $227.00
Data Structures and Other Objects Using Java is a gradual, "just-in-time" introduction to Data Structures for a CS2 course. Each chapter provides a review of the key aspects of object-oriented programming and a syntax review, giving students the foundation for understanding significant programming concepts. With this framework they are able to accomplish writing functional data structures by using a five-step method for working with data types; understanding the data type abstractly, writing a specification, using the data type, designing and implementing the data type, and analyzing the implementation. Students learn to think analytically about the efficiency and efficacy of design while gaining exposure to useful Java classes libraries.
Product Details

Table of Contents

CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT 11.1 Specification, Design, Implementation 4Design Technique: Decomposing the Problem 5How to Write a Specification for a Java Method 6Pitfall: Throw an Exception to Indicate a Failed Precondition 9Temperature Conversion: Implementation 10Programming Tip: Use Javadoc to Write Specifications 13Programming Tip: Use Final Variables to Improve Clarity 13Programming Tip: Make Exception Messages Informative 14Programming Tip: Format Output with System.out.printf 14Self-Test Exercises for Section 1.1 151.2 Running Time Analysis 16The Stair-Counting Problem 16Big-O Notation 21Time Analysis of Java Methods 23Worst-Case, Average-Case, and Best-Case Analyses 25Self-Test Exercises for Section 1.2 261.3 Testing and Debugging 26Choosing Test Data 27Boundary Values 27Fully Exercising Code 28Pitfall: Avoid Impulsive Changes 29Using a Debugger 29Assert Statements 29Turning Assert Statements On and Off 30Programming Tip: Use a Separate Method for Complex Assertions 32Pitfall: Avoid Using Assertions to Check Preconditions 34Static Checking Tools 34Self-Test Exercises for Section 1.3 34Chapter Summary 35Solutions to Self-Test Exercises 36CHAPTER 2 JAVA CLASSES AND INFORMATION HIDING 382.1 Classes and Their Members 40Defining a New Class 41Instance Variables 41Constructors 42No-Arguments Constructors 43Methods 43Accessor Methods 44Programming Tip: Four Reasons to Implement Accessor Methods 44Pitfall: Division Throws Away the Fractional Part 45Programming Tip: Use the Boolean Type for True or False Values 46Modification Methods 46Pitfall: Potential Arithmetic Overflows 48Complete Definition of Throttle.java 48Methods May Activate Other Methods 51Self-Test Exercises for Section 2.1 512.2 Using a Class 52Creating and Using Objects 52A Program with Several Throttle Objects 53Null References 54NullPointerException 55Assignment Statements with Reference Variables 55Clones 58Testing for Equality 58Terminology Controversy: "The Throttle That t Refers To" 59Self-Test Exercises for Section 2.2 592.3 Packages 60Declaring a Package 60The Import Statement to Use a Package 63The JCL Packages 63More about Public, Private, and Package Access 63Self-Test Exercises for Section 2.3 652.4 Parameters, Equals Methods, and Clones 65The Location Class 66Static Methods 72Parameters That Are Objects 73Methods May Access Private Instance Variables of Objects in Their Own Class 74The Return Value of a Method May Be an Object 75Programming Tip: How to Choose the Names of Methods 76Java's Object Type 77Using and Implementing an Equals Method 77Pitfall: ClassCastException 80Every Class Has an Equals Method 80Using and Implementing a Clone Method 81Pitfall: Older Java Code Requires a Typecast for Clones 81Programming Tip: Always Use super.clone for Your Clone Method 85Programming Tip: When to Throw a Runtime Exception 85A Demonstration Program for the Location Class 85What Happens When a Parameter Is Changed Within a Method? 86Self-Test Exercises for Section 2.4 892.5 The Java Class Libraries 90Chapter Summary 92Solutions to Self-Test Exercises 93Programming Projects 95CHAPTER 3 COLLECTION CLASSES 1033.1 A Review of Java Arrays 104Pitfall: Exceptions That Arise from Arrays 106The Length of an Array 106Assignment Statements with Arrays 106Clones of Arrays 107The Arrays Utility Class 108Array Parameters 110Programming Tip: Enhanced For-Loops for Arrays 111Self-Test Exercises for Section 3.1 1123.2 An ADT for a Bag of Integers 113The Bag ADT-Specification 114OutOfMemoryError and Other Limitations for Collection Classes 118The IntArrayBag Class-Specification 118The IntArrayBag Class-Demonstration Program 122The IntArrayBag Class-Design 125The Invariant of an ADT 126The IntArrayBag ADT-Implementation 127Programming Tip: Cloning a Class That Contains an Array 136The Bag ADT-Putting the Pieces Together 137Programming Tip: Document the ADT Invariant in the Implementation File 141The Bag ADT-Testing 141Pitfall: An Object Can Be an Argument to Its Own Method 142The Bag ADT-Analysis 142Self-Test Exercises for Section 3.2 1443.3 Programming Project: The Sequence ADT 145The Sequence ADT-Specification 146The Sequence ADT-Documentation 150The Sequence ADT-Design 150The Sequence ADT-Pseudocode for the Implementation 156Self-Test Exercises for Section 3.3 1583.4 Programming Project: The Polynomial 159Self-Test Exercises for Section 3.4 1623.5 The Java HashSet and Iterators 162The HashSet Class 162Some of the HashSet Members 162Iterators 163Pitfall: Do Not Access an Iterator's next Item When hasNext Is False 164Pitfall: Changing a Container Object Can Invalidate Its Iterator 164Invalid Iterators 164Self-Test Exercises for Section 3.5 165Chapter Summary 165Solutions to Self-Test Exercises 166Programming Projects 169CHAPTER 4 LINKED LISTS 1754.1 Fundamentals of Linked Lists 176Declaring a Class for Nodes 177Head Nodes, Tail Nodes 177The Null Reference 178Pitfall: NullPointerExceptions with Linked Lists 179Self-Test Exercises for Section 4.1 1794.2 Methods for Manipulating Nodes 179Constructor for the Node Class 180Getting and Setting the Data and Link of a Node 180Public Versus Private Instance Variables 181Adding a New Node at the Head of a Linked List 182Removing a Node from the Head of a Linked List 183Adding a New Node That Is Not at the Head 185Removing a Node That Is Not at the Head 188Pitfall: NullPointerExceptions with removeNodeAfter 191Self-Test Exercises for Section 4.2 1914.3 Manipulating an Entire Linked List 192Computing the Length of a Linked List 193Programming Tip: How to Traverse a Linked List 196Pitfall: Forgetting to Test the Empty List 197Searching for an Element in a Linked List 197Finding a Node by Its Position in a Linked List 198Copying a Linked List 200A Second Copy Method, Returning Both Head and Tail References 204Programming Tip: A Method Can Return an Array 205Copying Part of a Linked List 206Using Linked Lists 207Self-Test Exercises for Section 4.3 2144.4 The Bag ADT with a Linked List 215Our Second Bag-Specification 215The grab Method 219Our Second Bag-Class Declaration 219The Second Bag-Implementation 220Programming Tip: Cloning a Class That Contains a Linked List 223Programming Tip: How to Choose between Different Approaches 225The Second Bag-Putting the Pieces Together 229Self-Test Exercises for Section 4.4 2324.5 Programming Project: The Sequence ADT with a Linked List 232The Revised Sequence ADT-Design Suggestions 232The Revised Sequence ADT-Clone Method 235Self-Test Exercises for Section 4.5 2384.6 Beyond Simple Linked Lists 239Arrays Versus Linked Lists and Doubly Linked Lists 239Dummy Nodes 240Java's List Classes 241ListIterators 242Making the Decision 243Self-Test Exercises for Section 4.6 244Chapter Summary 244Solutions to Self-Test Exercises 245Programming Projects 248CHAPTER 5 GENERIC PROGRAMMING 2515.1 Java's Object Type and Wrapper Classes 252Widening Conversions 253Narrowing Conversions 254Wrapper Classes 256Autoboxing and Auto-Unboxing Conversions 256Advantages and Disadvantages of Wrapper Objects 257Self-Test Exercises for Section 5.1 2575.2 Object Methods and Generic Methods 258Object Methods 259Generic Methods 259Pitfall: Generic Method Restrictions 260Self-Test Exercises for Section 5.2 2615.3 Generic Classes 262Writing a Generic Class 262Using a Generic Class 262Pitfall: Generic Class Restrictions 263Details for Implementing a Generic Class 263Creating an Array to Hold Elements of the Unknown Type 263Retrieving E Objects from the Array 264Warnings in Generic Code 264Programming Tip: Suppressing Unchecked Warnings 265Using ArrayBag as the Type of a Parameter or Return Value 266Counting the Occurrences of an Object 266The Collection Is Really a Collection of References to Objects 267Set Unused References to Null 269Steps for Converting a Collection Class to a Generic Class 269Deep Clones for Collection Classes 271Using the Bag of Objects 279Details of the Story-Writing Program 282Self-Test Exercises for Section 5.3 2825.4 Generic Nodes 283Nodes That Contain Object Data 283Pitfall: Misuse of the equals Method 283Other Collections That Use Linked Lists 285Self-Test Exercises for Section 5.4 2855.5 Interfaces and Iterators 286Interfaces 286How to Write a Class That Implements an Interface 287Generic Interfaces and the Iterable Interface 287How to Write a Generic Class That Implements a Generic Interface 288The Lister Class 289Pitfall: Don't Change a List While an Iterator Is Being Used 291The Comparable Generic Interface 292Parameters That Use Interfaces 293Using instanceof to Test Whether a Class Implements an Interface 294The Cloneable Interface 295Self-Test Exercises for Section 5.5 2955.6 A Generic Bag Class That Implements the Iterable Interface (Optional Section) 296Programming Tip: Enhanced For-Loops for the Iterable Interface 297Implementing a Bag of Objects Using a Linked List and an Iterator 298Programming Tip: External Iterators Versus Internal Iterators 298Summary of the Four Bag Implementations 299Self-Test Exercises for Section 5.6 2995.7 The Java Collection Interface and Map Interface (Optional Section) 300The Collection Interface 300The Map Interface and the TreeMap Class 300The TreeMap Class 302The Word Counting Program 305Self-Test Exercises for Section 5.7 306Chapter Summary 309Solutions to Self-Test Exercises 310Programming Projects 312CHAPTER 6 STACKS 3156.1 Introduction to Stacks 316The Stack Class-Specification 317We Will Implement a Generic Stack 319Programming Example: Reversing a Word 319Self-Test Exercises for Section 6.1 3206.2 Stack Applications 320Programming Example: Balanced Parentheses 320Programming Tip: The Switch Statement 324Evaluating Arithmetic Expressions 325Evaluating Arithmetic Expressions-Specification 325Evaluating Arithmetic Expressions-Design 325Implementation of the Evaluate Method 329Evaluating Arithmetic Expressions-Testing and Analysis 333Evaluating Arithmetic Expressions-Enhancements 334Self-Test Exercises for Section 6.2 3346.3 Implementations of the Stack ADT 335Array Implementation of a Stack 335Linked List Implementation of a Stack 341Self-Test Exercises for Section 6.3 3446.4 More Complex Stack Applications 345Evaluating Postfix Expressions 345Translating Infix to Postfix Notation 348Using Precedence Rules in the Infix Expression 350Correctness of the Conversion from Infix to Postfix 353Self-Test Exercises for Section 6.4 354Chapter Summary 354Solutions to Self-Test Exercises 355Programming Projects 356CHAPTER 7 QUEUES 3607.1 Introduction to Queues 361The Queue Class 362Uses for Queues 364Self-Test Exercises for Section 7.1 3657.2 Queue Applications 365Java Queues 365Programming Example: Palindromes 366Programming Example: Car Wash Simulation 369Car Wash Simulation-Specification 369Car Wash Simulation-Design 369Car Wash Simulation-Implementing the Car Wash Classes 374Car Wash Simulation-Implementing the Simulation Method 375Self-Test Exercises for Section 7.2 3757.3 Implementations of the Queue Class 383Array Implementation of a Queue 383Programming Tip: Use Helper Methods to Improve Clarity 386Linked List Implementation of a Queue 393Pitfall: Forgetting Which End Is Which 398Self-Test Exercises for Section 7.3 3987.4 Deques and Priority Queues (Optional Section) 399Double-Ended Queues 399Priority Queues 400Priority Queue ADT-Specification 400Priority Queue Class-An Implementation That Uses an Ordinary Queue 402Priority Queue ADT-A Direct Implementation 403Java's Priority Queue 403Self-Test Exercises for Section 7.4 404Chapter Summary 404Solutions to Self-Test Exercises 404Programming Projects 406CHAPTER 8 RECURSIVE THINKING 4098.1 Recursive Methods 410Tracing Recursive Calls 413Programming Example: An Extension of writeVertical 413A Closer Look at Recursion 415General Form of a Successful Recursive Method 418Self-Test Exercises for Section 8.1 4198.2 Studies of Recursion: Fractals and Mazes 420Programming Example: Generating Random Fractals 420A Method for Generating Random Fractals-Specification 421The Stopping Case for Generating a Random Fractal 426Putting the Random Fractal Method in an Applet 426Programming Example: Traversing a Maze 429Traversing a Maze-Specification 429Traversing a Maze-Design 432Traversing a Maze-Implementation 433The Recursive Pattern of Exhaustive Search with Backtracking 435Programming Example: The Teddy Bear Game 437Self-Test Exercises for Section 8.2 4378.3 Reasoning about Recursion 439How to Ensure That There Is No Infinite Recursion in the General Case 442Inductive Reasoning about the Correctness of a Recursive Method 444Self-Test Exercises for Section 8.3 445Chapter Summary 446Solutions to Self-Test Exercises 446Programming Projects 448CHAPTER 9 TREES 4539.1 Introduction to Trees 454Binary Trees 454Binary Taxonomy Trees 457More Than Two Children 458Self-Test Exercises for Section 9.1 4599.2 Tree Representations 459Array Representation of Complete Binary Trees 459Representing a Binary Tree with a Generic Class for Nodes 462Self-Test Exercises for Section 9.2 4649.3 A Class for Binary Tree Nodes 464Programming Example: Animal Guessing 473Animal-Guessing Program-Design and Implementation 475Animal-Guessing Program-Improvements 481Self-Test Exercises for Section 9.3 4819.4 Tree Traversals 484Traversals of Binary Trees 484Printing a Tree with an Indentation to Show the Depths 488BTNode, IntBTNode, and Other Classes 497Self-Test Exercises for Section 9.4 4979.5 Binary Search Trees 498The Binary Search Tree Storage Rules 498The Binary Search Tree Bag-Implementation of Some Simple Methods 503Counting the Occurrences of an Element in a Binary Search Tree 504Adding a New Element to a Binary Search Tree 505Removing an Element from a Binary Search Tree 506The addAll, addMany, and union Methods 510Pitfall: Violating the addTree Precondition 511Implementing addAll 512Time Analysis and an Internal Iterator 513Self-Test Exercises for Section 9.5 513Chapter Summary 514Solutions to Self-Test Exercises 514Programming Projects 517CHAPTER 10 TREE PROJECTS 52010.1 Heaps 521The Heap Storage Rules 521The Priority Queue Class with Heaps 522Adding an Element to a Heap 523Removing an Element from a Heap 524Self-Test Exercises for Section 10.1 52710.2 B-Trees 527The Problem of Unbalanced Trees 527The B-Tree Rules 528An Example B-Tree 529The Set Class with B-Trees 530Searching for an Element in a B-Tree 535Programming Tip: Private Methods to Simplify Implementations 537Adding an Element to a B-Tree 537The Loose Addition Operation for a B-Tree 538A Private Method to Fix an Excess in a Child 540Back to the add Method 541Employing Top-Down Design 543Removing an Element from a B-Tree 543The Loose Removal from a B-Tree 544A Private Method to Fix a Shortage in a Child 546Removing the Biggest Element from a B-Tree 549Programming Tip: Write and Test Small Pieces 549External B-Trees 550Self-Test Exercises for Section 10.2 55110.3 Java Support for Trees 552The DefaultMutableTreeNode from javax.swing.tree 552Using the JTree Class to Display a Tree in an Applet 552The JApplet Class 552Programming Tip: Adding a Component to a JApplet 553What the TreeExample Applet Displays 553Self-Test Exercises for Section 10.3 55310.4 Trees, Logs, and Time Analysis 558Time Analysis for Binary Search Trees 559Time Analysis for Heaps 559Logarithms 562Logarithmic Algorithms 563Self-Test Exercises for Section 10.4 563Chapter Summary 563Solutions to Self-Test Exercises 564Programming Projects 566CHAPTER 11 SEARCHING 56711.1 Serial Search and Binary Search 568Serial Search 568Serial Search-Analysis 568Binary Search 571Binary Search-Design 572Pitfall: Common Indexing Errors in Binary Search Implementations 574Binary Search-Analysis 574Java's Binary Search Methods 579Self-Test Exercises for Section 11.1 58111.2 Open-Address Hashing 581Introduction to Hashing 581Noninteger Keys and Java's hashCode Method 583Pitfall: Classes Often Need a New hashCode Method 584The Table ADT-Specification 584The Table ADT-Design 587The Table ADT-Implementation 589A Practical Illustration of Open-Address Hashing 594Choosing a Hash Function to Reduce Collisions 596Double Hashing to Reduce Clustering 596Self-Test Exercises for Section 11.2 59811.3 Using Java's Hashtable Class 59911.4 Chained Hashing 600Self-Test Exercises for Section 11.4 60111.5 Programming Project: A Table Class Implemented with Java's Vector and LinkedList 603A New Table Class 603Data Structures for the New Table Class 603Implementing the New Table Class 604Self-Test Exercises for Section 11.6 60511.6 Time Analysis of Hashing 605The Load Factor of a Hash Table 607Self-Test Exercises for Section 11.5 609Chapter Summary 609Solutions to Self-Test Exercises 610Programming Projects 612CHAPTER 12 SORTING 61412.1 Quadratic Sorting Algorithms 615Selectionsort-Specification 615Selectionsort-Design 616Selectionsort-Testing 619Selectionsort-Analysis 620Programming Tip: Rough Estimates Suffice for Big-O 622Insertionsort 622Insertionsort-Analysis 626Self-Test Exercises for Section 12.1 62912.2 Recursive Sorting Algorithms 629Divide-and-Conquer Using Recursion 629Mergesort 630The merge Function 631Mergesort-Analysis 638Mergesort for Files 640Quicksort 640The Partition Method 643Quicksort-Analysis 646Quicksort-Choosing a Good Pivot Element 648Self-Test Exercises for Section 12.2 64812.3 An O(n log n) Algorithm Using a Heap 649Heapsort 649Making the Heap 656Reheapification Downward 657Heapsort-Analysis 658Self-Test Exercise for Section 12.3 65912.4 Java's Sort Methods 660Self-Test Exercises for Section 12.4 66012.5 Concurrent Recursive Sorting 660Mergesort with a Threshold 661Pitfall: The RecursiveAction Class Did Not Appear Until Java 7 662Java's RecursiveAction Class 662The Sorter's Constructor 663The Sorter's compute Method 664Programming Tip: Using InvokeAll 664Using a ForkJoinPool to Get Concurrent Recursion Started 665Beyond the Simple Sorter Class 668Self-Test Exercises for Section 12.5 668Chapter Summary 669Solutions to Self-Test Exercises 669Programming Projects 671CHAPTER 13 SOFTWARE REUSE WITH EXTENDED CLASSES 67513.1 Extended Classes 676How to Declare an Extended Class 678The Constructors of an Extended Class 679Using an Extended Class 680Descendants and Ancestors 681Overriding Inherited Methods 682Covariant Return Values 684Widening Conversions for Extended Classes 684Narrowing Conversions for Extended Classes 685Self-Test Exercises for Section 13.1 68613.2 Generic Type Parameters and Inheritance 686Self-Test Exercise for Section 13.2 68813.3 Simulation of an Ecosystem 688Programming Tip: When to Use an Extended Class 689Implementing Part of the Organism Object Hierarchy 689The Organism Class 689The Animal Class: An Extended Class with New Private Instance Variables 693How to Provide a New Constructor for an Extended Class 693The Other Animal Methods 695Self-Test Exercises for the Middle of Section 13.3 696The Herbivore Class 700The Pond Life Simulation Program 703Pond Life-Implementation Details 708Using the Pond Model 708Self-Test Exercises for the End of Section 13.3 70913.4 Abstract Classes and a Game Class 710Introduction to the AbstractGame Class 710Protected Methods 716Final Methods 716Abstract Methods 717An Extended Class to Play Connect Four 718The Private Member Variables of the Connect Four Class 718Three Connect Four Methods That Deal with the Game's Status 720Three Connect Four Methods That Deal with Moves 721The clone Method 722Writing Your Own Derived Games from the AbstractGame Class 723Self-Test Exercises for Section 13.4 724Chapter Summary 724Further Reading 724Solutions to Self-Test Exercises 725Programming Projects 727CHAPTER 14 GRAPHS 72814.1 Graph Definitions 729Undirected Graphs 729Programming Example: Undirected State Graphs 730Directed Graphs 733More Graph Terminology 734Airline Routes Example 735Self-Test Exercises for Section 14.1 73614.2 Graph Implementations 736Representing Graphs with an Adjacency Matrix 736Using a Two-Dimensional Array to Store an Adjacency Matrix 737Representing Graphs with Edge Lists 738Representing Graphs with Edge Sets 739Which Representation Is Best? 739Programming Example: Labeled Graph ADT 740The Graph Constructor and size Method 741Methods for Manipulating Edges 742Methods for Manipulating Vertex Labels 743Labeled Graph ADT-Implementation 743Self-Test Exercises for Section 14.2 74914.3 Graph Traversals 749Depth-First Search 750Breadth-First Search 754Depth-First Search-Implementation 756Breadth-First Search-Implementation 758Self-Test Exercises for Section 14.3 75914.4 Path Algorithms 759Determining Whether a Path Exists 759Graphs with Weighted Edges 759Shortest-Distance Algorithm 760Shortest-Path Algorithm 770Self-Test Exercises for Section 14.4 771Chapter Summary 771Solutions to Self-Test Exercises 772Programming Projects 773APPENDIXESA. JAVA'S PRIMITIVE TYPES AND ARITHMETIC OVERFLOW 775B. JAVA INPUT AND OUTPUT 778C. THROWING AND CATCHING JAVA EXCEPTIONS 782D. ARRAYLIST, VECTOR, HASHTABLE, AND HASHMAP CLASSES 787E. A CLASS FOR NODES IN A LINKED LIST 791F. A CLASS FOR A BAG OF OBJECTS 799G. FURTHER BIG-O NOTATION 805H. JAVADOC 807I. APPLETS FOR INTERACTIVE TESTING 814INDEX 815

About the Author

Michael Main is an Associate Professor in the Department of Computer Science at the University of Colorado - Boulder. He earned his BS, MS, and Ph.D. from Washington State University.

Look for similar items by category
How Fishpond Works
Fishpond works with suppliers all over the world to bring you a huge selection of products, really great prices, and delivery included on over 25 million products that we sell. We do our best every day to make Fishpond an awesome place for customers to shop and get what they want — all at the best prices online.
Webmasters, Bloggers & Website Owners
You can earn a 5% commission by selling Data Structures and Other Objects Using Java on your website. It's easy to get started - we will give you example code. After you're set-up, your website can earn you money while you work, play or even sleep! You should start right now!
Authors / Publishers
Are you the Author or Publisher of a book? Or the manufacturer of one of the millions of products that we sell. You can improve sales and grow your revenue by submitting additional information on this title. The better the information we have about a product, the more we will sell!
Item ships from and is sold by Fishpond.com, Inc.
Back to top