Preface xvll
CHAPTER 1 INTRODUCTION
1.1 Abstract Data Types
ADT Format
1.2 C++ Classes and Abstract Types
Encapsulatlon and Information Hidlng
Message Passing
1.3 Objecls in C++ Appllcatlons
Applicatlon: The Circle Class
1.4 Oblect Design
Objects and Composltion
C++ Geometric Classes
Objects and Inherltance
Inheritance In Frogrammlng
Ordered Llsts and Inheritance
Software Reusability
SeqLlst and OrderedLlsl Class Speclfications
1.5 Applicatlons with Class Inherltance
1.6 Object-Oriented Program Design
Problem Analysis/Program Definition
Deslgn
Coding
Tesllng
Program Deslgn Illustratlon: A Dlce Graph
1.7 Program Testlng and Malnlenance
Object Testlng
Contrul Module Testing
Program Malntenance and Documentation
1.8 The C++ Programming Language
1.9 Abstract Base Classes and Polymorphism
Polymorphlsm and Dynamic Binding
Written Exerclses
CHAPTER2 BASIC DATA TYMS
2.1 IntegerTypes
Computer Storage of Integers
Data In Memory
C++ Representatlon of Integers
2.2 Character Types
ASCIl Characlers
2.3 Real Data Types
Real Number Representatlons
2.4 Enumerated Types
Implementing C++ Enumerated Types
2.5 Pointers
Pointer ADT
l'olnter Values
2.6 The Array Type
the Buill-In C++ Array Type
Sloragc of One-Dimcnslonal Arrays
Array Bounds
Two-Dlmensional Arrays
Storage of Two-Dimenslonal Arrays
2.7 String Literals and Variables
C++ Strings
Appllcallon: Reverslng Names
2.8 Records
C++ Structures
2.9 Files
C++ Stream Hlerarchy
2.10 Array and Record Appllcations
Sequentlal Seareh
Exchange Sort
Counting C++ Reserved Words
Wrltten Exercises
ProgrammlIlg Exerclses
CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES
3.1 The User Type CLASS
Class Declaration
Constructor
Object Declarallon
Class Implementatlon
Implementing a Constructor
Bulldlng Objects
3.2 Sample Classes
The Temperature Class
The Random Number Class
3.3 Oblects and Information Passlng
An Object as a Return Value
An Object as a Function Parameter
3.4 Arrays of Objects
The Default Conslructor
3.5 Multlple Constructors
3.6 Case Study: Triangular Matrices
llpper Triangular Matrlx Properties
Written Exerclses
Programming Exereises
CHAPTER 4 COLLECTION CLASSES
4.1 Describing Llnear Collectlons
Dlrecl Access Collections
Sequentlal Access Collectlons
Generalized Indexing
4.2 Describing Nonlinear Collectlons
Group Collectlons
4.3 Analysls of Algorllhms
Performance Crlteria
Common Orders of Magnltude
4.4 The Sequential and Blnary Search
Blnary Search
4.5 The Baslc Sequentlal List Class
List Modincatlon Melhods
Wrlllen Exerclses
Programming Exerclses
CHAPTER 5 STACKS AND QUEUES
5.1 Stacks
5.2 The Stack Class
5.3 Expression Evaluation
Postfix Evaluation
Appllcatlon: A Posttlx Calculator
5.4 Queues
5.5 The Oueue Class
5.6 Prlorlty Queues
A Prlorlty Queue Class
5.7 Case Study: Event-Drlven Slmulalion
Wrltten Exerclses
Programmlng Exerclses
CHAPTER 6 ABSTRACT OPERATORS
6.1 Describlng Operator Overloading
Client-Defined External Functlons
Class Members
Frlend Functlons
6.2 Rational Number System
Representlng Ratlonal Numbers
Ratlonal Number Arithtnetlc
Ralional Number Converslon
6.3 The Ratlonal Class
6.4 Ratlonal Operators as Member Funclions
Implemenllng the Ratlonal Operators
6.5 The Ratlonal Stream Operators as Friends
Implementlng Ratlonal Stream Operators
6.6 Converting Rational Numbers
Conversion to Object Type
Converslon from Object Type
6.7 Using Ratlonal Numbers
Wrltten Exerclses
Programmlng Exerclses
CHAPTER 7 OENERIC DATA TYPES
7.1 Template Functlons
Template-Based Sort
7.2 Template Classes
Deflning a Template Class
Declaring Template Class Oblects
Defining Tcmplate Class Methods
7.3 Template Llst Classes
7.4 Infix Expression Evaluatlon
Wrltten Exerclses
Programming Exercises
CHAPTER 8 CLASSES AND DYNAMIC MEMORY
8.1 Pointers and Dynamic Data Structures
The Memory Allocation Operator New
Dynamlc Array Allocatlon
The Memory Deallocatlon Operator Delete
8.2 Dynamlcally Allocated Oblecte
Deallocatlng Object Data: The Destructor
8.3 Asslgnment and Inltlaltzatlon
Asslgnment Issues
Overloadlng the Assignment Operator
The Thls Polnter
Inltlallzatlon Issues
Creating a Copy Constructor
8.4 Safe Arrays
The Array Class
Memory Allocatlon for the Array Class
Array Bounds Checklng and the Overloaded 1] Operator
Convertlng an Object to a Polnter
Using the Array Class
8.5 A Strlng Class
String Class Implemenlation
8.6 Pattern Matehlng
The Flnd Process
Pattern Matchlng Algorlthm
Analysls of the Pattern Matchlng Algorlthm
8.7 Integral Sets
Sets of Integral Types
C++ Blt Handllng Operators
Representlng Set Elements
The Sleve of Eratosthenes
Set Class Implementatlon
Wrltten Exereises
Programmlng Exerclses
CHAPTER9 LINKIDLISTS
Descrlbing a Llnked Llst
Chapter 9 Overvlew
9.1 The Node Class
Declarlng a Node Type
Implementlng the Node Class
9.2 Bulldlng Llnked Llsts
Creating a Node
Insertlng a Node: InsertFront
Traversing a Llnked Llst
Insertlng a Node: InsertRear
Appllcatlon: Student Graduatlon Llst
Creatlng an Ordered Llst
Appllcation: Sortlng wlth Llnked Llsts
9.3 Deslgnlng a Llnked List Class
Llnked Llst Data Members
Llnked List Operatlons
9.4 The LlnkedLlst Class
9.5 Implementlng the LinkedList Class
9.6 Implementlng Collectlons wlth Llnked Lists
Llnked Queues
Implementlng Queue Methods
Llnked SeqLlst Class
Implementlng SeqLlst Data Access Methods
Appllcation: Comparlng SeqLlst Implementations
9.7 Case Study: A Prlnt Spooler
Implementing the Spooler Update Method
Spooler Evaluation Methods
9.8 Clreular Llsts
Clrcular Node Class Implementation
Appllcatlon: Solvlng the Josephus Problem
9.9 Doubly Llnked Lista
Appllcation: Doubly Linked List Sort
DNode Class Implementation
9.10 Case Study: Wlndow Management
The Wlndow Llst
WindowList Class Implementatlon
Writlen Exerclses
Programmlng Exercises
CHAPTCR 10 RECURSION
10.1 The Concept of Recurslon
Recurslve Deflnltions
Recursive Problems
10.2 Deslgnlng Recurslve Functlons
10.3 Recursive Code and the Runtlme Stack
The Runtlme Stack
10.4 Problem-Solvlng wlth Recurslon
Blnary Search
Combinatorics: The Commlttee Problem
Combinalorlcs: Permutations
Maze Handllng
Maze Class Implementatlon
10.5 Evaluatlng Recurslon
Wrlllen Exerclses
Programmlng Exerclses
CHAPTER 11 TREES
Tree Termlnology
Binary Trees
11.1 Binary Tree Structure
Deslgning a TreeNode Class
Bulldlng a Blnary Tree
11.2 Deslgnlng TreeNode Funclions
Recursive Tree Traversals
11.3 Uslng Tree Scan Algorlthms
Application: Vlsitlng Tree Nodes
Appllcation: Tree Prlnt
Appllcation: Copyfng and Delellng Trees
Applicatlon: Upright Tree Prlnting
11.4 Blnary Search Trees
The Key in a Blnary Search Tree Node
Operatlons on a Blnary Search Tree
Declaring a Blnary Search Tree ADT
11.5 LIsing Binary Search Trees
Duplicate Nodes
11.6 The BlnSTree Implementation
List Operations
11.7 Case Study: Concordance
Written Exercises
Programming Exercises
CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES
12.1 A Vlew of Inheritance
Class Inherltance Termlnology
12.2 Inheritance In C++
Constructors and Derived Classes
What Cannot Be Inherited
12.3 Polymorphism and Vlrtual Functlons
Demonstratlng Polymorphlsm
Appllcation: Geometrlc Figures and Virtual Methods
Virtual Melhods and the Destructor
12.4 Abstract Base Classes
Abstract Base Class-List
Derlvlng SeqLlst from Abstract Base Class List
12.5 Iterators
The Iterator Abstract Base Class
Derlving Llst Iterators
Building the SeqLlst Iterator
Array Iterator
Applicatlon: Merglng Sorted Runs
Arraylterator Implementatlon
12.6 Ordered Llsts
OrderedLlst Class Implementatlon
12.7 Heterogeneous Llsts
Heterogeneous Arrays
Heterogeneous Linked Lists
Wrltten Exercises
Programmlng Exerelses
CHAPTER 13 ADVANCED NONLINEAR STRUCTURES
13.1 Array-Based Binary Trees
Appllcation: The Tournament Sort
13.2 Heaps
The Heap as a List
The Heap Class
13.3 Implementlng the Heap Class
Appllcatlon: Heap Sort
13.4 Priorlty Queues
Appllcation: Long Runs
13.5 AVLTrees
AVL Tree Nodes
13.6 The AVL Tree Class
Memory Allocation for the AVLTree
Evaluatlng AVL Trees
13.7 Trce Iterators
The Inorder Iterator
Inorderlteralor Class Implementatlon
Appllcation: TreeSort
13.8 Graphs
Connected Components
13.9 The Graph Class
Declaring a Graph ADT
Graph Class Implementatlon
Graph Traversals
Appllcatlons
Reachabillty and Warshall's Algorlthm
Writlen Exercises
Programmlng Exercises
CHAPTER 14 ORGANIZING COLLECTIONS
14.1 Baslc Array Sortlng Algorithms
The Selection Sort
The Bubble Sorl
The Insertion Sort
14.2 OuickSort
OulckSort Descrlption
OuickSort Algorithm
Comparison of Array Sort Algorithms
14.3 Hashing
Keys and a Hash Function
Hashing Functions
Other Hash Methods
Colllslon Resolutlon
14.4 Hash Table Class
Appllcation: Strlng Frequency
HashTable Class Implementation
HashTableIterator Class Implementation
14.5 The Performance of Searching Methods
14.6 Blnary Flles and External Data Operatlons
Binary Flles
The BlnFlle Class
External Flle Searching
External Flle Sort
Long Run MergeSort
14.7 Dictionarles
Writlen Exerclses
Programming Exercises
APPENDIX ANSWERS TO SELECTED EXERCISES
BIBLIOGRAPHY
· · · · · · (收起)