|
Our goal in writing this book was to combine a strong emphasis on problem solving
and software design with the study of data structures. To this end, we discuss applications
of each data structure to motivate its study. After providing the specification
(a header file) and the implementation of an abstract data type, we cover case studies
that use the data structure to solve a significant problem. Examples include a
phone directory using an array and a list, postfix expression evaluation using a stack,
simulation of an airline ticket counter using a queue, and Huffman coding using a
binary tree and a priority queue. In the implementation of each data structure and in
the solutions of the case studies, we reinforce the message “Think, then code” by performing
a thorough analysis of the problem and then carefully designing a solution
(using pseudocode and UML class diagrams) before the implementation. We also
provide a performance analysis when appropriate. Readers gain an understanding of
why different data structures are needed, the applications they are suited for, and the
advantages and disadvantages of their possible implementations.
The text is designed for the second course in programming, especially those that
apply object-oriented design (OOD) to the study of data structures and algorithms.
The text could carry over to the third course in algorithms and data structures for
schools with a three-course sequence. In addition to the coverage of the basic data
structures and algorithms (lists, stacks, queues, trees, recursion, sorting), there are
chapters on sets and maps, balanced binary search trees, and graphs. Although we
expect that most readers will have completed a first programming course in C++,
there is an extensive review chapter for those who may have taken a first programming
course in a different object-oriented language, or for those who need a
refresher in C++.
Think, Then Code To help readers “Think, then code,” we provide the appropriate
software design tools and background in the first two chapters before they begin
their formal study of data structures. The first chapter discusses two different models
for the software life cycle and for object-oriented design (OOD), the use of the
Uniform Modeling Language™ (UML) to document an OOD, and the use of interfaces
to specify abstract data types and to facilitate contract programming. We
develop the solution to an extensive case study to illustrate these principles. The second
chapter focuses on program correctness and efficiency by discussing exceptions
and exception handling, different kinds of testing and testing strategies, debugging
with and without a debugger, reasoning about programs, and using big-O notation.
As part of our emphasis on OOD, we introduce two design patterns in Chapter 3,
the object factory and delegation. We make use of them where appropriate in the
textbook. |
