Data Structures: Abstraction and Design Using Java (3rd Edition)
Book Preface
Our goal in writing this book was to combine a strong emphasis on problem solving and software design with the study of data structures. To this end, we discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (a Java class), we then cover case studies that use the data structure to solve a significant problem. Examples include maintaining an ordered list, evaluating arithmetic expressions using a stack, finding the shortest path through a maze, and Huffman coding using a binary tree and a priority queue. In the implementation of each data structure and in the solutions of the case studies, we reinforce the message “Think, then code†by performin a thorough analysis of the problem and then carefully designing a solution (using pseudocode and UML class diagrams) before the implementation. We also provide a performance analysis when appropriate. Readers gain an understanding of why different data structures are needed, the applications they are suited for, and the advantages and disadvantages of their possible implementations.
Intended Audience
This book was written for anyone with a curiosity or need to know about data structures, those essential elements of good programs and reliable software. We hope that the text will be useful to readers with either professional or educational interests. It is intended as a textbook for the second programming course in a computing curriculum involving the study of data structures, especially one that emphasizes Objectâ€Oriented Design (OOD). The text could also be used in a moreâ€advanced course in algorithms and data structures. Besides coverage of the basic data structures and algorithms (lists, stacks, queues, trees, recursion, sorting), there are chapters on sets and maps, balanced binary search trees, graphs, and an online appendix on eventâ€oriented programming. Although we expect that most readers will have completed a first programming course in Java, there is an extensive review chapter (included as an appendix) for those who may have taken a first programming course in a different language, or for those who need a refresher in Java.
Emphasis on the Java Collections Framework
The book focuses on the interfaces and classes in the Java Collections Framework. We begin the study of a new data structure by specifying an abstract data type as an interface, which we adapt from the Java API. Readers are encouraged throughout the text to use the Java Collections Framework as a resource for their programming. Our expectation is that readers who complete this book will be familiar with the data structures available in the Java Collections Framework and will be able to use them in their future programming. However, we also expect that they will want to know how the data structures are implemented, so we provide thorough discussions of classes that implement these data structures. Each class follows the approach taken by the Java designers where appropriate. However, when their industrialâ€strength solutions appear to be too complicated for beginners to understand, we have provided simpler implementations but have tried to be faithful to their approach.
Think, then Code
To help you “Think, then code†we discuss problem solving and introduce appropriate software design tools throughout the textbook. For example, Chapter 1 focuses on OOD and Class Hierarchies. It introduces the Uniform Modeling Language (also covered in Appendix B) to document an OOD. It introduces the use of interfaces to specify abstract data types and to facilitate contract programming and describes how to document classes using Javadocâ€style comments. There is also coverage of exceptions and exception handling. Chapter 2 introduces the Java Collections Framework and focuses on the List interface, and it shows how to use bigâ€O notation to analyze program efficiency. In Chapter 3, we cover different testing strategies in some detail including a discussion of testâ€driven design and the use of the JUnit program to facilitate testing.
Download Ebook | Read Now | File Type | Upload Date |
---|---|---|---|
Download here
|
Read Now | May 30, 2020 |
How to Read and Open File Type for PC ?