C++ classes and data structures

Cover
Contents
Preface
Chapter 1 Structs and Classes
	1.1 Structs
	1.2 Basic Class Concepts
	1.3 Class Implementation
	1.4 Testing a Class
	1.5 Placing Function Definitions in the Class Definition (and Why We Shouldn't Do It)
	1.6 Commenting a Class
	1.7 The Differences Between a Struct and a Class
	Summary
	Exercises
Chapter 2 Overloaded Operators, Class Templates, and Abstraction
	2.1 Overloaded Operators
	2.2 Using a Check Struct in the Checkbook Class
	2.3 Class Templates
	2.4 Classes and Abstraction
	Summary
	Exercises
Chapter 3 More about Classes
	3.1 The const Specifier
	3.2 Constructors
	3.3 Class Modification
	3.4 Modifying the Checkbook Class to Keep a History of Checks
	Summary
	Exercises
Chapter 4 Pointers and Dynamic Arrays
	4.1 Pointers
	4.2 The [ ] Operator
	4.3 Dynamically Allocated Memory
	4.4 Dynamic Arrays
	4.5 The Delete Operator
	4.6 Pointers to Objects
	4.7 Running out of Heap Memory
	4.8 Adjustable Arrays
	Summary
	Exercises
Chapter 5 An Array Class
	5.1 Array Class Template
	5.2 Using the Array Class
	5.3 Destructors
	5.4 The Copy Constructor
	5.5 The Overloaded Assignment Operator Function
	5.6 An Example
	5.7 Advantages and Disadvantages of an Array Class
	5.8 The Standard Template Library
	Summary
	Exercises
Chapter 6 Introduction to Object-Oriented Programming
	6.1 Composition
	*6.2 Inheritance
	*6.3 Polymorphism
	Summary
	Exercises
Chapter 7 Methods for Making Data Structures
	7.1 Using Arrays in Data Structures
	7.2 Introduction to Linked Structures
	7.3 Writing Code for Linked Lists
	7.4 Arrays vs. Linked Lists
	Summary
	Exercises
Chapter 8 Stacks and Queues
	8.1 The Stack ADT
	8.2 Array Implementation of a Stack
	8.3 Linked-List Implementation of a Stack
	8.4 The Queue ADT
	8.5 The Linked-List Implementation of a Queue
	8.6 Other Linked-List Implementations of Queues
	*8.7 Array Implementation of a Queue
	Summary
	Exercises
Chapter 9 Introduction to Time Complexities
	9.1 Time Complexity Basics
	9.2 The Constant Time Complexity
	9.3 Big-Oh Notation
	9.4 The Logarithmic Time Complexity
	9.5 The Binary Search Algorithm
	9.6 Computer Speed: Where Does It Really Come From?
	9.7 Time Complexities of Data Structure Functions
	*9.8 Amortized Analysis of Array Expansion and Contraction
	Summary
	Exercises
Chapter 10 The Linked List as a Data Structure
	10.1 The List ADT
	10.2 Using Key Values in Records of Information
	10.3 Linked-List Implementation
	10.4 Other Implementations
	Summary
	Exercises
Chapter 11 Hash Tables
	11.1 The Hash Table ADT
	11.2 Hash Functions and Hash Table Design
	11.3 Implementation Issues for a Hash Table
	11.4 Pointers to Functions
	11.5 A Hash Table Implementation
	11.6 Using the Hash Table Implementation
	11.7 A Hash Table Implementation of a Doubly Linked List
	Summary
	Exercises
Chapter 12 Priority Queues, Trees, and Heaps
	12.1 Priority Queue ADT
	12.2 Priority Queue Design
	12.3 Trees
	12.4 Heaps
	12.5 Using a One-Assignment Swap
	12.6 A Heap Implementation of a Priority Queue (Array-Based)
	*12.7 The Design of a Linked (Embedded) Heap
	*12.8 A Linked (Embedded) Heap Implementation of a Priority Queue
	Summary
	Exercises
Chapter 13 Recursion
	13.1 A Recursive Factorial Function
	13.2 Guidelines for Writing Recursive Functions
	13.3 Using Recursion on Linked Structures
	13.4 Time Complexities of Recursive Functions
	Summary
	Exercises
Chapter 14 Introduction to Sorting Algorithms
	14.1 Heapsort
	14.2 Insertion Sort
	14.3 Quicksort
	14.4 Counting Sort
	14.5 Sorting a Linked List
	Summary
	Exercises
Chapter 15 Other Data Structures
	15.1 Binary Search Trees
	15.2 Comparison of the BST with Other Data Structures
	15.3 Graphs
	15.4 Comparing Adjacency Matrices with Adjacency Lists
	Summary
	Exercises
Appendix A: How to Compile and Work with Multiple-File Programs
	Microsoft Visual Studio 2005 C++ Compiler
	Compiling and Running Code Using Classes (Not Class Templates)
	Compiling and Running Code Using Class Templates
	Writing Code Using Microsoft Visual Studio 2005
	Opening a Project in Microsoft Visual Studio 2005 That You Have Already Created
	When Things Really Get Screwed Up
	UNIX Compilers
Index
	A
	B
	C
	D
	E
	F
	G
	H
	I
	J
	K
	L
	M
	N
	O
	P
	Q
	R
	S
	T
	U
	V
	W