Drozdek A. Data Structures and Algorithms in C++

Brooks/Cole, 2001, -665 p.The study of data structures, a fundamental component of a computer science education, serves as the foundation upon which many other computer science fields are built. Some knowledge of data structures is a must for students who wish to do work in design implementation, testing, or maintenance of virtually any software system. The scope and presentation of material in Data Structures and Algorithms in C++ provide students with the necessary knowledge to perform such work.
This book highlights three important aspects of data structures. First, a very strong emphasis is placed on the connection between data structures and their algorithms, including analyzing algorithms' complexity. Second, data structures are presented in the object-oriented setting in accordance with the current design and implementation paradigm. In particular, the information-hiding principle to advance encapsulation and decomposition is stressed. Finally, an important component of the book is data structure implementation, which leads to the choice of C++ as the programming language.
The language C++, an object-oriented descendant of C, is widespread in industry and academia as an excellent programming language. It is also useful and natural for introducing data structures. Traditionally, Pascal has been used to teach data structures, although Modula-2 and Ada have also been used. However, because of the wide use of C++ in application programming and the object-oriented characteristics of the language, using C++ to teach a data structures and algorithms course, even on the introductory level, is well justified.
This book provides the material for a course that includes the topics listed under CS2 and CS7 of the old ACM curriculum. It also meets the requirements for most of the courses C^ 202, CD 202, and CF 204 of the new ACM curriculum.
Most chapters include a case study that illustrates a complete context in which certain algorithms and data structures can be used. These case studies were chosen from different areas of computer science such as interpreters, symbolic computation, and file processing, to indicate the wide range of applications to which topics under discussion may apply.
Brief examples of C++ code are included throughout the book to illustrate the practical importance of data structures. However, theoretical analysis is equally important, so presentations of algorithms are integrated with analyses of efficiency.
Great care is taken in the presentation of recursion because even advanced students have problems with it. Our experience has shown that recursion can be explained best if the run-time stack is taken into consideration. Changes to the stack are shown when tracing a recursive function not only in the chapter on recursion but in other chapters as well. For example, a surprisingly short function for tree traversal may remain a mystery if work done by the system on the run-time stack is not included in the explanation. Standing aloof from the system and retaining only a purely theoretical perspective when discussing data structures and algorithms are not necessarily helpful.
The thrust of this book is data structures, and other topics are treated here only as much as necessary to ensure a proper understanding of this subject. Algorithms are discussed from the perspective of data structures so that the reader will not find a comprehensive discussion of different kinds of algorithms and all the facets that a full presentation of algorithms requires. However, as mentioned, recursion is covered in depth. In addition, complexity analysis of algorithms is presented in some detail.Object-Oriented Programming Using C++
Complexity Analysis
Linked Lists
Stacks and Queues
Recursion
Binary Trees
Multiway Trees
Graphs
Sorting
Hashing
Data Compression
Memory Management