This is a book for students and instructors who love programming in object-oriented style. The authors understand how to write object-oriented code and how to explain it to students. The strength of the book comes from the single-minded focus that we have had throughout the writing of it, on explaining the code thoroughly and consistently. Normally, books on data structures and software in general, do an excellent job explaining the algorithm but somehow fail to follow up the rigor of the algorithm with the clarity of the code resulting from it. It is almost as if the designers wave a wand and utter the magic words "abraca dabra" and the code jumps out. We have consciously made an effort to connect the linkages that exist naturally between different phases of data structures design, and implementation. The second, perhaps more important, development is the use of STL or Standard Template Library in some texts. Experience professors who teach data structures are pretty evenly split between teaching data structures by designing them ground up and teaching data structures using STL.
Each approach has its merits and demerits. Our book, while adhering to designing most data structures from the scratch also employs STL for those who want to follow this approach. We believe this balance is much needed.
Complex data structures are best explained in object-oriented style. Object-oriented design is language independent but its implementation benefits from a language that is designed as object-oriented from the scratch. The popular object-oriented languages that are in vogue today include C++, Java, C#, and Smalltalk. Although many books do use C++ or Java as the programming language of implementation, in our opinion, they do not fully take advantage of the object-oriented features available in the languages but instead simply translate the code from C or Pascal. The techniques we have used have been explained thoroughly and used consistently in the textbook.
To facilitate an understanding of our approach to implementing data structures, we have used a pattern containing the following salient characteristics:
• Defining a data structure as an abstract data type;
• Providing type information about data that will be stored in the structure; we have used templates for all data that is stored in the data structures,
• determine what errors will require exceptions to be thrown and write the exception class hierarchy;
• write an abstract base class for the data structure so that we could implement it more than one way, if necessary;
• determine the fields required in the C++ class and write the constructors to initialize those fields and destructors to dispose of them;
• write accessor methods to allow the user to examine the fields;
• write insertion and deletion methods (and other methods if necessary);
• design an Enumeration class for the data structure;
• write an ostream < method;
• write a test method for the class, which can be called from a main() function.
In addition, the text provides a suite of STL methods to illustrate a complementary approach.
"Complete coverage of many data structures with complete implementation"
We have designed and implemented many data structures. We also employ STL for the sake of completeness and broader coverage. We have developed the implementation of each data structure systematically and explained the development of code consistently. One can consider this book to be even alternatively titled as "Data Structures Featuring C++: Code Explained." In our teaching experience (a combined 45 years), students are better learners of programming when provided with code for reading and testing. Many current textbooks on data structures fall short of this goal.