Each chapter includes a general introduction to the topic, an explanation of the algorithm(s), (in some cases line-by-line descriptions), an example application(s), and comments on improving execution speed, or reducing memory usage. Programmer's Notes
provide reasons behind or recommendations on the algorithm(s) provided.
The code for each example and the file that it belongs too are clearly identified, which makes it easy to understand the program implementation. However, although the code in the book is written using C++, it is written in C
structure, and so is very poorly structured from an Object-Oriented perspective. In most cases the algorithm is coded in the same file as the example application code as one program; rather than with the algorithm as a class with a separate file to drive the object under test. This would make the book a more practical guide for novice C++ programmers, as well as enhancing the reusability of the presented algorithms.
Although some of the chapters use the Microsoft Foundation Classes (MFC) for the graphical interface, the authors state that the book compiles with the ANSI/ISO C++ standard, and so will work with any compiler. However I have not used any code in the book, so I can not confirm this. The authors state that the book's code was tested with Microsoft's Visual C++ compiler.
4 Sep 2001
Sorting
Presents several well-known techniques for sorting data that resides in memory. Algorithms are given for;
- Bubble Sort
- Selection Sort
- Basic Quick Sort
- Enhanced Quick Sort
- Merge Sort
Linked Lists
Explores linked lists and provides examples of their implementation, such as building blocks for stacks, queues, hash tables. Algorithms for integers and as template classes are given for a simple;
- Singly Linked List
- Doubly Linked List
Binary Trees
Algorithms for a;
- Simple Binary Search Tree template class
- Balanced Binary Search Tree template class
are given.
Hash Tables and Sparse Arrays
Introduces the use of hash tables and sparse arrays for optimising the access of some times of data. Covers hash table and sparse array design and includes algorithms for;
- Simple Hash Table with Integer Keys
- Hash Table with char *keys
- One Dimensional Sparse Array
- Two Dimensional Sparse Array
Memory Management for C and C++
Describes reason why you may want to overload the global
new and
delete operators. The algorithms for;
- Overloading the Global New Operator
- Simple Array-Based Allocator
- Simple List-Based Allocator
are given.
Working with Files and Directories
Algorithms for a;
- text file Search and Replace command line utility
- program to recursively search through all the files in a directory tree, (use Win32 API). Some description of the API functions used is given, but does not intend to be exhaustive)
- program to read the contents of a file and display its contents in hex, (command line and Windows versions provided)
are given.
Encryption Fundamentals
The provides an introduction to encryption covering,
- the theory behind Single Key
- the theory behind Public Key
- the theory behind Digital Signitures
- the theory behind the Rivest, Shamir and Adleman (RSA) algorithm
- the Windows Encryption API
- Cryptographic Service Providers (CSPs)
- the CryptoAPI Programming Model, (and how to use its basic functions, including adding digital signatures, and adding CryptoAPI support to MFC programs)
A program which provides encryption support to a simple file viewer program is given.
Managing Source Code
This chapter designs and presents the code for a program to scan code and provide information on the file, namely, list all the included files, create a colourised version of the input file in HTML, indent the lines in the input file according to the rules defined for the language.
Algorithms for a;
- token class to identify the components of the file
- parser, to manipulate the identified tokens
- scanner, to identify the tokens, are given
The program is designed so that it can be modified for different indentation rules and languages.
C/C++ for Internet Access
Introduces the WinSockAPI and the TCP/IP protocol.
- a simple HTML browser that is able to provide basic rendering of an HTML file, (i.e. bold, underlined, italicised fonts and headings, but not graphics)
- using the Windows
CHtmlView internet class to write a simple browser and a MultiSearch
program, which can display four web-pages at a time
are given.
Performing Financial Calculations
Algorithms for;
- computing Straight-Line Depreciation
- computing Sum-of-Years Digits Depreciation
- computing Double-Declining Depreciation
are given.
Algorithms for;
- computing the Future Value Based on a Single Payment
- computing the Future Value Based on a Series of Payments
- computing a Single Payment to Reach a Future Value
- computing the Contributions Necessary to Reach a Specified Future Value
- a Simple Loan Calculator
- computing Retirement Fund Contributions
are given.
Performing Statistical Calculations
Algorithms for;
- computing a Simple Average
- computing a Weighted Mean
- computing a Geometric Mean
- computing a Root Sum Square
- performing linear regression on doubles
are given.
A program to perform a series of tests using a random number generator to show how probabilities approach a limit, is also given.
Creating Fractals with Graphics Routines
The chapter begins with a introduction to fractals and an overview of the MFC document/view architecture. The chapter contains the program to draw a fractal using the Windows CDocument class, (CDC). (The image is drawn direct to screen and is not buffered). The allows the user to draw a Duff fractal, (with limitations due to the implementation of the Ellipse() in the CDC); a Kam Torus fractal; a Julia set fractal; a Mandelbrot fractal.
The description of the fractal calculation code, identifies the parameters that will alter the fractal's properties, allowing the programmer to change how the fractal appears.
An Object-Oriented Expression Parser
The chapter develops, over three successively more complex algorithms, a recursive decent parser that is able to evaluate algebraic expressions, with any numeric type. The parser is also able to work with single character named variables.
Implementing Language Interpreters in C++
The chapter adapts the expression parser developed in chapter 13 to create a language interpreter that is able to handle the syntax for a subset of the BASIC language, (namely PRINT, INPUT, IF, THEN, FOR, NEXT, TO, GOTO, GOSUB, RETURN, END), as well as evaluate algebraic expressions and work with single character named variables.
Exploring the Standard Template Library
The chapter gives an overview of the STL and is aimed at readers who are at least moderately familiar with the STL.
The chapter contains programs for;
- sorting a container, (a vector of integers)
- performing a partial sort on a container, (a vector of integers)
- performing a heap sort of a heap, (that has been created from a vector of integers)
- sorting user defined elements in a container (a vector of employees by name)
- sorting using a user-defined algorithm
- searching a container for the first occurrence of a value, (a vector of integers)
- performing a binary search a container, (a vector of integers)
- using function objects
- reading and writing containers to streams, (cin, cout and to a file
- comparing strings
- finding a subset of strings using the STL Set algorithm
- a prioritised message server, (using the STL priority_queue)
- showing how to create a binary search tree that is able to store elements of any type against a key value. (The program provides a framework to build on, it includes the most essential functionality, including Insert(), Search(), Remove(), Traverse(), (in order), and an iterator for inorder iteration)
C/C++ for CGI Design
Provides an introduction to the CGI (Common Gateway Interface) architecture, the HTTP (HyperText Transport Protocol) transaction and Uniform Resource Locators, (URLs).
The chapter contains programs for;
- a clock component that inserts the current time and date into an HTML page
- to generate a basic form that asks for the user's name, e-mail address, and phone number, processes the user's response when the Send button is clicked, and then provides a reply
