Elliot Koffman is currently Professor of Computer and Information Sciences at Temple University.  He received his Ph.D. at Case Institute of Technology.  He has authored and co-authored numerous textbooks and other publications.  Paul Wolfgang is currently Professor of Computer and Information Sciences at Temple University.  He received his B.S. in electrical engineering at University of Pennsylvania.

• Preface iiiChapter P A C++ Primer 1P.1 The C++ Environment 2P.2 Preprocessor Directives and Macros 7P.3 C++ Control Statements 12P.4 Primitive Data Types and Class Types 16P.5 Objects, Pointers, and References 23P.6 Functions 29P.7 Arrays and C Strings 33P.8 The string Class 38P.9 Input/Output Using Streams 44Chapter Review, Exercises, and Programming Projects 59Chapter 1 Introduction to Software Design 631.1 The Software Life Cycle 641.2 Using Abstraction to Manage Complexity 731.3 Defining C++ Classes 751.4 Abstract Data Types, Interfaces, and Pre- and Postconditions 981.5 Requirements Analysis, Use Cases, and Sequence Diagrams 1021.6 Design of an Array-Based Phone Directory 1081.7 Implementing and Testing the Array-Based Phone Directory 1141.8 Completing the Phone Directory Application 121Chapter Review, Exercises, and Programming Projects 125Chapter 2 Program Correctness and Efficiency 1292.1 Program Defects and “Bugs” 1302.2 Exceptions 1382.3 Testing Programs 1482.4 Debugging a Program 1602.5 Reasoning about Programs: Assertions and Loop Invariants 1662.6 Efficiency of Algorithms 170Chapter Review, Exercises, and Programming Projects 179Chapter 3 Inheritance and Class Hierarchies 1853.1 Introduction to Inheritance and Class Hierarchies 1863.2 Member Function Overriding, Member Function Overloading, and Polymorphism 1933.3 Abstract Classes, Assignment, and Casting in a Hierarchy 2023.4 Multiple Inheritance 2103.5 Namespaces and Visibility 2133.6 A Shape Class Hierarchy 220Chapter Review, Exercises, and Programming Projects 225Chapter 4 Sequential Containers 2314.1 Template Classes and the Vector 2324.2 Applications of vector 2384.3 Implementation of a vector Class 2404.4 The Copy Constructor, Assignment Operator, and Destructor 2474.5 Single-Linked Lists and Double-Linked Lists 2524.6 The list Class and the Iterator 2644.7 Implementation of a Double-Linked List Class 2714.8 Application of the list Class 2854.9 Standard Library Containers 2924.10 Standard Library Algorithms and Function Objects 297Chapter Review, Exercises, and Programming Projects 307Chapter 5 Stacks 3115.1 The Stack Abstract Data Type 3125.2 Stack Applications 3155.3 Implementing a Stack 3255.4 Additional Stack Applications 332Chapter Review, Exercises, and Programming Projects 351Chapter 6 Queues and Deques 3576.1 The Queue Abstract Data Type 3586.2 Maintaining a Queue of Customers 3626.3 Implementing the Queue ADT 3656.4 The Deque 3766.5 Simulating Waiting Lines Using Queues 380Chapter Review, Exercises, and Programming Projects 398Chapter 7 Recursion 4037.1 Recursive Thinking 4047.2 Recursive Definitions of Mathematical Formulas 4127.3 Recursive Search 4207.4 Problem Solving with Recursion 4267.5 Backtracking 435Chapter Review, Exercises, and Programming Projects 440Chapter 8 Trees 4458.1 Tree Terminology and Applications 4478.2 Tree Traversals 4548.3 Implementing a Binary_Tree Class 4578.4 Binary Search Trees 4668.5 Heaps and Priority Queues 4848.6 Huffman Trees 496Chapter Review, Exercises, and Programming Projects 505Chapter 9 Sets and Maps 5119.1 Associative Container Requirements 5129.2 Maps and Multimaps 5219.3 Hash Tables 5309.4 Implementing the Hash Table 5429.5 Implementation Considerations for the hash_map 5559.6 Additional Applications of Maps 558Chapter Review, Exercises, and Programming Projects 564Chapter 10 Sorting 56910.1 Using C++ Sorting Functions 57010.2 Selection Sort 57210.3 Bubble Sort 57710.4 Insertion Sort 58110.5 Comparison of Quadratic Sorts 58610.6 Shell Sort: A Better Insertion Sort 58810.7 Merge Sort 59210.8 Heapsort 59910.9 Quicksort 60410.10 Testing the Sort Algorithms 61410.11 The Dutch National Flag Problem (Optional Topic) 616Chapter Review, Exercises, and Programming Projects 620Chapter 11 Self-Balancing Search Trees 62311.1 Tree Balance and Rotation 62411.2 AVL Trees 62811.3 Red-Black Trees 64311.4 2-3 Trees 65611.5 2-3-4 and B-Trees 663Chapter Review, Exercises, and Programming Projects 681Chapter 12 Graphs 69112.1 Graph Terminology 69212.2 The Graph ADT and Edge Class 69712.3 Implementing the Graph ADT 70112.4 Traversals of Graphs 71512.5 Applications of Graph Traversals 72712.6 Algorithms Using Weighted Graphs 734Chapter Review, Exercises, and Programming Projects 743Appendix A Advanced C++ Topics 755A.1 Source Character Set, Trigraphs, Digraphs, and Alternate Keywords 755A.2 The Allocator 756A.3 Traits 757A.4 Virtual Base Classes 759A.5 Smart Pointers 764Appendix B Overview of UML 769B.1 The Class Diagram 770B.2 Sequence Diagrams 776Appendix C The CppUnit Test Framework 779Glossary 783Index 795

Elliot Koffman is currently Professor of Computer and Information Sciences at Temple University.  He received his Ph.D. at Case Institute of Technology.  He has authored and co-authored numerous textbooks and other publications.  Paul Wolfgang is currently Professor of Computer and Information Sciences at Temple University.  He received his B.S. in electrical engineering at University of Pennsylvania.

• Preface iiiChapter P A C++ Primer 1P.1 The C++ Environment 2P.2 Preprocessor Directives and Macros 7P.3 C++ Control Statements 12P.4 Primitive Data Types and Class Types 16P.5 Objects, Pointers, and References 23P.6 Functions 29P.7 Arrays and C Strings 33P.8 The string Class 38P.9 Input/Output Using Streams 44Chapter Review, Exercises, and Programming Projects 59Chapter 1 Introduction to Software Design 631.1 The Software Life Cycle 641.2 Using Abstraction to Manage Complexity 731.3 Defining C++ Classes 751.4 Abstract Data Types, Interfaces, and Pre- and Postconditions 981.5 Requirements Analysis, Use Cases, and Sequence Diagrams 1021.6 Design of an Array-Based Phone Directory 1081.7 Implementing and Testing the Array-Based Phone Directory 1141.8 Completing the Phone Directory Application 121Chapter Review, Exercises, and Programming Projects 125Chapter 2 Program Correctness and Efficiency 1292.1 Program Defects and “Bugs” 1302.2 Exceptions 1382.3 Testing Programs 1482.4 Debugging a Program 1602.5 Reasoning about Programs: Assertions and Loop Invariants 1662.6 Efficiency of Algorithms 170Chapter Review, Exercises, and Programming Projects 179Chapter 3 Inheritance and Class Hierarchies 1853.1 Introduction to Inheritance and Class Hierarchies 1863.2 Member Function Overriding, Member Function Overloading, and Polymorphism 1933.3 Abstract Classes, Assignment, and Casting in a Hierarchy 2023.4 Multiple Inheritance 2103.5 Namespaces and Visibility 2133.6 A Shape Class Hierarchy 220Chapter Review, Exercises, and Programming Projects 225Chapter 4 Sequential Containers 2314.1 Template Classes and the Vector 2324.2 Applications of vector 2384.3 Implementation of a vector Class 2404.4 The Copy Constructor, Assignment Operator, and Destructor 2474.5 Single-Linked Lists and Double-Linked Lists 2524.6 The list Class and the Iterator 2644.7 Implementation of a Double-Linked List Class 2714.8 Application of the list Class 2854.9 Standard Library Containers 2924.10 Standard Library Algorithms and Function Objects 297Chapter Review, Exercises, and Programming Projects 307Chapter 5 Stacks 3115.1 The Stack Abstract Data Type 3125.2 Stack Applications 3155.3 Implementing a Stack 3255.4 Additional Stack Applications 332Chapter Review, Exercises, and Programming Projects 351Chapter 6 Queues and Deques 3576.1 The Queue Abstract Data Type 3586.2 Maintaining a Queue of Customers 3626.3 Implementing the Queue ADT 3656.4 The Deque 3766.5 Simulating Waiting Lines Using Queues 380Chapter Review, Exercises, and Programming Projects 398Chapter 7 Recursion 4037.1 Recursive Thinking 4047.2 Recursive Definitions of Mathematical Formulas 4127.3 Recursive Search 4207.4 Problem Solving with Recursion 4267.5 Backtracking 435Chapter Review, Exercises, and Programming Projects 440Chapter 8 Trees 4458.1 Tree Terminology and Applications 4478.2 Tree Traversals 4548.3 Implementing a Binary_Tree Class 4578.4 Binary Search Trees 4668.5 Heaps and Priority Queues 4848.6 Huffman Trees 496Chapter Review, Exercises, and Programming Projects 505Chapter 9 Sets and Maps 5119.1 Associative Container Requirements 5129.2 Maps and Multimaps 5219.3 Hash Tables 5309.4 Implementing the Hash Table 5429.5 Implementation Considerations for the hash_map 5559.6 Additional Applications of Maps 558Chapter Review, Exercises, and Programming Projects 564Chapter 10 Sorting 56910.1 Using C++ Sorting Functions 57010.2 Selection Sort 57210.3 Bubble Sort 57710.4 Insertion Sort 58110.5 Comparison of Quadratic Sorts 58610.6 Shell Sort: A Better Insertion Sort 58810.7 Merge Sort 59210.8 Heapsort 59910.9 Quicksort 60410.10 Testing the Sort Algorithms 61410.11 The Dutch National Flag Problem (Optional Topic) 616Chapter Review, Exercises, and Programming Projects 620Chapter 11 Self-Balancing Search Trees 62311.1 Tree Balance and Rotation 62411.2 AVL Trees 62811.3 Red-Black Trees 64311.4 2-3 Trees 65611.5 2-3-4 and B-Trees 663Chapter Review, Exercises, and Programming Projects 681Chapter 12 Graphs 69112.1 Graph Terminology 69212.2 The Graph ADT and Edge Class 69712.3 Implementing the Graph ADT 70112.4 Traversals of Graphs 71512.5 Applications of Graph Traversals 72712.6 Algorithms Using Weighted Graphs 734Chapter Review, Exercises, and Programming Projects 743Appendix A Advanced C++ Topics 755A.1 Source Character Set, Trigraphs, Digraphs, and Alternate Keywords 755A.2 The Allocator 756A.3 Traits 757A.4 Virtual Base Classes 759A.5 Smart Pointers 764Appendix B Overview of UML 769B.1 The Class Diagram 770B.2 Sequence Diagrams 776Appendix C The CppUnit Test Framework 779Glossary 783Index 795