# Ammeraal, L. (1996) Algorithms and Data Structures in C++, Chichester: John Wiley

You can download the file algdscpp.zip, containing the programs of this book, by clicking here.

## Contents

Preface ix

Chapter 1 Some Aspects of Programming in C++ 1
1.1 Introduction 1
1.2 References and Reference Counting 4
1.3 Function Templates 10
1.4 Recursive Functions 12
1.5 Dynamic Arrays, Chunks and Class Templates 16
1.6 Exception Handling 19
Exercises 22

Chapter 2 Arithmetic 23
2.1 Euclid's Algorithm for the GCD 23
2.2 Horner's Rule 24
2.3 Radix Conversion for Input Operations 25
2.4 Radix Conversion for Output Operations 27
2.5 Powers with Integer Exponents 29
2.6 Double-precision Unsigned Integers 30
2.7 Multi-precision Arithmetic 33
2.8 Binomial Coefficients 37
2.9 Decimal Expansion of pi 39
Exercises 43

Chapter 3 Sorting Arrays and Files 45
3.1 Sorting Very Short Lists 45
3.2 Selection Sort 50
3.3 Bubblesort and Shakersort 52
3.4 Insertion Sort 54
3.5 Shellsort 55
3.6 Distribution Counting 56
3.7 The Quicksort Algorithm 58
3.8 The qsort Library Function 65
3.9 Heapsort 70
3.10 Merging and Mergesort 72
3.11 External Sorting 73
3.12 Median and Order Statistics 81
Exercises 84

Chapter 4 Stacks, Queues and Lists 85
4.1 Array Implementation of Stacks 85
4.2 Array Implementation of Queues 90
4.6 Simple Insertion and Deletion; Inheritance 102
4.8 Do-It-Yourself Memory Allocation in an Array 111
4.9 Circular and Doubly-linked Lists 115
4.11 Using a Stack for Recursion Removal 123
Exercises 130

Chapter 5 Searching and String Processing 133
5.1 Sequential Search 133
5.2 Binary Search 134
5.3 Hashing 138
5.4 Text Searching 150
Exercises 157

Chapter 6 Binary Trees 159
6.1 Basic Operations on Binary Search Trees 159
6.2 Perfectly Balanced Binary Trees 166
6.3 Deleting Nodes of Binary Search Trees 177
6.4 AVL Trees 182
Exercises 192

Chapter 7 Btrees 195
7.1 Building and Searching a Btree 195
7.2 Deleting Nodes in a Btree 208
7.3 Btrees on Disk 213
Exercises 227

Chapter 8 Tries, Priority Queues and File Compression 229
8.1 Tries 229
8.2 A Priority Queue Implemented as a Heap 239
8.3 The Huffman Algorithm for File Compression 244
Exercises 252

Chapter 9 Graphs 255
9.1 Directed and Undirected Graphs 255
9.2 Graph Representations 256
9.3 Topological Sorting; Detecting Cycles 257
9.4 Activity Networks; Critical Path Method 263
9.5 Associating Strings with Integers 272
9.6 The Shortest Path Between Two Vertices 275
Exercises 284

Chapter 10 Some Combinatorial Algorithms 285
10.1 A Variable Number of Nested Loops 285
10.2 Permutations 290
10.3 Combinations 297
10.4 The Knapsack Problem 301
10.5 Dynamic Programming 304
Exercises 310

Chapter 11 Fundamentals of Interpreters and Compilers 311
11.1 Syntax Diagrams for a Very Simple Language 311
11.2 A Source-text Interpreter 315
11.3 Conversion from Infix to Postfix 319
11.4 A Postfix Interpreter 323
11.5 Object Program and Runtime System 326
11.6 A VSL Compiler 329
Exercises 333

Appendix A: A Class for Large Integers 335

Bibliography 347

Index 349

Back to list of recent books by the same author
Publisher's web page