책 이미지
책 정보
· 분류 : 외국도서 > 컴퓨터 > 프로그래밍 언어 > Java
· ISBN : 9781119703617
· 쪽수 : 688쪽
목차
Preface
Chapter 1 Object-Oriented Programming and Class Hierarchies
1.1 Abstract Data Types(ADTs), Interfaces, and the Java API
Interfaces
The implements Clause
Declaring a Variable of an Interface Type
Exercises for Section 1.1
1.2 Introduction to OOP
A Superclass and Subclass Example
Use of this
Initializing Data Fields in a Subclass
The No‐Parameter Constructor
Protected Visibility for Superclass Data Fields
Is‐a versus Has‐a Relationships
Exercises for Section 1.2
1.3 Method Overriding, Method Overloading, and Polymorphism
Method Overriding
Method Overloading
Polymorphism
Methods with Class Parameters
Exercises for Section 1.3
1.4 Abstract Classes
Referencing Actual Objects
Initializing Data Fields in an Abstract Class
Abstract Class Number and the Java Wrapper Classes
Summary of Features of Actual Classes, Abstract Classes,
and Interfaces
Implementing Multiple Interfaces
Extending an Interface
Exercises for Section 1.4
1.5 Class Object and Casting
The Method toString
Operations Determined by Type of Reference Variable
Casting in a Class Hierarchy
Using instanceof to Guard a Casting Operation
The Class Class
Exercises for Section 1.5
1.6 A Java Inheritance Example—The Exception Class Hierarchy
Division by Zero
Array Index Out of Bounds
Null Pointer
The Exception Class Hierarchy
The Class Throwable
Checked and Unchecked Exceptions
Handling Exceptions to Recover from Errors
Using try-catch to Recover from an Error
Throwing an Exception When Recovery Is Not Obvious
Exercises for Section 1.6
1.7 Packages and Visibility
Packages
The No‐Package‐Declared Environment
Package Visibility
Visibility Supports Encapsulation
Exercises for Section 1.7
1.8 A Shape Class Hierarchy
Case Study: Processing Geometric Figures
Exercises for Section 1.8
Java Constructs Introduced in This Chapter
Java API Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 2 Lists and the Collections Framework
2.1 Algorithm Efficiency and Big-O
Big-O Notation
Formal Definition of Big-O
Summary of Notation
Comparing Performance
The Power of O(log n) Algorithms
Algorithms with Exponential and Factorial Growth Rates
Exercises for Section 2.1
2.2 The List Interface and ArrayList Class
The ArrayList Class
Generic Collections
Exercises for Section 2.2
2.3 Applications of ArrayList
A Phone Directory Application
Exercises for Section 2.3
2.4 Implementation of an ArrayList Class
The Constructor for Class KWArrayList<E>
The add(E anEntry) Method
The add(int index, E anEntry) Method
The set and get Methods
The remove Method
The reallocate Method
Performance of the KWArrayList Algorithms
Exercises for Section 2.4
2.5 Single‐Linked Lists
A List Node
Connecting Nodes
A Single-Linked List Class
Inserting a Node in a List
Removing a Node
Completing the KWSingleLinkedList Class
The get and set Methods
The add Methods
Exercises for Section 2.5
2.6 Double‐Linked Lists and Circular Lists
The Node Class
Inserting into a Double‐Linked List
Removing from a Double‐Linked List
A Double‐Linked List Class
Circular Lists
Exercises for Section 2.6
2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces
The LinkedList Class
The Iterator
The Iterator Interface
The Enhanced for Loop
The ListIterator Interface
Comparison of Iterator and ListIterator
Conversion between a ListIterator and an Index
The Iterable Interface
Exercises for Section 2.7
2.8 Application of the LinkedList Class
Case Study: Maintaining an Ordered List
Testing Class OrderedList
Exercises for Section 2.8
2.9 Implementation of a Double‐Linked List Class
Implementing the KWLinkedList Methods
A Class that Implements the ListIterator Interface
The Constructor
The hasNext and next Methods
The hasPrevious and previous Methods
The add Method
Inner Classes: Static and Nonstatic
Exercises for Section 2.9
2.10 The Collections Framework Design
The Collection Interface
Common Features of Collections
The AbstractCollection, AbstractList, and
AbstractSequentialList Classes
The List and RandomAccess Interfaces (Advanced)
Exercises for Section 2.10
Java API Interfaces and Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 3 Testing and Debugging
3.1 Types of Testing
Preparations for Testing
Testing Tips for Program Systems
Exercises for Section 3.1
3.2 Specifying the Tests
Testing Boundary Conditions
Exercises for Section 3.2
3.3 Stubs and Drivers
Stubs
Preconditions and Postconditions
Drivers
Exercises for Section 3.3
3.4 The JUnit5 Platform
Exercises for Section 3.4
3.5 Test‐Driven Development
Exercises for Section 3.5
3.6 Testing Interactive Programs in JUnit
ByteArrayInputStream
ByteArrayOutputStream
Exercises for Section 3.6
3.7 Debugging a Program
Using a Debugger
The IntelliJ and Eclipse Debuggers
Exercises for Section 3.7
Java API Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming
Answers to Quick-Check Exercises
Chapter 4 Stacks, Queues, and Deques
4.1 Stack Abstract Data Type
Specification of the Stack Abstract Data Type
Exercises for Section 4.1
4.2 Stack Applications
Case Study: Finding Palindromes
Exercises for Section 4.2
4.3 Implementing a Stack
Implementing a Stack with an ArrayList Component
Implementing a Stack as a Linked Data Structure
Comparison of Stack Implementations
Exercises for Section 4.3
4.4 Additional Stack Applications
Case Study: Evaluating Postfix Expressions
Case Study: Converting from Infix to Postfix
Method processOperator
Case Study: Converting Expressions with Parentheses
Tying the Case Studies Together
Exercises for Section 4.4
4.5 Queue Abstract Data Type
A Print Queue
The Unsuitability of a “Print Stack”
A Queue of Customers
Using a Queue for Traversing a Multi‐Branch Data Structure
Specification for a Queue Interface
Class LinkedList Implements the Queue Interface
Exercises for Section 4.5
4.6 Queue Applications
Case Study: Maintaining a Queue
Exercises for Section 4.6
4.7 Implementing the Queue Interface
Using a Double‐Linked List to Implement the Queue Interface
Using a Single‐Linked List to Implement the Queue Interface
Using a Circular Array to Implement the Queue Interface
Exercises for Section 4.7
4.8 The Deque Interface
Classes that Implement Deque
Using a Deque as a Queue
Using a Deque as a Stack
Exercises for Section 4.8
Java API Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 5 Recursion
5.1 Recursive Thinking
Steps to Design a Recursive Algorithm
Proving that a Recursive Method Is Correct
Tracing a Recursive Method
The Run‐Time Stack and Activation Frames
Exercises for Section 5.1
5.2 Recursive Definitions of Mathematical Formulas
Tail Recursion versus Iteration
Efficiency of Recursion
Exercises for Section 5.2
5.3 Recursive Array Search
Design of a Recursive Linear Search Algorithm
Implementation of Linear Search
Design of a Binary Search Algorithm
Efficiency of Binary Search
The Comparable Interface
Implementation of Binary Search
Testing Binary Search
Method Arrays.binarySearch
Exercises for Section 5.3
5.4 Recursive Data Structures
Recursive Definition of a Linked List
Class LinkedListRec
Removing a List Node
Exercises for Section 5.4
5.5 Problem Solving with Recursion
Case Study: Towers of Hanoi
Case Study: Counting Cells in a Blob
Exercises for Section 5.5
5.6 Backtracking
Case Study: Finding a Path through a Maze
Exercises for Section 5.6
User‐Defined Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 6 Trees 257
6.1 Tree Terminology and Applications
Tree Terminology
Binary Trees
Some Types of Binary Trees
General Trees
Exercises for Section 6.1
6.2 Tree Traversals
Visualizing Tree Traversals
Traversals of Binary Search Trees and Expression Trees
Exercises for Section 6.2
6.3 Implementing a BinaryTree Class
The Node<E> Class
The BinaryTree<E> Class
Exercises for Section 6.3
6.4 Lambda Expressions and Functional Interfaces
Functional Interfaces
A General Preorder Traversal Method
Using preOrderTraverse
Exercises for Section 6.4
6.5 Binary Search Trees
Overview of a Binary Search Tree
Performance
Interface SearchTree
The BinarySearchTree Class
Insertion into a Binary Search Tree
Removal from a Binary Search Tree
Testing a Binary Search Tree
Case Study: Writing an Index for a Term Paper
Exercises for Section 6.5
6.6 Heaps and Priority Queues
Inserting an Item into a Heap
Removing an Item from a Heap
Implementing a Heap
Priority Queues
The PriorityQueue Class
The Other Methods
The compare Method
Exercises for Section 6.6
6.7 Huffman Trees
Case Study: Building a Custom Huffman Tree
Exercises for Section 6.6
Java API Interfaces and Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 7 Sets and Maps
7.1 Sets and the Set Interface
The Set Abstraction
The Set Interface and Methods
Using Method of to Initialize a Collection
Comparison of Lists and Sets
Exercises for Section 7.1
7.2 Maps and the Map Interface
The Map Hierarchy
The Map Interface
Creating a Map
Exercises for Section 7.2
7.3 Hash Tables
Hash Codes and Index Calculation
Methods for Generating Hash Codes
Open Addressing
Table Wraparound and Search Termination
Traversing a Hash Table
Deleting an Item Using Open Addressing
Reducing Collisions by Expanding the Table Size
Reducing Collisions Using Quadratic Probing
Problems with Quadratic Probing
Chaining
Performance of Hash Tables
Exercises for Section 7.3
7.4 Implementing the Hash Table
Interface KWHashMap
Class Entry
Class HashtableOpen
Class HashtableChain
Testing the Hash Table Implementations
Exercises for Section 7.4
7.5 Implementation Considerations for Maps and Sets
Methods hashCode and equals
Implementing HashSetOpen
Writing HashSetOpen as an Adapter Class
Implementing the Java Map and Set Interfaces
Interface Map.Entry and Class AbstractMap.SimpleEntry
Creating a Set View of a Map
Method entrySet and Classes EntrySet and SetIterator
Classes TreeMap and TreeSet
Exercises for Section 7.5
7.6 Additional Applications of Maps
Case Study: Implementing a Cell Phone Contact List
Case Study: Completing the Huffman Coding Problem
Encoding the Huffman Tree
Exercises for Section 7.6
7.7 Navigable Sets and Maps
Application of a NavigableMap
Exercises for Section 7.7
Java API Interfaces and Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 8 Sorting
8.1 Using Java Sorting Methods
Exercises for Section 8.1
8.2 Selection Sort
Analysis of Selection Sort
Code for Selection Sort
Exercises for Section 8.2
8.3 Insertion Sort
Analysis of Insertion Sort
Code for Insertion Sort
Exercises for Section 8.3
8.4 Comparison of Quadratic Sorts
Comparisons versus Exchanges
Exercises for Section 8.4
8.5 Shell Sort: A Better Insertion Sort
Analysis of Shell Sort
Code for Shell Sort
Exercises for Section 8.5
8.6 Merge Sort
Analysis of Merge
Code for Merge
Algorithm for Merge Sort
Trace of Merge Sort Algorithm
Analysis of Merge Sort
Code for Merge Sort
Exercises for Section 8.6
8.7 Timsort
Merging Adjacent Sequences
Implementation
8.8 Heapsort
First Version of a Heapsort Algorithm
Revising the Heapsort Algorithm
Algorithm to Build a Heap
Analysis of Revised Heapsort Algorithm
Code for Heapsort
Exercises for Section 8.8
8.9 Quicksort
Algorithm for Quicksort
Analysis of Quicksort
Code for Quicksort
Algorithm for Partitioning
Code for partition
A Revised partition Algorithm
Code for Revised partition Method
Exercises for Section 8.9
8.10 Testing the Sort Algorithms
Exercises for Section 8.10
8.11 The Dutch National Flag Problem (Optional Topic)
Case Study: The Problem of the Dutch National Flag
Exercises for Section 8.11
Java Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 9 Self-Balancing Search Trees
9.1 Tree Balance and Rotation 428
Why Balance Is Important
Rotation
Algorithm for Rotation
Implementing Rotation
Exercises for Section 9.1
9.2 AVL Trees
Balancing a Left–Left Tree
Balancing a Left–Right Tree
Four Kinds of Critically Unbalanced Trees
Implementing an AVL Tree
Inserting into an AVL Tree
Removal from an AVL Tree
Performance of the AVL Tree
Exercises for Section 9.2
9.3 Red–Black Trees
Insertion into a Red–Black Tree
Removal from a Red–Black Tree
Performance of a Red–Black Tree
The TreeMap and TreeSet Classes
Exercises for Section 9.3
9.4 2–3 Trees
Searching a 2–3 Tree
Inserting an Item into a 2–3 Tree
Analysis of 2–3 Trees and Comparison with
Balanced Binary Trees
Removal from a 2–3 Tree
Exercises for Section 9.4
9.5 B‐Trees and 2–3–4 Trees
B‐Trees
Implementing the B‐Tree
Code for the insert Method
The insertIntoNode Method
The splitNode Method
Removal from a B‐Tree
B+ Trees
2–3–4 Trees
Relating 2–3–4 Trees to Red–Black Trees
Exercises for Section 9.5
Java Classes Introduced in This Chapter
User‐Defined Interfaces and Classes in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Chapter 10 Graphs
10.1 Graph Terminology
Visual Representation of Graphs
Directed and Undirected Graphs
Paths and Cycles
Relationship between Graphs and Trees
Graph Applications
Exercises for Section 10.1
10.2 The Graph ADT and Edge Class
Representing Vertices and Edges
Exercises for Section 10.2
10.3 Implementing the Graph ADT
Adjacency List
Adjacency Matrix
Overview of the Hierarchy
Declaring the Graph Interface
The ListGraph Class
The MatrixGraph Class
Comparing Implementations
The MapGraph Class
Exercises for Section 10.3
10.4 Traversals of Graphs
Breadth‐First Search
Depth‐First Search
Exercises for Section 10.4
10.5 Applications of Graph Traversals
Case Study: Shortest Path through a Maze
Case Study: Topological Sort of a Graph
Exercises for Section 10.5
10.6 Algorithms Using Weighted Graphs
Finding the Shortest Path from a Vertex to All Other Vertices
Minimum Spanning Trees
Exercises for Section 10.6
10.7 A Heuristic Algorithm A* to Find the Best Path
A* (A-Star) an Improvement of Dijkstra’s Algorithm
Exercises for Section 10.7
User‐Defined Classes and Interfaces in This Chapter
Quick‐Check Exercises
Review Questions
Programming Projects
Answers to Quick-Check Exercises
Appendix A Introduction to Java
A.1 The Java Environment and Classes
The Java Virtual Machine
The Java Compiler
Classes and Objects
The Java API
The import Statement
Method main
Execution of a Java Program
Use of jshell
Exercises for Section A.1
A.2 Primitive Data Types and Reference Variables
Primitive Data Types
Primitive‐Type Variables
Primitive‐Type Constants
Operators
Postfix and Prefix Increment
Type Compatibility and Conversion
Referencing Objects
Creating Objects
Exercises for Section A.2
