Data Abstraction and Problem Solving with Java: Walls and Mirrors
International Edition
1st Edition
Published on 18. September 2014
960 pages
978-1-292-01413-5 (ISBN)
Description
The Third Edition of Data Abstraction and Problem Solving with Java: Walls and Mirrors employs the analogies of Walls (data abstraction) and Mirrors (recursion) to teach Java programming design solutions, in a way that beginning students find accessible. The book has a student-friendly pedagogical approach that carefully accounts for the strengths and weaknesses of the Java language. With this book, students will gain a solid foundation in data abstraction, object-oriented programming, and other problem-solving techniques.
More details
Other editions
Additional editions
Janet Prichard | Frank M. Carrano
Data Abstraction and Problem Solving with Java: Walls and Mirrors
International Edition
Book
02/2011
3rd Edition
Pearson Education Limited
€92.98
Shipment within 10-20 days
Content
- Cover
- Contents
- Preface
- Chapter Dependency Chart
- PART ONE: Problem-Solving Techniques
- 1 Review of Java Fundamentals
- 1.1 Language Basics
- Comments
- Identifiers and Keywords
- Variables
- Primitive Data Types
- References
- Literal Constants
- Named Constants
- Assignments and Expressions
- Arrays
- 1.2 Selection Statements
- The if Statement
- The switch Statement
- 1.3 Iteration Statements
- The while Statement
- The for Statement
- The do Statement
- 1.4 Program Structure
- Packages
- Classes
- Data Fields
- Methods
- How to Access Members of an Object
- Class Inheritance
- 1.5 Useful Java Classes
- The Object Class
- The Array Class
- String Classes
- 1.6 Java Exceptions
- Catching Exceptions
- Throwing Exceptions
- 1.7 Text Input and Output
- Input
- Output
- The Console Class
- 1.8 File Input and Output
- Text Files
- Object Serialization
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 2 Principles of Programming and Software Engineering
- 2.1 Problem Solving and Software Engineering
- What Is Problem Solving?
- The Life Cycle of Software
- What Is a Good Solution?
- 2.2 Achieving an Object-Oriented Design
- Abstraction and Information Hiding
- Object-Oriented Design
- Functional Decomposition
- General Design Guidelines
- Modeling Object-Oriented Designs Using UML
- Advantages of an Object-Oriented Approach
- 2.3 A Summary of Key Issues in Programming
- Modularity
- Modifiability
- Ease of Use
- Fail-Safe Programming
- Style
- Debugging
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 3 Recursion: The Mirrors
- 3.1 Recursive Solutions
- A Recursive Valued Method: The Factorial of n
- A Recursive void Method: Writing a String Backward
- 3.2 Counting Things
- Multiplying Rabbits (The Fibonacci Sequence)
- Organizing a Parade
- Mr. Spock's Dilemma (Choosing k out of n Things)
- 3.3 Searching an Array
- Finding the Largest Item in an Array
- Binary Search
- Finding the kth Smallest Item in an Array
- 3.4 Organizing Data
- The Towers of Hanoi
- 3.5 Recursion and Efficiency
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 4 Data Abstraction: The Walls
- 4.1 Abstract Data Types
- 4.2 Specifying ADTs
- The ADT List
- The ADT Sorted List
- Designing an ADT
- Axioms (Optional)
- 4.3 Implementing ADTs
- Java Classes Revisited
- Java Interfaces
- Java Packages
- An Array-Based Implementation of the ADT List
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 5 Linked Lists
- 5.1 Preliminaries
- Object References
- Resizeable Arrays
- Reference-Based Linked Lists
- 5.2 Programming with Linked Lists
- Displaying the Contents of a Linked List
- Deleting a Specified Node from a Linked List
- Inserting a Node into a Specified Position of a Linked List
- A Reference-Based Implementation of the ADT List
- Comparing Array-Based and Reference-Based Implementations
- Passing a Linked List to a Method
- Processing Linked Lists Recursively
- 5.3 Variations of the Linked List
- Tail References
- Circular Linked Lists
- Dummy Head Nodes
- Doubly Linked Lists
- 5.4 Application: Maintaining an Inventory
- 5.5 The Java Collections Framework
- Generics
- Iterators
- The Java Collection's Framework List Interface
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- PART TWO: Problem Solving with Abstract Data Types
- 6 Recursion as a Problem-Solving Technique
- 6.1 Backtracking
- The Eight Queens Problem
- 6.2 Defining Languages
- The Basics of Grammars
- Two Simple Languages
- Algebraic Expressions
- 6.3 The Relationship Between Recursion and Mathematical Induction
- The Correctness of the Recursive Factorial Method
- The Cost of Towers of Hanoi
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 7 Stacks
- 7.1 The Abstract Data Type Stack
- Developing an ADT During the Design of a Solution
- 7.2 Simple Applications of the ADT Stack
- Checking for Balanced Braces
- Recognizing Strings in a Language
- 7.3 Implementations of the ADT Stack
- An Array-Based Implementation of the ADT Stack
- A Reference-Based Implementation of the ADT Stack
- An Implementation That Uses the ADT List
- Comparing Implementations
- The Java Collections Framework Class Stack
- 7.4 Application: Algebraic Expressions
- Evaluating Postfix Expressions
- Converting Infix Expressions to Equivalent Postfix Expressions
- 7.5 Application: A Search Problem
- A Nonrecursive Solution That Uses a Stack
- A Recursive Solution
- 7.6 The Relationship Between Stacks and Recursion
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 8 Queues
- 8.1 The Abstract Data Type Queue
- 8.2 Simple Applications of the ADT Queue
- Reading a String of Characters
- Recognizing Palindromes
- 8.3 Implementations of the ADT Queue
- A Reference-Based Implementation
- An Array-Based Implementation
- An Implementation That Uses the ADT List
- The JCF Interfaces Queue and Deque
- Comparing Implementations
- 8.4 A Summary of Position-Oriented ADTs
- 8.5 Application: Simulation
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 9 Advanced Java Topics
- 9.1 Inheritance Revisited
- Java Access Modifiers
- Is-a and Has-a Relationships
- 9.2 Dynamic Binding and Abstract Classes
- Abstract Classes
- Java Interfaces Revisited
- 9.3 Java Generics
- Generic Classes
- Generic Wildcards
- Generic Classes and Inheritance
- Generic Implementation of the Class List
- Generic Methods
- 9.4 The ADTs List and Sorted List Revisited
- Implementations of the ADT Sorted List That Use the ADT List
- 9.5 Iterators
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 10 Algorithm Efficiency and Sorting
- 10.1 Measuring the Efficiency of Algorithms
- The Execution Time of Algorithms
- Algorithm Growth Rates
- Order-of-Magnitude Analysis and Big O Notation
- Keeping Your Perspective
- The Efficiency of Searching Algorithms
- 10.2 Sorting Algorithms and Their Efficiency
- Selection Sort
- Bubble Sort
- Insertion Sort
- Mergesort
- Quicksort
- Radix Sort
- A Comparison of Sorting Algorithms
- The Java Collections Framework Sort Algorithm
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 11 Trees
- 11.1 Terminology
- 11.2 The ADT Binary Tree
- Basic Operations of the ADT Binary Tree
- General Operations of the ADT Binary Tree
- Traversals of a Binary Tree
- Possible Representations of a Binary Tree
- A Reference-Based Implementation of the ADT Binary Tree
- Tree Traversals Using an Iterator
- 11.3 The ADT Binary Search Tree
- Algorithms for the Operations of the ADT Binary Search Tree
- A Reference-Based Implementation of the ADT Binary Search Tree
- The Efficiency of Binary Search Tree Operations
- Treesort
- Saving a Binary Search Tree in a File
- The JCF Binary Search Algorithm
- 11.4 General Trees
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 12 Tables and Priority Queues
- 12.1 The ADT Table
- Selecting an Implementation
- A Sorted Array-Based Implementation of the ADT Table
- A Binary Search Tree Implementation of the ADT Table
- 12.2 The ADT Priority Queue: A Variation of the ADT Table
- Heaps
- A Heap Implementation of the ADT Priority Queue
- Heapsort
- 12.3 Tables and Priority Queues in the JCF
- The JCF Map Interface
- The JCF Set Interface
- The JCF PriorityQueue Class
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 13 Advanced Implementations of Tables
- 13.1 Balanced Search Trees
- 2-3 Trees
- 2-3-4 Trees
- Red-Black Trees
- AVL Trees
- 13.2 Hashing
- Hash Functions
- Resolving Collisions
- The Efficiency of Hashing
- What Constitutes a Good Hash Function?
- Table Traversal: An Inefficient Operation under Hashing
- The JCF Hashtable and TreeMap Classes
- The Hashtable Class
- The TreeMap Class
- 13.3 Data with Multiple Organizations
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 14 Graphs
- 14.1 Terminology
- 14.2 Graphs as ADTs
- Implementing Graphs
- Implementing a Graph Class Using the JCF
- 14.3 Graph Traversals
- Depth-First Search
- Breadth-First Search
- Implementing a BFS Iterator Class Using the JCF
- 14.4 Applications of Graphs
- Topological Sorting
- Spanning Trees
- Minimum Spanning Trees
- Shortest Paths
- Circuits
- Some Difficult Problems
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- 15 External Methods
- 15.1 A Look at External Storage
- 15.2 Sorting Data in an External File
- 15.3 External Tables
- Indexing an External File
- External Hashing
- B-Trees
- Traversals
- Multiple Indexing
- Summary
- Cautions
- Self-Test Exercises
- Exercises
- Programming Problems
- A: A Comparison of Java to C++
- B: Unicode Character Codes (ASCII Subset)
- C: Java Resources
- Java Web Sites
- Using Java SE 6
- Integrated Development Environments (IDEs)
- D: Mathematical Induction
- Example 1
- Example 2
- Example 3
- Example 4
- Example 5
- Self-Test Exercises
- Exercises
- Glossary
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- Self-Test Answers
- Index
- Symbols
- Numbers
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- Z
