For one-semester Introductory courses or two-semester courses in data structures (CS-2) in the departments of Computer Science, Computer Engineering, Business, and Management Information Systems. This highly anticipated innovative book by two of the leading CS-1/CS-2 authors focuses the design specification and implementation of ADTs. This book was created from the ground up with objects and Java in mind and shows students how to use and implement key data organizations. Its unique object oriented presentation divides the material into short bite size segments that are organized into small chapters. This makes learning easier for the student and allows for teaching flexibility.
Table of Contents
1. Java Classes.
2. Creating Classes from Other Classes.
3. Designing Classes.
5. List Implementations That Use Arrays.
6. List Implementations That Link Data.
8. Java's Iterator Interfaces.
9. The Efficiency of Algorithms.
11. An Introduction to Sorting.
12. Faster Sorting Methods.
13. Sorted Lists.
14. Inheritance and Lists.
15. Mutable, Immutable, and Cloneable Objects.
18. Dictionary Implementations.
19. Hashing as a Dictionary Implementation.
21. Stack Implementations.
22. Queues, Deques, and Priority Queues.
23. Queue, Deque, and Priority Queue Implementations.
25. Tree Implementations.
26. A Binary Search Tree Implementation.
27. A Heap Implementation.
28. Balanced Search Trees.
30. Graph Implementations.
Appendix A: Java Essentials.
Appendix B: Exception Handling.
Appendix C: File I/O.
Appendix D: Documentation and Programming Style.
Appendix E: Java Resources.
Appendix F: Answers to Self-Test Questions.
Inside covers (end papers).
Unicode Character Codes.
Here is the first edition ofData Structures and Abstractions with Java,a brand-new book for an introductory course in data structures, typically known as CS-2. Readers ofJava: An Introduction to Computer Science & Programmingby Walter Savitch can treat our new book as a sequel. A New Approach This book was created specifically with objects and Java in mind. It is not derived from a previous work written for another programming language. Our approach makes learning easier by focusing the reader's attention on one issue at a time, by providing flexibility in the order in which you can cover topics, and by clearly distinguishing between the specification and implementation of abstract data types, or ADTs. To accomplish these goals, we have divided the material into short, numbered segments that are organized into 30 relatively short chapters. Each segment covers a single idea. Individual chapters deal with either the specification and use of an ADT or its implementations. You can choose to cover the specification of an ADT followed by its various implementations, or you can treat the specification and use of several ADTs before you consider any implementation issues. Our organization makes it easy for you to choose the topic order that you .prefer. Features 30 relatively short chapters can be covered in several orders. Individual but consecutive chapters separate the specification and implementation of ADTs. Short, bite-sized segments focus attention on one issue at a time. Many examples illustrate new concepts. Highlighted notes emphasize key material and provide supplementary comments. Programming tips give additional programming advice. Numerous figures make the presentation visual and accessible. Questions throughout the book--and their answers--elaborate on the material presented. Initial chapters cover Java classes, inheritance, polymorphism, and class design. Java code includes javadoc comments. Appendices review Java basics, exceptions, files, and documentation. A Prentice Hall Companion Website at www.prenhall.com/carrano provides the Java co8e that appears in the book as well as any updates or corrections. Supplements for instructors include PowerPoint slides, laboratory materials, and answers to selected exercises and programming projects. A Note to Students After looking over this preface, you should read the Introduction. There you will quickly see what this book is about and what you need to know about Java before you begin. Appendices A through D review Java and serve as a primer on exceptions, files, and javadoc comments. Note that inside the front and back covers you will find Java's reserved words, the precedence of its operators, and a list of Unicode characters. The topics that we cover in this book are fundamental to your future study of computer science. Even if you do not study all of these topics now, you are likely to encounter them later. We hope that you will enjoy reading the book now, and that it will serve as a useful reference for your future courses. All of the Java code that appears in this book is available for download from the book's companion website at www.prenhall.com/carrano . There you also will find the class SavitchIn that you can use for keyboard input. Appendix A describes this class and provides some examples of its use. Throughout each chapter, you will find questions that should help you to understand the material. The answers to these questions are in Appendix E at the back of the book. Unfortunately, we cannot give you answers to the exercises and programming projects that appear at the end of each chapter, even if you are not enrolled in a class. Only instructors who adopt the bo