Data Structures and Program Design in C++

About

Features

• Uses the C++ programming language throughout. Briefly reviews the syntax of C++ in chapter 1 and provides a brief introduction to the language in an appendix.

• The text and all programs have been completely written from the Object-Oriented perspective.

  • The book is native C++ making full use of C++ features and object-oriented programming.

• Templates for classes are introduced early and used throughout.

  • Introduces the Standard Template Library (STL).

  • Code for all data structures is developed in fully reusable form (as templated classes).

• Includes informal specification (pre- and postconditions) with all subprograms.

• Recursion is treated early and very thoroughly.

• Features numerous case studies that integrate various topics into programs of various size.

• Simplified treatment of the Life program.

• Simplified treatment of the Big-O and related notations, with additional examples and applications.

• Discusses major principles of software engineering and applies them to large programming projects.

• Reviews several topics (in appendices) that are often missing from student's preparation:

  • Mathematical methods.

  • C++ language features.

• Emphasizes the process of data abstraction and abstract data types (ADTs), separating ADTs from implementation decisions.

• Covers several more advanced,modern topics, e.g.:

  • Splay trees.

  • Red-black trees.

  • Amortized algorithm analysis.

• Contains innovative exercises and programming projects—including continuing projects on information retrieval that request students to compare the performance of several different data structures and algorithms.

Description

76899-4

Object-oriented programming and powerful features of C++ enable this carefully crafted text to build data structures from basic ideas into complete, fully-developed programs and interesting applications. In the process, the text explores problem solving and programming principles, data abstraction, recursion, and the comparative analysis of algorithms as fundamentals tools of software design.

Employing substantial case studies, reusable software development, and programming projects to increase understanding, successful authors Robert L. Kruse and Alexander J.Ryba include topics such as:

• C++ templates are introduced early; code for data structures is developed as templated classes in fully reusable form; the Standard Template Library (STL) is mentioned as appropriate.
• Recursion is treated early and applied throughout the text.
• Data abstraction and abstract data types (ADTs) are emphasized, with conceptual development separated from implementation issues.
• Advanced structures and algorithms are developed into complete programs, including splay trees, B-trees, red-black trees, and graph algorithms such as minimal spanning trees.

Data Structures and Program Design in C++ will prove useful to both computer science students and professionals. The authors supply all code in this book on the Web, and, as well, they provide an excellent instructor support package that includes an Instructor's Resource Manual with transparency masters, solutions, and source code to all of the programming examples and projects in the text.

Sample Content

Table of Contents

 1. Programming Principles.


 2. Introduction to Stacks.


 3. Queues.


 4. Linked Stacked and Queues.


 5. Recursion.


 6. Lists and Strings.


 7. Searching.


 8. Sorting.


 9. Tables and Information Retrieval.


10. Binary Trees.


11. Multiway Trees.


12. Graphs.


13. Case Study: The Polish Notation.


Appendix A: Mathematical Methods.


Appendix B: Random Numbers.


Appendix C: Packages and Utility Functions.


Appendix D: Programming Precepts, Pointers, and Pitfalls.


Index.

Updates

Submit Errata