C++ How to Program, 4/e Tour of the Book (Continued)
Chapter 17 Data Structures
discusses the techniques used to create
and manipulate dynamic data structures. The chapter begins with discussions of
self-referential classes and dynamic memory allocation, then proceeds with a
discussion of how to create and maintain various dynamic data structures,
including linked lists, queues (or waiting lines), stacks and trees. For each
type of data structure, we present complete, working programs and show sample
outputs. The chapter also helps the student master pointers. The chapter
includes abundant examples that use indirection and double
indirection—particularly difficult concepts. One problem when working with
pointers is that students have trouble visualizing the data structures and how
their nodes are linked together. We have included illustrations that show the
links and the sequence in which they are created. The binary-tree example is a
superb capstone for the study of pointers and dynamic data structures. This
example creates a binary tree, enforces duplicate elimination and introduces
recursive preorder, inorder and postorder tree traversals. Students have a
genuine sense of accomplishment when they study and implement this example.
They particularly appreciate seeing that the inorder traversal prints the node
values in sorted order. We include a substantial collection of exercises. A
highlight of the exercises is the special section "Building Your Own
Compiler." The exercises walk the student through the development of an
infix-to-postfix-conversion program and a postfix-expression-evaluation
program. We then modify the postfix-evaluation algorithm to generate
machine-language code. The compiler places this code in a file (using the
techniques of Chapter ). Students then run the machine language produced
by their compilers on the software simulators they built in the exercises of
Chapter . The 47 exercises include recursively searching a list,
recursively printing a list backwards, binary-tree node deletion, level-order
traversal of a binary tree, printing trees, writing a portion of an optimizing
compiler, writing an interpreter, inserting/deleting anywhere in a linked
list, implementing lists and queues without tail pointers, analyzing the
performance of binary-tree searching and sorting, implementing an indexed-list
class and a supermarket simulation that uses queueing. After studying Chapter
, the reader is prepared for the treatment of STL containers, iterators and
algorithms in Chapter . The STL containers are pre-packaged, templatized
data structures that most programmers will find sufficient for the vast
majority of applications they will need to implement. STL is a giant leap
forward in achieving the vision of reuse.
Chapter 18 Bits, Characters, Strings and Structures
Presents a
variety of important features. C++'s powerful bit-manipulation capabilities
enable programmers to write programs that exercise lower-level hardware
capabilities. This helps programs process bit strings, set individual bits and
store information more compactly. Such capabilities, often found only in
low-level assembly languages, are valued by programmers writing system
software, such as operating systems and networking software. As you recall, we
introduced C-style char
* string
manipulation in Chapter and presented the most popular
string-manipulation functions. In Chapter , we continue our presentation
of characters and C-style char
* strings.
We present the various character-manipulation capabilities of the
<cctype> library—these include the ability to test a character to determine whether it
is a digit, an alphabetic character, an alphanumeric character, a hexadecimal
digit, a lowercase letter or an uppercase letter. We present the remaining
string-manipulation functions of the various string-related libraries; as
always, every function is presented in the context of a complete, working C++
program. Structures in C++ are like records in other languages— they aggregate
data items of various types. A feature of the chapter is its high-performance
card-shuffling and dealing simulation. This is an excellent opportunity for
the instructor to emphasize the quality of algorithms. The 91 exercises
encourage the student to try out most of the capabilities discussed in the
chapter. The feature exercise leads the student through the development of a
spelling-checker program. Are mostly the "C legacy" portion of C++. In particular, this
chapter presents a deeper treatment of C-like,
char
* strings for the
benefit of C++ programmers who are likely to work with C legacy code. Again,
Chapter discusses class string and discusses manipulating strings as full-fledged objects.
Chapter 19 Preprocessor
Provides detailed discussions of the
preprocessor directives. The chapter includes more complete information on the #include directive, which causes a copy of a specified file to be included in place of
the directive before the file is compiled and the
#define directive
that creates symbolic constants and macros. The chapter explains conditional
compilation for enabling the programmer to control the execution of
preprocessor directives and the compilation of program code. The
# operator that
converts its operand to a string and the
## operator that concatenates two tokens are
discussed. The various predefined preprocessor symbolic constants (__LINE__, __FILE__, __DATE__, __STDC__, __TIME__ and __TIMESTAMP__)
are presented. Finally, macro assert of the header file <cassert> is discussed, which is valuable in program testing, debugging, verification
and validation.
Chapter 20 C Legacy-Code Topics
Presents additional topics
including several advanced topics not ordinarily covered in introductory
courses. We show how to redirect program input to come from a file, redirect
program output to be placed in a file, redirect the output of one program to
be the input of another program (piping) and append the output of a program to
an existing file. We develop functions that use variable-length argument lists
and show how to pass command-line arguments to function
main and use them
in a program. We discuss how to compile programs whose components are spread
across multiple files, register functions with
atexit to be
executed at program termination and terminate program execution with function exit. We
also discuss the const and volatile type qualifiers, specifying the type of a numeric constant using the integer
and floating-point suffixes, using the signal-handling library to trap
unexpected events, creating and using dynamic arrays with
calloc and
realloc, using unions as a
space-saving technique and using linkage specifications when C++ programs are
to be linked with legacy C code. As the title suggests, this chapter is
intended primarily for C++ programmers who will be working with C legacy code.