We have studied fixed-size data structures such as one-dimensional arrays, two-dimensional arrays and structs. This chapter introduces dynamic data structures that grow and shrink during execution. Linked lists are collections of data items "lined up in a row"insertions and removals are made anywhere in a linked list. Stacks are important in compilers and operating systems: Insertions and removals are made only at one end of a stackits top. Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and removals are made from the front (also referred to as the head) of a queue. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, representation of file system directories and compilation of expressions into machine language. These data structures have many other interesting applications.

We discuss several popular and important data structures and implement programs that create and manipulate them. We use classes, class templates, inheritance and composition to create and package these data structures for reusability and maintainability.

Studying this chapter is solid preparation for Chapter 23, Standard Template Library (STL). The STL is a major portion of the C++ Standard Library. The STL provides containers, iterators for traversing those containers and algorithms for processing the elements of those containers. You will see that the STL has taken each of the data structures we discuss in this chapter and packaged them into templatized classes. The STL code is carefully written to be portable, efficient and extensible. Once you understand the principles and construction of data structures as presented in this chapter, you will be able to make the best use of the prepackaged data structures, iterators and algorithms in the STL, a world-class set of reusable components.

The chapter examples are practical programs that you will be able to use in more advanced courses and in industry applications. The programs employ extensive pointer manipulation. The exercises include a rich collection of useful applications.

We encourage you to attempt the major project described in the special section Building Your Own Compiler. You have been using a C++ compiler to translate your programs to machine language so that you could execute these programs on your computer. In this project, you will actually build your own compiler. It will read a file of statements written in a simple, yet powerful, high-level language similar to early versions of the popular language BASIC. Your compiler will translate these statements into a file of Simpletron Machine Language (SML) instructionsSML is the language you learned in the Chapter 8 special section, Building Your Own Computer. Your Simpletron Simulator program will then execute the SML program produced by your compiler! Implementing this project using an object-oriented approach will give you a wonderful opportunity to exercise most of what you have learned in this book. The special section carefully walks you through the specifications of the high-level language and describes the algorithms you will need to convert each type of high-level language statement into machine-language instructions. If you enjoy being challenged, you might attempt the many enhancements to both the compiler and the Simpletron Simulator suggested in this chapter's exercises.

Introduction to Computers, the Internet and World Wide Web

Introduction to C++ Programming

Introduction to Classes and Objects

Control Statements: Part 1

Control Statements: Part 2

Functions and an Introduction to Recursion

Arrays and Vectors

Pointers and Pointer-Based Strings

Classes: A Deeper Look, Part 1

Classes: A Deeper Look, Part 2

Operator Overloading; String and Array Objects

Object-Oriented Programming: Inheritance

Object-Oriented Programming: Polymorphism


Stream Input/Output

Exception Handling

File Processing

Class string and String Stream Processing

Web Programming

Searching and Sorting

Data Structures

Bits, Characters, C-Strings and structs

Standard Template Library (STL)

Other Topics

Appendix A. Operator Precedence and Associativity Chart

Appendix B. ASCII Character Set

Appendix C. Fundamental Types

Appendix D. Number Systems

Appendix E. C Legacy Code Topics

Appendix F. Preprocessor

Appendix G. ATM Case Study Code

Appendix H. UML 2: Additional Diagram Types

Appendix I. C++ Internet and Web Resources

Appendix J. Introduction to XHTML

Appendix K. XHTML Special Characters

Appendix L. Using the Visual Studio .NET Debugger

Appendix M. Using the GNU C++ Debugger


C++ How to Program
C++ How to Program (5th Edition)
ISBN: 0131857576
EAN: 2147483647
Year: 2004
Pages: 627 © 2008-2020.
If you may any questions please contact us: