Data Structures
and
Program Design
in C
++
NAVIGATING THE DISK
ForinformationonusingtheAcrobattoolbarandotherAcrobatcommands,consult
the Help document within Acrobat. See especially the section “Navigating Pages.”
Material displayed in green enables jumps to other locations in the book, to
transparency masters, and to run sample demonstration programs. These come in
three varieties:
➥ The green menu boxes in the left margin of each page perform jumps to fre-
quently used parts of the book:
➥ Green material in the text itself will jump to the place indicated. After taking
such a jump, you may return by selecting the
// icon (go back) in the Acrobat
toolbar.
➥ The transparency-projector icon ( ) brings up a transparency master on the
current topic. Return by selecting the
// icon (go back) in the Acrobat toolbar.
➥ The Windows ( ) icon in the left margin select and run a demonstration pro-
gram, which will operate only on the Windows platform.
This CD contains a folder
textprog that contains the source code for all programs
and program segments appearing in the book. These files cannot be compiled
directly, but they can be copied and used for writing other programs.
HINTS FOR PAGE NAVIGATION
➥ Each chapter (or other major section) of the book is in a separate pdf file, so
you may start Acrobat directly on a desired chapter.
➥ To find a particular section in the current chapter, hit the Home key, or select
|/ in the Acrobat toolbar or in the green menu bar, which will jump to the
first page of the chapter where there is a table of contents for the chapter.
➥ After jumping to a new location in the book, you can easily return to your
previous location by selecting
// (go back) in the Acrobat toolbar.
➥ To find a particular topic, select the index icon ( ) in the left margin.
➥ To find a particular word in the current chapter, use the binoculars icon in the
Acrobat toolbar.
➥ The PgDown and Enter (or Return) keys advance one screenful, whereas ., ↓,
→, and advance one page. Of these, only will move from the last page of
one chapter to the first page of the next chapter.
➥ To move backwards, PgUp and Shift+Enter move up one screenful, whereas
/, ↑, ←, and move back one page. Of these, only will move from the first
page of one chapter to the last page of the previous chapter.
Data Structures
and
Program Design
in C
++
Robert L. Kruse
Alexander J. Ryba
CD-ROM prepared by
Paul A. Mailhot
Prentice Hall
Upper Saddle River, New Jersey 07458
Library of Congress Cataloging–in–Publication Data
KRUSE,ROBERT L.
Data structures and program design in C++ / Robert L. Kruse,
Alexander J. Ryba.
p. cm.
Includes bibliographical references and index.
ISBN 0–13–087697–6
1. C++ (Computer program language) 2. Data Structures
(Computer Science) I. Ryba, Alexander J. II. Title.
QA76.73.C153K79 1998 98–35979
005.13’3—dc21 CIP
Publisher: Alan Apt
Editor in Chief: Marcia Horton
Acquisitions Editor: Laura Steele
Production Editor: Rose Kernan
Managing Editor: Eileen Clark
Art Director: Heather Scott
Assistant to Art Director: John Christiana
Copy Editor: Patricia Daly
Cover Designer: Heather Scott
Manufacturing Buyer: Pat Brown
Assistant Vice President of Production and
Manufacturing:
David W. Riccardi
Editorial Assistant: Kate Kaibni
Interior Design: Robert L. Kruse
Page Layout: Ginnie Masterson (PreT
E
X, Inc.)
Art Production: Blake MacLean (PreT
E
X, Inc.)
Cover art: Orange, 1923, by Wassily Kandinsky (1866-1944), Lithograph in Colors. Source: Christie’s Images
© 2000 by Prentice-Hall, Inc.
Simon & Schuster/A Viacom Company
Upper Saddle River, New Jersey 07458
The typesetting for this book was done with PreT
E
X, a preprocessor and macro package for the T
E
X typesetting system
and the P
OSTSCRIPT page-description language. PreT
E
X is a trademark of PreT
E
X, Inc.; T
E
X is a trademark of the American
Mathematical Society; P
OSTSCRIPT is a registered trademarks of Adobe Systems, Inc.
The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the re-
search, development, and testing of the theory and programs in the book to determine their effectiveness. The authors
and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documenta-
tion contained in this book. The authors and publisher shall not be liable in any event for incidental or consequential
damages in connection with, or arising out of, the furnishing, performance, or use of these programs.
All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writ-
ing from the publisher.
Printed in the United States of America
10987654321
ISBN 0-13-087697-6
Prentice-Hall International (U.K.) Limited,
London
Prentice-Hall of Australia Pty. Limited, Sydney
Prentice-Hall Canada Inc., Toronto
Prentice-Hall Hispanoamericana, S.A., Mexico
Prentice-Hall of India Private Limited, New Delhi
Prentice-Hall of Japan, Inc., Tokyo
Simon & Schuster Asia Pte. Ltd., Singapore
Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro
Contents
Preface ix
Synopsis xii
Course Structure xiv
Supplementary Materials xv
Book Production xvi
Acknowledgments xvi
1
Programming
Principles
1
1.1 Introduction 2
1.2 The Game of Life 4
1.2.1 Rules for the Game of Life 4
1.2.2 Examples 5
1.2.3 The Solution: Classes, Objects,
and Methods 7
1.2.4 Life: The Main Program 8
1.3 Programming Style 10
1.3.1 Names 10
1.3.2 Documentation and Format 13
1.3.3 Refinement and Modularity 15
1.4 Coding, Testing,
and Further Refinement 20
1.4.1 Stubs 20
1.4.2 Definition of the Class Life 22
1.4.3 Counting Neighbors 23
1.4.4 Updating the Grid 24
1.4.5 Input and Output 25
1.4.6 Drivers 27
1.4.7 Program Tracing 28
1.4.8 Principles of Program Testing 29
1.5 Program Maintenance 34
1.5.1 Program Evaluation 34
1.5.2 Review of the Life Program 35
1.5.3 Program Revision
and Redevelopment 38
1.6 Conclusions and Preview 39
1.6.1 Software Engineering 39
1.6.2 Problem Analysis 40
1.6.3 Requirements Specification 41
1.6.4 Coding 41
Pointers and Pitfalls 45
Review Questions 46
References for Further Study 47
C++ 47
Programming Principles 47
The Game of Life 47
Software Engineering 48
2
Introduction
to Stacks
49
2.1 Stack Specifications 50
2.1.1 Lists and Arrays 50
2.1.2 Stacks 50
2.1.3 First Example: Reversing a List 51
2.1.4 Information Hiding 54
2.1.5 The Standard Template Library 55
v