Kruse - Data Structures and Program Design in C++ (Prentice, 2000).pdf

(5914 KB) Pobierz
Data Structures
and
Program Design
in C++
NAVIGATING THE DISK
For information on using the Acrobat toolbar and other Acrobat commands, 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
icon (go back) in the Acrobat
such a jump, you may return by selecting the
toolbar.
¯
The transparency-projector icon ( ) brings up a transparency master on the
icon (go back) in the Acrobat toolbar.
current topic. Return by selecting the
¯
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
K
RUSE
, R
OBERT
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 (PreTEX, Inc.)
Art Production:
Blake MacLean (PreTEX, Inc.)
Source: Christie’s Images
Cover art:
Orange
, 1923, by Wassily Kandinsky (1866-1944), Lithograph in Colors.
© 2000 by Prentice-Hall, Inc.
Simon & Schuster/A Viacom Company
Upper Saddle River, New Jersey 07458
The typesetting for this book was done with PreTEX, a preprocessor and macro package for the TEX typesetting system
and the P
OST
S
CRIPT
page-description language. PreTEX is a trademark of PreTEX, Inc.; TEX is a trademark of the American
Mathematical Society; P
OST
S
CRIPT
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
10
9
8
7
6
5 4
3 2
1
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
xv
Synopsis
xii
Course Structure
xiv
Supplementary Materials
Book Production
xvi
Acknowledgments
xvi
1.4.7 Program Tracing
28
1.4.8 Principles of Program Testing
29
1
Programming
Principles
2
1.5 Program Maintenance
34
1.5.1 Program Evaluation
34
1.5.2 Review of the Life Program
1.5.3 Program Revision
and Redevelopment
38
35
1
1.1 Introduction
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
1.3.3 Refinement and Modularity
1.4 Coding, Testing,
and Further Refinement
20
1.4.1 Stubs
20
1.4.2 Definition of the Class Life
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
13
15
1.6 Conclusions and Preview
39
1.6.1 Software Engineering
39
1.6.2 Problem Analysis
40
1.6.3 Requirements Specification
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
41
2
Introduction
to Stacks
49
51
55
22
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
2.1.4 Information Hiding
54
2.1.5 The Standard Template Library
v

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin