CHAPTER 1 INTRODUCTION 1
1.1 Abstract Data Types 2
ADT Format 3
1.2 C++ Classes and Abstract Types 6
Encapsulation and Information Hiding 7
Message Passing 7
1.3 Objects in C++ Applications 8
Application： The Circle Class 8
1.4 Object Design 11
Objects and Composition 11
C++ Geometric Classes 13
Objects and Inheritance 14
Inheritance in Programming 15
Ordered Lists and Inheritance 18
Software Reusability 19
SeqList and OrderedList Class Specifiications 19
1.5 Applications with Class Inheritance 21
1.6 Object-Oriented Program Design 22
Problem Analysis/Program Definition 23
Design 23
Coding 24
Testing 24
Program Design Illustration： A Dice Graph 24
1.7 Program Testing and Maintenance 31
Object Testing 31
Control Module Testing 31
Program Maintenance and Documentation 32
1.8 The C++ Programming Language 32
1.9 Abstract Base Classes and Polymorphism 33
Polymorphism and Dynamic Binding 34
Written Exercises 36
CHAPTER 2 BASIC DATA TYPES 38
2.1 Integer Types 39
Computer Storage of Integers 41
Data in Memory 42
C++ Representation of Integers 43
2.2 Character Types 43
ASCII Characters 44
2.3 Real Data Types 45
Real Number Representations 46
2.4 Enumerated Types 48
Implementing C++ Enumerated Types 49
2.5 Pointers 49
Pointer ADT 49
Pointer Values 51
2.6 The Array Type 52
The Built-In C++ Array Type 52
Storageof One-Dimensional Arrays 53
Array Bounds 54
Two-Dimensional Arrays 55
Storage of Two-Dimensional Arrays 57
2.7 String Literals and Variables 58
C++ Strings 61
Application： Reversing Names 63
2.8 Records 65
C++ Structures 66
2.9 Files 66
C++ Stream Hierarchy 69
2.10 Array and Record Applications 72
Sequential Search 72
Exchange Sort 75
Counting C++ Reserved Words 77
Written Exercises 80
Programming Exercises 88
CHAPTER 3 ABSTRACT DATA TYPES AND CLASSES 91
3.1 The User Type CLASS 92
Class Declaration 92
Constructor 94
Object Declaration 94
Class Implementation 95
Implementing a Constructor 96
Building Objects 97
3.2 Sample Classes 101
The Temperature Class 101
The Random Number Class 104
3.3 Objects and Information Passing 110
An Object as a Return Value 110
An Object as a Function Parameter 110
3.4 Arrays of Objects 111
The Default Constructor 112
3.5 Multiple Constructors 113
3.6 Case Study： Triangular Matrices 116
Upper Triangular Matrix Properties 117
Written Exercises 126
Programming Exercises 131
CHAPTER 4 COLLECTION CLASSES 141
4.1 Describing Linear Collections 144
Direct Access Collections 145
Sequential Access Collections 146
Generalized Indexing 150
4.2 Describing Nonlinear Collections 151
Group Collections 152
4.3 Analysis of Algorithms 154
Performance Criteria 154
Common Orders of Magnitude 159
4.4 The Sequential and Binary Search 160
Binary Search 161
4.5 The Basic Sequential List Class 167
List Modification Methods 170
Written Exercises 178
Programming Exercises 181
CHAPTER S STACKS AND QUEUES 184
5.1 Stacks 185
5.2 The Stack Class 188
5.3 Expression Evaluation 197
Posttix Evaluation 198
Application： A Postfix Calculator 199
5.4 Queues 204
5.5 The Queue Class 207
5.6 Priority Queues 221
A Priority Queue Class 223
5.7 Case Study： Event-Driven Simulation 231
Written Exercises 245
Programming Exercises 249
CHAPTER 6 ABSTRACT OPERATORS 253
6.1 Describing Operator Overloading 255
Client-Defiined External Functions 255
Class Members 256
Friend Functions 259
6.2 Rational Number System 260
Representing Rational Numbers 261
Rational Number Arithmetic 261
Rational Number Conversion 262
6.3 The Rational Class 263
6.4 Rational Operators as Member Functions 265
Implementing the Rational Operators 266
6.5 The Rational Stream Operators as Friends 267
Implementing Rational Stream Operators 268
6.6 Converting Rational Numbers 269
Conversion to Object Type 269
Conversion from Object Type 271
6.7 Using Rational Numbers 272
Written Exercises 277
Programming Exercises 284
CHAPTER 7 GENERIC DATA TYPES 289
7.1 Template Functions 290
Template-Based Sort 294
7.2 Template Classes 294
Defining a Template Class 294
Declaring Template Class Objects 295
Defiining Template Class Methods 295
7.3 Template List Classes 297
7.4 Infiix Expression Evaluation 299
Written Exercises 308
Programming Exercises 309
CHAPTER 8 CLASSES AND DYNAMIC MEMORY 313
8.1 Pointers and Dynamic Data Structures 315
The Memory Allocation Operator New 315
Dynamic Array Allocation 316
The Memory Dealiocation Operator Delete 317
8.2 Dynamically Allocated Objects 318
Deallocating Object Data： The Destructor 319
8.3 Assignment and Initialization 322
Assignment Issues 322
Overloading the Assignment Operator 324
The This Pointer 325
Initialization Issues 325
Creating a Copy Constructor 326
8.4 Safe Arrays 329
The Array Class 329
Memory Allocation for the Array Class 331
Array Bounds Checking and the Overloaded ｛} Operator 332
Converting an Object to a Pointer 333
Using the Array Class 335
8.5 A String Class 337
String Class Implementation 343
8.6 Pattern Matching 349
The Find Process 350
Pattern Matching Algorithm 350
Analysis of the Pattern Matching Algorithm 355
8.7 Integral Sets 356
Sets of Integral Types 356
C++ Bit Handling Operators 357
Representing Set Elements 360
The Sieve of Eratosthenes 363
Set Class Implementation 366
Written Exercises 369
Programming Exercises 379
CHAPTER 9 LINKED LISTS 383
Describing a Linked List 386
Chapter Overview 386
9.1 The Node Class 387
Declaring a Node Type 387
Implementing the Node Class 390
9.2 Building Linked Lists 393
Creating a Node 393
Inserting a Node： InsertFront 393
Traversing a Linked List 394
Inserting a Node： InsertRear 397
Application： Student Graduation List 401
Creating an Ordered List 404
Application： Sorting with Linked Lists 406
9.3 Designing a Linked List Class 409
Linked List Data Members 409
Linked List Operations 410
9.4 The LinkedList Class 413
9.5 Implementing the LinkedList Class 421
9.6 Implementing Collections with Linked Lists 429
Linked Queues 429
Implementing Queue Methods 431
Linked SeqList Class 432
Implementing SeqList Data Access Methods 433
Application： Comparing SeqList Implementations 434
9.7 Case Study： A Print Spooler 436
implementing the Spooler Update Method 439
Spooler Evaluation Methods 440
9.8 Circular Lists 443
Circular Node Class Implementation 445
Application： Solving the Josephus Problem 447
9.9 Doubly Linked Lists 450
Application： Doubly Linked List Sort 452
DNode Class Implementation 455
9.10 Case Study： Window Management 457
The Window List 458
WindowList Class Implementation 461
Written Exercises 465
Programming Exercises 474
CHAPTER 10 RECURSION 480
10.1 The Concept of Recursion 481
Recursive Definitions 483
Recursive Problems 484
10.2 Designing Recursive Functions 489
10.3 Recursive Code and the Runtime Stack 494
The Runtime Stack 494
10.4 Problem-Solving with Recursion 497
Binary Search 497
Combinatorics： The Committee Problem 500
Combinatorics： Permutations 503
Maze Handling 514
Maze Class Implementation 518
10.5 Evaluating Recursion 521
Written Exercises 527
Programming Exercises 530
CHAPTER 11 TREES 533
Tree Terminology 535
Binary Trees 537
11.1 Binary Tree Structure 540
Designing a TreeNode Class 540
Building a Binary Tree 543
11.2 Designing TreeNode Functions 544
Recursive Tree Traversals 546
11.3 Using Tree Scan Algorithms 550
Application： Visiting Tree Nodes 550
Application： Tree Print 552
Application： Copying and Deleting Trees 553
Application： Upright Tree Printing 559
11.4 Binary Search Trees 564
The Key in a Binary Search Tree Node 566
Operations on a Binary Search Tree 567
Declaring a Binary Search Tree ADT 568
11.5 Using Binary Search Trees 573
Duplicate Nodes 575
11.6 The BinSTree Implementation 578
List Operations 579
11.7 Case Study： Concordance 590
Written Exercises 596
Programming Exercises 602
CHAPTER 12 INHERITANCE AND ABSTRACT CLASSES 606
12.1 A View of Inheritance 607
Class Inheritance Terminology 609
12.2 Inheritance in C++ 610
Constructors and Derived Classes 612
What Cannot Be Inherited 619
12.3 Polymorphism and Virtual Functions 620
Demonstrating Polymorphism 622
Application： Geometric Figures and Virtual Methods 626
Virtual Methods and the Destructor 629
12.4 Abstract Base Classes 630
Abstract Base Class—List 632
Deriving SeqList from Abstract Base Class List 633
12.5 Iterators 635
The Iterator Abstract Base Class 636
Deriving List Iterators 637
Building the SeqList Iterator 638
Array Iterator 643
Application： Merging Sorted Runs 644
Arraylterator Implementation 649
12.6 Ordered Lists 650
OrderedList Class Implementation 651
12.7 Heterogeneous Lists 654
Heterogeneous Arrays 654
Heterogeneous Linked Lists 658
Written Exercises 664
Programming Exercises 674
CHAPTER 13 ADVANCED NONLINEAR STRUCTURES 678
13.1 Array-Based Binary Trees 679
Application： The Tournament Sort 682
13.2 Heaps 688
The Heap as a List 688
The Heap Class 690
13.3 Implementing the Heap Class 694
Application： Heap Sort 701
13.4 Priority Queues 705
Application： Long Runs 707
13.5 AVL Trees 713
AVL Tree Nodes 713
13.6 The AVL Tree Class 717
Memory Allocation for the AVLTree 720
Evaluating AVL Trees 729
13.7 Tree Iterators 731
The Inorder Iterator 732
lnorderlterator Class Implementation 733
Application： TreeSort 735
13.8 Graphs 737
Connected Components 738
13.9 The Graph Class 739
Declaring a Graph ADT 739
Graph Class Implementation 744
Graph Traversals 748
Applications 751
Reachability and Warshall’s Algorithm 760
Written Exercises 764
Programming Exercises 774
CHAPTER 14 ORGANIZING COLLECTIONS 778
14.1 Basic Array Sorting Algorithms 779
The Selection Sort 779
The Bubble Sort 782
The Insertion Sort 784
14.2 QuickSort 786
QuickSort Description 786
QuickSort Algorithm 790
Comparison of Array Sort Algorithms 794
14.3 Hashing 799
Keys and a Hash Function 799
Hashing Functions 800
Other Hash Methods 802
Collision Resolution 803
14.4 Hash Table Class 805
Application： String Frequency 809
HashTable Class Implementation 811
HashTablelterator Class Implementation 812
14.5 The Performance of Searching Methods 815
14.6 Binary Files and External Data Operations 816
Binary Files 816
The BinFile Class 819
External File Searching 825
External File Sort 830
Long Run MergeSort 832
14.7 Dictionaries 841
Written Exercises 850
Programming Exercises 856
APPENDIX ANSWERS TO SELECTED EXERCISES 862
BIBLIOGRAPHY 882
INDEX 884