Excerpts

This text is designed for a two-semester course in data structures and programming. For several years, we have taught a course in data structures to students who have completed a semester course in high-level language programming. We found that a considerable amount of time was spent in teaching programming techniques because the students did not have sufficient background in programming and were unable to implement abstract structures on their own. The brighter students eventually caught on. The weaker students never did. Based on this experience, we have reached the firm conviction that a first course in data structures must go hand-in-hand with a second course in programming. This text is a product of that conviction. The text introduces abstract concepts, shows how they are useful in problem solving, and then shows how the abstractions can be made concrete by using a programming language. Equal emphasis is placed on both the abstract and concrete versions of concepts, so that the students learn about the concept itself, its implementation, and its application. The language used in this text is Java. Java is-well suited to such a course because it contains the control structures necessary to make programs readable and allows basic data structures, such as stacks, linked lists, and trees, to be implemented in a variety of ways. This allows students to appreciate the choices and tradeoffs that face a programmer in a real situation. Java is widely used on many different computers and continues to grow in popularity. The fact that Java is object-oriented allows students to go more easily from abstractions to implementations. The only prerequisite for students using this text is a one-semester course in programming. Students who have had a course in programming using another language can use this text together with an elementary Java text. Chapter 1 provides the information necessary for such students to acquaint themselves with Java. Chapter 1 is an introduction to data structures. Section 1.1 introduces abstract data structures and implementations. Sections 1.2 and 1.3 introduce arrays and classes in Java. Chapter 2 discusses stacks and their Java implementation. Since the stack is the first new data structure introduced, considerable discussion of the pitfalls of implementing it is included. Section 2.3 introduces postfix, prefix, and infix notations. Chapter 3 covers recursion, its applications, and its implementation. Chapter 4 introduces queues, priority queues, and linked lists and their implementations, using arrays of available nodes as well as dynamic storage. Chapter 5 discusses trees, Chapter 6 introduces O notation and covers sorting, and Chapter 7 covers both internal and external searching. Chapter 8 introduces graphs, and chapter 9 discusses storage management. A one-semester course in data structures consists of section 1.1, chapters 2-7, and sections 8.1, 8.2, and part of 8.4. Parts of chapters 3, 6, 7, and 8 can be omitted if time is pressing. This text covers the following knowledge units as described in the report Computing Curricula 2001 of the ACM/IEEECS Joint Curriculum Task Force: PF2 (Algorithms and problem-solving), PF3 (Fundamental data-structures), PF4 (Recursion), DSS (Graphs and trees), ALI (Basic Algorithmic analysis), AU (Fundamental computing algorithms), and PL6 (Object-oriented programming). The book can be used for the following courses of that curriculum: CS 1031 (Data Structures and Algorithms); CS 1121 (Data Abstraction); CS103o (Algorithms and Data Structures); as a supplement to CS 1120 (Object-Oriented Design and Methodology); CS 102s (Algorithms and Programming Techniques) and CS 1038 (Principles of Object-Oriented Design); and as a supplement to CS 112A (Programming Methodology). Algorithms are presented as intermediaries between English-language descriptions and Java programs. They are written in Java style interspersed with English. These algorithms allow the reader to focus on the method used to solve a problem without concern about declaration of variables and the peculiarities of real language. In transforming an algorithm in to a program, we introduce these issues and point out the pitfalls that accompany them. We distinguish between algorithms and programs by presenting the former in italics and the latter in roman. Most of the concepts in the text are illustrated by several examples. Some of these examples are important topics in their own right (e.g., postfix notation, multiword arithmetic) and may be treated as such. Other examples illustrate different implementation techniques (e.g., sequential storage of trees). Instructors are free to cover as many or as few of these examples as they wish. Examples may also be assigned to students as independent reading. It is anticipated that all the examples will not be covered in sufficient detail within the confines of a one- or two-semester course. At the stage of a student's development for which the text is designed, it is more important to cover several examples in great detail than to cover a broad range of topics cursorily. Several additional supplementary materials are available to the instructor. These include chapter objectives and slides of all the figures in the text; solutions (and, when applicable, working code) to the end-of-chapter exercises; working versions of all the code in the text; and approximately one thousand additional exercises to supplement the exercises at the end of each chapter. All the programs and algorithms in this text have been tested and debugged. The programs given in this book were developed using the Sun™Java 2 Standard Edition SDK available at http://java.sun.com/j2se/ . Readers are encouraged to download the Sun™Java 2 Platform as well as the associated documentation in order to develop their own programs. The Forte for Java™, release 3.0, Community Edition IDE may also be useful and is freely available at the aforementioned site. We wish to thank Shalva S. Landy and Edward Mardakhaev for their invaluable assistance in this task. Their zeal for the task was above and beyond the call of duty, and their suggestions were always valuable. Of course, any errors that remain are the sole responsibility of the authors. The exercises vary widely in type and difficulty. Some are drill exercises to ensure comprehension of topics in the text. Others involve modifications of programs or algorithms presented in the text. Still others introduce new concepts and are quite challenging. Often, a group of successive exercises includes the complete development of a new topic that can be used as the basis for a term project or an additional lecture. The instructor should take care in assigning exercises to ensure that they are suitable to the level of the students. We consider it imperative for students to be assigned from five to twelve (depending on difficulty) programming projects per semester. The exercises contain several projects of this type. We would like to thank Sarita Setton-Bakst, Alexander Kaplan, Shalva S. Landy, Marina Marchenko, Edward Mardakhaev, Amani Saleh, Boris Sery, and Nechama Stern for their invaluable assistance. The authors would like to thank Vivienne Esther Langsam for helping us complete the index in the face of a fast approaching deadline. We would like thank the editors and staff at Prentice Hall and especially the reviewers for their helpful comments and suggestions. Finally, we thank our wives, Vivienne Langsam, Gail Augenstein, and Miriam Tenenbaum, for their advice and encouragement during the long and arduous task of producing such a book, and our children and grandchildren, who make it all worthwhile. YEDIDYAH LANGSAM MOSHE AUGENSTEIN AARON M.TENENBAUM Excerpted from Data Structures Using Java by Moshe J. Augenstein, Yedidyah Langsam, Aaron M. Tenenbaum All rights reserved by the original copyright owners. Excerpts are provided for display purposes only and may not be reproduced, reprinted or distributed without the written permission of the publisher.