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__
) 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.
| 5 | 6