John R. Hubbard University of Richmond, jhubbard@richmond.edu
Anita Huray University of Richmond, ahubbard@richmond.edu
Follow this and additional works at: http://scholarship.richmond.edu/bookshelf
Part of the Computer Sciences Commons, and the Mathematics Commons
Recommended Citation Hubbard, J. R., and Anita Huray. Data Structures with Java. Upper Saddle River, NJ: Pearson Prentice Hall, 2004.
NOTE: This PDF preview of Data Structures with Java includes only the preface and/ or introduction. To purchase the full text, please click here. This Book is brought to you for free and open access by UR Scholarship Repository. It has been accepted for inclusion in Bookshelf by an authorized administrator of UR Scholarship Repository. For more information, please contact scholarshiprepository@richmond.edu. .. LN10 rf\-C-. QA Data Structures 7~.g D3.5 with Java™ ,
H5Lf) dCPL\
John R. Hubbard Anita Huray University of Richmond
PEARSON · Prentice~ ~·.Hall
Upper Saddle River, NJ 07458
AJgorllhms + Dala Strucans = ~ - Nlldaus Wirth, 1976
Preface
This book is intended to be used as a textbook for a university course in data structures, the standard CS2 course offered in American universities. It assumes that the student has completed an elemen- tary course in computer programming with Java. A summary of Java fundamental s is provided in Appendix B for students who need to review the language. The book covers all the classical data structures topics: basic concepts in Chapters 1-3, linear data structures (stacks, queues, lists, and tables) in Chapters 4-9, nonlinear data structures (tree and graphs) in Chapters 10-14 and 16, and a substantial treatment of ten sorting algorithm in Chapter 15. It is flexible enough to be used either for a one-semester course in data structures or for a two-semester course in data structures and algorithms. Algorithms are presented explicitly throughout the book. They are introduced in Section 1.5 at a simple level and then studied at progressively deeper levels in later chapters. Complexity analysis is introduced in Section 3.6 and then applied later in chapters 9-16. Loop invariants are finally introduced in Chapter 15 to establish the correctness of the orting algorithms. Some of these advanced topics can easily be omitted in a one-semester CS2 course. The chart on the next page shows the chapter dependencies. It show that the book is flexible enough to support a reordering of some topics. For example, recursion could be done near the beginning of the course, and hash tables could be done at the end of the course. We use the spiral approach on difficult topics. For example, linked tructures are introduced in Chapter 4 as a variant of indirect arrays, and then gradually developed through Chapters 5-8. The book emphasizes the important distinction between abstract data types (ADTs) and their underlying data structure . ADTs are represented by UML diagram and realized as Java inter- faces. Specific data structures, such as arrays and linked lists, are een a backing structures ,for alternative implementations of a given ADT. This important separation of design from implemen- tation is embodied throughout the Java Collections Framework (JCF), which is thoroughly covered in Chapter 7 and Appendix D. Not only does the JCF clarify the value of abstraction, but it also provides the student with many exemplary programming strategies. Although this i a textbook about data structures, the authors are well aware that students in this course are still learning fundamental programming concepts and Java techniques. Accord- ingly, we have included many examples and explanation of topics such as polymorphism, simula- tion, abstract clas es, inner classes, and reflection.
vii viii Preface :tt~T"l----------------------------------------
Chapter 1 Object-Oriented Programming
Chapter 2 Abstract Data Types
Chapter 3 Arrays
Chapter4 Linked Structures
Chapter6 Chapter 5 Chapter?
Queues Stacks Collections
Chapter 8 Lists
Chapter 11 Chapter 9 Trees Hash Tables
Chapter 12 Binary Trees
Chapter 13 Chapter 14 Search Trees Heaps and Priority Queues
Chapter 15 Sorting
Chapter Dependencies
We are firm believers in the old adage, "A picture is worth 1024 words." So you will find extensive illustrations throughout the book. It contains over 350 figures. It could be subtitled "Visual Data Structures." We have also tried to make the book as current as possible. It uses Java 1.4, including new fea- tures such as the assert statement in Chapter 2 and the new Li nkedHash classes in Appendix D. It also uses Unified Modeling Language (UML) diagrams to summarize class definitions and their relationships. Preface ix
The companion website for this book is:
www.prenhall.com/hubbard/ It contains an on-line study guide and Java source code for all the examples in the book. An Instructor's Resource CD is also available. It contains Power Point slides, a test bank for each chapter, and solutions to all the exercises and programming problems in the book. We are grateful for the assistance we have received on this work from our friends at Prentice- Hall and at the University of Richmond. In particular, we wish to thank Matthew Albin, Rom Chan, Natalie Goldberg, Dan Katz, Andrew Lobo, and Molly McCann at Richmond, and Lakshmi Balasubramanian, Petra Reeter, and Camille Trentacoste at Prentice-Hall.We also appre- ciate the suggestions and insights provided by reviewers Benjamin Shults at Western Carolina University, Ted Pawlicki at the University of Rochester, Simon Gray at Ashland University, Frank Coyle at Southern Methodist University, and Bina Ramamurthy at SUNY Buffalo. Finally, we thank our students who used the pre-publication versions in our Data Structures course. JOHN R. HUBBARD ANITAHURAY
