You can download the file algdscpp.zip, containing the programs of this book, by clicking here.
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.3 Linked Stacks 93
4.4 Linked Queues 96
4.5 Linked Lists 98
4.6 Simple Insertion and Deletion; Inheritance 102
4.7 Ordered Linked Lists 106
4.8 Do-It-Yourself Memory Allocation in an Array 111
4.9 Circular and Doubly-linked Lists 115
4.10 Sorting Linked Lists 121
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