1 Introduction

1-1 Pseudocode

Algorithm Header

Purpose,Conditions,and Return

Statement Numbers

Variables

Algorithm Analysis

Statement Constructs

Pseudocode Example

1-2 The Abstract Data Type

Data Structure

Atomic and Composite Data

Abstract Data Type

1-3 A Model for an Abstract Data Type

ADT Operations

ADT Data Structure

ADT Class Templates

1-4 Algorithm Efficiency

Linear Loops

Logarithmic Loops

Nested Loops

Big-O Notation

Standard Measures of Efficiency

Big-O Analysis Examples

1-5 Summary

1-6 Practice Sets

Exercises

Problems

Projects

2 Searching

2-1 List Searches

Sequential Search

Variations on Sequential Searches

Binary Search

Binary Search Algorithm

Analyzing Search Algorithms

2-2 C++ Search Algorithms

Sequential Search in C++

Binary Search in C++

Search Example

2-3 Hashed List Searches

Basic Concepts

Hashing Methods

Hashing Algorithm

2-4 Collision Resolution

Open Addressing

Bucket Hashing

Linked List Resolution

Hash List Example

Combination Approaches

2-5 Summary

2-6 Practice Sets

Exercises

Problems

Projects

3 Linked Lists

3-1 Linear List Concepts

Insertion

Deletion

3-2 Linked List Concepts

Retrieval

Traversal

Nodes

Linked List Data Structure

Pointers to Linked Lists

3-3 Linked List Algorithms

Create List

Insert Node

Delete Node

Search List

Retrleve Node

Unordered List Search

Full List

Empty List

List Count

Traverse List

Destroy List

3-4 Processing a Linked List

Add Node

Remove Node

Print List

Testing Insert and Delete Logic

Append Lists

3-5 List Applications

Array of Lists

3-6 Complex Linked List Structures

Circularly Linked Lists

Doubly Linked Lists

Multilinked Lists

Multilinked List Insert

Multilinked List Delete

3-7 Building a Linked List-C++Implementation

Data Structure

Application Functions

3-8 List Abstract Data Type-Linked List Implementation

List ADT Declaration

3-9 Summary

3-10 Practice Sets

Exercises

Problems

Projects

4 Stacks

4-1 Basic Stack Operations

Push

Pop

Data Structure

4-2 Stack Linked List Implementation

Stack Top

Stack Algorithms

4-3 Stack Applications

Reversing Data

Reverse a List

Convert Decimal to Binary

Parsing

Postponement

Backtracking

4-4 Eight Queens Problem-C++Implementation

Get Board Size

Main Line Logic

4-5 Stack Abstract Data Type Implementation

Data Structure

Stack ADT Implementation

4-6 Stack ADT-Array Implementation

Array Data Structure

Create Stack Array

Push Stack Array

Pop Stack Array

Stack Top Array

Stack Count Array

Full Stack Array

Empty Stack Array

Destory Stack Array

4-7 Summary

4-8 Practice Sets

Exercises

Problems

Projects

5 Queues

5-1 Queue Operations

Enqueue

Dequeue

Queue Rear

Queue Front

Queue Example

5-2 Queue Linked List Design

Data Structure

Queue Algorithms

Create Queue

Enqueue

Dequeue

Retrieving Queue Data

Full Queue

Empty Queue

Queue Count

Destroy Queue

5-3 Queuing Theory

5-4 Queue Applications

Queue Simulation

Categorizing Data

5-5 Categorizing Data-C++Implementation

Main Line Logic

Fill Queues

Print Queues

Print One Queue

Queue Structure

5-6 Queue ADT-Linked List Implementation

Queue ADT Implementation

5-7 Queue ADT-Array Implementation

Array Queues Implementation

5-8 Summary

5-9 Practice Sets

Exercises

Problems

Projects

6 Recursion

6-1 Factorial-A Case Study

Recursion Defined

Recursive Solution

Iterative Solution

6-2 How Recursion Works

6-3 Designing Recursive Algorithms

The Design Methodology

Limitations of Recursion

Design Implementation-Reverse a Linked List

6-4 Another Case Study-Fibonacci Numbers

6-5 The Towers of Hanoi

Recursive Towers Of Hanoi

6-6 C++Implementations of Recursion

Fibonacci Numbers

Prefix to Postfix Conversion

Towers of Hanoi

6-7 Summary

6-8 Practice Sets

Exercises

Problems

Projects

7 Introduction to Trees

7-1 Basic Tree Concepts

Terminology

Tree Representation

7-2 Binary Trees

Properties

Depth-First Traversals

7-3 Binary Tree Traversals

Breadth-First Traversals

7-4 Expression Trees

Infix Traversal

Postfix Traversal

Prefix Traversal

7-5 General Trees

Changing General Tree to Binary Tree

Insertions into General Trees

General Tree Deletions

7-6 Huffman Code

7-7 Summary

7-8 Practice Sets

Exercises

Problems

Projects

8 Search Trees

8-1 Binary Search Trees

Definition

Operations on Binary Search Trees

Binary Search Tree Search Algorithms

8-2 AVL Trees

Balancing Trees

AVL Balance Factor

AVL Node Structure

AVL Delete Algorithm

Adjusting the Balance Factors

8-3 AVL Tree Implementation

Data Structure

Program Design

Count Words Summary

8-4 AVL Abstract Data Type

AVL Tree Data Structures

AVL Tree Functions

AVL Tree Data Processing

AVL Tree Utility Functions

8-5 Summary

8-6 Practice Sets

Exercises

Problems

Projects

9 Heaps

9-1 Heap Definition

9-2 Heap Structure

9-3 Basic Heap Algorithms

ReheapUp

ReheapDown

9-4 Heap Data Structure

9-5 Heap Algorithms

ReheapUp

ReheapDown

BuildHeap

InsertHeap

DeleteHeap

9-6 Heap Applications

Selection Algorithms

Priority Queues

9-7 A Heap Program

Heap Program Design

Heap Functions

9-8 Summary

9-9 Practice Sets

Exercises

Problems

Projects

10 Multiway Trees

10-1 m-Way Search Trees

10-2 B-Trees

B-Tree Insertion

B-Tree Insert Design

B-Tree Insert Node

B-Tree Deletion

Traverse B-Tree

B-Tree Search

10-3 Simplified B-Trees

2-3 Tree

2-3-4 Tree

10-4 B-Tree Variations

B*Tree

B+Tree

10-5 Lexical Search Tree

Tries

Utility Functions

Header File

Trie Structure

10-6 B-Tree Abstract Data Type

Insert Algorithms

Delete Algorithms

10-7 Summary

10-8 Practice Sets

Exercises

Problems

Projects

11 Advanced Sorting Concepts

Sort Order

11-1 General Sort Concepts

Sort Stability

Sort Efficiency

Passes

11-2 Insertion Sorts

Straight Insertion Sort

Shell Sort

Insertion Sort Algorithms

Insertion Sort Implementation

11-3 Selection Sorts

Straight Selection Sort

Selection Sort Algorithms

Selection Sort Implementation

11-4 Exchange Sorts

Bubble Sort

Bubble Sort Algorithm

Quick Sort

Exchange Sort Algorithms

11-5 Summary

Exchange Sort Implementation

11-6 External Sorts

Merging Ordered Files

Merging Unordered Files

The Sorting Process

Sort Phase Revisited

11-7 Summary

11-8 Practice Sets

Exercises

Problems

Projects

12 Graphs

12-1 Terminology

12-2 Operations

Add Vertex

Find Vertex

Delete Edge

Add Edge

Delete Vertex

Traverse Graph

12-3 Graph Storage Structures

Adjacency Matrix

Adjacency List

12-4 Graph Algorithms

Create Graph

Insert Vertex

Delete Vertex

Insert Arc

Delete Arc

Retrieve Vertex

First Arc

Depth-First Traversal

Breadth-First Traversal

12-5 Networks

Minimum Spanning Tree

Shortest Path Algorithm

12-6 Abstract Data Type

Insert Vertex

Delete Vertex

Insert Arc

Delete Arc

Depth-First Traversal

Breadth-First Traversal

12-7 Summary

12-8 Practice Sets

Exercises

Problems

Projects

Appendixes

A ASCII Tables

B Structure Charts

C Program Standards and Styles

D Random Numbers

E Standard C++Libraries

F C++Function Prototypes

G Classes Related to Input and Output

H The String Class

I Pointers to Functions

J Inheritance

K C++Templates

L Standard Template Library

Solutions to Selected Exercises

Glossary

Index