Data Structures Featuring C++ A Programmer's Perspective: Data Structures in C++

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.

Sridhar Radhakrishnan is a Professor in the School of Computer Science at The University of Oklahoma, Norman, Oklahoma since the Fall of 1990. Prior to joining The University of Oklahoma, he completed his PhD degree in Computer Science from Louisiana State University, Baton Rouge, Louisiana. He has been teaching the Sophomore level course in Data Structures for many years that resulted in the creation of this textbook. He has published widely and his publications appear in numerous IEEE publications and other professional conferences and journals. Lee Wise has been a software architect and analytics developer for MSCI, Inc., and a predecessor company, RiskMetrics Group, Inc., since 1998. Her particular project, written in C++, has grown from the work of a single programmer to the work of dozens spread across the planet, and from a monolithic program running on a single box to distributed applications running on thousands of cores, handling terabytes of data and processing millions of complex queries per day. Chandra N. Sekharan is a Professor in the Department of Computer Science, Loyola University Chicago. Prior to joining Loyola University Chicago in 1993, he was with the Center for Parallel Computation, Department of Computer Science at University of Central Florida, Orlando. He completed his PhD degree in Mathematical Sciences at Clemson University under the supervision of Stephen Hedetniemi. Prof. Sekharan has taught many courses in computer science at both undergraduate and graduate levels. His recent focus in teaching has been on introducing concepts of parallel computing in the CS2 course at Loyola. He has published in IEEE and ACM conferences extensively in the areas of parallel computation, graph algorithms and mobile networking.