Data Structures in Java A Laboratory Course (Sandra Andersen) (z-library.sk, 1lib.sk, z-lib.sk)

TEAMFL Y Team-Fly®

DATA STRUCTURES IN JAVA Sandra Andersen Concordia College JONES AND BARTLETT PUBLISHERS Sudbury, Massachusetts BOSTON TORONTO LONDON SINGAPORE A Laboratory Course

Copyright © 2002 by Jones and Bartlett Publishers, Inc. Library of Congress Cataloging-in-Publication Data Andersen, Sandra. Data structures in Java: a laboratory course / Sandra Andersen. p. cm. ISBN 0-7637-1816-5 1. Java (Computer program language) 2. Data structures (Computer science) I. Title. QA76.73.J38 A46 2001 005.13’3—dc21 2001050446 All rights reserved. No part of the material protected by this copyright notice may be reproduced or utilized in any form, electronic or mechanical, including photocopying, recording, or any information storage or retrieval system, without written permission from the copyright owner. Editor-in-Chief: J. Michael Stranz Development and Product Manager: Amy Rose Production Assistant: Tara McCormick Composition: Northeast Compositors Cover Design: Kristin Ohlin Printing and Binding: Courier Stoughton Cover printing: Courier Stoughton This book was typeset in FrameMaker 5.5 on a Macintosh G4. The font families used were Rotis Sans Serif, Rotis Serif, and Prestige Elite. Printed in the United States of America 05 04 03 02 01 10 9 8 7 6 5 4 3 2 1 World Headquarters Jones and Bartlett Publishers 40 Tall Pine Drive Sudbury, MA 01776 978-443-5000 info@jbpub.com www.jbpub.com Jones and Bartlett Publishers Canada 2406 Nikanna Road Mississauga, ON L5C 2W6 CANADA Jones and Bartlett Publishers International Barb House, Barb Mews London W6 7PA UK

To my family and friends, for their love and encouragement. —S.A.

v Preface TO THE STUDENT Objectives To learn a subject such as computer science, you need to immerse yourself in it — learning by doing rather than by simply observing. Through the study of several classic data structures and algorithms, you will become a better informed and more knowledgeable computer science stu- dent and programmer. To be able to professionally choose the best algorithm and data structure for a particular set of resource constraints takes practice. An emphasis on learning by doing is used throughout Data Structures in Java: A Laboratory Course. In each laboratory, you explore a particular data structure by implementing it. As you create an implementation, you learn how the data structure works and how it can be applied. The resulting implementation is a working piece of software that you can use in later laborato- ries and programming projects. Organization of the Laboratories Each laboratory consists of four parts: Prelab, Bridge, In-lab, and Postlab. The Prelab is a home- work assignment in which you create an implementation of a data structure using the tech- niques that your instructor presents in lecture, along with material from your textbook. In the Bridge exercise, you test and debug the software you developed in the Prelab. The In-lab phase consists of three exercises. The first two exercises apply or extend the concepts introduced in the Prelab. In the third exercise, you apply the data structure you created in the Prelab to the solution of a problem. The last part of each laboratory, the Postlab, is a homework assignment in which you analyze a data structure in terms of its efficiency or use. Your instructor will specify which exercises you need to complete for each laboratory. Be sure to check whether your instructor wants you to complete the Bridge exercise prior to your lab period or during lab. Use the cover sheet provided with the laboratory to keep track of the exer- cises you have been assigned. Student Source Code The Student Source Code that accompanies this manual (which is available at http:// www.oodatastructures.jbpub.com) contains a set of tools that make it easier for you to create data structure implementations. Each laboratory includes a visualization method called show- Structure that displays a given data structure. You can use this method to watch how your rou- tines change the content and organization of the data structure. Each laboratory also includes an interactive test program that you can use to help you test and debug your work.

PREFACE vi Additional files containing data, partial solution shells, and other supporting routines also are provided in the source code. The file Readme.txt lists the files used in each laboratory. TO THE INSTRUCTOR Objective Laboratories are a way of involving students as active, creative partners in the learning process. By making the laboratories the focal point of the course, students are immersed in the course material. Students are thus challenged to exercise their creativity (in both programming and analysis) and yet receive the structure, feedback, and support that they need to meet the chal- lenge. Organization of the Laboratories In this manual, the laboratory framework includes a creative element but shifts the time-inten- sive aspects outside of the closed laboratory period. Within this structure, each laboratory includes four parts: Prelab, Bridge, In-lab, and Postlab. Prelab The Prelab exercise is a homework assignment that links the lecture with the laboratory period. In the Prelab, students explore and create on their own and at their own pace. Their goal is to synthesize the information they learn in lecture with material from their textbook to produce a working piece of software, usually an implementation of an abstract data type (ADT). A Prelab assignment—including a review of the relevant lecture and textbook materials—typically takes an evening to complete (that is, four to five hours). Bridge The Bridge exercise asks students to test the software they developed in the Prelab. The stu- dents create a test plan that they then use as a framework for evaluating their code. An interac- tive, command-driven test program is provided for each laboratory, along with a visualization routine (showStructure) that allows students to see changes in the content and organization of a data structure. This assignment provides an opportunity for students to receive feedback on their Prelab work and to resolve any difficulties they might have encountered. It should take students approximately one hour to finish this exercise. In-lab The In-lab section takes place during the actual laboratory period (assuming you are using a closed laboratory setting). Each In-lab consists of three exercises, and each exercise has a dis- tinct role. The first two exercises stress programming and provide a capstone to the Prelab. In

PREFACE vii Exercise 3, students apply the software they developed in the Prelab to a real-world problem that has been honed to its essentials to fit comfortably within the closed laboratory environ- ment. Exercises 1 and 2 take roughly 45 minutes each to complete. Exercise 3 can be com- pleted in approximately one and one-half hours. Most students will not be able to complete all the In-lab exercises within a typical closed labora- tory period. A range of exercises has been provided so that you can select those that best suit your laboratory environment and your students’ needs. Postlab The last phase of each laboratory is a homework assignment that is done following the labora- tory period. In the Postlab, students analyze the efficiency or utility of a given data structure. Each Postlab exercise should take roughly 20 minutes to complete. Using the Four-Part Organization in Your Laboratory Environment Computer science instructors use the term laboratory to denote a broad range of environments. One group of students in a data structures course, for example, might attend a closed two-hour laboratory; at the same time, another group of students might take the class in a televised for- mat and “attend” an open laboratory. This manual has been developed to create a laboratory format suitable for a variety of open and closed laboratory settings. How you use the four-part organization depends on your laboratory environment. Two-Hour Closed Laboratory Prelab Students attending a two-hour closed laboratory are expected to make a good-faith effort to complete the Prelab exercise before coming to the lab. Their work need not be perfect, but their effort must be real (roughly 80 percent correct). Bridge Students are asked to complete the test plans included in the Bridge exercise and to begin testing and debugging their Prelab work prior to coming to lab (as part of the 80 percent correct guideline). In-lab The first hour of the laboratory period can be used to resolve any problems the students might have experienced in completing the Prelab and Bridge exercises. The intent is to give constructive feedback so that students leave the lab with working Prelab software - a significant accomplishment on their part. During the second hour, students complete one of the In-lab exercises to reinforce the concepts learned in the Prelab. You can choose the exercise by section or by student, or you can let the students decide which one to complete. Students leave the lab having received feedback on their Prelab and In-lab work. You need not rigidly enforce the hourly divisions; a mix of activities keeps everyone interested and moti- vated.

PREFACE viii Postlab After the lab, the students complete one of the Postlab exercises and turn it in during their next lab period. One-hour Closed Laboratory Prelab If there is only one hour for the closed laboratory, students are asked to complete both the Prelab and Bridge exercises before they come to the lab. This work is turned in at the start of the period. In-lab During the laboratory period, the students complete one of the In-lab exercises. Postlab Again, the students complete one of the Postlab exercises and submit it during their next lab period. Open Laboratory In an open laboratory setting, the students are asked to complete the Prelab and Bridge exer- cises, one of the In-lab exercises, and one of the Postlab exercises. You can stagger the submis- sion of these exercises throughout the week or have students turn in the entire laboratory as a unit. ADAPTING THE MANUAL TO YOUR COURSE Student preparation This manual assumes that students have a background in C, C++, or Java. The first laboratory introduces the use of classes to implement a simple ADT. Succeeding laboratories introduce more complex Java language features (abstract window toolkit, cloning, inheritance, and so forth) in the context of data structures that use these features. Order of Topics Each of us covers the course material in the order that we believe best suits our students’ needs. To give instructors flexibility in the order of presentation, the individual laboratories have been made as independent of one another as possible. It is recommended that you begin with the fol- lowing sequence of laboratories. Laboratory 1 (Logbook ADT) Introduces the implementation of an ADT using a built-in Java class Laboratory 2 (Point List ADT) or Laboratory 3 (String ADT) Introduces tokenized input and the use of the abstract window toolkit Laboratory 4 (Array Implementation of the List ADT) Introduces use of a Java interface Laboratory 5 (Stack ADT) Introduces linked lists

PREFACE ix You might wonder why the performance evaluation laboratory is near the end of the manual (Laboratory 15). The reason is simple: everyone covers this topic at a different time. Rather than bury it in the middle of the manual, it is near the end so that you can include it where it best serves your and your students’ needs (I do it toward the end of the semester, for instance). Since it is important to introduce students to problems that are broad in scope, Laboratory 16 is a multi-week programming project in which students work in teams to solve a more open- ended problem. This laboratory gives students practice in using widely accepted object-ori- ented analysis and design techniques. It also gives students some experience with HTML which, like Java, is another common component of web page development. During the first week, each team analyzes a problem in terms of objects and then develops a design for the problem. During the second week, they create and test an implementation based on their design. Laboratory 16 begins by walking students through the design and implementation of a simple child’s calculator program. The software development framework used in this example stresses object-oriented design and programming, iterative code development, and systematic testing. The students then apply this framework to the solution of a more challenging—and more inter- esting—problem. This laboratory exercise aids in structuring the dynamics of the team software development process; however, it can also be assigned as an individual project simply by giving the students more time to complete the project. ADT Implementation The laboratories are designed to complement a variety of approaches to implementing each ADT. All ADT definitions stress the use of data abstraction and generic data elements. As a result, you can adapt them with minimal effort to suit different implementation strategies. For each ADT, class definitions that frame an implementation of the ADT are given as part of the corresponding Prelab exercise. This definition framework is also used in the visualization method that accompanies the laboratory. Should you elect to adopt a somewhat different imple- mentation strategy, you need only make minor changes to the data members in the class defini- tions and corresponding modifications to the visualization routine. You do not need to change anything else in either the supplied software or the laboratory text itself. Differences between the Manual and Your Text Variations in style between the approaches used in the textbook and the laboratory manual dis- courage students from simply copying material from the textbook. Having to make changes, however slight, encourages students to examine in more detail how a given implementation works. Combining the Laboratories with Programming Projects One goal in the design of these laboratories was to enable students to produce code in the labo- ratory that they can use again as part of larger, more applications-oriented programming

PREFACE x projects. The ADTs the students develop in the Prelab exercises provide a solid foundation for such projects. Reusing the material that they created in a laboratory frees students to focus on the application they are developing. More important, they see in concrete terms—their time and effort—the value of such essential software engineering concepts as code reuse, data abstraction, and object-oriented programming. The last exercise in each In-lab is an applications problem based on the material covered in the Prelab for that laboratory. These exercises provide an excellent starting point for programming projects. Free-form projects are also possible. The projects directory in the Instructor’s files contains a set of programming projects based on the ADTs developed in the laboratories. Student Files Challenging students is easy; helping them to meet a challenge is not. The Student Source Code for this manual is available at http://www.oodatastructures.jbpub.com. It includes a set of soft- ware tools that assist students in developing ADT implementations. The tools provide students with the means for testing an ADT implementation using simple keyboard commands and for visualizing the resulting data structure using ASCII text on a standard text display. Additional files containing data, partial solution shells, and other supporting routines are also included at this site. Instructor’s Files Instructor’s support is available on request from Jones and Bartlett Publishers at http://www.oodatastructures.jbpub.com. This material contains solutions to all the Prelab and In-lab exercises, as well as a set of programming projects compatible with the laboratories in this manual. Contact your sales representative at 800-832-0034 to obtain a password to this site. ACKNOWLEDGMENTS I would like to thank my editors at Jones and Bartlett, Michael Stranz and Amy Rose, for their assistance in guiding this project to completion. I am also grateful to the students in my Fundamentals of Data Structures II course at Concordia College-Moorhead, MN, who helped me class-test many of these laboratory exercises. Their comments and suggestions have improved the quality of the final version of these laboratories. Finally, I owe a debt of thanks to my husband Don for his patience and support while I was working on this project. S.A. TEAMFL Y Team-Fly®

xi Contents Laboratory 1 Logbook ADT 1 Focus: Implementing an ADT using a Java class Application: Generating a calendar display Prelab Exercise 7 Bridge Exercise 13 In-lab Exercise 1 15 In-lab Exercise 2 17 In-lab Exercise 3 19 Postlab Exercise 1 21 Postlab Exercise 2 22 Laboratory 2 Point List ADT 23 Focus: Array implementation of a point list Application: Displaying a dragon curve Prelab Exercise 29 Bridge Exercise 34 In-lab Exercise 1 37 In-lab Exercise 2 39 In-lab Exercise 3 43 Postlab Exercise 1 45 Postlab Exercise 2 46 Laboratory 3 String ADT 47 Focus: Java’s built-in String class Application: Lexical analysis Prelab Exercise 55 Bridge Exercise 57 In-lab Exercise 1 61 In-lab Exercise 2 65 In-lab Exercise 3 70 Postlab Exercise 1 73 Postlab Exercise 2 74

CONTENTS xii Laboratory 4 Array Implementation of the List ADT 77 Focus: Array implementation of a list Application: Analyzing DNA sequences Prelab Exercise 85 Bridge Exercise 88 In-lab Exercise 1 92 In-lab Exercise 2 94 In-lab Exercise 3 96 Postlab Exercise 1 99 Postlab Exercise 2 101 Laboratory 5 Stack ADT 103 Focus: Array and singly linked list implementations of a stack Application: Evaluating postfix arithmetic expressions Prelab Exercise 109 Bridge Exercise 114 In-lab Exercise 1 116 In-lab Exercise 2 117 In-lab Exercise 3 120 Postlab Exercise 1 125 Postlab Exercise 2 128 Laboratory 6 Queue ADT 129 Focus: Array and singly linked list implementations of a queue Application: Simulating the flow of customers through a line Prelab Exercise 135 Bridge Exercise 138 In-lab Exercise 1 140 In-lab Exercise 2 142 In-lab Exercise 3 144 Postlab Exercise 1 147 Postlab Exercise 2 148 Laboratory 7 Singly Linked List Implementation of the List ADT 149 Focus: Singly linked list implementation of a list Application: Slide show program Prelab Exercise 155 Bridge Exercise 157

CONTENTS xiii In-lab Exercise 1 160 In-lab Exercise 2 162 In-lab Exercise 3 164 Postlab Exercise 1 167 Postlab Exercise 2 169 Laboratory 8 Doubly Linked List Implementation of the List ADT 171 Focus: Circular doubly linked list implementation of a list Application: Anagram puzzle Prelab Exercise 177 Bridge Exercise 179 In-lab Exercise 1 181 In-lab Exercise 2 183 In-lab Exercise 3 186 Postlab Exercise 1 189 Postlab Exercise 2 191 Laboratory 9 Ordered List ADT 193 Focus: Array implementation of an ordered list using inheritance Application: Assembling messages in a packet switching network Prelab Exercise 199 Bridge Exercise 203 In-lab Exercise 1 205 In-lab Exercise 2 207 In-lab Exercise 3 209 Postlab Exercise 1 211 Postlab Exercise 2 213 Laboratory 10 Recursion with Linked Lists 215 Focus: Using recursion to process and restructure linked lists Application: Replacing recursion with iteration Prelab Exercise 223 Bridge Exercise 234 In-lab Exercise 1 238 In-lab Exercise 2 242 In-lab Exercise 3 244 Postlab Exercise 1 247 Postlab Exercise 2 248

CONTENTS xiv Laboratory 11 Expression Tree ADT 249 Focus: Linked implementation of an expression tree Application: Logic circuits Prelab Exercise 257 Bridge Exercise 259 In-lab Exercise 1 261 In-lab Exercise 2 264 In-lab Exercise 3 266 Postlab Exercise 1 271 Postlab Exercise 2 273 Laboratory 12 Binary Search Tree ADT 275 Focus: Linked implementation of a binary search tree Application: Indexed accounts database Prelab Exercise 281 Bridge Exercise 283 In-lab Exercise 1 285 In-lab Exercise 2 287 In-lab Exercise 3 289 Postlab Exercise 1 295 Postlab Exercise 2 296 Laboratory 13 Heap ADT 299 Focus: Array implementation of a heap Application: Simulating the flow of tasks in an operating system using a priority queue Prelab Exercise 307 Bridge Exercise 309 In-lab Exercise 1 311 In-lab Exercise 2 313 In-lab Exercise 3 318 Postlab Exercise 1 323 Postlab Exercise 2 324 Laboratory 14 Weighted Graph ADT 325 Focus: Adjacency matrix implementation of the Weighted Graph ADT Application: Computation of shortest paths Prelab Exercise 331 Bridge Exercise 334

CONTENTS xv In-lab Exercise 1 336 In-lab Exercise 2 339 In-lab Exercise 3 342 Postlab Exercise 1 347 Postlab Exercise 2 349 Laboratory 15 Performance Evaluation 351 Focus: Determining execution times Application: Analyzing the execution times of sorting and searching routines Prelab Exercise 357 Bridge Exercise 358 In-lab Exercise 1 360 In-lab Exercise 2 363 In-lab Exercise 3 366 Postlab Exercise 1 369 Postlab Exercise 2 370 Laboratory 16 Team Software Development Project 373 Focus: Object-oriented analysis and design techniques Application: Create a program that generates an HTML noteboard consisting of a set of monthly calendars and associated notes Week 1: Prelab Exercise 1 375 Week 1: Prelab Exercise 2 382 Week 1: Bridge Exercise 390 Week 1: In-lab Exercise 397 Week 2: In-lab Exercise 404 Postlab Exercise 407

1 LABORATORY 1 Logbook ADT OBJECTIVES In this laboratory, you • examine the components that form an abstract data type (ADT) in Java. • implement a programmer-defined ADT in Java. • create a method that displays a logbook in calendar form. • investigate how to overload methods in Java. OVERVIEW Because it is a pure object-oriented programming language, all Java programs contain one or more class (or ADT) definitions. Java defines many built-in classes and hundreds of methods. The purpose of this laboratory is for you to review how you can implement an abstract data type (ADT) of your own design while utilizing some of the built-in ADTs already implemented in Java. We use a monthly logbook as our example ADT. A monthly logbook consists of a set of entries, one for each day of the month. Depending on the logbook, these entries might denote a business’s daily receipts, the amount of time a person spent exercising, the number of cups of coffee consumed, and so forth. A typical logbook is shown below. When specifying an ADT, you begin by describing the elements (or attributes) that the ADT consists of. Then you describe how these ADT elements are organized to form the ADT’s overall structure. In the case of the monthly logbook abstract data type—or Logbook ADT, for short— the elements are the entries associated with the days of the month and the structure is linear: February 2002 1 100 2 95 3 90 4 0 5 150 6 94 7 100 8 105 9 100 10 100 11 50 12 110 13 110 14 100 15 125 16 110 17 0 18 110 19 0 20 125 21 100 22 110 23 115 24 111 25 0 26 50 27 110 28 125

LABORATORY 1 2 the entries are arranged in the same order as the corresponding days. In Java these elements are called the data members of the ADT (or class). Having specified the ADT’s data members, you then define its behavior by specifying the opera- tions that are associated with the ADT. For each operation, you specify what conditions must be true before the operation can be applied (its requirements or precondition) as well as what con- ditions will be true once the operation has completed (its results or postcondition). The Log- book ADT specification below includes operations (or methods in Java) that create a logbook for a given month, store/retrieve the logbook entry for a specific day, and provide general infor- mation about the month. Logbook ADT Elements A set of integer values for a logbook month and its associated calendar. Structure Each integer value is the logbook entry for a given day of the month. The number of logbook entries varies depending on the month for which data is being recorded. We will refer to this month as the logbook month. Each logbook month is actually a calendar month for a particular year. Thus each logbook month starts on a particular day of the week and has a fixed number of days in that month based on our Gregorian calendar. Constructor Logbook ( int month, int year ) Precondition: Month is a valid calendar month between 1 and 12 inclusive. Postcondition: Constructor. Creates an empty logbook for the specified month—that is, a logbook in which all the entries are zero. If month is an invalid value, it will default to today’s date.

LABORATORY 1 3 Methods void putEntry ( int day, int value ) Precondition: Day is less than or equal to the number of days in the logbook month. Postcondition: Stores the value as the logbook entry for the specified day. int getEntry ( int day ) Precondition: Day is less than or equal to the number of days in the logbook month. Postcondition: Returns the logbook entry for the specified day or 1 if there is no such day. int month ( ) Precondition: None. Postcondition: Returns the logbook month. int year ( ) Precondition: None. Postcondition: Returns the logbook year. int daysInMonth ( ) Precondition: None. Postcondition: Returns the number of days in the logbook month.