~ibra, y of Congress Caralogi11g-i11-Publicatio11 Da1a

{RUSE RoBEltT LEROY

Oa1a Struc1urcs ~lnd Progra,n Design in C I
Robert L. Kruse, Bruce P. Leung, Clovis L. T01ldo.

ISBN
p. c,n.
Ir.eludes bibl iographical rererences. Inc ludes index..
0.. 13- 725649-3
I. C (Computer program language)
Ill. Title.
I. Leung, Bruce P. II. Tondo, Clovis L.
Contents
QA76.73.C 15K78 1991
005.13'3-dc20 90-7 161

Editorial production/supervision: Kathleen Schiaparelli

Interior design: Kenny Beck
Cover design: Wanda Lube/ska
Manufacturing buyers: Linda Behrens and Patrice Fraccio
Page layout: Rosemarie Paccione and Roberr Kruse

The typesening for 1his book was done by the authors using PreTi:;X, a preprocessor and macro package
for the TE)( typcsening sys1cm and 1he PosTSCRIPT page-descrip1ion language.
PreTE)( is a trademark of Roben L. Kruse; TE)( is a trademark of the American Mathematical Society;
POSTSCRIPT is a registered 1rademark of Adobe Systems. Inc.

The au1hors and publisher of this book have used their best effons in preparing this book. These effons
include the research. developmen1, and 1es1ing of the theory and progrtms in the book lO determine their
effectiveness. The au1hors and publisher make no warranty of any kind, expressed or implied. wi1h
regard 10 1hese programs or 1he documen1ation contained in this book. The au1hors and publisher shall
not be liable in any event for inciden1al or consequent ial damages in connect ion wi1h. or arising out of, Preface _________ xi Review Questions 27
the furnishing, perfom1ance. or use of these programs.
Synopsis xii
Course Structure xiii
References for Further Study 28
Acknowledgments xiv T he C Language 28
Programming Principles 28
T he Game of Life 29
CHAPTER 1
• e 1991 by Prentice-Hall, Inc. Programming Principles_ __ _ 1
= A Paramount Communications Company
1.1 Introduction 2
CHAPTER 2
- Englewood Cliffs, New Jersey 07632 Introduction
All righcs reserved . No part of this book may be reproduced, in any form or by any means, withou1
1.2 The Game of Life 3
1.2.1 Rules for the Game of Life 4
to Software Engineering _ _ _ 30
permission in writing from the publisher. 1.2.2 Examples 4
2.1 Program Maintenance 31
1.2.3 The Solution 6
Printed in the Uniced States of America 1.2.4 Life: T he Main Program 6 2.2 Lists in C 35
10 9 1.3 Programming Style 9
2.3 Algorithm Development:
1.3.1 Names 9
A Second Version of Life 37
1.3.2 Documentation and Format 11 2.3 .1 The Main Program 37
ISBN 0 - 13-725649-3 1.3.3 Refinement and Modularity 12
2.3.2 Refinement:
1.4 Coding, Testing, and Further Refinement 17 Development of the Subprograms 39
1 .4.1 Stubs 17 2.3.3 Coding the Functions 40
Prentice-Hall lnccmational ( UK) L imiced. London
Prentice-Hall of Australia P1y. Limited. Sydney
1.4 .2 Cou nting Neighbors 18
1 .4.3 Input and Output 19 2.4 Verification of Algorithms 44
Prentice-Hall Canada Inc.. Toro1110
1.4 .4 Drivers 21 2.4.1 Proving the Program 44
Prentice-Hall Hispanoamericana, S.A., Mexico
Prenlice-Hall of India Private Limi1ed, New Delhi 1.4.5 Program Tracing 22 2.4.2 Invariants and Assertions 46
Pren1ice-Hall of Japan, Inc., Tokyo 1.4.6 Princip les of Program Testing 23 2.4.3 Initialization 47
Simon & Schus1er Asia Pie. Ltd .. Singapore
Edi1ora Pren1ice-Hall do Brasil. Ltda .. Rio de Janeiro Pointers and Pitfalls 26 2.5 Program A nalysis and Comparison 48

v
 CONTENTS CONTENTS vii

CHAPTER 6
6 Conclusions and Preview 51 4.3 Further Operations on linked lists 114 7.7 Mergesort for linked Lists 240
2.6.1 The Game of Life 51 4.3.1 Algorithms for Simply Linked Lists 114 Tables 7. 7.1 The Functions 240
2.6.2 Program Design
2.6.3 The C Language
53
55
4.3.2 Comparison of Implementations
4.3.3 Programming Hints 121
120
and Information Retrieva~I_ _ 178 7.7.2 Analysis of Mergesort 242

6.1 Introduction: Breaking the lg n Barrier 179

7.8 Quicksort for Contiguous lists 246
Pointers and Pitfalls 57 4.4 Application: Polynomial Arithmetic 123 7.8.1 The Main Function 247
4.4.1 Purpose of the Project 123 6.2 Rectangular Arrays 179 7.8.2 Partitioning the List 247
Review Questions 57
4.4.2 The Main Program 124 7 .8.3 Analysis of Quicksort 249
6.3 Tables of Various Shapes 182
References for Further Study 58 4.4.3 Data Structures 7 .8.4 Average -Case Analysis of Quicksort 251
6.3.1 Triangular Tables 182
and Their Implementation 128 7.8.5 Comparison with Mergesort 253
6.3.2 Jagged Tables 184
4.4.4 Reading and Writing Polynomials 130
6.3.3 Inverted Tables 184
HAPTER 3 4.4.5 Addition of Polynomials 131 7.9 Review: Comparison of Methods 256
ists ___________ 59 4.4.6 Completing the Project 132 6.4 Tables: A New Abstract Data Type 187
Pointers and Pitfalls 259
4.5 Linked lists in Arrays 135 6.5 Hashing 189
1 Static and Dynamic Structures 60 6.5.1 Sparse Tables 189 Review Questions 259
2 Stacks 60 4.6 Abstract Data Types 6.5.2 Choosing a Hash Function 191
3.2.1 Definition and Operations 60 and Their Implementations 140 6.5.3 Collision Resolution References for Further Study 260
3.2.2 Examples 61 4.6.1 Introduction 140 with Open Addressing 193
3.2.3 Array Implementation of Stacks 64 4.6.2 General Definitions 141 6.5.4 Collision Resolution by Chaini1g 197
4 .6.3 Refinement of Data Specification 143 6.6 Analysis of Hashing 201
3 Queues 68 CHAPTER 8
3.3.1 Definitions 68 Pointers and Pitfalls 145 6.7 Conclusions: Comparison of Methods 206 Recursion _________ 262
3.3.2 Implementations of Queues 69
3.3.3 Circular Queues in C 72 Review Questions 146 6.8 Application: The Life Game Revisited 207
6.8.1 Choice of Algorithm 207 8.1 Divide and Conquer 263
4 Application of Queues: Simulation 77 References for Further Study 146 6.8.2 Specification of Data Structures 207 8.1 .1 The Towers of Hanoi 263
3.4.1 Introduction 77 6.8.3 The Main Program 209 8.1.2 The Solution 264
3.4.2 Simulation of an Airport 78 6.8.4 Functions 210 8.1.3 Refinement 264
3.4.3 The Main Program 80 8.1.4 Analysis 265
3.4.4 Steps of the Simulation 81 CHAPTER 5 Pointers and Pitfalls 213
8.2 Postponing the Work 266
3.4.5 Random Numbers
3.4.6 Sample Results 85
84
Searching _ _ _ _ _ _ __ 147 Review Questions 214 8.2.1 Generating Permutations 266
References for Further Study 215 8.2.2 Backtracking: Nonattacking Queens 271
5 Other Lists and their Implementation 89 5.1 Searching: Introduction and Notation 148
8.3 Tree-Structured Programs:
Pointers and Pitfalls 96 5.2 Sequential Search 151
CHAPTER 7 Look-Ahead in Games 278
Review Questions 96 8.3.1 Game Trees 278
5.3 Binary Search 154 Sorting _ _ _ _ _ _ __ 216 8.3.2 The Minimax Method 279
References for Further Study 97 5.3.1 The Forgetful Version 155
8.3.3 Algorithm Development 280
5.3.2 Recognizing Equality 156 7.1 Introduction and Notation 217 8.3.4 Refinement 281
HAPTER 4 5.4 Comparison Trees 157 7.2 Insertion Sort 218
8.4 Compilation by Recursive Descent 284
5.4.1 Analysis for n = IO 158 7 .2.1 Contiguous Version 21 9
inked Lists _ _ _ _ _ __ 98 5.4.2 Generalization 161 7.2.2 Li nked Version 220
8.5 Principles of Recursion 288
5.4.3 Comparison of Methods 164 7.2.3 Analysis 222
Dynamic Memory Allocation and Pointers 8.5.1 Guidelines for Using Recursion 288
99 5.4.4 A General Relationship 165
4 .1 .1 The Problem of Overflow 99 7.3 Selection Sort 225 8.5.2 How Recursion Works 288
4.1.2 Pointers 99 8.5.3 Tail Recu rsion 292
5.5 Lower Bounds 167 7.4 Shell Sort 228
4.1.3 Further Remarks 100 8.5.4 Wt1tm Nut lu Us~ R~vursion 294
4 .1.4 Dynamic Memory Allocation 101 5.6 Asymptotlcs 171 7.5 Lower Bounds 230 8.5.5 Guidelines and Conclusions 299
4.1.5 Pointers and Dynamic Memory in C 101
Pointers and Pitfalls 175 7.6 Divide and Conquer 233 Pointers and Pitfalls 300
2 Linked Stacks and Queues 106 7.6.1 The Main Ideas 233
4.2.1 Declarations 106 Review Questions 176 7.6.2 An Example 234 Review Questions 301
4.2.2 Linked Stacks 107 7.6.3 Recursion 237
4.2.3 Linked Queues 111 References for Further Study 177 7.6.4 Tree of Subprogram Calls 237 References for Further Study 302
 CONTE NT S ix
ii CONTENTS
APPENDIX A APP E NDI X C
HAPTER 9
:inary Trees ______ _ 304
10.3 External Searching: B· Trees
10.3.1 Access Time 367
367
Mathematical Methods____ 443 An Introduction to C _ _ __ 489
10.3.2 Multiway Search Trees 367 A.1 Sums of Powers of Integers 443
1 Definitions 305 10.3.3 Balanced Muitiway Trees 367 C.1 Introduction 489
10.3.4 Insertion into a B·tree 368 A.2 Logarithms 446 C.1.1 Overview of a C Program 489
2 Treesearch 308 10.3.5 C Algorithms: A.2.1 Definition ot Logaritnms 446
Searching and Insertion 370 A.2.2 Simple Properties 447 C.2 C Elements 490
,3 Traversal of Binary Trees 309
10.3.6 Deletion from a B-tree 375 A.2.3 Choice of Base 448 C.2.1 Reserved Words 490
,4 Treesort 312 A.2.4 Natural Logarithms 448 C.2.2 Constants 490
9.4.1 Insertion into a Search Tree 313 10.4 Graphs 382 A.2.5 Change of Base 449
9.4.2 The Treesort Algorithm 314 10.4.1 Mathematical Background 382 A.2.6 Logarithmic Graphs 450 C.3 Types and Declarations 491
9.4.3 Deletion from a Search Tree 316 10.4.2 Computer Representation 384 A.2.7 Harmonic Numbers 450 C.3.1 Basic Types 491
10.4.3 Graph Traversal 388
A.3 Permutations, Combinations, Factorials 452 C.3.2 Arrays 492
,5 Building a Binary Search Tree 321 10.4.4 Topological Sorting 391
9.5.1 Getting Started 323 A.3.1 Permutations 452 C.3.3 Enumerations 492
10.4.5 A Greedy Algorithm :
9.5.2 Declarations and the Main Program 324 Shortest Pat1s 395 A.3.2 Combinations 453 C.3 4 Structures 492
9.5.3 Inserting a Node 325 10.4.6 Graphs as Data Structures 399 A.3.3 Factorials 453 C.3.5 Unions 493
9.5.4 Finishing the Task 325 A.4 Fibonacci Numbers 455 C.3.6 typedef 494
9.5.5 Evaluation 326 Pointers and Pitfalls 401
9.5.6 Random Search Trees and Optimality 327 Review Questions 402 A.5 Catalan Numbers 456 C.4 Operators 495
A.5.1 The Main Result 456
,6 Height Balance: AVL Trees 330 References for Further Study 402 A.5.2 The Proof C.5 Control Flow Statements 496
9.6.1 Definition 330 by One-to-One Correspondences 457 C.5.1 If-Else 496
9.6.2 Insertion of a Node 330 CHAPTER 11 A.5.3 History 460 C.5.2 Switch 497
9.6.3 Deletion of a Node 337 A.5.4 Numerical Results 460 C.5.3 Loops 497
9.6.4 The Height of an AVL Tree 338 Case Study: C.5.4 Break and Continue 498
References for Further Study 460
.7 Contiguous Representation of Binary Trees: The Polish Notation _____ 404 C.5.5 Goto 498
Heaps 343 11 .1 The Problem 405 APPENDIX B C.6 Pointers 498
9.7.1 Binary Trees in Contiguous Storage 343
11.1 .1 The Quadratic Formula 405
9.7.2 Heaps and Heapsort 344
11.1.2 Unary Operators and Priorities 406 Removal of Recursion 462 C.6.1 Pointer to a Simple Variable 498
9.7 .3 Analysis of Heapsort 348 C.6 2 Pointer to an Array 499
9.7.4 Priority Queues 349 11 .2 The Idea 406 8 .1 General Methods for Removing C.6.3 Array of Pointers 500
11.2.1 Expression Trees 406 Recursion 462 C.6 4 Pointer to Structures 500
Pointers and Pitfalls 351 11.2.2 Polish Notation 408 B.1.1 Preliminary Assumptions 463
Review Questions 352 11.2.3 C Method 41 o B.1.2 General Rules 463 C.7 Functions 501
B. 1.3 Indirect Recursion 464 C.7.1 Arguments to Functions:
11.3 Evaluation of Polish Expressions 410
References for Further Study 353 8.1 .4 Towers of Hanoi 465 Call by Value 502
11.3.1 Evaluation ol an Expression
B.1 .5 Further Simplifications 457
in Prefix Forn 410 C.7.2 Arguments to Functions:
HAPTER 10 11 .3.2 C Conventions 411 8.2 Recursion Removal by Folding 467 Call by Reference 502
11.3.3 C Function for Prefix Evaluation 412 B.2.1 Program Schemata 467 C.7.3 Function Prototypes
'rees and Graphs _ _ _ __ 354 11.3.4 Evaluation of Postfix Expressions 413 B.2.2 Proof of the Transformation 469 and Include Files 503
11.3.5 Proof of the Program: B.2.3 Towers of Hanoi: The Final Version 471
0.1 Orchards, Trees, and Binary Trees 355 Counting Stack Entries 414 C.8 Pointers and Functions 504
10.1 .1 On the Classification of Species 355 8.3 Nonrecursive Quicksort 472
11 .3.6 Recursive E•,aluation C.8.1 Pointer to a Function 504
10.1 .2 Ordered Trees 356 of Postfix Expressions 417 8.4 Stackless Recursion Removal: Mergesort 474 C.8.2 Functions that Return a Pointer 504
10.1 .3 Forests and Orchards 357 C.8.3 Pointer to a Pointer as an Argument 505
10.1 .4 The Formal Correspondence 359 11.4 Translation from Infix Form 8.5 Threaded Binary Trees 478
10.1.5 Rotations 360 to Polish Form 421 B.5.1 Introduction 478
B.5.2 Threads 480 References for Further Study 506
10.1.6 Summary 360 11.5 An Interactive Expression Evaluator 426
11.5.1 The Main Program 426 B.5.3 lnorder and Preorder Traversal 481
0.2 Lexicographic Search Trees: Tries 362 B.5.4 Insertion in a Threaded Tree 482
11.5.2 Representation of the Data 428
10.2.1 Tries 362 B.5.5 Postorder Traversal 484
11.5.3 Predefined Tokens 430
10.2.2 Searching for a Key
10.2.3 C Algorithm 364
363
11.5.4 Translation of the Expression 430 References for Further Study 488 Index __________ 501
11.5.5 Evaluating the Expression 439
10.2.4 Insertion into a Trie 365
11 .5.6 Summary 440
10.2.5 Deletion from a Trie 365
10.2.6 Assessment of Tries 366 References for Further Study 442
Preface

An apprentice carpenter may want only a hammer and a saw, but a master craftsman
employs many precision tools. Computer programming likewise requires sophisticated
tools to cope with the com plexity of real applications, and only practice with these tools
will build skill in their use. This book treats structured problem solving, the process of
data abstraction and structuring, and the comparative study of algori thms as fundamental
tools of program design. Several case studies of s ubstantial size are worked out in detail,
to show how all the tools are used together to build complete programs.
Many of the algorithms and data s tructures st udied here possess an intrinsic elegance,
a sim plicity that cloaks the range and power of their applicability. Before long the student
discovers that vast improvements can be made over the naive methods us ually used in
introductory courses. And yet this elegance of method is tempered with uncertainty.
The s tudent soon finds that it can be far from obvious which of several approaches will
prove best in particular applications. Hence comes an early opportunity to introduce
trnly difficult problems of both intrinsic interest and practical importance and to exhibit
the applicability of mathematical methods to algorithm verification and analysis.
The goal of programming is the construction of programs that are clear, complete,
and functional. Many students, however, find difficulty in translating abstract ideas into
practice. This book, therefore, takes special care in the fom1ulation of ideas into algo-
rithms and in the refinement of algorithms into concrete programs that can be applied to
practical problems. The process of data specification and abstraction, similarly, comes
before the selection of data s tructures and their implementations.
We believe in progressing from the concrete to the abstract, in the careful develop-
ment of motivating examples, followed by the presentation of ideas in a more general
form. At an early stage of their careers most students need reinforcement from seeing the
xi
 PR EFACE PR E FA CE xiii

immediate application of the ideas that they study, and they require the practice of writ- examples and apologizing for its alleged expense. Others give little regard to its pitfalls.
ing and running programs to illustrate each important concept that they learn. This book We have therefore essayed to provide as balanced a treatment as possible. Whenever
therefore contains many sample programs, both short functions and complete programs recursion is !he natural approach ii is used without hesitation. Its first use in this text
of substantial length. The exercises and programming projects, moreover, constitute an Recursion is the second half of Chapter 7. where mergesort and quicksort are introduced. Chapter
indispensable part of this book. Many of these are immediate applications of the topic 8 (which may be read any time after stacks are defined) continues to study recursion in
under study, often requesting that programs be written and run, so that algorithms may depth. It includes examples illustrating a broad range of applications, an exposition of
be tested and compared. Some are larger projects, and a few are su itable for use by a the implementation of recursion, and gu idelines for deciding whether recursion is or is
group of several students working together. not an appropriate method t.o em ploy.
Binary trees arc surely among the most elegant a nd useful of data structures. Their
ynopsis Binary Trees study, which occupies Chap1er 9, ties together concepts from lists, searching, and sorting.
Programming By working through the first large projec1 (CONWAY'S game of Life), Chapter I expounds At the same time, binary trees provide a natural examp le of recursively defined data
Principles principles of top-down refinement, program design, review, and testing, principles that structures, anc therewith_afford an excellenl opportuni1y for 1he student to become more
the student will see demonstrated and is expec1ed to follow throughout the seque l. At comfonablc v.ith recursion applied both to data structures and algorithms.
the same time, this project provides an opportunity for the student to review the syntax Trees and Graphs Chapter IO completes the study of data structures by collecting several important
of C, the programming language used throughout the book. uses of rnultiway trees as data structures, including tries and B-trees, after which the
Introduction to Chapter 2 introduces a few of the basic concerns of software e ngi neeri ng, including chapter introduces graphs as more general structures useful for problem solving. The
Software problem specification and ana lysis, prototyping, algorithm design, refinement, verifica- presentations in each major section of Chapter IO are independent from each other.
Engineering tion, and analysis. These topics are illustrated by the development of a second program Case Study: The The case study in Chapter 11 examines the Polish notation in considerable detail,
Polish Notation exploring !he interplay of recursion, trees, and stacks as vehicles for problem solving
for the Life game, one based on an algorithm that is sufficiently subtle as to s how the
need for precise specifi ca1ions and verifica1ion, and one that shows why care must be and a lgorithm development. Some of the questions addressed can serve as an informal
taken in the choice of data structures. introduction to compiler design. Again, the algori1hms are fully developed within a func-
Lists The study of data structures begins in Chapter 3 with stacks, queues, and lists in tioning C program. This program accepts as input an expression in ordinary (infix) form,
contiguous implementation, always emphasizing the separation between the use of data lranslates the expression into postfix fom1, and evaluaies the expression for specified
Linked Lists structures and their implementation. Chapter 4 continues by studying the same data values of the variable(s).
structures in linked implementations and culminaies with a discussion of abstract data Removal of recursion is a topic that, we hope, most programmers may soon no
types. Compatible packages of C functions are developed for each impl ementation and longer need to study. But at present much important work must be done in contexts
are used in both large and small sample programs. The major goal of these chapters (like FORTRAN or CoooL) disallowing recursion. Methods for manual recursion removal
is to bring the student to appreciate data abstraction and to apply methods of top-down Removal of are therefore requ ired, and are collected for reference as Appendix B. Some instruc-
Recursion tors will wish t.o include the study of threaded binary trees wilh Chapter 9; this section
design to data as well as to algorithms.
Searching Chapters 5, 6, and 7 present algorithms for searching, table access (including hash- is therefore \Hitten so that it can be read independently of the remainder of Appen-
Tables and ing), and sorting. These chapters illustrate the interplay between a lgorithms and the dix B.
Information associated abstract data types, data structures, and implementations. The text introduces An lmroduction to C Appendix C, finally, is a brief introduction to the C programming language. This
Retrieval the ''big Oh" notation for elementary algorithm ana lysis and highlights the crucial choices is not a thorough treaiment of 1he language, but it is imended to serve as a review of C
Sorting to be made regarding best use of space, time, and programming effo1t. syntax and as a reference for the student.
These choices require that we find ana lyt ica l methods 10 assess algorithms, and
producing such analyses is a battle for which combinatorial mathematics must provide Course Structure
the arsenal. At an elementary level we can expect s1udents neither to be well armed nor
to possess the mathematical maturity needed to hone their ski lls to perfection. Our goal, The prerequisite for this book is a first cou rse in programming, wilh experience using 1he
therefore, is only to help students recognize the impo1tance of such skills and be glad for prerequisite elementary features or C. It is possible to introduce C concurrently if the students have
Mathematical later chances to study mathematics. Appendix A presents some necessary mathematics. had experience with a similar high level language such as Pascal. Chapter 2 includes a
Methods Most of the topics in the appendix will be familiar to the well-prepared swdent, but brief discussion of structures and Chapter 4 a study of pointers, in case students have
are included to help with common deficiencies. The final two sections of Appendix A, not previously met these topics. A good knowledge of high school mathematics will
on Fibonacci and Catalan numbers, are more advanced, are no! needed for any vital suffice for almost all the algorithm analyses, but further (perhaps concu rrent) preparation
purpose in the text, but are included to encourage combinatorial interest in the more in discrete mathematics will prove valuable.
mathematically inclined. content This book. includes all the topics of the ACM Course CS 2 (Program Design and
Recursion is a powerful tool, but one that is often misunderstood and sometimes Implementation), with additional emphasis on data abstraction, data structures, algorithm
used improperly. Some tex1books treat it as an afterthought, applying it on ly 10 trivial analysis, and large case studies, so that it is also suitable for a version of Course CS 7
iv PR E FA CE P R EF A CE xv
(Data Structures and Algorithm Analysis) that emphasizes program design along with • Projects. Programming projects also appear in most major sections. These include
implementations and applications of data structures. The book contains significantly more simple variations of programs appearing in the text, completion of projects begun
material than can usually be studied in a single term, and hence it allows flexibility in in the te.>..t, and major new projects investigating questions posed in the text.
designing courses with different content and objectives.
• Review Questions. Each chapter (except Chapter 11) concludes with simple re-
CS 2 The core topics specified for ACM Course CS 2 occupy Chapters 1-8 and the first
view questions to help the student collect and summarize the principal concepts of
third of Chapter 9. A one-term course based closely on CS 2 will normally include
the chapter.
almost all the content of these chapters, except for the more detailed algorithm analy-
ses, verifications, and some of the sample programs. The later chapters include all the • hlstr11ctor's Supplements. Instructors teaching from this book may obtain copies
advanced optional topics suggested for possible inclusion in CS 2. of the following materials:
An elementary course on data structures and algorithms should consider Chapters
• The Instructor's Resource Manual contains teaching notes on each chapter,
data structures I and 2 briefly (to look at the questions of data specification and time-space tradeoffs),
together wi th complete, detailed solutions to every exercise and programming
emphasize Chapters 3-10, and select other topics if time permits.
project in the text. The manual also includes software disks with complete,
CS7 A more advanced course in Data Structures and Algorithm Analysis (ACM course
running versio_ns for every programming project in the text.
CS 7) should begin with a brief review of the topics early in the book, placing special
emphasis on data abstraction, algorithm analysis, and criteria for choosing data structures • The Transparency Masters (several hundred in total) contain enlarged copies
and algorithms under various conditions. The remaining chapters will then provide a solid of almost all diagrams, program segments, and other important extracts from
core of material on data structures, algorithm design, and applications. the text.
two-term course A two-term course can cover the entire book, thereby attaining a satisfying integra-
tion of many of the topics from both of ACM courses CS 2 and CS 7. Students need time Acknowledgments
and practice to understand general methods. By combining the study of data abstraction,
data structures, and algorithms with their implementation in projects of realistic size, an We are grateful to the many people-colleagues. students, friends, and family- who
integrated course can build a solid foundation on which later, more theoretical courses have contributed in numerous ways to the development of the Pascal version on which
can be built. the current book is based. Some of these people arc named in the preface to the Pascal
Even if it is not covered in its entirety, this book will provide enough depth to enable Version. In addition, many more people have helped us produce the current C version.
interested students to continue using it as a reference in later work. It is important in BRIAN KERNIGHAN reviewed the entire manuscript with the greatest of care and pro·
vided us with many valuable comments and suggestions.
any case to assign major programming projects and to allow adequate time for their
completion. Further detailed reviews giving us much helpful information came from PHIL ADAMS
(Nova University), ALAN J. F1ursK1 (Arizona State University), DAN HIRSCHBERG (Univer·
sity of California at Irvine), SAM Hs u (Florida Atlantic University). GARY KNOTI (Uni·
:urther Features
versity of Maryland), 0ARRJ;N MrcLETIE (IBM), ANuRi::w NATHANSON (AGS information
Systems), TERRY SHOR!:: (South Shore Enterprises), Eo S1Mc6 (Nova University), MARTIN
• Chapter Previews. Each chapter begins with an outline and a brief statement of
goals and content to help the reader establish perspective. K. SOLOMON (Florida Atlantic University), CARLOS To:-mo (South Shore Enterprises), and
RED V1scuso (IBM).
• Application Programs. The text includes several large, complete programs that GERRY DIAZ, ROLLIE Gu1LO, Eo SHOCKLEY, and EDEN YouNT provided many helpful
illustrate principles of good software design and application of the methods devel- suggestions.
oped in the text. Code reading is an important skill for a programmer, but one that STEVEN MATHESON helped to develop the PrefJ:X typesetting system, incl uding the
is often neglected in textbooks. software for typesetting C program listings.
• Programming Precepts. Many principles of good programming are summarized We are grateful for the support of fami ly and friends: ANNE ALDOUS, DAVE EGAN,
with short, pithy statements that are well worth remembering. CHRIS KIKG, ESTHER KRUSE, HOWARD and SHIRLEY LEUNG, JULIA MISTRELLO, DEEANNE
• Marginal Notes. Keywords and other important concepts are high lighted in the SAFFORD, VICKI SHORE. and CAREN WEBSTER.
left margin, thereby allowing the reader to locate the principal ideas of a section Finally, we owe much to our friends at Prentice Hall: our editor MARCIA HORTON
without delay. (Editor in ChiP.f for r.omp11tP.r St.iP.nt.~ anci Engineering), .ToHN WAIT, who suggested
• Pointers and Pitfalls. Each chapter of the book (except Chapter 11) contains a this project, supplements editor ALICE DwoRK1N. marketing manager JEN'IIFER YouNG,
section giving helpful hints concerning problems of program design. KATHLEEN ScHIAPARE1.1.1 and the production staff whose names appear on the copyright
page, and all the others who have contributed to our work in many ways.
• Exercises. Exercises appear not only at the ends of chapters but with almost every
major section. These exercises he lp with the immediate reinforcement of the ideas
of the section and develop further related ideas.
Data Structures
and
Program Design
inC
CHAPTER 1

Programming
Principles
This chapter summarizes important principles of f!,ood programming, espe-
cially as applied to larf!,e projects, and illustrates methods for discovering
effective algorithms. In the process we raise questions in program desif!,n
that we shall address in later chapters, and review many of the special
features of the laniuage C by using them to write programs.

1.1 Introduction 2 1.4.3 Input and Output 19

1.4.4 Drivers 21
1.2 The Game of Life 3 1.4.5 Program Tracing 22
1.2.1 Rules for the Game of Life 4
1.2.2 Examples 4 1.4.6 Principles of Program Testing 23
1.2.3 The Solution 6
1.2.4 Life: The Main Program 6 Pointers and Pitfalls 26
1.3 Programming Style 9
1.3.1 Names 9
Review Questions 27
1.3.2 Documentation and Format 11
1.3.3 Refinement and Modularity 12
1.4 Coding, Testing , and Further References for Further Study 28
Refinement 17 The C Language 28
1.4 .1 Stubs 17 Programming Principles 28
1.4.2 Counting Neighbors 18 The Game of Life 29

1
 Programming Principles C HAPTER 1 SEC TION 1.2 The Game of Life 3

.1 INTRODUCTION and algorithms that might work that it can be hard 10 decide which is best, which may
lead to programming difficulties, or which may be hopelessly inefficient. The greatest
The greatest difficulties of writing large computer programs are not in deciding what the data strucJures room for variability in algorithm design is generally in the way in which the data of the
goals of the program should be, nor even in finding methods that can be used to reach program are stored:
these goals. The presi<lent of a business might say, "Let's get a computer to keep track
of all our inventory information, accounting records, and personnel files, and let it tell us • How they are arranged in relation to each other.
when inventories need to be reordered and budget lines are overspent, and let it handle • \Vhich d~ta arc kept in memory.
the payroll." With enough time and effort, a staff of systems analysts and programmers
might be able to determine how various staff members are now doing these tasks and • Which are calculated when needed.
write programs to do the work in the same way. • Which are k.epl in files, and how are the files arranged.
This approach, however, is almost certain to be a disastrous failure. Wh ile inter-
viewing employees, the systems analysts will find some tasks that can be put on the A second goal of chis book, therefore, is 10 present several elegant, yet fundamentally
problems of computer easily and will proceed to do so. Then, as they move other work to the si mple ideas for the organization of data, and several powerful algorithms for important
large programs computer, they will find that it depends on the first tasks. The output from these, un- tasks within data processing, such as sorting and searching.
fortunately, will not be quite in the proper form. Hence they need more programming When there are several different ways to organize data and devise algorithms it
to convert the data from the form given for one task to the form needed for another. becomes impo11ant to develop criteria to recommend a choice. Hence we devote attention
The programming project begins 10 resemble a patchwork quilt. Some of the pieces are analysis to analyzing the behavior of algorithms under various conditions.
stronger, some weaker. Some of the pieces are carefully sewn onto the adjacent ones, The difficulty of debugg ing a program increases much faster than its size. That is,
some are barely tacked together. If the programmers are lucky, their creation may hold if one program is twice the size of another, then it will likely not take twice as long to
together well enough to do most of the routine work most of the time. But if any change tes1i11g a11d debug, but perhaps four times as long. Many very large programs (such as operating
verification systems) are put into use still containing bugs that the programmers have despaired
must be made, it will have unpredictable consequences throughout the system. Later, a
new request will come along, or an unexpected problem, perhaps even an emergency, of finding, because the difficulties seem insurmountable. Sometimes projects that have
and the programmers' efforts will prove as effective as using a patchwork qu ilt as a consumed years of effort must be discarded because it is impossible to discover why
safety net for people jumping from a tall building. they will not work. If we do not wish such a fate for our own projects, then we must
purpose of book The main purpose of this book is to describe programming methods and tools use methods that will
that will prove effective for projects of realistic size, programs much larger than those program correctness • Reduce the number of bugs, making it easier to spot those that remain.
ordinarily used to illustrate features of elementary programming. Since a piecemeal
approach to large problems is doomed to fail, we must first of all adopt a consistent, • Enable LL~ to verify in advance that our algorithms are correct.
unified, and logical approach, and we must also be careful to observe important principles • Provide us with ways to test our programs so that we can be reasonably confident
of program design, principles that are sometimes ignored in writing small programs, but that they will not misbehave.
whose neglect wi ll prove di sastrous for large projects.
The first major hurdle in attacking a large problem is deciding exactly what the Development of such methods is another of our goals, but one that cam1ot yet be fully
problem problem is. It is necessary to translate vague goals, contradictory requests, and perhaps within our grasp.
specification unstated desires into a precisely formulated project that can be programmed. And the Infonnal su rveys show that, once a large and impot1ant program is fully debugged
methods or division s of work that people have previously used are not necessarily the and in use, then less than half of the programming effort that will be invested altogether
best for use in a machine. Hence our approach must be to determine overall goals, but maintenance in the project will have been completed. Maiflten a11ce of programs, that is, modifications
precise ones, and then slowly divide the work into smaller problems unti l they become needed to meet new requests and new operating environments, takes, on average, more
of manageable size. than half of the programming investment. For this reason, it is essential that a large
program design The maxim that many programmers observe, "First make your program work, then project be written to make it as easy to understand and modify as possible.
make it pretty," may be effective for small programs, but not for large ones. Each part
of a large program must be well organized. clearly written. and thoroughly understood.
or else its structure will have been forgotten. and it can no longer be tied to the other 1.2 THE GAME OF LIFE
parts of the project at some much later time, perhaps by another programmer. Hence
we do not separate style from other parts of program design, but from the beginning we If we may take the liberty to abuse an old proverb:
must be careful 10 form good habits.
Even with very large projects, difficu lties usua lly arise not from the inability to One conG-rete problem is worth a thousand unapplied abstractions. s,
find a solution but, rather, from the fact that there can be so many different methods
 SECTION 1 .2 The Game of Lile 5
Programming Principles CHAPTER 1

case study Throughout this chapter we shall concentrate on one case study that, while not large by
realistic standards, illustrates both the methods of program design and the pitfalls that we 0 0 0 0 0 0
should learn to avoid. Sometimes the example motivates general principles; sometimes
0 1 2 2 1 0
the general discussion comes first; always it is with the view of discovering general
methods that will prove their value in a range of practical applications. In later chapters 0 1 • 1 •1 1 0
we shall employ similar methods for much larger projects. moribund example
The example we shall use is the game called Life, which was introduced by the 0 1 2 2 1 0
British mathematician J. H. CONWAY in 1970.
0 0 0 0 0 0

1.2.1 Rules for the Game of life

Life is really a simulation, not a game with players. It takes place on an unbounded rect- By rule 2 both the living cells will die in the coming generation, and rule 5 shows that
definitions angular grid in wh ich each cell can either be occupied by an organism or not. Occupied no cells will become alive, so the community dies out.
cells are called alive; unoccupied cells are called dead. Which cells are alive changes On the other hand, the community
from generation to generation according to the number of neighboring cells that are alive,
as follows:
0 0 0 0 0 0
transition rules 1. The neighbors of a given cell are the eight cells that touch it vertically, horizontally, 1
0 2 2 1 0
or diagonally.
0 2 • 3 • 3 2 0
2. If a cell is alive but either has no neighboring cells alive or only one alive, then in
the next generation the cell dies of loneliness. stahility 0 2 • 3 •3 2 0
3. If a cell is alive and has four or more neighboring cells also alive, then in the next
0 1 2 2 1 0
generation the cell dies of overcrowding.
4. A living cell with either two or three living neighbors remains alive in the next 0 0 0 0 0 0

generation.
5. If a cell is dead, then in the next generation it will become alive if it has exactly has the neighbor counts as shown. Each of the living cells has a neighbor count of three,
three neighboring cells, no more or fewer, that are already alive. All other dead and hence remains alive, but the dead cells all have neighbor counts of two or less, and
cells remain dead in the next generation. hence none of them becomes alive.
6. All births and deaths take place at exactly the same time, so that dying cells can The two communities
help to give birth to another, but cannot prevent the death of others by reducing
overcrowding, nor can cells being born either preserve or kill cells living in the
previous generation. 0 0 0 0 0 0 I 1 1 0

1 2 3 2 1 0 2 •1 2 0
1.2.2 Examples •1 •2 •1 •2
1 1 and 0 3 3 0
alternation
As a first example, consider the community
1 2 3 2 1 0 2 •1 2 0

0 0 0 0 0 0 1 1 I 0

• • continue to alternate from generation to generation, as indicated by the neighbor counts

shown.
It is a suqrising fact that, from very simple initial configurations, quite complicated
progressions of Life communities can develop, lasting many generations, anti it is usually
The counts of living neighbors for the cells are as follows:
 Programming Principles CHAPTER 1 SECTION 1 .2 The Game of Lile 7

variety not obvious what changes will happen as generations progress. Some very small initial I* Simulation of Conway's game of Life on a bounded grid
I* Version 1 • I
*'
configurations will grow into large communities; others will slowly die out; many will
reach a state where they do not change, or where they go through a repeating pattern #include II general.h II
every few generations. #include 11 lifedef.h"
#include 11 calls.h 11
I* common include files and definitions
I* Life's defines and typedefs *'*'
I* Life's function declarations
popularity Not long after its invention, M ARTIN GARDNER discussed the Life game in his column
in Scientific American, and, from that time on, it has fascinated many people, so that for void main (void)
*'
several years there was even a quarterly newsletter devoted to related topics. It makes {
an ideal display for microcomputers. int row, col;
Our first goal, of course, is to write a program that will show how an initial com-

*'*'
GridJype map; I* current generation
munity will change from generation to generation. GridJype newmap; I* next generation

i nirializario11 Initialize (map);

.2.3 The Solution WriteMap (map) ;
At most a few minutes' thought will show that the solution to the Life problem is so do {
simple that it would be a good exercise tor the members of a beginning programming ca/cu/are changes for (row = O; row< MAXROW; row++ )
class who had just learned about arrays. All we need to do is to set up a large rectangular for (col= O; col< MAXCOL; col ++ )
merhod array whose entries correspond to the Life cells and will be marked with the status of the switch (NeighborCount(row, col, map)) {
cell, either alive or dead. To determine what happens from one generation to the next, case 0:
we then need only count the number of living neighbors of each cell and apply the rules. case 1:
Since, however, we shall be using loops to go through the array, we must be careful not newmap [row J [col] = DEAD;
to violate rule 6 by allowing changes made earlier to affect the count of neighbors for break;
cells studied later. The easiest way to avoid this pitfall is to set up a second array that case 2:
will represent the community at- the next generation and, after it has been completely newmap [row] [col] = map [row] [col];
calculated, then make the generation change by copying it to the original array. break;
Next let us rewrite this method as the steps of an infonnal algorithm. case 3:
newmap [row] [col] = ALIVE;
break;
algorithm Initialize an array called map to contain the initial configuration of living cells. case 4:
Repeat the following steps for as long as desired: case 5:
case 6:
For each cell in the array do the following: case 7:
Counc the number of living neighbors of the cell. case 8:
newmap [ row] [col] = DEAD;
If the count is 0, 1, 4, 5, 6. 7, or 8, then set the corresponding cell in
another array called newmap to be dead; if the count is 3, then set break;
the corresponding cell to be alive: and if the count is 2, then set the }
corresponding cell to be the same as the cell in array map (since the advance ge11erario11 CopyMap(map, newmap);
status of a cell with count 2 does not change). WriteMap(map);
Copy the array newmap into the a1ny map. } while (Enquire());
}
Print the array map for the user.
Before we discuss the C program above we need to establish what is included with the
#include preprocessor command. There are three files: general.h, lifedel.h, and calls.h .
.2.4 Life: The Main Program
The file general.h contains the definitions and #include statements for the standard
The preceding outline of an algorithm for the game of Life translates into the following fi les that appear in many programs and wi ll be used throughout this book. The file
C program. includes
 CHAPTER 1 SECTION 1 .3 Programming Style 9
Programming Principles
statement to set up the array newmap, the function CopyMap copies array newmap into
#include <stdio.h>
array map, and the functi on WriteMap writes out the result.
#include <stdlib.h>
typedef enum booleanJag { FALSE, TRUE } Boolean.type;
Exercises Determine by hand calculation what will happen to each of the comm unities shown in
void Error ( char *) ; 1.2 Figure 1. 1 over the course of fi ve generati ons. [SuggesTion: Set up the Life configuration
on a checkerboard. Use one color of checkers for living cells in the current generation
The function Error is a simple function we use throughout the book. Error displays an
and a second color to mark those that will be born or die in the nex t generation.]
error message and terminates execution. Here is the function.

I* Error: print error message and terminate the program. *I

void Error(char *S)
{
(a)- (b ) :t::tt1ttJ:+
~ ,c, IH·H·H·II
(d)II
fprintf(stderr, "%s\n", s);
exit(1);
}
l•J~
The file lifedef.h contains the definiti ons for the Life program:
• •• IH·HH·HI
~
(f)

#define MAXROW 50
#define MAXCOL 80
I* maximum number of rows
I* maximum number of columns
typedef enum status-tag { DEAD, ALIVE } Status.type;
typedef Status.type Grid_type [MAXROW] [MAXCOL] ;
*'*' (g )
I
I
••• •• •• •
(h)ma (i)- • •••
••
functions and calls.h contains the function prototypes for the Life program:
I
I
' Effl=a
void CopyMap ( Grid.type, GridJype); (j) (k) (I)

• ••••
BooleanJype Enquire (void);
void lnitialize (Grid.type); ••••• •• ••
int NeighborCount(int, int, Grid.type); I
I
• ••• ••
void WriteMap (Grid.type) ; I
'
We create a new calls.h file with the function prototypes for each program we write. In Figure 1.1. Life configurations
this program we still must write the functions Initialize and WriteMap that will do the input
and output, the function Enquire that will determine whether or not to go on to the next
generation, the function CopyMap that will copy the updated grid, newmap, into map,
and the function NeighborCount that will count the number of cells neighboring the one
1.3 PROGRAMMING STYLE
in row ,col that are occupied in the array map. The program is entirely straightforward. Before we tum to writing the functions for the Life game, let us pause to consider several
First, we read in the initial situation to establish the first configuration of occupied cells. principles that we should be careful to employ in programming.
Then we commence a loop that makes one pass for each generation. Within this loop
we first have a nested pair of loops on row and col that will mn over all entries in the 1.3.1 Names
array map. The body of these nested loops consists of the one special statement In the story of creation (Genesis 2: 19), God brought all the animals to ADAM to see
what names he would give them. Accord ing to an old Jewish tradition, it was only when
switch { . . . } ,
ADAM had named an animal that it sprang to life. This story brings an important moral
to computer programming: Even if data and algorithms exist before, it is only when they
which is a multiway selection statement. In the present application the function Neigh·
are given meaningful names that their places in the program can be properly recognized
borCount will return one of the values 0, 1, ... , 8, and for each of these cases we can
and appreciated, that they first acqu ire a life of their own.
take a separate action, or, as in our pro1,rram, some of the cases may lead to the same
purpose of For a program to work properly it is of the utmost importance to know exactly what
action. You should check that the action prescribed in each case corresponds correctly to careful naming each variable represents, and to know exactly what each function does. Documentation
the rules 2, 3, 4, and 5 of Section 1.2. l. Finally, after us ing the nested loops and switch
 CHAPTER 1 SECTION 1 .3 Programming Style 11
O Programming Principles

explaining the variables and functions should therefore always be included. The names 6. Avoid choosing names th at are close to each other in spelling or otherwise easy to
of variables and functions should be chosen wit,h care so as to identify thei r meanings confuse.
clearly and succinctly. Finding good names is not always an easy task, but is important 7. Be careful in the use of the letter "I" (small ell}, ''O" (capi tal oh) and " O" (zero).
enough t.o be singled out as our fi rst programming precept Within words or numbers these usua ll y can be recognized from the context, and
cause nu p1 olJlt:111, lJu t '·I" am.I ''O " should 11ever l>e used alu11e as names. Consider
the examples

. " ;h.1ways narr)e

your varrab1es and 1unctions I = 1; x = 1; x = I; x = O;
' :wif~the:great;st care;' and ex~la{p them t,,h oro~:ghiy. -;:<:

C requi res declarations for local variables and arguments. Constants used in a program 1.3.2 Documentation and Format
can be given names through enumerators or symbolic constants.
The careful choice of names can go a long way in clarifying a program and in Most students initially regard documentation as a chore that must be endured, after a
helping to avoid misprints and common errors. Some guidelines are program is finished, to ensure that the marker and instructor can read it, so that no credi t
will be lost for obscu rity. The author of a small program indeed can keep all the details
guidelines I. Give special care to the choice of names for functions, constants, symbolic constants, in his head, and so needs documentation only to explain the program to someone else.
and all global variables and types used in different parts of the program. These the purpose of With large programs (and with small ones after some months have elapsed), it becomes
names should be meaningful and should suggest clearly the purpose of the function, doc11me111arion impossible to remember how every detai l relates to every other, and therefore to write
variable, and the like. large programs, it is essential that appropriate documentation be prepared along with each
2. Keep the names simple for variables used only briefly and locally. A single letter small part of the program. A good habit is to prepare documentation as the program
is often a good choice for the variable controlling a for loop, but would be a poor is being written, and an even better one, as we shall see later, is to prepare part of the
choice for a function or for a variable used three or four times in widely separated documentation before starting to wri te the program.
parts of the program. Not all documentation is appropriate. Almost as common as programs with little
documentation or onl y cryptic comments are programs with verbose documentation that
3. Use common prefixes or suffixes to associate names of the same general category.
adds little to understanding the program. Hence our second programming precept:
The files used in a program, for example, might be called

lnputFile Tra nsactionFile TotalFile OutFile RejectFile Programming Precept

4. Avoid deliberate misspellings and meaningless suffixes to obtain different names. Keep your documentation concise but descriptive.
Of all the names
The style of documentation, as with all wntmg styles, is highly personal, and many
index indx ndex indexx index2 index3
different styles can prove effective. There are, nonetheless. some commonly accepted
only one (the first) should normally be used. When you arc tempted to introduce guidelines that should be respected:
multiple names of th is sort, take it as a sign that you should think harder and devise
g11ideli11es 1. Place a prologue at the beginning of each function including
names that better describe the intended use.
5. Avoid choosing cute names whose meaning has little or nothing to do with the a. Identification (programmer's name, date, version number).
problem. The statements b. Statement of the purpose of the function and method used.
c. The changes the function makes and what data it uses.
while (tv == HOCK) d. Reference to further documentation external to the program.
Study();
2. When each variable, constant, or type is declared, explain what it is and how it is
if ( ! s leepy)
Play(); used. Better still, make this information evident from the name.
else 3. Introduce each significant section of the program with a comment stating briefly its
Nap(); purpose or action.
4. Indicate the end of each significant section if it is not otherwise obvious.
may be funny but they are bad programming!
12 Programming Principles CHAPTER 1 SECTI ON 1.3 Programming Style 13

5. Avoid comments that parrot what the code does, such as any large organization the top management cannot worry about every detail of every
activity; the top managers must concentrate on general goa ls and problems and delegate
count++; I* Increase counter by 1. *I specific responsibilities to their subordinates. Again, middle-level managers cannot do
everything: They must subdivide the work and send it to other people. So it is with
or that are meaningless jargu11, sud1 as subdivision computer programming. Even when a project is sma ll enough that one person can take
it from start to finish, it is most imponant to divide the work, starting with an overall
I* horse string length into correctitude *' understanding of the problem, dividing it into subproblems, and attacking each of these
in tum without worrying about the others.
(This example was taken directly from a systems program.) Let us restate this principle with a classic proverb:
6. Explain any statement that employs a trick or whose meaning is unclear. Better
still, avoid such statement.s. Programming Precept
7. The code itself should explain how the program works. The documentation should Don't lose sight of the forest for its trees.
explain why it works and what it does.
8. Whenever a program is modified, be sure that the documentation is correspondingly top-down refinement This principle, called top-down refinement, is the real key to writing large programs
modified. that work. The principle implies the postponement of detailed consideration, but not the
postponement of precision and rigor. It does not mean that the main program becomes
format Spaces, blank lines, and indentation in a program are an important fonn of documentation.
some vague entity whose task can hardly be described. On the contrary, the main program
TI1ey make the program easy to read, allow you to te ll at a glance which parts of
will send almost all the work out to various functions, and as we write the main program
the program relate to each other, where the major breaks occur, and precisely which
specifications (which we should do first), we decide exac1ly how the work will be divided among them.
statements are contained in each loop or each alternative of a conditional statement.
Then, as we later work on a particular function, we shall know before starting exactly
There are many systems (some automated) for indentation and spacing, all with the goal
what it is expected to do.
of making it easier to detennine the structure of the program.
It is often not easy to decide exactly how to divide the work into functions, and
A C beautifier, usually named cb, is a system utility that reads a C program moving
sometimes a decision once made must later be modified. Even so, two guidelines can
the text between lines and adjusting the indentation so as to improve the appearance of
help in deciding how to divide the work:
the program and make its structure more obvious. The utility cb was originally available
on UN1x. If a C beautifier is available on your system, you might experiment with it to
see if it helps the appearance of your programs. Programming Precept
<:0nsistency Because of t.he importance of good format for programs, you should settle on some
Each function should do only one task, but do it well.
reasonable rules for spacing and indentation and use your rules consistently in all the
programs you write. Consistency is essential if tJ1e system is to be useful in reading
programs. Many professional programming groups decide on a unifom1 system and That is, we should be able to describe the purpose of a function succinctly. If you find
insist that all the programs they write confonn. Some classes or student programming yourself writing a long paragraph to specify the task of a function, then either you are
teams do likewise. In this way, it becomes much easier for one programmer to read and givi ng too much detail (that is, you are writing the function before it is time to do so)
understand the work of another. or you should rethink the division of work. The function itself will undoubtedly contain
many details, but they should not appear until the next stage of refinement.
Programming Precept
Programming Precept
The reading time for programs is much more than the writing time.
Make reading easy to do. Each function should hide something.

A middle-level manager in a large company does not pass on everything he receives from
his departments to his superior; he summarizes, collates, and weeds out the infonnation,
1.3.3 Refinement and Modularity handles many requests himself, and sends on only what is needed at the upper levels.
problem solving Computers do not solve problems; people do. Usually the most important part of the Similarly, he does not transmit everything he learns from higher management to his
process is dividing the problem into smaller problems that can be understood in more subordinates. He transmits to each person only what he needs to do his job. The
detail. If these are still too difficult, then they are subdivided again, and so on. Jn functions we write should do likewise.
14 Programming Principles CHAPTER 1 SECTION 1.3 Programming Style 15

One of the most important parts of the refinement process is deciding exactly what needs to produce more than one result, then some of the parameters should be passed by
the task of each function is, specifying precisely what its input will be and what result it reference and the function should be of type void.
will produce. Errors in these specifications are among the most frequent program bugs before and after The second way in which the specifications of a function should be made precise is
conditions in describing the action of the funct ion. The documentation should include a statement
and are among the hardest to find . First, the data used in the function must be precisely
s pecified . These data are of five kinds: of exactly what conditions the funct ion expects to find when it is started. These are
called the preconditions for the fu nction. The documentation should also indicate what
changes the function will make, and therefore what cond itions will hold after the function
parame1ers • Input parameters are used by the function but are not changed by the function. In finishes. These are called the postconditions for the function.
C, input parameters are usually passed by value; that is, a copy of the parameter is While all these principles of top-down design may seem almost self-evident, the
passed to the function. (Exception: Arrays are always passed by reference; that is, only way to learn them thoroughly is by practice. Hence throughout this book we shall
the address of the array is passed to the function.) be careful to apply them to the large programs that we write, and in a moment it wi ll be
• Output parameters contain the resulls of the calculations from the function. In C, appropriate to return to our first example proj ect.
output parameters must be passed by reference.
• Inout parameters are used for both input and output; the initial value of the pa- Exercises E l. Rewrite the follow ing function so that it accomplishes the same resul t in a less
rameter is used and then modified by the function. In C, inout parameters must be 1.3 tricky way.
passed by reference.
void DoesSomething ( int * first, int *Second )
variables • Local variables are declared in the function and exist only while the function is {
being executed. T hey arc not initialized before the function begins and are discarded *first = * Second - *first;
when the function ends. *Second = * Second - * first;
• Global variables are used in the function but not defined in the function. It can * first = * Second + *first;
be quite dangerous to use global variables in a function , since after the function }
is written its author may forget exactly what global variables were used and how.
E2. Determine what each of the fo llowing funct ions does. Rewrite each function with
If the main program is later changed, then the function may mysteriously begin to
mys1ery f11nc1ions meaningful variable names, with better format, and without unnecessary variables
misbehave. If a function alters the value of a global variable it is said to cause a side
and statements.
side effects effect. Side effect5 are even more dangerous than using global variables as input
to the function because side effects may alter the performance of other functions, a. #define MAXINT 100
thereby misdirecting the programmer's debugging efforts to a part of the program int Calculate (int apple, int orange)
that is already correct. { int peach, lemon;
peach = O; lemon = O; if (apple < orange) {
peach = orange; } else if (orange<= apple) {
peach = apple; } else { peach = MAXINT; lemon = MAXINT;
Programming PreceJt " ., · } if (lemon ! = MAXINT) { return ( peach); } }
~~ ·ffi ·-~; m $- ·" : ,_ § ,,. *' · ~ X:!,

,, ® Keep you~ conmectioros simple, Avoid <9lobal variables whenever l)ossible. , b. double Figure(double vector1 [ J, int n)
{ int loop1; double loop2; double loop3; int loop4;
loop 1 = O; loop2 = vector1 [ loop 1J; loop3 = 0.0;
loop4 = loop1; for ( loop4 = O; loop4 < n; loop4 = loop4 + 1)
4
i» i " ': " ' i;, .
1
;·. ·;~fi @. ·<~;: ,~, ~-: ~J ·m
'" ~ rograminlhg
~ ::-- "{, 'Pri cef't " ~~' ~' "'·1' { loop1 = loop1 + 1; loop2 = vector1 [ loop1 - 1];
loop3 = loop2 + loop3; } loop2 = loop1;
1& ·

,,,. t '' .,, , ~,. Never cause side effe<::ts. loop2 = loop3/loop2; return ( loop2); }
If you must use•global variables as input;- document them thoroughly.'
' .~ §: ~;'.i:· '. -~ ~ ·~· & ~ ·~ -~ ,;~- ' ';; . ,:;.: c. void Question (int * a17, int *Stuff)
{ int another, yetanother, stillonemore;
In the case of a function that returns a non-void value, the definition of side effect i s
another= yetanother; stillonemore = * a17;
further expanded to include changes made to parameters as well as global variables.
yetanother = * Stuff; another = stillonemore; * a17 = yetanother;
A function typically returns one result. When a function does not return a result the
stillonemore = yetanother;
function should be of type void. When the function returns a result then the function
* Stuff = another; another = yetanother; yetanother = * Stuff; }
should have a type qualifier that indicates the type of result being returned. If a function
16 Programming Principles CHAPTER 1 SECTION 1 .4 Coding, Testing, and Further Re1inement 17

d. int Mystery ( int apple, int orange, int peach) y = (2*Y + xi ( y*y) ) /3
{ if (apple> orange) if (apple> peach) if
(peach> orange) return (peach); else if (apple < orange) until fabs ( Y*Y*Y - x) <= 0.00001.
return(apple); else return(orange); else return(apple); else c. Which of these tasks i s easier?
if (peach > apple) ii (peach > orange) return (orange); else
ES. The mean of a sequence of real numbers is cheir sum divided by the count of
return(peach); else return(apple); }
statistics numbers in the sequence. The (population) variance of the sequence is the mean
of the squares of all numbers in the sequence, minus the square of the mean of the
E3. The following statement is designed to check the relative sizes of three integers,
numbers in the sequence. The standard deviation i s the square root of the variance.
nested it statements which you may assume to be different from each other:
Write a well -structured C function to ca lculate the standard deviation of a sequence
if (x < z) if (x < y) if (y < z) c = 1; else c = 2; else of n numbers, where n is a constant and the numbers are in an array indexed from
if (y < z) c = 3; else c = 4; else if (x < y) O to n - I , where n i s a parameter to the function. Write, then use, subsidiary
if (x<z) c=S; elsec=6; else if (y<z) C=7; else functions 10 calculate the mean and variance.
if (z < x) if (z < y) c = 8; else c = 9; else c = 1O; plotting E6. Design a program that will plot a given set of points on a graph. T he input to the
program wi ll be a text file, each line of which contains two numbers that are the
a. Rewrite this statement in a form that is easier to read. x and y coordinates of a point to be plotted. The program will use a routine to
b. Since there are only six possible orderings for the three integers, only six of plot one such pair of coordinates. The details of the routine involve the specific
the ten cases can actually occur. Find those that can never occur, and eliminate method of plotting and cannot be written since they depend on the requirements
the redundant checks. of the plotting equipment, which we do not know. Before plotting the points the
c. Write a simpler, shorter statement that accomplishes the same result. program needs to know the maximum and minimum values of x and y that appear
in its input file. The program should therefore use another routine Bounds that
E4. The following C function calculates the cube root of a real number (by the N EWTON
wi ll read the whole file and determine these four maxima and minima. Afterward,
cube roots approximation), using the f'.lct that, if y is one approximation to the cube root of
another routine is used to draw and label the axes; then the file can be reset and the
x, then
indiv idual points plotted.
2y + x/y2
z = - - -- a. Write the main program , not including the rout ines.
3
b. Write the function Bounds.
is a closer approximation. c. Write the header lines for the remaining functions together with appropriate
documentation showing their purposes and their requirements.
double Fen (double stuff)
{ double april, tim, tiny, shadow, tom, tam, square;
BooleanJype flag;
tim = stuff; tam = stuff; tiny = 0.00001;
if (stuff!= O) do {shadow= tim + tim;
1.4 CODING , TESTING, AND FURTHER REFINEMENT
square = tim * tim; The three processes in the title above go hand-in-hand and must be done together. Yet it is
tom= (shadow + stuff/square); important to keep them separate in our thinking, since each requires its own approach and
april = tom/3; method. Coding, of course, is the process of writing an algorithm in the correct syntax
if (april * april * april - tam> -tiny) (grammar) of a computer language like C, and testing is the process of running the
if (april * april * april - tam < tiny) flag = TRUE; program on sample data chosen to find errors if they are present. For further refinement,
else flag = FALSE; else flag = FALSE; we tum to the functions not yet written and repeat these steps.
if (flag == FALSE) tim = april; else tim = tam; }
while (flag == FALSE) ;
1.4.1 Stubs
if (stuff== 0) return (stuff); else return(april); }
After coding the main program, most programmers will wish to complete the writing and
a. Rewrite this function with meaningful variable names, without the extra vari- coding of the functions as soon as possible, to see i f the whole project will work. For a
ables that contribute nothing to the understanding, with a better layout, and early debugging project as small as the Life game, this approach may work, but for larger projects, writing
without the redundant and useless statements. and testing and coding all the functions w ill be such a large job that, by the time it is complete,
b. Write a function for calculating the cube root of x directly from the mathemat- many of the details of the main program and functions that were written early wi ll have
ical formula, by starting with the assignment y = x and then repeating been forgotten. l n fact, different people may be writ ing different functions, and some
18 Programming Principles CHAPTER 1 SEC T I ON 1 . 4 Coding, Testing, and Further Refinement 19

of those who started the project may have left it before all functions are written. It is variables for the lower and upper limits of the loops, and make sure that they remain
much easier to understand and debug a progra111 when it is fresh in your mind. Hence, within range. Since the loops will incorrectly consider that the cell in position row, col
for larger projects, it is much more efficient to debug and test each function as soon as is a neighbor of itself, we must make a correction after completing the loops.
it is written than it is to wait until the project has been completely coded.
Even for smaller projects, there are good reasons for de huggi ng functions one at a
time. We might, for example, be unsure of some point of C syntax that will appear in
I* NeighborCount: count neighbors of row.col. * I
several places through the program. If we can compile each function separately, then
int NeighborCount (int row, int col, GridJype map)
we shall quickly learn to avoid errors in syntax in later functions. As a second example, {
suppose that we have decided that the major steps of the program should be done in a
cc1tain order. If we test the main program as soon as it is written, then we may find
that sometimes the major steps are done in the wrong order, and we can quickly correct
int i, j;
int rlow, rh igh;
I* loop indices for row, column
I* limits for row loop *'
*I
the problem, doing so more easily than if we waited until the major steps were perhaps
int claw, chigh;
int count;
I* limits for column loop
*'
obscured by the many details contained in each of them.
To compile the program correctly, there must be something in the place of each
I* Count neighbors.
*'
if ( row<= 0)
stubs function that is used, and hence we must put in short, dummy functions, called stubs.
The simplest stubs are those that do nothing at all:
else
rlow = O;
I* Determine the boundaries.
*'
I* Initialize: initialize grid map. * I rlow = row - 1 ;
void Initialize ( Grid.type map) if (row>= MAXROW - 1)
{ rhigh = MAXROW- 1;
} else
I* WriteMap: write grid map.
void WriteMap (GridJype map)
*' rhigh =row + 1;
if (col <= 0)
{ clow = O;
} else
claw = col - 1 ;
f* NeighborCount: count neighbors of row.col. * I if ( col >= MAXCOL -1)
int NeighborCount(int row, int col, GridJype map) chigh = MAXCOL - 1 ;
{
else
return 1; chigh = col + 1;
}
count = O;
Even with these stubs we can at least compile the program and make sure that the for (i = rlow; i <= rhigh; i+ +)
f* Nested loops count neighbors.
*'
declarations of types and variables are syntactically correct. Normally, however, each for (j = claw; j <= chigh; j ++)
stub should print a message stating that the function was invoked. When we execute the if ( map [i] [j) == ALIVE)
program, we find thal some variables are used without initialization, and hence, to avoid count++;
these errors, we can add code to function Initia lize. Hence the stub can slowly grow and if (map[row] [col] == ALIVE)
be refined into the final form of the function. For a small project like the Life game, we count - - ;
can simply write each funcLion in tum, substitute it for its stub, and observe the effect return count;
on program execution. }

1.4.2 Counting Neighbors 1.4.3 Input and Output

Let us now refine our program further. The function that counts neighbors of the cell It now remains only to write the functions Initialize, WriteMap, and Enquire that do
funcrion in row, col requires that we look in the eighl adjoining positions. We shall use a pair of careful inplll the input and output. In computer programs designed to be used by many people, the
NeighborCount for loops to do this, one running usually from row -1 to row + 1 and the other usually and Olllput functions performing input and output are often the longest. Input to the program must
from col - 1 to col + 1. We need to be careful, when row, col is on a boundary of the be fully checked to be certain that it is valid and consistent, and errors in input must
grid, that we look only at legitimate positions in the grid. To do so we introduce four be processed in ways to avoid catastrophic failure or production of ridiculous results.
 Programming Principles CHAPTER SECTION 1 . 4 Coding, Testing, and Further Refinement 21

The output must be carefully organized and formatted, with considerable thought to what The function CopyMap copies newmap into map.
should or should not be printed, and with provision of various alternatives to suit differing
circumstances.
I* CopyMap: copy newmap into map. • I
Initialization
void CopyMap(Grid. type map, Grid.type newmap)
The task that function Initialize must accomplish is to set the map to its initial configu- {
ration. To initialize the map, we could consider each possible coordinate pair separately int row, col;
input method and request the user to indicate whether the cell is to be occupied or not. This method
for (row= O; row< MAXROW; row++)
would require the user to type in MAXROW • MAXCOL = 50 * 80 = 4000 entries, which
for (col= O; col< MAXCOL; col++ )
is prohibitive. Hence, instead, we input only those coordinate pairs corresponding to
map [row) [col) = newmap [row] [col];
initially occupied cells.
}
'* Initialize: initialize grid map.
void lnitialize(Grid_type map)
*' response from user Finally comes the function Enquire that determines whether the user wishes to go on to
{ calculate the next generation. The task of Enquire i s to ask the user to respond yes or
int row, col; '* coordinates of a cell
printf ( "This program is a simulation of the game of Life. \n"); *'
no; to make the program more tolerant of mistakes in input, this request is placed in a
loop, and Enquire wai ts for a valid response.
for (row= O; row< MAXROW; row ++ )
for (col= O; col < MAXCOL; col ++ )
I* Enquire: TRUE if the user wants to continue execution. * I
map [row] [col] = DEAD;
Boolean.type Enquire ( void)
printf ( "On each line give a pair of coordinates for a living cell. \n 11 ) ; {
printf("Terminate the list with the special pair -1 -1 \n");
int c;
scant ( "%d %d ", &:row, &:col);
while (row!= -1 II col!= -1) { do {
if (row>= 0 &&: row< MAXROW &&: col >= 0 &:& col < MAXCOL) print! ( "Continue (y,n)?\n");
while ( (c = getchar ( ) ) == '\n')
else
map [row] [col) = ALIVE;
; I* Ignore the new line character.
} while (c !='y'&:&c !=' Y'&&c !='n'&&:c ! = ' N');
*'
printf ( "Values are not within range. \n");
scanf("%d %d", &row, &col); if (c == 'y' II c == 'Y')
} retu rn TRUE;
} else
return FALSE;
output For the output function WriteMap we adopt the simple method of writing out the entire }
array at each generation, with occupied cells denoted by * and empty cells by dashes.

'* WriteMap: write grid map.

void WriteMap(GridJype map)
*' At this point, we have all functions for the Life simulation. It is time to pause and check
that it works.
{
int row, col; 1.4.4 Drivers
printf ( 11 \n \n"); separate debugging For small projects, each function is usually inserted in its proper place as soon as it is
for (row= O; row< MAXROW; row ++ ) { written, and the resulting program can then be debugged and tested as far as possible.
for (col= O; col < MAXCOL; col+ + ) For large projects, however, compilation of the entire project can overwhelm that of a
if (map [row] [col] == ALIVE) new function being debugged, and it can be difficult to tell, looking only at the way the
printf ( 11 • 11 ) ; whole program runs, whether a particular function is working correctly or not. Even in
else small projects the output of one function may be used by another in ways that do not
printf (" - " ) ; immediately reveal whether the information transmitted is correct.
printf( 11 \n 11 ) ; One way to debug and test a single function is to write a short auxiliary program
}
whose purpose is to provide the necessary input for the function, call it, and evaluate the
}
driver program result. Such an auxiliary program is called a driver for the function. By using drivers,
 CHAPTER 1 SECTION 1 . 4 Coding, Testing, and Further Refinement 23
22 Programming Principles
print! statemems is to take snapshots of program execution by inse11ing print! statements su rrounded by
each function can be isolated and studied by itself, and thereby bugs can often be spotted
for debugging #ifdefs at key points in the program. A message can be printed each time a function
~~ly. . .. .. is called, and the values of impo11ant variables can be printed before and after each
As an example, Jet us write drivers for the functions of the Life proJect. First, we
function is called. Such snapshots can help the programmer converge quickl y on the
consider the function NeighborCount. In the main program its output is used, but has
not been directly displayed tor our inspecuon , so we should have little confidence that it particular location whe re an error is occurring. Scaffolding is anothe r term frequently
used to describe code inse11ed into a program 10 help wi th debugging. Never hesitate to
is correct. To test NeighborCount we shall supply it with the array map, call it for each
entry of the array, and write out the results. The resulting driver hence uses function put scaffoldi ng into your programs as you write them; it will be easy to recompile the
code without lhe printf statements by not defining certain flags at compile time, and it
Initialize to set up the array and bears some resemblance to the original main program.
may save you much grief during debugging.
I* Driver: test NeighborCount ( ) . *f For very large programs yet another tool is sometimes used. This is a static analyzer,
void main(void) a program that exami nes the source program (as written in C, for example) looking for
{ uninitialized or unused variables, sections of the code th at can never be reached, and
GridJ ype map; other occurrences that are probably incorrect. One example is the UNIX utility lint. This
int i, j; utility finds po11abili1y problems, performs type checking more strictly than the compiler,
and finds problems that are difficult to see. If a version of lint is ava ilable on your system
lnitialize ( map); you might want to run you code through it and check the warnings it may give.
for ( i = O; i < MAXROW; i+ + ) {
for (j = O; j < MAXCOL; i++) 1.4.6 Principles of Program Testing
printf ( "%3d", NeighborCount (i, j, map));
printf ( "\n"); So far we have said nothing about the choice of data to be used to test programs and
} functions. T his choice, of course, depends intimately on the project under development,
} choosing test data so we can make only some general remarks. First we should note:

Sometimes two functions can be used to check each other. The easiest way, for example,
Programming Precept
to check functions Initial ize and WriteMap is to use a driver whose declarations are those
of the main program, and whose action part is The quality of test data is more important than its quantity.

Initialize (map) ; Many sample runs that do the same calculations in the same cases provide no more
WriteMap(map); effective a tesl than one run.
Both functions can be tested by running this driver and making sure that the configuration
printed is the same as that given as input. Programming Precept
Program testing can be used to show the presence of bugs,
1.4.5 Program Tracing but never their absence.

After the functions have been tested, it is time to check out the complete program. One It is poss ible that other cases remain that have never been tested even after many sample
of the most. effective ways to uncover hidden defects is called a structured walkthro11gh. runs. For any program of substantial complexity, it is impossible to perform exhaustive
In this the programmer shows the completed program to another programmer or a small tests, yet the careful choice of test data can provide substantial confidence in the program.
group disc11ssio11 group of programmers and explains exactly what happens, beginning with an explanation Everyone, for example, has great confidence that the typical computer can add two
of the main program followed by the functions, one by one. Stmctured walkthroughs floating-point numbers correctly, but this confidence is certainly not based on testing
are helpful for three reasons. First, programmers who are not familiar with the actual the computer by having it add all possible floating-point numbers and checking the
code can often spot bugs or conceptual errors that the original programmer overlooked. results. If a double-precision floating-point number takes 64 bits, then there are 2 128
Second. the questions that other people ask can help you to clarify your o wn thinking distinct pairs of numbers that could be added. This number is astronom ically large: All
and discover your own mistakes. Third, the structured walkthrough often suggests tests computers manufactured to date have performed altogether but a tiny fraction of this
that prove useful in later stages of software production. number of additions. Our confidence that computers add correctly is based on tests
It is unusual for a large program to run correctly the first time it is executed as of each component separately, that is, by checking that each of the 64 digits is added
a whole, and if it does not, it may not be easy to determine exactly where the errors correctly, and that carrying from one place to another is done correctly.
are. On many systems sophisticated trace tools are available to keep track of function 1es1i11g methods There are at least three general philosophies that are used in the choice of test data.
calls, changes of variables, and so on. A simple and effective debugging tool, however,
!4 Programming Principles CHAPTER 1 S ECTION 1 . 4 Coding, Testing, and Further Relinement 25

I. The Black-Box Method

Most users of a large program are not interested in the details of its functioning; they
only wish to obtain answers. That is, they wish to treat the program as a black box;
hence the name of this method. Similarly, test data should be chosen according to the switch (a) a== 1
specifications of the problem, without regard to the internal details of the program, to case 1:
x • 3; a == 2
check that the program operates correctly. At a minimum the test data should be selected break;
in the following ways: case 2:
if {b •• 0)
x = 2;
data selection l. Easy values. The program should be debugged with data that are easy to check. ,lse x = 3; x = 2; while (c> 0)
x = 4; c = process (c);
More than one student who tried a program only for complicated data, and thought it
break;
worked properly, has been embarrassed when the instructor tried a trivial example. case 3:
while (c >Ol
2. Typical, realistic values. Always try a program on data chosen to represent how the c = process (cl;
program wi ll be used. These data should be sufficiently simple so that the results break

can be checked by hand.

3. Extreme values. Many programs err at the limits of their range of applications. It
is very easy for counters or array bounds to be off by one.
a== 1 a e• 2 a •• 2
... , ~
4. Illegal values. "Garbage in, garbage out" is an old saying that should not be b I= 0
respected in computer circles. When a good program has garbage coming in. then
its output should at least be a sensible error message. It is preferable that the while (c > 0)
c = process (c);
program should provide some indication of the likely errors in input and perform x • 3; x = 2; x = 4;
any calculations that remain possible after disregarding the erroneous input.

!. The Glass-Box Method

The second approach to choosing test data begins with the observation that a program can
hardly be regarded as thoroughly tested if there are some parts of its code that, in fact, Path 1 Path 2 Path 3 Path 4
have never been executed. In the glass-box method of testing, the logical structure of the Figure 1.2. The execution paths through a program segment
path testing program is examined, and for each alternative that may occur, test data are devised that
wi ll lead to that alternative. Thus care is taken to choose data to check each possibility in
ime,face errors not within a function but in the interface between functions, in misunderstanding of the
every switch statement, each clause of every if statement, and the termination condition of
exact conditions and standards of information interchange between functions. It would
each loop. If the program has several selection or iteration statements then it will require
therefore appear that a reasonable testing philosophy for a large project would be to
different combinations of test data to check all the paths that are possible. Figure 1.2
apply glass-box methods to each small module as it is written and use black-box test
shows a short program segment with its possible execution paths.
data to test larger sections of the program when they are complete.
For a large program the glass-box approach is clearly not practicable, but for a
single small module, it is an excellent debugging and testing method. In a well-designed 3. The Ticking-Box Method
program, each module will involve few loops and alternatives. Hence only a few well-
chosen test cases will suffice to test each module on its own. To conclude this section, let us mention one further philosophy of program testing, the
modular testing In glass-box testing, the advantages of modular program design become evident. philosophy that is, unfortunately, quite widely used. This might be called the ticking-box
Let us consider a typical example of a project involving 50 functions, each of which can method. It consists of doing no testing at all after the project is fairly well debugged,
involve 5 different cases or alternatives. If we were to test the who le program as one, but instead turning it over to the customer for trial and acceptance. The result, of course,
we would need 5 50 test cases to be sure that each alt.ema1ive was tested. Each module is ~ rime homh.
separately requires only 5 (easier) test cases, for a total of 5 x 50 = 250. Hence a
problem of impossible size has been reduced to one that, for a large program, is of quite
modest size.
Exercises El. Find suitable black-box test data for each of the following:
comparison Before you conclude that glass-box testing is always the preferable method, we 1.4 a. A function that returns the largest of its three parameters, which are real num-
should comment that, in practice, black-box testing is usually more effective in uncov- bers.
ering errors. Perhaps one reason is that the most subtle programming errors often occur b. A function that returns the sq uare root of a real number.
!6 Programming Principles C HA P T E R 1 CH AP TER 1 Review Questions 27

c. A function that returns the least common multiple of its two parameters, which
must be positive integers. (The least common multiple is the smallest integer
••
• •• •• ••• •• •• •• •••
that is a multiple of both parameters. Examples: The least common multiple
of 4 and 6 is 12, of 3 and 9 is 9, and of 5 and 7 is 35.) •• •• •• ••
d. A function that sorts three integers, g iven as its parameters, into ascending
R Pentomino
••
•• ••
•• ••
•• ••
•• ••
•• ••
•• •• ••
order.
e. A function that sorts an array a of integers indexed from O to a variable n - 1 ••
•• ••
•• ••
• ••
•• ••
•• •• •• ••••
••
•• •• •• ••• •• •• ••••
into ascending order, where a and n arc both parameters.
E2. Find suitable glass-box test data for each of the following: • •••
•• •• •• •• •• ••
a. The statement
•• •• •• ••
•• ••
•• ••• ••• ••
•• ••
•• •• •
• •• •• • •• ••••
if (a < b) if (c > d) x = 1; else if Cc== d) x = 2 ;
••
•• ••• ••
•• •• ••
•• ••••
else x = 3; else if (a == b) x = 4; else i' (c == d) x = 5; Cheshire Cat
else x = 6; Virus

b. The function NeighborCount (row, col, map) .

•••• ••
••
Programming Pl. Enter the Life program of this section on your computer and make sure that it works •• ••• ••• • • •
Proj ects correctly. •• •• ••
1.4 P2. Test the Life program with the examples shown in Figure 1.1 . • •
Tumbler • •
P3. Run the Life program with the initial configurations shown in Figure 1.3.
• •
• •
•
t>QINTERS AND PITFALLS ••• • • • •
1. Be sure you understand your problem before you decide how to solve it. •• • •
2. Be sure you understand the algorithmic method before you start to program.
• • • •
•• • •
3. In case of difficulty, divide the problem into pieces and think of each part separately.
•• •••••• • •
4. Keep your functions short and simple; rarely should a single function be more than
a page long.
•••• ••
• ••
5. Use stubs and drivers, black-box and glass-box testing to simplify debugging. Barber Pole Harvester

6. Use plenty of scaffolding to help loca.li ze errors.

7. In programming with arrays, be wary of index values that are off by l. Always use
extreme-value testing to check programs that use arrays.
• ••
8. Keep
much
your programs well-formatted as you write them-it will make debugging
easier. ••• ••• ••• ••
9. Keep your documentation consistent with your code, and when reading a program
• ••
•••
•••
•• •••
make sure that you debug the code and not just the comments.
IO. Explain your program to somebody else: Doing so will help you understand it better
yourself. The Gl ider Gun

l l. Remember the Programming Precepts! Figure 1.3. Life configurations

28 Programming Principles CHAPTER 1 CHAPTER 1 References tor Further Study 29

REVIEW QUESTIONS The Game of Life

Most chapters of this book conclude with a set of questions designed to help you review The promine n1 British mathematician J. H. CONWAY has made many orig inal contributions
to subjects as di verse as the theory of finite simple gro ups, logic, and combinatorics.
the main ideas of the chapter. These questions can all be answered directly from the
discussion in the book; if you are unsure of any answer, refer to the appropriate section. He dev ised the game of Life by sta rting with previous, techn ical studies of cellular
auto mata and devising re produc tio n rules that would make it di fficult for a configuration
I .3 1. When is it appropriate to use one-letter variable names? to grow without bound, but for which many configurations would go through interesting
2. Name four kinds of infomiation that should be included in program documentation. progressions. CONWAY, however, did not publish his observatio ns, but communicated
3. Why should side effects of functions be avoided? them to MARTIN GARDNER. T he populari ty of the game s kyrocketed when it was discussed
1.4 4. What is a program stub? in
MARTIN GARDNER, "Mathema1ical Games'' (regu lar column), Scie,uific American 223,
S. What is the difference between stubs and drivers, and when should each be used? no. 4 (Oc1ober 1970), 120-123; 224, no. 2 (February 197 1). 11 2-11 7.
6. What is a structured walkthrough? The examples at the end of Sections 1.2 and 1.4 are taken from these columns. These
7. Name two methods for testing a program, and discuss whe n each should be used. column s have been repri nted w ith further results in
8. If you cannot immediately picture all details needed for solving a problem, what MARTIN GARDNER. Wheels, Life and Other Mathematical Amusements, W. H. Freeman,
should you do with the problem? New York, 1983, pp. 214-257.
This book also contai ns a bibliography of art icles o n Life. A quarte rly newslette r,
enti tled Lifeline, was even published for some years to keep the real devotees up to date
on cu rrent deve lopme nts in Life and rel ated topics.
REFERENCES FOR FURTHER STUDY
The C Language
The C programming language was devised by D3NNIS M. RITCHIE. The s tandard reference
is
BRIAN W. KERNIGJIAN and DENNIS M. R.tTCHIE, The C Programming Language, second
edition, Prentice Hall. Englewood Cliffs. N.J., 1988. 272 pages.
This book contains many examples and exercises. For the solutions to the exercises in
Kernighan and Ritchie, together with a chance to study C code, see
Cwv1s L. T oNDO and Scorr E. G1MPEL, The C Answer Book , second edition, Prcmicc
Hall , Englewood Cliffs, N.J.. 1989, 208 pages.

Programming Principles
Two books that contain many helpful hints on prog ramming style and correctness, as
well as examples of good and bad practices, are
BRIAN W. K F.RNJGHAN and P. J. P 1.A1:0ER. The Elements of Programming Style, second
edition, M cGraw- Hill, New York, 1978, 168 pages.

DEN:sre VAN TASSEL, Program Style, Design, Ehiciency, Debugging . and Testing, second
edition, Prentice Hall, Englewood Cliffs, N.J., 1978. 323 pages.
EDSGER W. DIJKSTRA pioneered the movement known as structured programming, which
insists on taking a carefully organized top-down approach to the design and writing of
programs, whe n in March 1968 he caused some consternation by publishing a lette r
e ntitled "Go 'Io Statement Considered Harmful" in the Communications of the ACM
(vol. 11, pages 147- 148). DIJKSTRA has since published several papers and books that
are most instructive in programming method. One book of s pecial interest is
E. W. DuKSTRA, A Discipline of Programming, Prentice Hall, Englewood Cli ffs. NJ.•
1976, 217 pages.
 S ECTION 2. 1 Program Maintenance 31
CHA P T E R 2
Software engineering is the discip line within computer science concerned with tech-
niques needed for the production and maintenance of large software systems. Our goal
in introducing some of these techniques is to demonstrate their importance in problems
of practical size. A lthough much of the discussion in this c hapter is motivated by the

Introduction I .ifo game and applied specifically to its program, the discussion is always intende.d to
illustrate more general methods that can be applied to a much broader range of problems
of practical importance.

to Software I
2.1 PROGRAM MAINTENANCE
Small programs wriuen as exercises or demonstrations are usually run a few times and
the n discarded. but the disposition of large practical programs is quite different. A
program of pract ical value w ill be run many times, usuall y by many different people,

Enginee
and its writing and debugging mark only the beginning of its use. They also mark only
the beginning of the work required to make and keep the program useful. It is necessary
to review and analyze the program to ensure that it meets the requirements specified for
it, adapt it to changing e nvironments, and modify it to make it better meet the needs of
its users.
Let us illustrate these activities by reconsidering the program for the Life game
written and tested in Chapter 1.
This chapter continues to expound the principles of good program design, 1. Review of the Life Program
with special emphasis on techniques required for the production of large
software systems. These techniques include problem specification, algo- If you have run the Life program on a s mall computer or on a busy time-sharing system ,
rithm development, ver(fication, and analysis, as well as program testing problems then you will likely have found two major problems. First, the method for input of
the initial configuration is poor. It is unnatural for a person to calculate and type in
and maintenance. These general principles are introduced in the context
the numeri cal coordinates of each living cell. The form of input should instead reflect
of developing a second program for the Life game, one based on more
the same visual imagery as the way the map is printed. Second, you may have found
sophisticated methods than those of the last chapter. the program's speed somewhat disappointing. There can be a noticeable pause between
printing one generation a nd starti ng to print the next.
Our goal is to improve the program so that it will run really efficiently on a micro-
computer. T he problem of improving the fonn of input is addressed as an exercise; the
2.1 Program Maintenance 31 2.4.3 Initialization 47 text discusses the problem of improving the speed.
2.2 Lists in C 35 2.5 Program Analysis and 2. Analysis of the Life Program
Comparison 48
2.3 Algorithm Development: A Second We must first find out where the program is spending most of its computation time. If
Version of Life 37 2.6 Conclusions and Preview 51 we examine the program, we can first note that the trouble cannot be in the function
2.3.1 The Main Program 37 2.6.1 The Game of Life 51 Initialize, since this is done only once, before the main loop is started. Within the loop
2.3.2 Refinement: Development of the 2.6.2 Program Design 53
operation counts that counts generatio ns, we have a pair of nested loops that, together, will iterate
Subprograms 39 2.6.3 The C Language 55
2.3.3 Coding the Functions 40
Pointers and Pitfalls 57 MAXROW x MAXCOL = 50 x 80 = 4000
2.4 Verification of Algorithms 44 Review Questions 57 times. Hence program lines within these loops will contribute substantially to the time
2.4.1 Proving the Program 44 used.
2.4.2 Invariants and Assertions 46 References for Further Study 58 The first thing done within the loops is to invoke the function NeighborCount. The
nested loops function itself includes a pair of nested loops (note that we are now nested to a total
depth of 5), whic h usually do their inner statement 9 times. The func tion also does 7
statements outside the loops, for a to tal (usually) of 16.
10
32 Introduction to Software Engineering C HAP TER 2 SECTION 2 . 1 Program Maintenance 33

Within the nested loops of the main program there are, along with the call to the occupied. If we can prevent or substantially reduce such useless calculation, we shall
function, only the comparison to find which c3:se to do and the appropriate assignment obtain a much betler program.
statement, that. is, there arc only 2 statements additional to the 16 in the function. Out- As a fi rst approach, let us consider trying to limit the calculations to cells in a
side of the nested loops there is the function call CopyMap ( map, newmap), which, in limited area around those that are occupied. If th is occupied area (which we would have
copying 4000 entries, is about equivalent to 1 more stareme.nt within the loops. There to defi ne precisely) is roughly rec1angula r, then we c~ n implement this scheme easil y by
is also a call to the function WriteMap, some variation of which is needed in any case replacing the limits in the loops by ot her variables that wou ld bound the occupied area.
so that. the user can see what the program is doing. Our primary concern is with the But th is scheme wou ld be very inefficient if the occupied area were shaped like a large
computation, however, so let us not worry about the time that WriteMap may need. \Ve ri ng, or, indeed, if there were only two small occupied areas in opposite comers of a
thus see that for each generation, the computation involves about very large rectangle. To try to carry out this plan for occupied areas not at all rectangular
in shape would probably require us to do so many comparisons, as well as the loops, as
4000 x 19 = 76,000 to obviate any savi ng of time.

statements, of which about 4000 x J6 = 64,0CX) are done in the function. 4. A Fresh Start and a New Method
On a small microcomputer or a tiny share of a busy time-sharing system, each
statement can easily require 100 to 500 microseconds for execution, so the time to Let us back up for a moment. If we can now decide to keep an array to remember
calculate a generation may easily range as high as 40 seconds, a delay that most users the number of occupied neighbors of each cell, then the only counts in the array that
will find unacceptable. wi ll change from generation to generation will be those that correspond to immediate
Since by far the greatest amount of time is used in the function calculating the neighbors of cells th at die or are born.
number of occupied neighbors of a cell, we should concentrate our attention on doing We can substantially improve the ru nning time of our program if we convert the
this job more efficiently. Before starting to develop some ideas, however, let us pause arrays and f11nc1io11s function Ne ighborCount into an array and add appropriate statements to update the array
momentarily to pontificate: wh ile we are doing the changes from one generation to the nex t embodied in the s witch
statement, or, if we prefer (what is perhaps conceptually easier), while we are copying
newmap into map we can note where the births and deaths have occurred and at that
time update the array.
To emphasize that we are now using an array instead of the function NeighborCount,
we shall change the name and write numbernbrs for the array.
The method we have now developed still involves scanning at least once through
the fu ll array map at every generation, which like ly means much useless work. By
It takes much practice and experience to decide what 1s important and what may be being slightly more careful, we can avoid the need ever to look at unoccupied areas.
neglected in analyzing algorithms for efficiency, but it is a skill that you should carefully algorithm As a cell is born or dies it changes the value of nu mbernbrs for each of its immediate
develop to enable you 10 choose alternative methods or tu concentrate your programming developme111 neighbors. While making these changes we can note when we find a cell whose count
efforts where they will do the most good. becomes such that it will be born or die in the next generation. Thus we should set up
two lists that will contain the cells that, so to speak, are moribund or are expecting in
3. Problem-solving Alternatives the coming generation. In th is way, once we have finished making the changes of the
current generation and printing the map, we will have waiting for us complete lists of all
Once we know where a program is doing most of its work, we can begin to consider the births and death s to occur in the comi ng generation. It should now be clear th at we
allemative methods in the hope of improving its efficiency. ln the case of the Life game, reall y need two lists for births and two for deaths, one each for the changes being made
Jet us ask ourselves how we can reduce the amount of work needed to keep track of now (which are depleted as we proceed) and one list each (which are being added to)
the number of occupied neighbors of each Life cell. ls it necessary for us to calculate contai ning the changes for the next generation. When the changes on the current lists
use or array the number of neighbors of every cell at every generation? Clearly not, if we use some are complete, we pri nt the map, copy the coming lists to the current ones, and go on to
way (such as an array) t.o remember the number of neighbors, and if this number does the next generation.
not change from one generat;on to the next.. If you have spent some time experimenting
with the Life program , then you will ce1tainly have noticed that in many interesting
configurations, the number of occupied cells at any time is far below the total number of 5. Algorithm Outline
positions available. Out of 4000 positions, typically fewer than 100 are occupied. Our
program is spending much of its time laboriously calculating the obvious facts that cells Let us now summarize our decisions by writing down an informal outline of the program
isolated from the living cells indeed have no occupied neighbors and will not become we shall develop.
14 Introduction to Software Engineering CHAPTER 2 SEC T I ON 2 . 2 Lists in C 35
Initial configuration:
live d ie
Exercises El. Sometimes the user might wish to run the Life game on a grid smaller than 50 x 80.
2 3 4 5
2.1 Detem1ine how it is possible to make maxrow and maxcol into variables that the
user can set when the program is run. Try to make as few changes in the program
2 • (2, 2)
(2, 4)
(3, 3) as possible.
3 • • • (4, 2) E2. One idea for changing the program to save some of the if statements in the func-
4 • (4, 4 )
tion NeighborCount is to add two extra rows and columns to the arrays map and
newmap. by changing their dimensions to
5

[MAX ROW + 2) [MAXCOL + 2) .

In progress (changes shown in italic and with • )
live die nextlive nextdie (Note that this would also mean changing the cell coordinates to be 1 to MAXROW
and 1 to MAXCOL rather than O to MAXROW- 1 and O to MAXCOL - 1.) Entries in the
extra rows and columns wou ld always be dead, so that the loops in NeighborCount
• • • ~
~
(1, 3)
(3, 7)
(2, 3)
(3, 2)
cou ld always run their full range from i - 1 to i + 1 and j - 1 to j + 1. How would
• • • (4, 2)
(4, 4)
(3, 4) this change affect the count of statements executed in NeighborCount?
• •
Programming Pl. Rewrite the function Initialize so that it accepts the occupied positions in some
Projects symbolic form, such as a sequence of blanks and X's in appropriate rows, rather
End of one generation (changes shown i n italic and with • )
2.1 than requiring the occupied positions to be entered as numerical coordinate pairs.
l ive die nextlive nextdie P2. On a slow-speed terminal writing out the entire map at every generation will be
quite slow. If you have access to a video terminal for which the cursor can be
• • • ~ (3, 3) U,3} (2,3)
(3, 2 )
controlled by the program, rewrite the function WriteMap so that it updates the map
instead of completely rewriting it at each generation.
• x • ~
~
(3, I)
(3,5) (3,4)

• • • l4,-4l (5,3) (4, 3)

2.2 LISTS IN C
l~___ ca_PY
__ ~J As we develop the revised Life program that follows the scheme we have devised in
Figure 2.1. Life using lists the last section, we must make some decisions about what variables we shall need and
the ways in which we shall implement the lists we have decided to use. (Lists will be
initialization Get the initial configuration of living cells and use it to calculate an array holding the
neighbor counts of all cells. Construct lists of the cell; that will become alive and covered in detail in Chapter 3.)
that will become dead in the first generation;
1. The Logical Structure of Lists
ma.in loop Repeat the following seeps as long as desired:
For each cell on the list of cells to become al ive: A list really has two distinct parts associated with it. First is a variable that gives the
Make the cell alive; number of items in the list. Second is an array that contains the items on the list. In
Update the neighbor c-ounts for each neighbor of the cell; most languages the programmer must carry the counter variable and the array separately
If a neighbor count reaches the appropriate value, then add the cell to the (and doing so is a frequent source of trouble for beginners). Sometimes tricks are used,
list of cells to be made alive or dead in the next generation; such as using entry O of the array as the counter.
For each cell on the list of cells to become dead:
Make the cell dead; Update the neighbor counts for each neighbor of the 2. Definition and Examples
cell; If a neighbor count reaches the appropriate value, then add the In our case, we may define a type called Lisltype with declarations such as the following:
cell to the list of cells to be made alive or dead in the next generntion;

prepare for next

generation
Write out the map for the user;
Copy the lists ()f cells to be changed in the next generation to the lists for the
current generation. declaration of list
#define MAXLIST 200
typedef struct lisUag {
f* maximum size of lists
*'
int count;
Clearly a great many details remain to be specified in this outline, but before we consider
these details, we need to develop some new tools.
Entry Jype entry [MAXLIST) ;
} LisUype;
f* Entry_type is defined elsewhere.
*'
36 Introduction to Software Engineering CHAPTER 2 S EC T I O N 2 . 3 Algorithm Development: A Second Version ol Lile 37

The four lists that we wish to have are now variables of type LisUype, declared as usual: The arrow (->) operator is used to access a structure member through a pointer to
the structure. Thus, list->count dereferences the pointer list and accesses the structure
member called count.
LisUype die, live, ne).(tdie, neictlive;

Exercises El. Write a function that wi ll delete the last coordinate from a list (as defined in the
3. Hierarchical Structures: Data Abstraction 2.2 text) or will invoke a function Error if the list was empty.

The entries in our I ists will be coordinate pairs [x, y] , and there is no reason why we E2. Write functions that will copy one list to another list (as the structure type defi ned
should not think of these pairs as a single structure, by defining in the text). Use the foll owing methods: (a) copy the entire structures; (b) use a
loop to copy only the entries. Wh ich vers ion is easier to write? Which vers ion will
usually run faster, and why?
typedef struct coordJag {
int row; f* x *'
int col; I* y *I
} Coord.type;
2.3 ALGORITHM DEVELOPMENT: A SECOND VERSION OF LIFE
Tf we then define Entry _type in terms of Coord_type, After deciding on the basic method and the overall outline of the data structures needed
for solving a problem, it is time to commence the process of algorithm development,
typedef Coord.type Entry .type; beginning with an overall outline and slowly introducing refinements until all the details
are specified and a program is formulated in a computer language.

we shall have put these coordinates into our lists, as we wish to do.
Note that we now have an example of a structure (coord.tag) contained as entries 2.3.1 The Main Program
hierarchical in arrays that are members of another structure (lisUag). Such structures are called
structures hierarchical. By putting structures within structures, structures in arrays, and arrays In the case of the Life game. we can now combine our use of structures as the data
in structures, we can build up complicated data structures that precisely describe the structures for lists with the outline of the method given in part 5 of Section 2.1, thereby
relationships in the data processed by a program. translating the outline into a main program written in C. With few exceptions, the dec-
larations of constants, types, and variables follow the discussion in Sections 2.1 and 2.2
When we work with structures, however, we should never think of them as having
along with the corresponding dec larations for the first vers ion of the Life game. The
top-down. design of such a complicated form. Instead, we should use top-down design for data structures
data structures include file liledef. h contains:
as well as for algorithms. When we process the large, outer structures, we need not be
concerned about the exact nature of each component within the structure. When we write #define MAXROW 50 I* maximum number of rows allowed *I
algorithms to manipulate the innermost components, we should treat them only in terms #define MAXCOL 80 I* maximum number of columns allowed * I
of their simple form and not be concerned as to whether they may later be embedded in #define MAX LIST 100 I* maximum number of elements in a list *I
larger structures or arrays. We can thus use structures to accomplish inf ormation hiding,
whereby we can design the upper levels both of algorithms and data structures without
worrying about the detai ls that will be specified later on lower levels of refinement.
typedef enu m status.tag { DEAD, ALIVE } Status.type; I* status of cell
*'
As one further example of processing hierarchical structures, we can write a short
function that will add an entry coordinate to the end of a list called list.
typedef Status.type G rid.type [MAXROW] [MAXCOL]; I* grid definition
typedef int GridcounUype [ MAXROW] [MAXCOL] ; *'
typedef struct coord .tag {
int row;
void Add (List.type *list, Coord.type coordinate) int col;
adding to a list { } Coard.type;
if (list- >count >= MAXUST)
Error ( "list overflow" ) ; typedef struct list.tag {
else int count;
list- >entry [list->count+ + J = coordinate; Coord.type entry [MAXLIST] ;
} } List.type;
18 Introduction to Software Engineering CHAPTER 2 SEC T I ON 2 . 3 Algorithm Development: A Second Version of Lile 39

The include file calls.h contains the function prototypes: array numbernbrs. As part of the same functions, when the neighbor count reaches an
appropriate value, a cell is added to the list nextlive or nextdie to indicate that it will
void Copy ( LisUype *, LisUype *) ; be born or die in the coming generation. Finally, we must copy the lists for the coming
int Enquire (void);
generation into the current ones.
void lnitialize(LisUype *, LisUype *, LisUype *, LisUype *,
GridJype, GridcounUype);
void WriteMap(Grid_type) ; 2.3.2 Refinement: Development of the Subprograms
void ReadMap(LisUype *, GridJype); After the solution to a problem has been outlined, it is time to turn to the various parts
void Vivify ( LisUype *, Grid_type, GridcounUype); of the outline, to include more details and thereby specify the solu tion exactly. While
void Kill (LisUype *, GridJype, GridcounUype); making these refinements, however, the programmer often discovers that the task of
void AddNeighbors(LisUype *, LisUype *, LisUype *, each subprogram was not specified as carefully as necessary, that the interface between
GridcounUype, GridJype); specifications and different subprograms must be reworked and spelled out in more detail, so that the
void SubtractNeighbors (LisUype *, LisUype *, LisUype *, problem solving different subprograms accomplish all necessary tasks, and so that they do so without
GridcounUype, GridJ ype); duplication or contradictory requirements. In a real sense, therefore, the process of
void Add(LisUype *, CoordJype) ; refinemen t requires going tack to the problem-solving phase to find the best way to split
The main program then is: the required tasks among the various subprograms. Ideally, this process of refinement
and specification should be completed before any coding is done.
I* Simulation of Conway's game of Life on a bounded gnd * I Let us illustrate this activity by work ing through the requirements for the various
I* Version 2. * I subprograms for the Life game.
#include "general.h"
#include II lifedef.h II I* Life's defines and typedefs 1. The Task for AddNeighbors
#include 11 calls.h II I* Life's function declarations Much of the work of our program will be done in the functions AddNeighbors and
Life2, main program void main ( void) SubtractNeighbors. We shall develop the first of these, leaving the second as an exercise.
{ The function AddNeighbors will go through the list live, and for each entry will find its
GridJype map;
GridcounUype numbernbrs;
I* current generation
I* number of neighbors *'*' immediate neighbors (as done in the original function NeighborCount), will increase the
count in numbernbrs for each of these, and must put some of these on the lists nextlive
LisUype live, nextlive; and nextdie. To determine which, let us denote by n the updated count for one of the
List.type die, nextdie; neighbors and consider cases.
Initialize ( &live, &die, &nextlive, &nextdie, map, numbernbrs);
cases for I. It is impossible that n = 0, since we have just increased n by I.
WriteMap (map); AddNeighbors
do { 2. If n = I or n = 2, then the cell is already dead and it should remain dead in the
Vivify( &live, map, numbernbrs); next generation. We need do nothing.
Kill ( &die, map, numbernbrs) ; 3. If n = 3, then a previously live cell still lives; a previously dead cell must be added
WriteMap (map) ; to the list nextlive.
AddNeighbors( &live, &nextlive, &nextdie, numbernbrs, map); 4. If n = 4, then a previously live cell dies; add it to nextdie. If the cell is dead, it
SubtractNeighbors ( &die, &nextlive, &nextdie, numbernbrs, map); remains so.
Copy ( &live, &nextlive); 5. If n > 4, then the cell is already dead (or is already on list nextdie) and stays there.
Copy( &die, &nextdie);
} while ( Enquire ( ) ) ; 2. Problems
}
One subtle problem arises wi th this function. When the neighbor count for a dead
Most of the action of the program is postponed to various functions. After initializing cell reaches 3, we add it to the list nextlive, but it may well be that later in function
desc:riprion all the lists and arrays, the program begins its main loop. At each generation we first spurious emries AddNeighbors, its neighbor count will again be increased (beyond 3) so that it should not
go through the cells waiting in lists live and die in order to update the array map, be vivified in the next generation after all. Similarly when the neighbor count for a live
which, as in the first version of L ife, keeps track of which cells are alive. This work cell reaches 4, we add it to nextdie, but the function SubtractNeighbors may well reduce
is done in the functions Vivify (which means make alive) and Kill. After writing the its neighbor count below 4, so that it should be removed from nextdie. Thus the final
revised configuration, we update the count of neighbors for each cell that has been determination of lists nextlive and nextdie cannot be made until the array numbernbrs
born or has died, using the functions AddNeighbors and SubtractNeighbors and the has been fully updated, but yet, as we proceed, we must tentatively add entries to the lists.
10 Introduction to Software Engineering CHAPTER 2 SEC TION 2 . 3 Algorithm Development: A Second Version of Life 41

postpone dif]iculty II turns out that, if we postpone solution of this problem, it becomes much easier.
map live d ie
Jn the functions AddNe ighbors and SubtractNeighbors, .let us add eelIs to nextlive and 2 3 4 5
nextdie without worrying whether they will later be removed. Then when we copy
0 1 0 2, 2 2,3

duplicate eruries
nextlive and nextdie to lists live and die, we can check that the neighbor counts arc
cunecl (iu live, for example, only dead cells with a neighbor cou nt of exactly J should
appear) and delete the erroneous entries with no difficulty.
After doing this, however, an even more subtle error remains. It is possible th at
Initial configuration :

Mai n loop:
2
3
4
3 •3
1 •2 •3 •2
2 3 2
3
2, 4
4.3
3, 2
3,3
3,4 --
the same cell may appear in list nextlive (or nextdie) more than once. A dead cell,
for example, may initially have a count of 2, which, when increased, adds the cell to
nextlive. lts count may then be increased fu1ther, and in SubtractNeighbors decreased
one or more times, perhaps ending at 3, so that SubtractNe ighbors again adds it to
generation status after Vivify and Kill: status at end of loop:
nextlive. Then, when neighbor counts are updated in the next generation, this birth will
incorrectly contribute 2 rather than I to the neighbor counts. We could solve this problem live die map live die
by search ing the lists for duplicates before copying them, but to do so would be slow,
and we can again solve the problem more easily by postponing it. When, in the next 2, 2 3 1. 3 2.3
generation, we wish to vivify a cell, we shall fi rst check whether it is already alive. If
so, then we know that its entry is a duplicate of one earher on list live. While we are
postponing work, we might as well also postpone checking the neighbor counts, so that
2, 4
4, 3
- •
•4

3
•s
•s
•
•
. 4

3
-- 4, 2
4, 4
3, 3
3, 2
3, 4 -
the copying function will now do nothing but copy lists, and all the checking is done
in Vivify and Ki ll. Figure 2.2 shows the trace of Life2 for one small configuration and spurious spurious
exhibits the appearance and deletion of spurious and duplicate entries in the various lists. 2 1, 3 2, 3 2 • 2 1, 2 , 2, 2 ;

r
;:., ,, ~.. ~~ 1
·~.~ -4 $i;:.. • $
*,
c:t ;_;. -:,
Programming Precept
._;· ·:.:·
·· ~~o,miliOJe~ P9Stponin~ proqle!JlS simJ)lifie~ their solu!ion.
.;.:. . ~- . ·.
"
4, 2
4, 4
3, 3
3, 2
3, 4 - 2
• 1

3
•, • 2
3 • 1

• 1
3 2 - 1, 4
3,1
3.5
3, 2
3, 4
2, 4
4,3
2.2~
4, 2
2, 4
-

2, 3 4, 4
duplicates
!.3.3 Coding the Functions 3 2. 3 2, 2 2 •1 2 1, 2 3. 2
Now that we have spelled out completely and precisely the requirements for each func-
tion, it is time to code them into our programming language. In a large software project
it is necessary to do the coding at the right time, not too soon and not too late. Most pro-
grammers err by starting to code too soon. If coding is begun before the requirements are
3, 4
3, 2
2.4
4,4
4, 2 - 1 • 2
3 •3

• 2
•2
3
1 - 1, 4
2. 4
3, 5
2, 2
3, 1
3, 4
2,3
4, 3
1, 3
--
specifi.cations made precise, then unwarranted assumptions about the specifications will inevitably be
complete made while coding, and these assumptions may render different subprograms incompat-
ible with each other or make the programming task much more difficult than it need be.
··.·.;, <, ~ »: ..
4 2, 2
2.4
1, 3
- •
2
. 4
3
•
2
- 1, 2
1, 3
1, 4
2, 3 -

Brogramming Precept • •
•
t(•p-down coding It is possible, on the other hand, to delay coding too long. Just as we design from the top
down, we should code from the top down. Once the specifications at the top levels are 5 1,3 2,3 -- •
complete and precise, we should code the subprograms at these levels and test them by • •
including appropriat.e stubs. lf we then find that our design is flawed, we can modify it stable
configuration • •
without paying an exorbitant price in low-level functions that have been rendered useless.
Now that the specifications for several of the Life subprograms are complete, let us
•
embody our decisions into functions coded in C. Figure 2.2. A trace of program Life2
 SECT ION 2.3 Algorithm Development: A Second Version of Life 43
42 Introduction to Software Engineering CHAP TE R 2
I* AddNeighbors: increase the neighbor count of vivified cells *I
1. Function Copy void AddNeighbors (LisUype * live, LisUype *nextlive, LisUype * nextdie,
Since we decided to postpone all the checking for spurious entries in the lists, the final Gridcount.type numbernbrs, GridJype map)
version of the copying function is trivial. It. need only copy one list to another and leave {
the first empty: int i, j; I* loop indices *I
int ilow, ihigh; I* row loop limits *I
I* Copy: copies the contents of one list to another. * I int jlow, jhigh; I* column loop limits *I
void Copy CList.type *IO, LisUype *from) int k, row, col; I* used to traverse list *'
copy one list { CoordJype nbr; I* structure form of a neighbor *'
int i;
for (k = O; k < live->count; k++ ) { I* Loop through vivified cells. *I
for ( i = O; i < from->count; i ++ ) row = live->entry [k] .row;
to- >entry [i] = from- >entry [i] ; col = live->entry [k] .col;
to->count = from->count; if (row<= 0) I* Set the loop limits. *I

}
from->count = O; I* Clear the copied list.
*' ilow = O;
else ilow = row - 1;
if (row>= MAXROW- 1)
2. Function Vivify ihigh = MAXROW - 1;
else ihigh = row + 1;
The function Vivify goes through the list live and vivifies each cell, provided that it was
if (col <= O)
previously dead and had a neighbor count of exactly 3. Otherwise, the cell is one of
jlow = O;
the spurious entries, and Vivify deletes it from the list. Hence at the conclusion of the
else jlow = col -1 ;
function, list live contains exactly those cells that were vivified and whose neighbor
if ( col >= MAXCOL- 1)
counts must therefore be updated by AddNeighbors.
jhigh = MAXCOL -1 ;
I* Vivify: make cells alive and check for duplicates *I else jhigh = col + 1;
void Vivify (List.type * live, GridJype map, GridcounUype numbernbrs) for (i = ilow; i <= ihigh; i+ +)
make cells alive { for (j = jlow; j <= jhigh; i ++ )
int k, row, col; if Ci ! = row 11 j ! = col) { I* Skip the cell itself. *I
k = O; find a neighbor nbr.row = i; f* Set up a coordinate structure. *I
while (k < live->count) { nbr.col = j;
row = live - >entry [k] .row; numbernbrs [i] [j] ++ ;
col = live->entry [ k] .col; switch ( numbernbrs [i] [j] ) {
if (map [row] [col] == DEAD && numbernbrs [row] [col] == 3) { put cells onto lists case 0:
map [row] [col] = ALIVE; I* Make the cell alive. *I printf (" Impossible case in AddNeighbors. \n") ;
k++; break;
} else { I* Delete entry k from the list. *' case 3:
live- >count--; if ( map [i] [j] == DEAD)
live->entry [k] = live- >entry [live- >count] ; Add(nextlive, nbr);
} break;
} case 4:
} if (map [i] [j] == ALIVE)
Add ( nextdie, nbr) ;
I. Function AddNeighbors break;
} /* switch statement *f
At the conclusion of function Vivify, the duplicate and ~purious entries have all been }
removed from list live, and what remains are the cells that were actually vivified. Hence
the function AddNeighbors can update all the related neighbor counts without problem.
This function has the following form.
}
} I* k loop
*'
 SECTION 2.4 Verification of Algorithms 45
14 Introduction to Software Engineering CHAPTER 2
same status (alive or dead) from the end of function Kill until the next generation, and the
l. Remaining Functions functions AddNeighbors and SubtractNeighbors check that only dead cells are added to
The functions Kill and SubtractNeighbors are similar in form to Vivify and AddNeighbors; nextlive and only living cells to nextdie.
they will be left as exercises. The function WriteMap can be used without change from How can we be sure that there are not more subtle questions of this sort, some of
the first. version. but. a much more efficient version is possible that makes use of the lists which might not be so easy to answer? The only way we can really be confident is to
live and die to update the screen rather than rewriting it. at. each generation. The function prove that our program does the right action in each case.
Add appear s in Section 2.2. We shall postpone writing function Initialize to the end of 2. The Main Loop
the next section.
The difficulty with our program is that what happens in one generation might affect the
next generation in some unexpected way. Therefore we focus our attention on the large
Programming Pl. Write the missing functions for the second version of Life: (a) Kill and (b) Sub- loop in the main program. At the beginning of the loop it is the contents of lists live
Projects tractNeighbors. and die that determine everything that happens later. Let us therefore summarize what
2.3 P2. Write driver programs for the functions (a) Kill anc (b) SubtractNeighbors, and we know abou1 these lists from our previous study.
devise appropriate test data to check the performance of these functions.
loop invaria111 At the begi1111ing of the main loop, list live contains only dead cells, and list die
collfains only living cells, bur the lists may contain duplicate entries, or spurious
entries whose neighbor counts are wrong . The lists nextlive and nextdie are empty.
2.4 VERIFICATION OF ALGORITHMS
At the very start of the program, it is one task of function Initialize to ensure that the
Another important aspect of the design of large programs is algorithm verification, that
lists live and die are set up properly, so that the preceding statements are correct at the
is, a proof that the algorithm accomplishes its task. This kind of proof is usually
start of the firs1 generation. What we must prove, then, is that if the statements are true
form ulated by looking at the speci fications for the subprograms and then arguing that
at the start of any one generation, then after the eight function calls within the loop, they
these specifications combine properly to accomplish the task of the whole algorithm.
will again be true for the nex t generation.
purpose While constructing such a proof we may find that the specifications must be changed
to enable us to infer the correctness of the algorithm, and, in doing so, the proof itself 3. Proof by Mathematical Induction
helps us fomrnlate the specifications for each subprogram with greater precision. Hence At this point, you should note that what we are really doing is using the method of
algorithm verification and algorithm design can go hand-in-hand, and sometimes the mathematical induction to establish that the program is correct. In this method of
verification can even lead the way. In any case, algorithm verification shou.l d precede initial case proof, we begin by establishing the result for an initial case. Next we prove the result
coding. for a later case, say case n, by using the result for earlier cases (those between the initial
case and case n - I ). See Appendix A. I for further discussion and examples of proof
~.4.1 Proving the Program by mathematical induction.
For our program, verification of the initial case amounts to a verification that Initialize
Let us again illustrate these concepts by turning to the Life program, first to be sure
induction step works properly. For the second part of the proof, let us examine the actions in the main
that its algorithm is correct and second to assist us in designing the remaining function,
loop, assuming that the statements are correct at its beginning. Function Vivify uses only
Initialize.
list live and carefully checks each entry before it vivifies a cell, removing erroneous and
Indeed, the fact that there were subtle errors in our initial attempts to organize the duplicate entries from list live as it goes. Hence at the conclusion of Vivify, list live
work done in functions Vivify, Ki ll, AddNeighbors, SubtractNeighbors, and Copy should
contains only those cells that were properly vivified, and no duplicates. Function Kill
caution alert us to the possible presence of further errors, or at least to the necessity of exercising similarly cleans up list die. Since the two lists originally had no cells in common, and
considerably more care to be sure that our algorithms are correct.
none has been added to either list, no cells have been improperly both vivified and killed.
Next, funct ion WriteMap is called, but does not change the lists. Function AddNeighbors
I. Possible Problems
works only from list live and puts only dead cells on list nextlive, and only living ones
By postponing the checking of neighbor counts, we were able to avoid difficulties both on list nextdie. Similarly, function SubtractNeighbors keeps the dead and living cells
with the problems of duplicate and of erroneous entries. But, for example, how can properly separated. Together these two functions add all the cells whose status should
we be sure that it is not still possible that the same cell might erroneously be included change in the next generation 10 the lists, but may add duplicate or spurious entries.
in both lists nextlive and nextdie? Tf so, then it. might first be vivified and then killed Finally, the copying function sets up lists live and die and empties lists nextlive and
immediately in the following generation (clearly an illegal happening). The answer to nextdie, as required to show that all conditions in our statements are again true at the
this particular question is no, since the main program calls both functions Vivify and end of proof beginning of the next generation. The logic of our program is therefore correct.
Kill before either function AddNeighbors or SubtractNeighbors. Thus the cell keeps the
46 Introduction to Software Engineering CHAPTER 2 S EC T I O N 2. 4 Verification of Algorithms 47

2.4.2 Invariants and Assertions a proof that a program is correct, but it is a very useful exercise. Attempting to find
simplifica1io11 invariants and assenions sometimes leads to simplifications in design of the algorithm,
Statements such as the one we established in the preceding proof are called loop invari- which make its correctness more obvious. Our goa l should always be to make our
ants. In general, a loop invariant is a stateme_nt that is true at the beginning of every algorithms so straightforward and clear that their logic is obviously correct, and the use
iteration of the loop. The. statements we made aho11t th~ s1a111s of various lists at dif- of loop invariants can help in this process.
ferent points of the loop are called assertions, and assertions that hold at the beginning
and end of each function (or, more generally, before and after any statement) are called
preconditions and postconditions. Programming Precept
As an example, let us write down preconditions and postconditions for some of our Know your problem.
functions: Give precise preconditions and postconditions for each function.

Algorithm verification is a subject under active research, in which many imponant ques-
Vivify:
tions remain to be answered. Correctness proofs have not yet been supplied for a large
precondition: List live contains only dead cells and contains all cells ready to be number of imponant algorithms that are in constant use. Sometimes exceptional cases ap-
vivified. pear that cause an algorithm to misbehave; correctness proofs would provide a consistent
postcondition: Array map has been updated with vivified cells, and list live contains means to delineate these exceptions and provide for their processing.
only those cells that were vivified, with no duplicates or spurious
entries.
2.4.3 Initialization
As we turn, finally, to the function Initialize, let us use the postconditions for the function
10 help in its composition. The first postcondition states that the array map is to be
Add Neighbors:
design of Initialize initialized with the starting configuration of living and dead cells. This task is similar to
precondition: List live contains all vivified cells whose neighbor counts have not the initialization of the first version of the program, and we leave the resulting function
yet been updated. ReadMap as an exercise. We shall, however, need the list of initially living cells for
postcondition: Array numbernbrs has increased counts for all cells neighboring calculating the neighbor counts, so we shall also require ReadMap to put this list into list
cells in list live . If the increased neighbor count makes the cell a live. As one of its postconditions ReadMap will be required to make sure that there are
candidate to be vivified lresp. killedJ then the cell has been added no duplicates in this list. (This can be achieved easily if the reading is done properly.)
to list nextlive [resp. nextdie]. The second task is to initialize the neighbor counts in array numbernbrs. But we
have required ReadMap to set up list live so that it contains exactly the information
needed for function AddNeighbors to set the neighbor counts properly for all neighbors
of living cells, provided that before calling AddNeighbors, we first set all entries in
Initi alize: numbernbrs to 0. As well as initializing numbernbrs, function AddNeighbors will
prec-ondffion: None. locate all dead cells that will become alive in the following generation and add them
to list nextlive. Hence by setti ng nextlive 10 be empty before calling AddNeighbors
postcondition: Array map contains the initial configuration of liv ing and dead cells. and copying nextlive to live afterward, we accomplish another of the postconditions of
Array numbernbrs contains counts of living neighbors correspond-
Initialize.
ing to the configuration in array map. List live contains only dead
The final postcondition is that list die contain all living cells that should die in the
cells and includes all candidates that may be vivified in the next
next generation. Some, but perhaps not all, of these may be found by AddNeighbors (in
generation. List die contains only living cells and contains all can-
the main loop, the remainder would be found by SubtractNeighbors, which we have no
didates that may die in the next generation. way tu use in Initialize). We can accomplish the postcondition more easily, however, by
simply putting all the living cells into list die. Recall that function Kill allows spurious
entries on its input list.
The purpose of loop invariants and assertions is to capture the essence of the dynamic
In this way the postconditions lead to the following function:
process. It is not always easy to find loop invariants and assertions that will lead 10
 CHAPTER 2 SECT I O N 2 . 5 Program Analysis and Comparison 49
48 Introduction to Software Engineeri ng

I * Initialize: set up the lists and grid. • I

1. Statement Counts
void Initialize (LisUype • live, LisUype *die, LisUype • nextlive, Let us now see about how much more quickly the program Life2 should run than the
LisUype •nextdie, Grid_type map, GridcounUype numbernbrs) previous version. As we did for the first version, let us ignore the time needed for input
ini1ializa1ion { and output in the main program, and look only at the statements inside the principal
int row, col; I* used to sot all ontrios in numbernbrs to O • I loop counting generations. Since all the work of Life2 is done wi th i n f um:tions, we must
analyze each in turn. Each of the functions does most of its work within a loop that
ReadMap(live, map); I• initializes map *I
runs through the entries of one of the lists live, die, nextlive, or nextdie. Thus the key
for (row = O; row< MAXROW; row++)
improvement of Life2 over the original program is that the amount of computation is no
I* Set all the entries in numbernbrs to O. * '
longer proportional to the size of the grid but to the number of changes being made. For
for (col= O; col < MAXCOL; col++ )
a typical configuration, there might be about I 00 occupied cells, with likely no more
numbernbrs [row] [col ] = O;
than SO dying or being born in a single generation. With these assumptions, we see that
nextlive- >count = O; I • Initialize the lists used by AddNeighbors. • t
each statement within the inner loops wi ll be executed about SO times. In Vivify there are
nextdie->count = O;
S statements within the loop, in Copy only I. Within the loop of AddNeighbors there
AddNeighbors ( live, nextlive, nextdie, numbernbrs, map) ;
are 2 assignment statemen ts and 4 if statements, then 3 statements each done 9 times,
I• Some of the cells just read in should die in the first generation. Kill will catch
and the switch statement done 8 times, for a total count of 41. The counts for Kill and
them. * ' count for Life2 SubtractNeighbors are similar: thus we obtain for each generation about
Copy ( die, live);
Copy(live, nextlive); I* Put output from AddNeighbors where needed. • I
nextdie->count = O;
SO x ( S + I + 41 + S + I + 4 I ) = 4700
}
statements. The number of statements executed outside the loops is insignificant (it is
less than I 0), so 4700 is a reasonable estimate of the statement count for each generation.
counl for life1 Our first version of the Life program had a count of 76,000 statements per generation.
Exercises El. Write down preconditions and postconditions for each of the following functions. Thus our rev ised program should run as much as 16 times faster. This constitutes a
2.4 a. float SquareRoot ( float x) returns the square root of x. substantial improvement, particularly in view of the fact that when program Life2 slows
down, it is because many changes are being made, not because it is repeating the same
b. float Meanx( LisUype A ) calculates the mean (average) x value in a list of predictable calculations.
coordinates (x, y) as declared in Section 2.2.
c. void Copy ( LisUype • to, LisUype • from). 2. Comparisons
d. function Kill. From other points of view, however, our second program is not as good as the first.
programming effor1 The fi rst of these is the point of view of programming effort. The first program was
e. function SubtractNeighbors.
short and easy to write, simple to understand, and easy to debug. The second program
f. function WriteMap. is longer, entailed subtle problems, and required sophisticated reasoning to establish its
E2. a. Write down the precondition and postcondition for the function ReadMap. correctness. Whether this additional work is worthwhi le depends on the application and
the number of times the program will be used. If a simple method works well enough,
b. Code the function ReadMap. then we should not go out of our way to find a more sophisticated approach. Only when
c. Write a dri ver for ReadMap and test it. simple methods fail do we need to try further devices.

Programming Precept
Keep your algorithms as simple as you can.
2.5 PROGRAM ANALYSIS AND COMPARISON When in doubt, choose the simple way.

In designing algorithms we need methods to separate bad algorithms from good ones,
space requiremems The second point of view is that of storage requirements. Our first program used very
to help us decide, when we have several possible ways in which to proceed, which
little memory (apart from that for the instructions) except for the two arrays map and
way will prove the most effecti ve for our problem. For thi s reason the analysis of algo-
newmap. These arrays have entries that, in assuming only the two values alive and
rithms and the comparison of alternative methods constitute an important part of software
dead, can be packed so that each entry takes only a single bit. In a typical computer
engineering.
50 Introduction to Software Engineering CHAPTER 2 SECTION 2 . 6 Conclusions and Preview 51

with word size of 32 or 16 bits, the two arrays need then occupy no more than 250 or E3. Note that there is some inefficiency in the program Life2 in having functions
500 words, respectively. On the other hand, program Life2 requires, along with the space AddNeighbors and SubtractNeigh bors called once from the main program, since
for its instructions, space for one such array, plus 4000 words for the array numbernbrs these functions must loop through the lists live and die just as Vivify and Kill already
and 401 words for each of its four lists, giving a total of more than 5700 words. do. It would be faster if these functions were written to update the neighbors of
onl y one cell and were called from Vivify and Kill whenever a cell was vivi fied or
3. Time and Space Trade-offs killed.
We have just seen the first of many examples illustrating the substantial trade-offs that a. Will the program work correctly if these changes are made?
can occur between time and space in computer algorithms. Which to choose depends b. If not, what further changes will make it work?
on available equipment. If the storage space is available and otherwise unused, it is c. With your revised program, fi nd the proper loop invariants and verify that your
obviously preferable to use the algori thm requiring more space and Jess time. If not, algorithm is correct.
then time may have to be sacrificed. Finally, for an important problem, by far the best
approach may be to sit back and rethink the whole problem: you will have learned much Programn1ing Pl. If you use a video terminal wi th direct cursor address ing, write a version of the
from your first efforts and may very well be able to find another approach that will save Projects function WriteMap that takes advantage of the lists live and die 10 update the map
both time and space. 2.5 rather than completely rewriting it at each generation.
P2. Run the complete program Life2 and compare timings with those of Life 1.

2.6 CONCLUSIONS AND PREVIEW

Th is chapter has surveyed a great deal of ground, but mainly from a bird's-eye view.
Some themes we shall treat in much greater depth in later chapters; others must be
postponed to more advanced courses; still others are best learned by practice.

2.6.1 The Game of Life

1. Future Directions
We are not yet fi nished with the game of Life, although we next shall turn to other topics.
When we return to the Life game (at the end of Chapter 6), we shall find an algorithm
Exercises El. We could save the time needed to copy lists if we did two generations instead of that does not require us 10 keep a large rectangular grid in memory.
2.5 one inside the main loop. We would pass the names of which of the lists to use
2. Problem specification
to all the functions, and in writing the instructions for the second generation, we
would simply swap the pairs of lists. How many statements, approximately, would For the moment, however, let us make only one observation, one that you may well have
be saved per generation? Do you think this change is worth implementing? If so, already made and, if so, one that has like ly been botheri ng you. What we have done
do it. througho ut this chapter and the previous one has been, in fact, incorrect, in that we have
E2. We could save the space needed for the array map by making a slight modification not been solving the Life game as it was origi nally described in Section 1.2. The rules
in how we keep information in the array numbernbrs. We could use positive make no mention of the boundaries of the grid containing the cells. In our programs,
entries in numbernbrs to denote living cells and negative entries to denote dead when a moving colony gets sufficiently close to a boundary, then room for neighbors
cells. However, we could then not tell whether an entry of O meant a dead cell or disappears, and the colony will be distorted by the very presence of the boundary. That
a living cell with no living neighbors. We could easily overcome that problem by is not supposed 10 be.
changing the definition of neighbor so that a cell is considered its own neighbor (so It is of course true that in any computer simulat ion there are absolute bounds on the
the neighbor count for a dead cell would range from O to 8, stored in nurnbernbrs values that may appear, but certainl y our use of a 50 by 80 grid is highly restrictive and
as O t.o - 8, and that for a Jiving cell from 1 to 9). arbitrary. Wri ting a more realistic program must be one of our goals when we return to
this problem. But on a first try, restrictions are often reasonable. Nevertheless,
a. With this change of definition, write down the revised rules (from Section 1.2.1)
for the game of Life.
b. Do you think that implementing the changes to eliminate array map is worth Programming Precept
the effort? Why or why not'! Be sure you understand your problem completely.
c. If you answered the last question positively, describe exactly what changes are If you must change its terms, explain exactly what you have done.
needed in the program.
i2 Introduction to Software Engineering CHAP T ER 2 SEC TI O N 2.6 Conclusions and Preview 53

When we sLart.ed in Section 1.4, we did nothing of the sort, but plunged right in with an 2.6.2 Program Design
approach leaving much to be desired. Almost every programmer learns this experience
the hard way and can sympathize with the following: 1. Criteria for Programs
A major goal of this book is to evaluate algorithms and data structures that purport to
' solve a problem. Amongst the many criteria by which we can judge a program, the
~·· t rogramming Precep.t
followi ng are some of the most important:
& "' Act in haste and repent at leisure.
:?'.-. ,;,:
:~...
Program in haste and debug forever.
;.,~. ~, ·h ' ·-.:
I. Does it solve the problem that is requested, according to the given specifications?
2. Does it work correctly under all conditions?
The same thought can be expressed somewhat more posirively: 3. Does it include clear and sufficient information for its user, in the form of instructions
and documentation?
, ·::;:. ~~::-;- --:-.:x: ~ cc')~' ~r· -~~ ·:-:-· ~f ~ ~ ? ~<... ~f
4. Is it logically and clearly written, with short modules and subprograms as appropriate
,,. v , . '" Programmln,g Precept ,. ~:
10 do logical tasks?
;, Starting' afresfl fs Jsually easier tnari patching an old program.
:r ~ ·.x ~-:.; <;;. :_f ::: *" _:, ·::t ..s:.. - ,.-: .. ,:x · 5. Does it make efficient use of time and of space?

Some of these criteria will be closely studied for the programs we write. Others will
A good rule of thumb is rhar, if more than Len percent of a program must be modified,
not be mentioned explicitly, but not because of any lack of importance. These criteria,
then it is time to rewrite the program completely. With repealed palches to a large
rather, can be met automatically if sufficient thought and effort are invested in every
program, the number of bugs Lends to remain constant. That is, the patches become so
stage of program design. We hope that the examples we study will reveal such care.
complicaled that each new patch tends to introduce as many new errors as it corrects.
2. Software Engineering
3. Prototyping
Software engineering is the study and practice of methods helpful for the construction
An excellent way to avoid having to rewrite a large project from scratch is to plan from and maintenance of large software systems. Although small by realistic standards, the
the beginning to write two versions. Before a program is running it is often impossible to program we have studied in this chapter illustrates many aspects of software engineering.
know what parts of the design will cause difficu lty or what features need to be changed to Software engineering begins with the realization that it is a very long process to
meet the needs of the users. Engineers have known for many years that it is not possible obtain good software. It begins before any programs are coded and continues maintenance
to build a large projecr. directly from the drawing board. For large projects engineers for years after the programs are put into use. This continuing process is known as the
always build prototypes, that is, scaled-down models that can be studied, tested, and life cycle of software. This life cycle can be divided into phases as follows:
sometimes even used for limiLed purposes. Models of bridges are built and tested in
wind tunnels; pilot plants are constructed before attempting to use new technology on phases of life cycle I. Analyze the problem precisely and completely. Be sure to specify all necessary
the assembly line. user interface with care.
software prototypes Prolotyping is especially helpful for computer software, since it eases communica- 2. Build a prototype and experiment with it until all specifications can be finalized.
tion between users and designers early in the project, thereby reducing misunderstandings 3. Design the algorithm, using the tools of data structures and of other algorithms
and helping to settle the design to everyone's satisfaction. In building a software proto- whose function is already known.
type the designer can use programs that are already written for input-output, for sorting,
or for other common requirements. The building blocks can be assembled with as little 4. Verify that the algorithm is correct, or make it so simple that its correctness is
new programming as possible to make a working model that can do some of the intended self-evident.
tasks. Even though the prototype may not function efficiently or do everything that the 5. Analyze the algorithm to determine its requirements and make sure that it meets the
final system will, it provides an excellent laboratory for the user and designer to exper- specifications.
iment with alternative ideas for the final design. The following precept is due to FRED 6. Code the algorithm into the appropriate programming language.
BROOKS. 7. Test and evaluate the program on carefully chosen test data.
~· ,, 8. Refine and repeat the foregoing steps as needed for additional subprograms until
t + Programming Pi ece.pt ,.;.. ,,. the software is complete and fully functional.
; Al~ays plan t9 ~uild a P(Ot~type an~ t~row it away. 9. Optimize the code to improve performance, but only if necessary .
·~
.· ..·''.: You'll
'
dO
'::;·
so whether
.
you;:,.-.; plan ...to or.not.
- ' JO. Maintain the program so th at it will meet the changing needs of its users.
 S E C TION 2.6 Conclusions and Preview 55
54 Introduction to Software Engineering CHAPTER 2
2.6.3 The C Language
Most of these topics have been discussed and illustrated in various sections of this and
the preceding chapter, but a few further remarks on the first phase, problem analysis and In this chapter and the previous one, we have had a whirlwind tour of many features
specification, are in order. of C. No attempt has been made to present an orderly or complete description of C
features. A concise summary of C appears in Appendix C, to which you should refer
3. Problem Analysis with questions of C syntax. For further examples and discussion, consult a C textbook.
Analysis of the problem is often the most difficult phase of the software life cycle. This
is not because practical problems are conceptually more difficult than are computing Programming Pl. A magic square is a square array of integers such that the sum of every row, the
science exercises-the reverse is often the case-but because users and programmers
Proj ects sum of every column, and sum of each of the two diagonals are all equal. Two
tend to speak different languages. Here are some questions on which the analyst and magic squares are shown in Figure 2.3. 1
user must reach an understanding:
2.6

specifications 1. What form will the input and output data take? How much data will there be?
2. Are there any special requirements for the processing'? What special occurrences
will require separate treatment? Il6 J g ~J 17 24 t 8 15

23 5 7 14 16
3. Will these requirements change? How? How fast will the demands on the system
grow?
~ ~(Q) ~ ij ~ 4 6 13 20 22
4. What parts of the system arc the most important? Which must run most efficiently? 9> 6 71 ~g 10 12 19 21 3
5. How should erroneous data be treated? What other error processing is needed?
6. What kinds of people will use the software? What kind of training will they have? ~ ij~ Il~ ~ 11 18 25 2 9
What kind of user interface will be best? sum = 34 sum = 65
7. How port.able must the soft.ware be, to move to new kinds of equipment? With what Figure 2.3. Two magic squares
other software and hardware systems must the project be compatible?
a. Write a program that reads a square array of integers and determines whether
8. What extensions or other maintenance arc anticipated? What is the history of
or not it is a magic square.
previous changes to software and hardware?
b. Write a program that generates a magic square by the foll owing method. This
method works only when the size of the square is an odd number. Start
4. Requirements Specification by placing I in the middle of the top row. Write down successive integers
The problem analysis and experimentation for a large project finally lead to a fonnal 2, 3, ... a long a diagonal going upward and to the right. When you reach the
statement of the requirements for the project.. This statement becomes the primary way in top row (as you do immediately since I is in the top row), continue to the
which the user and the software engineer attempt to understand each other and establishes bottom row as though the bottom row were immediately above the top row.
the standard by which the final project will be j udged. Among the contents of this When you reach the rightmost column, continue to the leftmost column as
specification will be the following: though it were immediately to the right of the rightmost one. When you reach
a position that is a lready occupied, instead drop straight down one position
I. Functional requirements for the system: what it will do and what commands will from the previous number to insert the new one. The 5 x 5 magic sq uare
be available to the user. constructed by this method is shown in Figure 2.3.
2. Assumptions and limitations on the system: what hardware will be used for the P2. One-dimensional Life takes place on a straight line instead of a rectangular grid.
system, what form the input must take, the maximum size of input, the largest Each cell has four neighboring positions: those at distance one or two ftom it on
number of users, and so on. each side. The rules are similar to those of two-dimensional Life except ( I) a
3. Maintenance requirements: anticipated extensions or growth of the system, changes dead cell with either two or three living neighbors will become alive in the next
in hardware, changes in user interface. generation, and (2) a liv ing cell dies if it has zero, one, or three living neighbors.
4. Documentation requirements: what kind of explanatory material is required for (Hence a dead cell with zero, one, or fou r living neighbors stays dead; a living cell
what kinds of users. with two or four living neighbors stays alive.) The progress of sample communities
is shown in Figure 2.4. Design, write, and test a program for one-dimensional Life.
The requirements s pecifications state what the software will do, not how it will be done.
These specifications should be understandable both to the user and to the programmer. If I
The magic square on the left appears as shown here in the etching Mela11colia by ALBRECHT D ORER.
carefully prepared, t.h ey will fonn the basis for the subsequent phases of design, coding, Nole 1he inclusion of 1he date of the e1ching, 1514.
testing, and maintenance.
56 Introduction to Software Engineering CHAPTER 2 C HAPTER 2 Review Questions 57

e. Usi ng the rules on leap years, s how that the sequence of calendars repeats
exactly every 400 years.
f. What is the probabi lity (over a 400 year period) that the 13th of a month is
I• I I· I I I• I a Friday? Why is the 13th of the month more likely to be a Friday than any
other day of the week? Wri te a program to calculate how many Friday the
13ths occu r in th is century.
II
Dies out Oscillates

POINTERS AND PITFALLS

I. To improve your program, rev iew the logic. Don't opt im ize code based on a poor
algori th m.

I• I I• I• I• I I 2. Never optimize a program until it is correct and work ing.

3. Don't optimize code unless it is absolutely necessary.
I• I I• I• I•I l•l•I l· I l•l• I 4. Keep your functions short; rarely shou ld any function be more than a page long.
5. Be su re your algorithm is correct before starting to code.
6. Verify the intricate parts of your algorithm.
7. Keep your log ic simp le.
I• I I• I I• I 8. Review the Programming Precepts!

I l• l•I l•l•I I I I
REVIEW QUESTIONS
I· I I· I I· I I· I 2./ 1. What is program mai nte nance?
2.2 2. W hat are hierarchical structures, and how s hould they be processed?

Glides to the right Repeats in six generations 2 .3 3. When shou ld allocation of tasks among functions be made?
Figure 2.4. One-dimensional Life con6guralions 4. How long shou ld coding be delayed?
2.4 5. What is mathematical induction?
P3. a. Write a program that will print the calendar of the c urrent year.
6. What is a loop invariant?
b. Modify the program so that it will read a year number and print the calendar
for that year. A year is a leap year (that is, February has 29 instead of 28 7. What are preconditions and postcond itions of a subprogram?
days) if it is a m ultiple of 4, except that century years (multiple of I00) are
2.5 8. What is a time-space tradeoff?
leap years on ly when the ye ar is divisible by 400. Hence the year 1900 is not
a leap year, but the year 2000 is a leap year. 2.6 9. What is a prototype?
c. Mod ify the program so that it will accept any date (day, month, year) and print 10. Name at least six phases of the software life cycle and state what each is.
the day of the week for that date.
11. Define software e ngi neering.
d. Modify tlle program so that it will read two dates and prim the number of days
from one to the other. 12. What are requirements specifications for a program?
58 Introduction to Software Engineering CHAPTER 2
C HA P T E R 3
REFERENCES FOR FURTHER STUDY
software engineering A thorough discussion of many aspects of structured programming is:
EDWARD YouROON, Techniques of Program Structure and Design, Prentice Hall, Engle-
wood Cliffs, N. J., 1975, 364 pages.
A perceptive discussion (in a book that is also enjoyable reading) of the many problems
that arise in the construction of large software systems is:
FR!ilJcRICKP. BROOKS, JR. , The Mythical Man- Month: EssC1ys 011 Software Engineering,
Addison-Wesley, Reading, Mass., 1975, 195 pages.
A good textbook on software engineering is:
Lists
IAN SOMMERVILLE, Software Engineering, Addison-Wesley, Wokingham, England, 1985,
334 pages. This chapter introduces the study of data structures by studying various
Program testing has been developed to the point where its methods can fill a large book: kinds of lists, including stacks and queues, together with their implemen-
WILLIAM E. PERRY, A Structured Approach to Systems Testing, Prentice Hall, Englewood tations in computer storage and C functions. The separation between the
Cliffs, N. J., 1983, 451 pages. use of da1a structures and their implementation is emphasized. Several
algorithm Two books concerned with proving programs and using assertions and invariants to examples are developed, including a simulation problem.
verification develop algorithms are
DAv10 GR1~s, The Science of Programming, Springer-Verlag, New York, 1981, 366 pages.
SllAD AtAc.1c and M1rnAi;1. A. ARRJR, The Design of Well-Structured and Correct Pro-
grams, Springer-Verlag, New York, 1978, 292 pages.
Keeping programs so simple in design that they can be proved to be correct is not easy, 3.1 Static and Dynamic Structures 60 3.4.3 The Main Program 80
but is very important. C. A. R. HOARE (who invented the quicksort algorithm that we 3.4.4 Steps of the Simulatibn 81
shall study in Chapter 7) writes: "There are two ways of constructing a software design: 3.2 Stacks 60 3.4.5 Random Numbers 84
3.2.1 Definition and Operations 60
One way is to make it so simple that there are obviously no deficiencies, and the other 3.4.6 Sample Results 85
3.2.2 Examples 61
way is to make it so complicated that there are no obvious deficiencies. The first method 3.2.3 Array Implementation of
is far more difficult." This quotation is from the 1980 Turing Award Lecture, "The Stacks 64 3.5 Other Lists and their
emperor's old clothes," Communications of the ACM 24 (1981), 75- 83. Implementation 89
Two books concerned with methods of problem solving are 3.3 Queues 68
3.3.1 Definitions 68
problem solving GEORGE P<\1-vA, How to Solve It. second edition, Doubleday, Garden City, N.Y., 1957, Pointers and Pitfalls 96
253 pages. 3.3.2 Implementations of Queues 69
3.3.3 Circular Queues in C 72
WAYNF. A. W1cKF.J.GRF.x, How ro Solve Problems, W. H. Freeman, San Francisco, 1974,
262 pages. Review Questions 96
3.4 Application of Queues: Simulation 77
The programming project on one-dimensional life is taken from 3.4.1 Introduction 77
3.4.2 Simulation of an Airport 78 References for Further Study 97
JoNAl'IJANK. M1LL!iR, "One-dimensional Life," Byte 3 (December, 1978), 68- 74.

59
 SEC TION 3.2 Stacks 61
60 Lists CHAPTER 3

3.1 STATIC AND DYNAMIC STRUCTURES

Soon after the introduction of loops and arrays, every elementary programming class
attempts some programming exercise like the following:

f'Read''a!Pin'leg"er4'n f wlfi8i l'Vi/l''b'i?'dtiifbsfr25', the11 read d*Hst of rir ,ifimbci·$, '1111il

'iprinl'thi'/['§1 fh f~v1,·sl ohtef. * it i ,, '"" ,, '" 0 w %' . %' @ ' ,· ,, • ·. .
,;-. . ;~i~ W @ it ?::·· }f ~~· .:i J: ;-:®i if /§: ·~( '.;.: i ~:t.-, it -:1' :f: -~- ~ 1'· ~r- ~~ +- «¢. :i,; ,, f#~ '/,

This little exercise will probably cause difficu lty for some students. Most will realize
t.hat they need to use an array, but some will attempt to set up the array t.o have n entries
and will be confused by the error message resulting from attempti ng to use a variable
rather tJ1an a constant to declare the size of the array. O:her students will say, "I could
solve the problem if I knew that there were 25 numbers, but I don't see how to handle
fewer." Or "Tell me before I write the program how large n is, and then I can do it."
The difficulties of these students come not from st.upidity, but from thinking logi-
cally. In a beginning course, there is sometimes not enough distinction drawn between
list.\· and arrays two quite different concepts. First is the concept of a list of n numbers, a list whose
size is variable, that is, a list for which numbers can be inserted or deleted, so that, if
n = 3, then the list contains only 3 numbers, and if n 19, then it contains 19 num- =
bers. Second is the programming feature called an array or a vector, which contains a
constant number of positions, that is, whose size is fixed when the program is compiled.
implementation The two concepts are, of course, related in that a list of variable si:te can be implemented
in a computer as occupying part of an array of fixed size, with some of the entries in the Figure 3.1. Stacks
array remain ing unused.
In this chapter we shall see that sometimes there are several different ways to in a busy cafeteria. Throughout the lunch hour, customers take trays off the top of
implement a list within computer memory, and therefore the careful programmer needs the stack, and employees place returned trays back on top of the stack. The tray most
choice of to make a conscious decision about which of these to choose. The need for careful recently put on the stack is the first one taken off. The bottom tray is the first one put
data structures decision making about how to store dat.a, in fact, extends back even further in the on, and the last one to be used.
process of program design. We shall soon see that there is more than one kind of list Sometimes thi s picture is described with plates or trays on a spring-loaded device so
(stacks and queues are the first. two kinds we study), and therefore the programmer must that the top of the stack stays near the same height. This imagery is poor and should be
first decide what kind of list (or what other conceptual s'.ructure) is needed for the data avoided. If we were to implement a computer stack in this way, it would mean moving
choice (if and then must decide how the conceptual structure will be implemented in computer every item in the stack whenever one item was inserted or deleted. This would be costly.
implementations memory. By keeping these decisions separate, we shall be able both to simplify the It is far better to think of the stack as resting on a firm counter or floor, so that only the
programming process and avoid some of the pitfalls that attend premature decisions. top item is moved when it is added or deleted. The spring-loaded imagery, however, has
Already in Sect.ion 2.2 we have discussed the implementation of lists inside C contributed a pai r of colorful words that are fim1ly embedded in computer jargon, and
arrays. We set up a structure type, so that we could keep track both of the array and of which we shall use. When we add an item to a stack, we say that we push it onto the
the variable that counts entries in the list, tied together as one logical structure. In th is push and pop stack, and when we remove an item, we say that we p op it from the stack. From the
chapter we shall continue with similar methods. same analogy, the term push-dow11 list is used synonymously with stack, but we shall
not employ this term. See Figure 3.2.

3.2 STACKS 3.2.2 Examples

1. Stack Frames for Subprograms

3.2.1 Definition and Operations
As one important application of stacks, consider what happens within the computer
stacks The easiest kind of list to use is called a stack and is defined formally as a list in which system when subprograms are called. The system (or the program) must remember
all insertions and deletions are made at one end, called the top of the stack. A helpful the place where the call was made, so that it can return there after the subprogram is
analogy (see Figure 3. 1) is to think of a stack of trays or of plates sitting on the counter
62 lists CHAPTER 3 S ECTION 3 .2 Stacks 63

Push box Q onto empty stack: I

/ Q

?1
Push box A onto stack:
~ c
data
8
data

..----....._/
Pop a box from stack : I
/ Q

?1 I A c:::1 ~ A
data 8
data
8
data
8
data

Pop a box from stack:

/
!empty)
- /
I
Q
,;::, --- A
data
8
data

A
data
8
data

A
8
data

A
8
data

A
data
8
data

A
data
8
data

A
8
data

A
8
data

A
Re' data data data data data
Push box R onto stack: I

Push box D onto stack:

s3 Time ._....
Figure 3.3. Stack frames for subprogram calls

consider the machine's task of assigning temporary storage areas for use by subprograms,

~
then these areas would be allocated in a list with this same property, that is, in a stack
Push box M onto stack; (see Figure 3.3). Hence yet one more name sometimes used for stacks is LIFO lists,
based on the acronym for this property.
----... ----.._ 2. Reversing a Line
Pop a b-Ol< Irom stack :
s3 I
/ M CJ As a simple example of using stacks, let us suppose that we wish to make a function
that will read a line of input and will then write it out backward. We can accomplish
this task by pushing each character onto a stack as il is read. When the line is finished,

~
we then pop characters off the stack, and they will come off in the reverse order. Hence
Push box Q onto stack: our function takes the following form :
f* ReverseRead: read one line of input and write it backward.
void Reverse Read ( void)
*'
{
ltem _type item;
Push box S onto stack:
ltemJype *item_ptr = &item;
StackJype stack;
Figure 3.2. Pushing a nd popping a stack Stack_type * Stack_ptr = &stack;

complete. It must also remember all the local variables, CPU registers, and the like, so
that information will not be lost while the subprogram is working. We can think of all
Initialize (stack_ptr); f* Initialize the stack to be empty.
while ( 1 Full(stack_ptr) && (item= getchar()) ! = ' \n') *'
subprogram data
this information as one large structure, a temporary storage area for each subprogram.
Suppose now that we have three subprograms called A, B, and C , and suppose
Push ( item, stack ptr);
while ( 1 Empty(stack_ptr)) {
f* Push each item onto the stack.
*'
srorage that A invokes B and B invokes C. Then B will not have finished its work until C
has finished and returned. Similarly A is the first to start work, but it is the last to be
Pop(item_ptr, stack_ptr);
putchar (item) ;
I* Pop an item from the stack.
*'
}
finished, not until sometime after B has finished and returned. Thus the sequence by putchar(' \n');
which subprogram activity proceeds is summed up as the property last in, first out. If we }
64 Lists CHAPTER 3 SECTION 3. 2 Stacks 65

In this function we have used not only Push and Pop but also a function Initialize that I• Push: push an item onto the stack. • I
initializes the stack to be empty and Boolean-valued functions Empty that checks whether void Push ( Item.type item, Stack.type • stack..ptr)
the stack is empty or not and Full that checks if it is completely full. T he declarations {
for a stack appear in Section 3.2.3. if (stack..ptr->top >= MAXSTACK)
Error ( "Stack is full");
3. Information Hiding else
Notice that we have been able to write our function before we consider how the stack stack..ptr->entry [stack..ptr->top++ J = item;
}
will actually be implemented in storage and before we write the details of the varibus
use offunctions functions. In this way we have an example of information hiding : lf someone else I • Pop: pop an item from the stack. •t
had already written the functions for handling stacks, then we could use them without void Pop(ltem.type • item..ptr, Stack.type • stack..ptr)
{
needing to know the details of how stacks are kept in memory or of how the stack
operations are actually done. if (stack..ptr->top <= O)
Error( "Stack is empty");
else
3.2.3 Array Implementation of Stacks • item..ptr = stack..ptr->entry [ - -stack..ptr->top];
}

1. Declarations Error is a function lhat receives a pointer to a character string, prints the string, and then
invokes lhe standard function exit to terminate the execution of the program.
To implement a stack in a computer we shall set up an array that will hold the items
in the stack and a counter to indicate how many items there are. In C we can make t• Error: print error message and terminate the program. • I
void Error ( char • s)
declarations such as the following, where MAXSTACK is a symbolic constant giving the
{
maximum size allowed for stacks and Item.type is the type describing the data that
fprintf ( stderr, "%s \n", s);
will be put into the stack. lype Item.type depends on the application and can range
exit(1);
from a single character or number to a large structure with many elements. Our stack.h
}
contains:
ln normal circumstances Error is not executed because, as in ReverseRead, we check
#define MAXSTACK 10 whether the siack is full before we push an item and we check if the stack is empty
typedef char Item.type; before we pop an item.
3. Other Operations
typedef struct stack.tag {
int top; I• Empty: returns non-zero if the stack is empty. • I
Item.type entry [ MAXSTACK] ; Boolean.type Empty ( Stack.type •stack..ptr)
} Stack.type; {
Boolean.type Empty ( Stack.type * ) ; return stack..ptr->top <= O;
Boolean.type Full (Stack.type *); }
void Initialize (Stack.type * ); I • Full: returns non-zero if the stack is full. • I
void Push ( Item.type, Stack.type *); Boolean.type Full (Stack.type • stack..ptr)
void Pop ( Item.type *, Stack.type *); {
return stack..ptr->top >= MAXSTACK;
2. Pushing and Popping }

Pushing and popping the stack are then implemented as follows. We must be careful The next function initializes a siack t0 be empty before it is first used in a program:
of the extreme cases: We might attempt to pop an item from an empty stack or to t• Initialize: initialize the stack to be empty. • t
push an item onto a full stack. We shall regard such attempts as errors fatal to the void Initialize ( Stack.type • stack..ptr)
execution of the program, and therefore we must also write Boolean-valued functions so {
that by checking emptiness or fullness the program can guard against these errors ever stack..ptr->top = O;
occurring. }
 SE C T I ON 3.2 Stacks 67
66 Lists CHAPTER 3
b. Return the third element from the top of the stack, provided that the stack con-
4. Advantages of the Operational Approach
tains at least three integers. I f not, return INT_MAX. Leave the stack unchanged.
If you think that we are belaboring the obvious by introducing all these functions, then c. Return the bottom element of stack (or INT_MAX i f stack is empty), and leave
in one sense you are right, since their substance is so simple that they could easily the stack unchanged. [Hint: Use a second stack.J
be written out wherever they are needed in a program, rather than keeping them as d. Delete all occurrences of x from the stack, leaving the other elements of the
separate functions. For large programs there is one important advantage, however, to stack in the same order.
flexibility of using a structure to implement stacks and separate functions to process them . It may E3. Sometimes a program requires two stacks containing the same type of items. If the
implernentarion well happen that, after we start work on a large project, we realize that another way of two stacks are stored in separate arrays, then one stack might overflow while there
implementing our stacks in storage would prove better than the method we had used. If was considerable unused space in the other. A neat way to avoid this problem is to
the instructions have been written out every time a stack is pushed or popped, then every put all the space in one array and let one stack grow from one end of the array and
occurrence will need to be changed. 1f we have used structures and functions, then only the other stack start at the other end and grow in the opposite direction, toward the
the definition of the structure type and the declarations of the functions must be altered. first stack. In this way, i f one stack turns out to be large and the other small, then
clarity of program A second advantage, of course, is that the very appearance of the words Push and Pop they w ill still both fit, and there will be no overflow until all the space is actually
will immediately alert a person reading the program to what is being done, whereas the used. Declare a new structure type DoubleStack that includes the array and the
wp-down design instructions themselves might be more obscure. A third advantage we shall find is that two indices topA and topB, and wri te fu nctions PushA, PushB, PopA, and PopB
separating the use of data structures from their implementation will help us improve the to handle the two stacks within one DoubleStack.
top-down design of both our data structures and our programs. E4. Write a program that uses a stack to read an integer and print all its prime divisors
in descending order. For example, with the integer 2 100 the output should be
Exercises El. Draw a sequence of stack frames showing the progress of each of the following
3.2 segments of code. (stack_ptr is a pointer to a stack of characters and x, y, z are 7 5 5 3 2 2.
character variables.)
[Hin t: The smallest div isor greater than l of any integer is guaranteed to be a
prime.)
a. Initialize (stack_ptr); c. Initialize (stack_ptr);
Push ('a', stack_ptr) ; Push ('a', stack_ptr) ; ES. A stack may be regarded as a railway switching network like the one in Figure 3.4.
Push C' b', stack_ptr); Push ( 'b' , stack. ptr ) ;
Push ( 'c', stack_ptr) ; Push ( 'c', stack_ptr ) ;
Pop C&x, stack_ptr);
Pop ( &y, stack_ptr) ;
Pop C&z, stack_ptr) ;
wh ile ( ! Empty(stack_ptr))
Pop ( &x, stack_ptr) ; - -
d. Initialize ( stack_ptr) ;
b. Initialize (stack_ptr); Push ('a' , stack_ptr) ;
Push ('a' , stack_ptr); Push ( 'b', stack_ptr);
Push C' b', stack._ptr) ; Push ( ' c' , stack_ptr) ;
Initialize (stack_ptr); Pop ( &x, stack_ptr) ;
Push ( 'c', stack_ptr); Pop ( &y, stack_ptr) ;
Pop ( &x, stack _ptr) ; Push (x, stack_ptr);
Push(' a', stack_ptr); Push(y, stack_ptr);
Pop ( &y, stack_ptr) ; Pop C&z, stack_ptr) ; Figure 3.4. Switching network for stack permutations
Push ( 'b', stack_ptr);
Pop ( &z, stack_ptr);
Cars numbered I, 2, ... , n are on the I ine at the left , and it is desired to
rearra nge (pennute) the cars as they leave on the rig ht ha nd track. A car that is on
E2. Let stack_ptr be a pointer to a stack stack of integers and item be an integer variable.
Use the functions Push, Pop, Initialize, Empty, and Full to write functions doing the spur (stack) can be left there or sent on i ts way down the right track, but it can
each of the following tasks. [You may declare additional variables in your functions never be sent back to the incoming track. For example, i f n = 3, and we have the
if needed.] cars I, 2, 3 on the left track , then 3 fi rst goes to the spur. We could then send 2 to
the spur, then on its way to the right, then send 3 on the way, then I , obtaining the
a. Return the top element of the stack and leave the top element unchanged. If new order l , 3, 2.
the stack is empty, return INLMAX.
68 Lists CHAPTER 3 S EC T ION 3 .3 Queues 69

a . For n = 3, find all possible permutations that can be obtained. 3.3.2 Implementations of Queues
b. Same, for n = 4.
c. [Challenging] For general n , find how many permutations can be obtained by 1. The Physical Model
using this stack.
As we d id for stacks, we can create a queue i11 computer storage eas il y by setting up an
ord inary array to hold the items. Now, however, we must keep track of both tiie front
and the rear of the queue. One method wou ld be to keep the front of the queue al ways
3.3 QUEUES in the first location of the array . Then an item could be added to the queue simp ly by
increas ing the counter showing the rear, in exact ly the same way as we added an item
to a stack. To delete an item from the queue, however, wou ld be very expensive indeed,
3.3.1 Definitions s ince after the fi rst item was removed, all the remaining items wou ld need to be moved
one position up the queue to fill in the vacancy. With a long queue, this process would
In ordinary English a queue is defined as a waiting line, like a line of people waiting to be prohibitively slow. Although this method of storage closely models a queue of people
purchase tickets, where the first person in line is the first person served. For computer waiting to be served, it is a poor choice for use in computers.
applications we s imilarly define a queue to be a list in which all additions to the li st are
made at one end, and all deletions from the list are made at the other end. Queues are 2. linear Implementation
a lso called first-in, first-out lists, or FIFO for short. See Figure 3.5.
For efficient processing of queues, we shall therefore need two indices so that we can
keep track of both the front and the rear of the queue without moving a ny items. To
add an item to the queue, we simply increase the rear by one and put the item in that
position. To remove an item, we take it from the position at the front and then increase
the front by one. This method, however, st ill has a major defect. Both the front and
defect rear indices are increased but never decreased. Even if there are never more than two
items in the queue, an unbounded amount of storage will be needed for the queue if the
sequence of operations is

Add, Add, Delete, Add, Delete, Add, Delete, ....

The problem, of course, is that, as the queue moves down the array, the storage space at
the beginning of the array is discarded and never used again. Perhaps the queue can be
li kened to a snake crawling th rough storage. Sometimes the snake is longer, sometimes
shorter, but if it always keeps crawling in a stra ight line, then it will soon reach the end
of the storage space.
Note, however, that for applications where the queue is regularly empt ied (such as
advanwge when a series of requests is allowed to bu ild up to a certain point, and then a task is
Figure 3.5. A queue
initiated that clears all the requests before returning), at a time when the queue is empty,
the fron t and rear can both be reset to the beginning of the array, and the s imp le scheme
Applications o f que ues are, if anything , even more common than are applications of using two indices and s traight- line storage becomes a very efficient storage method.
applications of s tac ks , since in performing tasks by compute r, as in all parts of life, it is so ofte n
necessary to wait one 's tum before having access to some thing. Within a computer 3. Circular Arrays
system there may be queues o f tasks waiting for the line prin ter, for access to disk
storage, o r e ven, in a time-sharing system, for use of the CPU. \Vithin a s ingle prog ram, I n concept we can overcome the inefficient use of space simply by thinking of the array
there may be m ultiple requests to be kept in a que ue, or one task may create other tasks, as a circle rather than a stra ight line. See Figu re 3.6. In this way as items are added and
wh ich must be done in turn by kee ping the m in a queue. removed from the queue, the head will continually c hase the tail around the array, so
front and rear The item in a queue ready to be served, that is, the first item that will be remo ved that the snake can keep crawling indefini tely but stay in a confined circuit. At different
from the q ueue, we call the front o f the queue (or, sometimes. the head of the que ue). times the queue wi ll occupy different parts of the array, but we never need worry about
S imilarly, the last item in the queue , that is, the one most recently added , we call the runn ing out of space unless the array is fully occupied, in which case we tru ly have
rear (or the tail) of the queue. overfl ow.
70 Lists CHAPTER 3
S ECTION 3. 3 Queues 71
O ma• - 1
if (i>=MAX - 1)
i = O;
else
i++;
Circular
q ueue
or even more easily (but perhaps less efficiently at run time) by using the% operator:

i = (i + 1) % MAX;
6. Boundary Conditions
Before writi ng fonnal algorithms to add to and delete from a queue, let us consider the
boundary conditions, that is, the indicators that a queue is empty or fu ll. If there is
exactly one entry in the queue, then the front index will equal the rear index. When th is
Unwind ing one entry is removed, then the front will be increased by l, so that an empty queue is
indicated when the rear is one posi tion before the front. Now suppose that the queue
is nearly fu11. Then the rear wi11 have moved we11 away from the front, a11 the way
around the circle, and when the array is fu11 the rear will be exactly one position behind
the front. Thus we have another difficulty: The front and rear indices are in exactly the
empty orfu/1? same relative positions for an empty queue and for a fu ll queue! There is no way, by
looking at the indices alone, to te11 a fu11 queue from an empty one. This situation is
occupied
illustrated in Figure 3.7.

Linear
implementatio,, front rear
Queue
containing
one item
.: z
II(I (I (l
z z 2

rear
Jf i front
L( rrI I I I I 0
z z z z z

0 1 2 occupied J
max - 2
ma>< - 1 i Remove the item.

.CJ tic
..: z 2 2 2 2 2 2 ? 2 2 2 2
Figure 3.6. Queue in a circular array
Empty
queue II(I II I 0 fro nt
II (I I I II
4. Implementation of Circular Arrays
Our next problem is to implement a circular array as an ordinary linear (that is, straight-

I ( rr rrr ~lz I ~ I I I i i rI I [ D
line) array. To do so, we think of the positions around the ci rcle as numbered from O to
Queue
< '7' , '7 '7 z z z
with one
MAX- 1, where MAX is the total number of entries in the circular array, and to implement empty
position
the circular array, we use the same-numbered entries of a linear array. T hen moving the rear front
modulal' arirhmeric indices is just the same as doing modular arithmetic: When we increase an index past
MAX - 1 we start over again at 0. This is like doing arithmetic on a circular clock face;
i Insert an item.

the hours are numbered from I to 12, and if we add four hours to ten o'clock, we obtain
two o'clock.
Perhaps a good human analogy of this linear representation is that of a priest serving
Full
queue
<
I I r z
i(i r r ,1: r t
~~ r I I ( r rr i ( D
:ront
-::,, -::,,

communion to people kneeling at the front of a church. The communicants do not move Figure 3.7. E mpty and fu ll queue.~
until the priest comes by and serves them. When the priest reaches the end of the row,
he returns to the beginning and starts again, since by this time a new row of people have
7. Possible Solutions
come forward.
I. empty position There are at least three essentia11y different ways to resolve this problem. One is to insist
5. Circular Arrays in C
on leaving one empty position in the array so that the queue is considered fu11 when the
Tn C we can increase an index i by I in a circular array by writing 2. jlag rear index has moved within two positions of the front. A second method is to introduce
72 Lists CHAPTER 3 SEC TION 3.3 Queues 73

a new variable. This can be a Boolean variable that will be used when the rear comes 1. Implementation with a Counter
just before the front to indicate whether the queue is full or not (a Boolean variable to
First, we take the method in which a variable count is used to keep track of the number
check emptiness would be just as good) or an integer variable that counts the number
of items in the queue. The queue.h file contains the structure declaration for a queue
3. special values of items in the queue. The third method is to set one or both of the indices to some
and the function prototypes associated with queues:
value(s) that would otherwise never occur in order to indicate an cn1pty (or full) queue.
Tf, for example, the array entries are indexed from O to MAX - 1, then an empty queue
could be indicated by setting the rear index to - I.
#define MAXQUEUE 3

typedef char ltem _type;

f * small value for testing
*'
8. Summary of Implementations typedef struct queue_tag {
To summarize the discussion of queues, let us list all the methods we have discussed for type queue int count;
implementing queues. int front;
int rear;
ltemJype entry [MAXQUEUE];
I. The physical model: a linear array with the front always in the first position and all
} OueueJype;
entries moved up the array whenever the front is deleted (this is generally a poor
method for use in computers). void AddQueue ( ltem _type, Queue_type *) ;
void DeleteOueue ( ltemJype *, OueueJype *);
2. A linear array with two indices always increasing (this is a good method if the
void lnitialize(Queue_type *);
queue can be emptied all at once).
int Size ( Oueue_type *) ;
3. A circular array with front and rear indices and one position left vacant. BooleanJype Empty ( QueueJype * );
BooleanJype Full ( OueueJype *);
4. A circular array with front and rear indices and a Boolean variable to indicate
fullness (or emptiness).
The first function we need wi ll initialize the queue to be empty.
5. A circular array with front and rear indices and an integer variable counting entries.
6. A circular array with front and rear indices taking special values to indicate empti- *'
I• Initialize: initialize queue.
void Initialize ( QueueJype •queue_ptr)
ness.
initialize {
In the next chapter we shall find still other ways to implement queues. The most impor- queue _ptr->count = O;
tant thing to remember from this list is that, wi th so many variations in implementation, queue_ptr->front = O;
postpone we should always keep questions concerning the use of data structures like queues sep- queue _ptr->rear = - 1;
implementation arate from questions concerning their implementation, md in programming we should }
decisions always consider only one of these cat.egories of questions at a time. After we have
considered how queues will be used in our application, and after we have written the The key functions for adding to and deleting from a queue follow our preceding discussion
functions employing queues, we will have more information to help us choose the best closely. We use a function Error (included in general.h) to keep track of error. conditions.
implementation of queues suited to our application.
I* AddQueue: add item to the queue. • I
3.3.3 Circular Queues in C void AddQueue ( ltem_type item, OueueJype *queue_ptr)
insertion {
Next let us write formal C functions for some of the possible implementations of a queue. if (queue_ptr->count >= MAXOUEUE)
We shall choose the last I wo implementations and leave the others as exercises. In all Error ("Queue is fu ll") ;
cases, however, we take the queue as stored in an array indexed with the range else {
queue_ptr->cou nt ++ ;
O to MAXQUEUE - 1 queue_ptr->rear = (queue_ptr->rear + 1) % MAXOUEUE;
queue_ptr->entry [queue_ptr->rearJ = item;
}
and containing entries of a type called ltem_type. The variables front and rear will point
}
to appropriate positions in the array.
74 Lists C HA P T E R 3 SECT I ON 3.3 Queues 75

I* DeleteQueue: delete and return item in front of queue. * I We shall use the conditions rear == - 1 and front == 0 to indicate an empty queue.
deletion void DeleteQueue ( ltem_type * item, QueueJype *queue_ptr) The initialization function is
{ I* Initialize: initialize queue. * I
if (queue_ptr->count <= O) initialize void Initialize ( Oueue_type *queue_ptr)
Error ("Queue is empty") ; {
else { queue_ptr->front = O;
queue_ptr->count - - ; queue_ptr->rear = - 1;
* item = queue _ptr->entry [queue _ptr->from]; }
queue _ptr->front = (queue_ptr->front + 1) % MAXQUEUE;
} To write the functi on for adding to the queue, we must first (for error checking) find a
} condition indicating whether the queue is full or not. Fullness is typically indicated by
rear == front - 1 together with rear > - 1, but it is also possible that front == O and
We shall also find use for three functions concerning the size of the queue, all of which
rear >= MAXQUEUE - 1. Building these conditi ons into the function, we obtain
are easy to write with this implementation.
I* Size: return current number of items in the queue. * I I* AddQueue: add item to the queue. * I
size int Size ( QueueJype *queue_ptr) insertion void AddQueue ( ltemJype item, QueueJype *queue_ptr)
{ {
return queue_ptr->count; if ( (queue_ptr- >rear == queue_ptr->front - 1 &&
} queue _ptr- >rear > - 1) II

empty?
I* Empty: returns non-zero if the queue is empty.
Boolean_type Empty(QueueJype *queue_ptr)
*' (queue_ptr->rear == MAXQUEUE - 1 &&
queue _ptr->front == 0))
{ Error( "Queue is full");
return queue_ptr->count <= O; else {
} queue_ptr->rear = (queue_ptr->rear + 1) % MAXQUEUE;

full? Boolean_type Full ( Queue_type * queue_ptr)

*'
I* Full: returns non-zero if the queue is full.
}
queue_ptr->entry [queue _ptr->rear] = item;

{ }
return queue _ptr->count >= MAXQUEUE;
Since emptiness is indicated by rear == - 1, the deletion function closely resembles the
}
previou s version.
2. Implementation with Special Index Values
Next let us tum to the method that relies on special values for the indices. Most of the deletion
I* DeleteQueue: delete and return item in front of queue. *'
void OeleteOueue(ltemJype *item _ptr, Queue_type * queue_ptr)
necessary changes in declarations are clear. The modified queue.h then becomes {
#define MAXQUEUE 3 if (queue_ptr->rear <= - 1)
typedef char ltem _type; Error ("Queue is empty") ;
else {
typedef struct queueJag {
*item _ptr = queue_ptr->entry [queue_ptr->front] ;
1ype queue int front;
if (queue_ptr->front ! = queue_ptr->rear)
int rear;
queue_ptr->front = (queue _ptr->front + 1) % MAXQUEUE;
ltem _type entry [MAXQUEUE];
} OueueJype;
void AddQueue ( ltemJype, QueueJype *) ;
else {
queue_ptr->front = O;
I* The queue is now empty.
*'
queue_ptr->rear = - 1;
void OeleteQueue ( ltemJype *, Queue_type *) ; }
void Initialize ( Queue_type *) ; }
int Size ( QueueJype *); }
Boolean_type Empty ( Queue_type *) ;
BooleanJype Full ( QueueJype *); The three functions Size, Empty, and Full will be left as exercises.
76 Lists C H AP T E R 3 SEC T I ON 3. 4 Application of Queues: Simulation 77

Exercises El. Suppose that queue_ptr is a pointer to a queue that holds characters and that x, y, z ES. Rewrite the first set of C functions for queue processing from the text, using a
3.3 are character variables. Show the contents of the queue at each step of the following Boolean variable full instead of a counter of items in the queue.
code segments. E9. Write C functions to implement queues in a circular array with one unused entry in
the array. That is, we consider that the array is full when the rear is two positions
a. In itialize ( queue_ptr); b. Initial ze ( queue_ptr) ; before the front; when the rear is one position before, it will always indicate an
AddQueue ('a', queue_ptr); AddQueue ('a', queue_ptr) ; empty queue.
AddQueue('b', queue_ptr); x = 'b';
DeleteQueue ( &x, queue_ptr) ; AddQueue (' x', queue_ptr) ;
AddQueue (x, queue_ptr); DeleteOueue( &y, queue_ptr); Programming Pl. Write a function that will read one line of input from the terminal. The input is
DeleteQueue( &y, queue_ptr); AddQueue (x, queue_ptr) ; Proj ect 3.3 supposed to consist of two parts separated by a colon ': '. As its result your function
DeleteOueue ( &z, queue_ptr) ; DeleteOueue ( &z, queue_ptr) ; should produce a single character as follows:
AddQueue (y, queue_ptr) ;
N No colon on the line.
E2. Suppose that you are a financier and purchase 100 shares of stock in Company X L The left part (before the colon) is longer than the right.
in each of January, April, and September and sell 100 shares in each of June and R The right part (after the colon) is longer than the left.
accounting November. The prices per share in these months were D The left and right parts have the same length but are different.
s The left and right parts are exactly the same.

Jan Apr Jun. Sep Nov

$10 $30 S20 $50 $30
Examples: Input Output
Sample Sample N
Determine the total amount of your capital gain or loss using (a) FIFO (first-in, Short:Long L
first-out) accounting and (b) UFO (last-in, first-out) accounting (that is, assuming Sample:Sample s
that you keep your stock certificates in (a) a queue or (b) a stack). The 100 shares
you still own at the end of the year do not enter the calculation. Use a queue to keep track of the left part of the line while reading the right part.
E3. Use the functions developed in the text to write other functions that will
a. Empty one stack onto the top of another stack.
b. Move all the items from a queue onto a stack.
3.4 APPLICATION OF QUEUES: SIMULATION
c. Start with a queue and an empty stack, and use the stack to reverse the order
of all the items in the queue.
E4. Implement the simple representation of queues in a linear array when it can be 3.4.1 Introduction
assumed that the queue can be emptied when necess2ry. Write a function AddOueue Simulation is the use of one system to imitate the behavior of another system. Simu-
that will add an item if there is room and, if not, will call another function that will lations are often used when it would be too expensive or dangerous to experiment with
empty the queue. While writing this second function, you may assume the existence the real system. There are physical simulations, such as wind tunnels used to experiment
of an auxiliary function Service ( ltem_type item) that will process a single item that with designs for car bodies and flight simulators used to train airline pilots. Mathemat-
you have just removed from the queue. ical simulations are systems of equations used to describe some system, and computer
ES. Write C functions to implement queues by the simple but slow method of keeping simulations use the steps of a program to imitate the behavior of the system under study.
the head of the queue always in the first position of a linear array. computer models In a computer simulation, the objects being studied are usually represented as data,
often as data structures like structures or arrays whose entries describe the properties
E6. Write C functions to implement queues in a linear array with two indices front and of the objects. Actions in the system being studied are represented as operations on
rear, such that when rear reaches the end of the array all the items are moved to the data, and the rules describing these actions are translated into computer algorithms.
the front of the array. By changing the values of the data or by modifying these algorithms, we can observe
E7. Write the three functions Size, Empty, and Full for the implementation of a queue the changes in the computer simulation, and then, we hope, we can draw worthwhile
in a circular array with special index values to indicate emptiness. inferences concerning the behavior of the actual system in which we are interested.
78 Lists C HAPTER 3 SECTION 3.4 Application of Queues: Simulation 79

While one object in a system is involved in some action, other objects and actions
will often need to be kept waiting. Hence queues are important data structures for use
f * simulation of an airport*'
f* This is an outline only; not ready to compile. * I
in computer simulations. We shall study one of the most common and useful kinds of first outline void main ( void)
computer simulations, one that concentrates on queues as its basic data structure. These {
simulations imitate the behavior of systems (often, in fact, called qu~u eing systems) in Queue Jype landing, takeoff;
which there are queues of objects wai ting to be served by various processes. OueueJype *Pl = &landing;
OueueJype *Pl = &takeoff;
Plane_type plane;
int curtime; I* current time unit *I
3.4.2 Simulation of an Airport
As a specific example, let us consider a small but busy airport with only one runway
int endtime;
int i;
I* total number of time units to run
I* loop control variable *'
*I
(see Figure 3.8). In each unit of time one plane can land or one plane can take off, but Initialize (pl) ; I* Initialize landing queue. *I
not both. Planes arrive ready to land or to take off at random times, so at any given
unit of time, the runway may be idle or a plane may be landing or taking off, and there
Initialize (pt); I* Initialize takeoff queue.
for (curtime = 1; curtime <= endtime; curtime++) { *'
may be several planes waiting either to land or take off. We therefore need two queues,
rules which we shall call landing and takeoff, to hold these planes. It is bener to keep a plane
waiting on the ground than in the air, so a small airport allows a plane to take off only if
new plane
ready to land
for (i = 1; i <= RandomNumber(); i ++ ) { I* landing queue
NewPlane ( &plane) ; *'
if ( Full (pl))
there are no planes waiting to land. Hence, after receiving requests from new planes to
land or take off, our simulation will first service the head of the queue of planes waiting
to land, and only if the landing queue is empty will it allow a plane to take off. We shall
else
Refuse (plane); I* Refuse plane if full.
*'
wish to run the simulation through many units of time, and therefore we embed the main
action of the program in a loop that runs for curtime (denoting current time) from 1 to
}
AddQueue (plane, pl); I* Add to landing queue.
*'
a variable endtime. With this notation we can write an outline of the main program. new plane
ready to take off
for (i = 1; i <= RandomNumber(); i++) { I* takeoff queue
NewPlane ( &plane); *'
if ( Full (pt))

-- ---
. . . ___ _ __ ~~
1 ,..--
--

I?
----r--------"*
~- ---
Landing queue -
'
'I
~ }
else
Refuse (plane) ;

AddQueue(plane, pt);

plane landing if ( ! Empty(pl)) {

plane= OeleteOueue(pl);
I* Bring plane to land.
*'
Land (plane) ;
plane raking off } else if ( ! Empty (pt)) { I* Allow plane to take off. *I
plane = DeleteOueue(pt);
Fly(plane);
} else
idle runway Idle ();
" }
f t •. •: f
IT~ ··, •

. ' ..' .
--c".,...,..,--
- -

}
Conclude ( ) ;

Some of the declarations we are going to use are

typedef enum action _tag { ARRIVE, DEPART } ActionJype;

typedef struct planeJag {
int id; I* identification number of airplane *I

Figure 3.8. An airport

int tm ;
} PlaneJype;
I* time of arrival in queue
*'
 SECTION 3.4 Application of Queues: Simulation 81
80 Lists CHAPTER 3
new p/ane(s) pri = RandomNumber(expectdepart);
3.4.3 The Main Program ready ro rake off for (i = 1; i <= pri; i ++ ) { I* Add to takeoff queue.
Although this outline clearly shows the use of queues in this simulation, more detail is NewPlane ( &plane, &nplanes, curtime, DEPART);
if ( Full (pt) )
*'
needed to keep track of all the interesting statistics concerning the problem, such as the
number of planes processed. the average time spent waiting. and the number of planes Refuse(plane, &nrefuse, DEPART);
(if any) refused service. These details are reflected in the declarations of constants, else
types, and variables to be inserted into the main program. We shall then need to write AddQueue (plane, pt);
the subprograms to specify how this information is processed. The declaration of type }
QueueJype is deliberately omitted from the follow ing program, in order that we can
postpone until later the decision concerning which method will be used to implement the
plane landing if ( ! Empty(pl)) { I* Bring plane to land.
DeleteQueue ( &plane, pl); *'
queues. Most of the remaini ng declarations are self-explanatory, except for the last two Land (plane, curtime, &nland, &landwait);
variables, which are concerned with generating random numbers, and will be explained
when we consider the use of random numbers.
plane raking off } else if ( ! Empty(pt)) { I* Allow plane to take off.
DeleteQueue ( &plane, pt); *'
The version of the main program in runnable C differs little from the preceding Fly (plane, curtime, &ntakeoff, &takeoffwait);
outline except for the inclusion of the many parameters used to update all the variables. runway idle } else
Idle (curtime, &idletime);
}
void main(void)
{
I* simulation of an airport
*' finish simulation Conclude(nplanes, nland, ntakeoff, nrefuse, landwait,
takeoffwait, idletime, endtime, pt, pl);
Queue.type landing, takeoff; }
Queue.type * Pl = &landing;
Queue.type * Pl = &takeoff;
Plane.type plane; 3.4.4 Steps of the Simulation
int curtime; I* current time; one unit = time for take off or landing * I
The actions of the functions for doing the steps of the simulation are generally straight-
int endtime; I* total number of time units to run *I
forward, so we proceed to write each in turn, with comments only as needed for clarity.
double expectarrive; I* number of planes arriving in one unit * I
double expectdepart; I* number of planes newly ready to take off * I
inti;
int idletime;
I* loop control variable
I* number of units when runway is idle
*'
*I
1. Initialization
int landwait; f* total waiting time for planes landed *I
int nland; f* number of planes landed *I I* start: print messages and initialize the parameters. * I
int nplanes; f* number of planes processed so far *f void Start (int *endtime, double *expectarrive, double *expectdepart)
int nrefuse;
int ntakeoff;
I* number of planes refused of airport
I* number of planes taken off
*'
*f
{
Boolean.type ok;
int pri; I* pseudo-random integer *I instruct user print! ( 11 This program simulates an airport with only one runway.\n 11 ) ;
int takeoffwait; I* total waiting time for take off *I print! ( 11 One plane can land or depart in each unit of time. \n 11 ) ;
initialize Initialize (pl); Initialize (pt);
printf( 11 Up to %d planes can 11 , MAXQUEUE);
nplanes = nland = ntakeoff = nrefuse = O; print! ( 11 be waiting to land or take off at any time. \n 11 ) ;
landwait = takeoffwait = idletime = O; print! ( 11 How many units of time will the simulation run? 11 ) ;
input parameter
Start ( &endtime, &expectarrive, &expectdepart); scanf ( 11 %d 11 , endtime);
for (curtime = 1; curtime <= endtime; curtime++) {
Randomize ( ) ; I* Initialize random number generation. *'
new plane(sj µri = Rc1ndomNurnber ( expectarrive);
do {
ready to land for ( i = 1; i <= pri; i+ +) { I* Add to landing queue.
NewPlane ( &plane, &nplanes, curtime, ARRIVE);
if (Full (pl))
*' print! ( 11 Expected number of arrivals per unit time II
11
(real number)? 11 ) ;
scanf ( 11 %11 11 , expectarrive) ;
Refuse (plane, &nrefuse, ARRIVE); print! ( 11 Expected number of departures per unit time? 11 ) ;
else AddQueue (plane, pl); scant ( 11 %11 11 , expectdepart) ;
}
82 Lists CHAPTER 3 SECTION 3.4 Application of Queues: Simulation 83

error checking if ( *expectarrive < 0.0 II *expectdepart < 0.0) { 4. Processing an Arriving Plane
printf ( "These numbers must be nonnegative.\n");
ok = FALSE;
} else if ( *expectarrive + *expectdepart > 1.0) { I * Land: process a plane p that is actually landing. *'
void Land ( Plane_type p, int curtim e, int * nland, int *landwait)
print! ("The airport will become saturated. "
"Read new numbers?\n"); {
ok = ! Enquire ( ) ; I* If user says yes, repeat loop. int wait;
} else wait = curtime - p.tm;
ok = TRUE; printf("%3d: Plane %3d landed; in queue %d units.\n",
} while (ok == FALSE) ; curtime, p.id, wait);
} ( * nland) ++;
*landwait += wait;
2. Accepting a New Plane }

I* NewPlane: make a new record for a plane, update nplanes. * ' 5. Processing a Departing Plane
void NewPlane (PlaneJype *P, int *nplanes, int curtime,
ActionJype kind)
{
( *nplanes) ++ ;
f* Fly: process a plane p that is actually taking off. *'
void Fly(PlaneJype p, int curtime, int *ntakeoff, int * lakeoffwait)
p - >id = *nplanes; {
p- >tm = curtime; int wait;
switch (kind) { wait = curtime - p.tm;
case ARRIVE: printf("%3d : Plane %3d took off; in queue %d units.\n",
print! (" Plane %3d ready to land. \n", *nplanes); curtim e, p.id, wait);
break; ( *ntakeoff) ++;
case DEPART: *lakeoffwait += wait;
print!(" Plane %3d ready to take off.\n", *nplanes); }
break;
}
} 6. Marking an Idle Time Unit

3. Handling a Full Queue

f* Idle: updates variables for idle runway. * I
void ldle(int curtime, int *idletime)
I* Refuse: processes a plane when the queue is full.
void Refuse (Plane_type p, int *nrefuse, ActionJ ype k"nd)
*' {
printf ( "%3d : Runway is idle.\n", curtime) ;
{ ( *idletime) ++ ;
switch (kind) { }
case ARRIVE:
printf (" Plane %3d directed to another airport.\n", p.id); 7. Finishing the Simulation
break;
case DEPART:
printf (" Plane %3d told to try later. \n", p.id) ; I* Conclude: write out statistics and conclude simulation. * I
break; void Conclude( int nplanes, int nland, int ntakeoff,
} int nrefuse, int landwait, int takeoffwait,
( *nrefuse) ++ ; int idletim e, int endtime,
} QueueJype * Pl, Queue_type * pl)
84 lists CHAPTER 3 SECTION 3.4 Application of Queues: Simulation 85

{ the number of seconds elapsed modulus 10000. This number provides a different starting
printf ( "Simulation has concluded after %d units.\n", endtime); point for srand each time it is run.
printf("Total number of planes processed: %3d\n ", nplanes); We can then use the standard system function rand for producing each pseudorandom
printf (" Number of planes landed: %3d\n", nland) ; uniform distrib11tion number from its predecessor. The function rand produces as its result an integer number
printf (" Number of planes taken off: %3d\n", ntakeoff) ; between O and INT_MAX. (Consult the file limits.h 10 determine the value of INT.MAX on
printf (" Number of planes refused use: %3d\n", nrefuse); your system.) For our simulation we wish to obtain an integer giving the number of
printf (" Number left ready to land : %3d\n " , Size(pl)); planes arriving ready to land (or take off) in a given time unit. We can assume that
printf (" Number left ready to take off: %3d\n" , Size (pt)); the time when one plane enters the system is independent of that of any other plane.
if (endtime > O) Poisson distrib11tio11 The number of planes arriving in one unit of time then follows what is called a Poisson
printf(" Percentage of time runway idle: %6.2f\n 11 , distribution in statistics. To ca lculate the numbers, we need to know the expected value,
((double) idletime/endtime) * 100.0); that is, the average number of planes arriving in one unit of time. If, for example, on
if (nland > O) average one plane arrives in each of four time units, then the expected value is 0.25.
print! ( 11 Average wait time to land : %6.2f\ n", Sometimes several planes may arrive in the same time unit, but often no planes arrive,
(double) landwait/nland) ; so that taking the average over many units gives 0.25.
if ( ntakeoff > 0) The following function determines the number of planes by generating pseudoran-
printf ( 11 Average wait time to take off: %6.2f\n", dom integers according to a Poisson distribution:
(double) takeoffwait/ ntakeoff) ;
} I* RandomNumber: generate a pseudorandom integer according to the Poisson distri-
bution. * I
Poisson generator int RandomNumber (double expectedvalue)
3.4.5 Random Numbers {

A key step in our simulation is to decide, at each time unit, how many new planes become
int n = O;
double em;
I* counter of iterations
I* e-v. where v is the expected value *I
*'
ready to land or take off. Although there are many ways in which these decisions can double x; I* pseudorandom number *I
be made, one of the most interesting and useful is to make a random decision. When
the program is run repeatedly with random decisions, the results wi ll differ from run to em = exp( - expectedvalue);
run, and with sufficient experimentation, the simulation may display a range of behavior x = rand () I (double) l~L MAX;
not unlike that of the actual system being studied. while (x > em) {
system random Many computer systems include random number generators, and if one is available n++ ;
number generator x * = rand( )/(double) INT_MAX;
on your system, it can be used in place of the one developed here.
}
The idea is to start with one number and apply a series of arithmetic operations
return n;
that will produce another number with no obvious con!lcction to the first. Hence the
}
numbers we produce are not truly random at all, as eact one depends in a definite way
seed for on its predecessor, and we should more properly speak of pseudorandom numbers. If
pseudorandom we begin the simulation with the same value each time the program is run , then the
numbers whole sequence of pseudorandom numbers will be exa:tly the same, so we nonnally
begin by setting the starting point for the pseudorandom integers to some random value,
3.4.6 Sample Results
for example, the time of day: We conclude this section with the outpu t from a sample run of the airport simulation.
You should note that there are periods when the runway is idle and others when the
I* Randomize: set starting point for pseudorandom integers.
void Randomize(void)
*' queues are completely full, so that some planes must be turned away.

{ This program simulates an airport with only one runway.

srand((unsigned int) (time (NULL) %10000)); One plane can land or depart in each unit of time.
} Up to 5 planes can be waiting to land or take off at any time.
How many units of time will the simulation run? 30
The function time returns the number of seconds elapsed since 00:00:00 GMT, January l , Expected number of arrivals per unit time (real number) ? 0.47
1970. The expression time (NULL) % 10000 produces ar: integer between O and 9999- Expected number of departures per unit time? 0.47
 SECTION 3.4 Application of Queues: Simulation 87
86 Lists CHAPTER 3

Plane 27 ready to take off.

Plane 1 ready to land.
Plane 27 told to try later.
1: Plane 1 landed; in queue O units.
19: Plane 24 landed; in queue O units.
2: Runway is idle.
Plane 28 ready to land.
both queues are Plane 2 ready to land.
empty Plane 3 ready to land. Plane 29 ready to land.
Plane 30 ready to land.
3: Plane 2 landed; in queue O units.
Plane 31 ready to land.
4: Plane 3 landed; in queue 1 units. landing queue is full Plane 31 directed to another airport.
Plane 4 ready to land.
20: Plane 25 landed ; in queue 1 units.
Plane 5 ready to land.
Plane 32 ready to land.
Plane 6 ready to take off. Plane 33 ready to take off.
Plane 7 ready to take off. Plane 33 told to try later.
5: Plane 4 landed; in queue O units. 21: Plane 26 landed; in queue 2 units.
Plane 8 ready to take off. 22: Plane 28 landed; in queue 2 units.
6: Plane 5 landed; in queue 1 units. 23: Plane 29 landed; in queue 3 units.
Plane 9 ready to take off. Plane 34 ready to take off.
Plane 10 ready to take off. Plane 34 told to try later.
7: Plane 6 took off; in queue 2 units. 24: Plane 30 landed; in queue 4 units.
8: Plane 7 took off; in queue 3 units. Plane 35 ready to take off.
9: Plane 8 took off; in queue 3 units. Plane 35 told to try later.
Plane 11 ready to land. Plane 36 ready to take off.
Plane 36 told to try later.
10: Plane 11 landed; in queue O units.
landing queue is Plane 12 ready to take off. 25: Plane 32 landed; in queue 4 units.
empty Plane 37 ready to take off.
11 : Plane 9 took off; in queue 4 units.
Plane 37 told to try later.
Plane 13 ready to land.
26: Plane 12 took off; in queue 15 units.
Plane 14 ready to land.
27: Plane 16 took off; in queue 12 units.
12: Plane 13 landed; in queue O units.
28: Plane 17 took off; in queue 13 units.
13: Plane 14 landed; in queue 1 units.
29: Plane 20 took off; in queue 13 units.
14: Plane 10 took off; in queue 7 units. Plane 38 ready to take off.
Plane 15 ready to land. 30: Plane 21 took off; in queue 14 units.
Plane 16 ready to take off.
Summary Simulation has concluded alter 30 units.
Plane 17 ready to take off.
Total number of planes processed: 38
15: Plane 15 landed; in queue O units. Number of planes landed: 19
Plane 18 ready to land. Number of planes taken off: 10
Plane 19 ready to land. Number of planes refused use: 8
Plane 20 ready to take off. Number left ready to land: 0
Plane 21 ready to take off. Number left ready to take off: 1
16: Plane 18 landed; in queue O units. Percentage of 1ime runway idle: 3.33
Plane 22 ready to land. Average wait time to land: 1.11
17: Plane 19 landed; in queue 1 units. Average wait time to take off: 8.60
takeoff queue is full Plane 23 ready to take off.
Plane 23 told to try later.
18: Plane 22 landed; in queue 1 units. Exercise El. In the airport simu lation we did not spec ify which implementation of queues to use.
Plane 24 ready to land. Which of the implementations would be best to use, and why? If lhe choice of
Plane 25 ready to land.
3.4
implementation does not make much difference, explain why.
Plane 26 ready to land.
 CHAPTER 3 S ECTION 3.5 Other Lists and their Implementation 89
88 Lists

Programming Pl. Experiment with several sample runs of the airport simu lation, adjusti ng the values
Projects for the expected numbers of planes ready to land and take off. Find approximate
values for these expt:eted numbers that are as large as possible subject to the con-
3.4
dition that it is very unlikely that a plane must be refused service. What happens
to these values if the maximum size of the queues is increased or decreased?
P2. Modify the simulation to give the airport two runways, one always used for landings
and one always used for takeoffs. Compare the tolal number of planes that can be
served with the number for the one-runway airport. Does it more than double?
P3. Modify the simulation to give the airport two runways, one usually used for landings
and one usuall y used for takeoffs. Tf one of the queues is empty, then both rnnways
can be used for the other queue. Also, if the landing queue is full and another plane
arrives to land, then takeoffs will be stopped and both runways used to clear the
backlog of landing planes.
P4. Modify the simulation to have three runways, one always reserved for each of Figure 3.9. A random walk
landing and takeoff and the third used fur landings unless the landing queue is
empty, in which case it can be used for takeoffs. upper left comer of the grid. Mod ify the simulation to see how much faster he
PS. Modify the original (one-runway) simulation so that when each plane arrives to land, can now get home.
it will (as pa11 of its structure) have a (randomly generated) fuel level, measured c. Modify the original simulation so that, if the drunk happens to arrive back at
in units of time remaining. If the plane does not have enough fuel to wai t in the the pub, then he goes in and the walk ends. Find out (dependi ng on the size
queue, it is allowed to land immediately. Hence the planes in the landing queue and shape of the grid) what percen tage of the time the drunk makes it home
may be kept waiting additional units, and so may ru n out of fue l them selves. Check successfull y.
this out as part of the landing function, and find abou t how busy the airport can get d . Modify the origi nal simulation so as to give the drunk some memory to help
before planes stai1 to crash from running out of fuel. him. as fo llows. Each time he arrives at a corner, if he has been there before
ranitom numbers P6. Write a stub to take the place of the random number function . The stub can be used on the current walk, he remembers what streets he has already taken and tries
both to debug the program and to allow the user to control exactly the number of a new one. If he has already tried all the streets from the corner, he decides
planes arriving for each queue at each time unit. at random which to take now. How much more qu ickl y does he get home?
The main program and the remai ning functions are the same as in the previous
P7. Write a dri ver program for functi on RandomNumber; use it to check th at the func-
version.
tion produces random integers whose average over the number of iterations per-
fom1ed is the specified expected value.
scissors-paper-rock PS. In a certain children's game each of two players simultaneously puts out a hand held 3.5 OTHER LISTS AND THEIR IMPLEMENTATION
in a fashion to denote one of scissors, paper, or rock. The rules are that scissors
beats paper (since scissors cut paper), paper beats rock (since paper covers rock),
and rock beats scissors (since rock breaks scissors). Write a program to simulate 1. General lists
playing this game with a person who types in S, P, or R at each turn. Stacks are the easiest kind of list to use because all additions and delet ions are made at
P9. After leaving a pub a drunk tries to walk home. The streets between the pub and one end of the list. In queues changes are made at both ends, but only at the ends, so
random walk the home form a rectangular grid. Each time the drunk reaches a corner he decides queues are still relatively easy to use. For many applicat ions, however. it is necessary
at random what direction to walk next. He never, however, wanders outside the to access all the elements of the list and to be able to make insertions or deletions at
grid. any point in the list. It might be necessary, for example, to insert a new name into the
a. Write a program to simulate this random walk. The number of rows and middle of a list that is kept in alphabetica l order.
col umns in the grid should be variable. Your program should calculate, over
many random walks on the same grid, how long it takes the drunk to get home 2. Two Implementations
on average. In vestigate how this number depends on the shape and size of the The usua l way of implementing a list, the one we wou ld probably first th ink of, is to keep
grid.
I . coumer the en tries of the list in an array and to use an index that counts the number of entries in
b. To improve his chances, the drunk moves closer to the pub-to a room on the
90 Lists C H AP TER 3 SECTI O N 3.5 Other Li sts and their Implementation 91

the list and allows us to locate its end. Variations of this implementation are often useful, status operation Boolean_type Empty(LisUype *list);
however. Instead of using a counter of elements, for example, we can sometimes mark BooleanJype Full (LisUype *list);
2. special value entries of the array that do not contain list elements with some special symbol denoting int Size ( LisUype *list) ;
emptiness. In a list of words, we might mark all unused positions by setting them to
blanks. In a list of numbers, we might use some number guaranteed never to appear in For most other operations we must specify the place in the list to use. At any instant we
the list. are only looking at one entry of the list, and we shall refer to this entry as the window
window into a list into the list. Hence, for a stack the window is always at the same end of the list; for a
If it is frequently necessary to make insertions and deletions in the middle of the
queue, it is at the front for deletions and at the rear for additions. For an arbitrary list we
relative advantages list, then this second implementation will prove advantageous. If we wish to delete
can move the window through the list one entry at a time, or position it to any desired
an element from the middle of a list where the elements are kept next to each other,
entry. The following are some of the operations we wish to be able to do with windows
then we must move many of the remaining elements to fill in the vacant position, while
and lists:
with the second implementation, we need only mark the deleted position as empty by
putting the special symbol there. See Figure 3.10. If, later, we wish to insert a new
element into a list in the first implementation, we must again move many elements. With
I* Initialize: initialize the list to be empty.
void Initialize ( LisUype *list);
*'
the second implementation, we need only move elements until we encounter a position
I* lsFirst: non-zero if w is the first element of the list. *I
marked empty. With the first implementation, on the other hand, other operations are
Boolean_type lsFirst(LisUype *list, int w);
easier. We can tell immediately the number of elements in the list, but with the second
implementation, we may need to step through the entire array counting entries not marked I* lsLast: non-zero if w is the last element of the list.
Boolean_type lslast(LisUype *list, int w);
*'
empty. With the first implementation, we can move to the next entry of the list simply
by increasing an index by one; with the second, we must search for an entry not marked window positioning I* Start: position the window at the first entry of list. * I
empty. void Start (LisUype *list, int *W);
I* Next: position window on the next entry, if there is one. * I
void Next (LisUype *list, int *W);

c.it cat cat cat

I* Preceding: position window on the preceding entry, if there is one.
void Preceding(LisUype *list, int *w);
*'
cow dog COii' null I* Finish: position window to the last entry of the list. *'
dog

hen
------
------
hen

pig
nul

do~
null

dog
list changes
void Finish ( LisUype *list, int *W);

I* Delete: delete entry at window and update window. * I

pig
------ hen

null
hen

null
void Delete (LisUype *list, int *w);
I* lnsertAfter: insert item after the window. *'
void lnsertAfter(LisUype *list, int *W, ltemJype item) ;

pig pig
I* lnsertBefore: insert item before current window. * I
void lnsertBefore (LisUype *list, int *W, ltem_type item);
count = 5

First implementation
count = 4

Second i1nplementation
I* Replace: replace the item at the window w.
void Replace(Lisuype *list, int w, ltem_type item);
*'
w. *'
Figure 3.10. Deletion from a list
I* Retrieve: retrieve an item at the window
void Retrieve(LisUype list, int w, ltemJype *item);
3. Operations on Lists 4. List Traversal
Because variations in implementation are possible, it is wise in des igning programs to One more action is commonl y done with lists-traversal of the list-which means to
separate decisions concerning the use of data strucwres from decisions concerning their start at the beginning of the list and do some action for each item in the list in turn,
implementation. To help in delineating these decisions, let us enumerate some of the traverse and visit finishing with the last item in the list. What act ion is done for each item depends on the
operations we would like to do with lists. application, for generality we say that we visit each item in the list. Hence we have the
First, there are three functions whose purposes are clear from their names: final function for list processing:
92 Lists CHAPTER 3 SECTION 3.5 Other Lists and their Implementation 93

I* Traverse: traverse list and invoke Visit for each item. *I I* Delete: delete entry at window and update window. * I
void Traverse(LisUype *list, void ( * Visit) (ltem_type x)); delerion. version I void Delete (LisUype *lisLptr, int *W)
{
Jimction as an (Yes, this declaration is standard C; pointers to functions are allowed as formal parameters int i;
argument for other functions, although this feature is not often u&ed in elementary programming.)
When function Traverse finishes, the window has not been changed. To be sure of for (i = *W + 1; i < list_ptr- >count; i++)
proper functioning, it is necessary to assume that function Visit makes no insertions or lisLptr->entry [ i - 1) = lisLptr->entry [i);
deletions in the list list. lisLptr->count - - ;
if ( Empty ( lisLptr))
5. C Programs Start ( lisLptr, w) ;
Let us now finally tum to the C details of the two implementations of lists introduced else if ( *W > Size ( lisLptr) )
earlier. Both methods will require the declaration of a constant MAXLIST giving the Finish ( lisLptr, w);
maximum number of items allowed in a list and typedefs used. The first method then }
requires the following structure and typedefs:
I* Delete: delete entry at window and update window. * I
#define MAXLIST 10 delerio11, versio11 2 void Delete(LisUype *lisLptr, int *W)
{
typedef char ltemJype;
BooleanJype flag;
type list typedef struct lisUag {
flag= lslast(lisLptr, w);
int count;
lisLptr->entry [ *W) = (ltemJype) NULL;
ltem_type entry [MAXLISlJ ;
if ( flag)
} LisUype;
Start (lisLptr, w);
The second method replaces the last declaration with else
Next (lisLptr, w);
typedef struct lisUag { }
ltemJype entry [ MAXLIST) ;
} LisUype; A lthough there remai n a good many functions to write in order to implement these list
structures fully in C, most of the details are simple and can safely be left as exercises. It
To show the relative advantages of the two implementations, let us write the functions is, of course, pem1issible to use functions already written as part of later functions. To
Size and Delete for each implementation. illustrate this. let us conclude this section with a version of function Traverse that will
f* Size: return the size of a list. * I work with either implementation.
size, version] int Size(LisUype * list)
{ I* Traverse: traverse the list and invoke Visit for each item. * I
void Traverse(LisUype * lisLptr, void ( *Visit) (ltemJype))
return list->count;
{
}
int w;
I* Size: return the size of a list. * I ltemJype item;
size, version 2 int Size(LisUype *lisL ptr)
if ( ! Empty(lisLptr)) { I* only if not empty *I
{
Start ( lisLptr, &w);
inti;
while ( ! lslast (lisLptr, &w)) {
int count= O;
Retrieve (lisLptr, &w, &item);
for (i = O; i < MAXLIST; i++ ) ( *Visit) (item) ;
if ( lisLptr- >entry [i] ! = ' \O' )
count++ ;
return count;
}
Next(lisLptr, &w); I* next position in the list
*'
Retrieve (list.ptr, &w, &item); I* Get last item. *I
} ( tVisit) (item);
As you can see, the fi rst version is somewhat simpler. On the other hand, for the Delete }
function, the second version is simpler. }
94 Lists CHAPTER 3 SECTION 3 . 5 Other Lists and their Implementation 95

As an example, let us write a simple version of the function Visit. We shall assume that track. Devise and draw a railway swi tching network that will represent a deque.
the it.e ms are characters , and we simply pri nt the charact~r. The network should have only one entrance and one exit.

f* Visit: print the item retrieved from the list.

void Visit ( ltem tyf)A ilAm)
*' E6. Suppose that data items numbered 1, 2, 3, 4, 5, 6 come in the input stream in this
order. By using (I) a queue and (2) a deque, which of the following rearrangements
can be obtained in the output order?
{
printf ("ite m is o/oc \n" , item ) ; (a) 1 2 3 4 5 6 (b) 2 4 3 6 5 I (c) I 5 2 4 3 6
} (d) 4 2 I 3 5 6 (e) I 2 6 4 5 3 (f) 5 2 6 3 4 I
scroll E7. A scroll is a data structure intennediate to a deque and a queue. In a scroll all
additions to the list are at its end, but deletions can be made ei ther at the end or at
Exercises El. Write C functions to implement the following operations on a list implemented with the beginning. Answer the preceding questions in the case of a scroll rather than a
deque.
3.5 (a) a structure type including an array of items and a counter of items in the list
and (b) an array with NULL entries denoting an empty position. a. Is it more appropriate to think of a scroll as implemen ted in a linear array or
a. Boolean_type Empty( LisU ype *lisLptr); a circular array? Why?
b. Boolean.type Full (LisUype * lisLptr); b. Write the four algorithms needed to add an item to each end of a scroll and to
c. Boolean.type lsFirst(LisUype *list.ptr, int w); delete an item from each end of a scroll.
d. Boolean.type lsLast(LisUype *lisLptr, int w); c. Devise and draw a railway switchi ng network that will represent a scroll. The
e. void Initia lize ( LisUype * list.ptr); network should have only one entrance and one exit.
f. void Start ( LisUype * lisLptr, int *W) ; d. Suppose that data items numbered I. 2, 3, 4, 5, 6 come in the input stream in
g. void Finish ( LisUype *list.ptr, int *W) ; this order. By using a scroll, which of the following rearrangements can be
h. void Next(LisU ype *list.ptr, int *W); obtained in the output order?
i. void Preceding ( LisUype * lisLptr, int *W) ; (a) I 2 3 4 5 6 (b) 2 4 3 6 5 I (c) I 5 2 4 3 6
j. void lnsertAfter ( LisUype * list.ptr, int *W, Item.type item) ; (d) 4 2 I 3 5 6 (e) 1264 5 3 (f) 5 2 6 3 4 I
k. void lnsertBefore(LisU ype * lisLptr, int *W, Item.type item ) ;
I. void Replace( LisU ype *lisLptr, int w, ltem J ype item) ; ES. Suppose that we think of dividing a deque in half by fixing some position in the
middle of it. Then the left and right halves of the deque are each a stack. T hus a
m. void Retrieve ( LisUype * lisLptr, int w) ;
deque can be implemented with two stacks. Write algori thms that will add to and
E2. Given the functions for operating with lists developed in this section, do the fol- delete from each end of the deque considered in this way. When one of the two
lowing tasks. stacks is empty and the other one not, and an attempt is made to pop the empty stack,
a. Write a function that deletes the last entry of a list. you will need to move items (equivalent to changing the place where the deque was
b. Write a function that deletes the fi rst entry of a list. broken in half) before the request can be satisfied. Compare your algorithms with
c. Write a function that. reverses the order of the entries in a list.. those of Exercise E4 in regard to
d. Write a function that splits a list into two other lists, so that the entries that a. clarity;
were in odd-numbered positions are now in one list (in the same relative order b. ease of composition;
as before) and those from even-numbered positions are in the other new list.
c. storage use;
T he word deque (pronounced either "deck" or " DQ") is a short.ened fonn of double· d. time used for typical accesses;
ended queue and denotes a list in which items can be added or deleted from either the e. time used when items must be moved.
first or the last positi on of the list, but no changes can be made elsewhere in the list.
Thus a deque is a generalization of both a stack and a queue. unordered list E9. In th is section we have implicitly assumed that all operations on a list were required
to preserve the order of the items in the list. In some applications, however, the
E3. Ts it more appropriate to think of a deque as implemented in a linear array or in a
order of the items is of no importance. ln the lists live and die that we set up for
circular array? Why?
the Life game in Chapter 2, for example, it made no difference in what order the
E4. Write the four algorithms needed to add an item to each end of a deque and to entries were in the lists, and so when we needed to delete an item from the list,
delete an item from each end of the deque. we could fill its hole simply by moving the last item from the list into the vacant
ES. Note from Figure 3.4 that a stack can be represented pictori all y as a spur track on position and reducing the count of items on the list by I. Function Vivify thus had
a straight rail way line. A queue can, of course, be represented simply as a straight the form
96 Lists C HA P TER 3 C HA P T ER 3 References for Further Study 97

f* Vivify: vivify a dead cell provided it meets the required conditions.

void Vivify (void)
*' 3. What are stack frames for subprograms? What do they s how?
4. What are the advantages of writing the operations on a data structure as functions?
{
S. Define the term queue. What operations can be done on a queue?
i = 1;
whilP. (i <= count) 6. How is a circular array implemented in a linear array?
if (entry[i] is OK) { 7. List three different implementations of queues.
process entry [i] ; 8. Define the term simulation.
i++ ; 9. Why are random numbe rs used in computer programs usually not really random?
} else {
entry [ i] = entry [count] ; 10. What is a deque?
count--; 11. Which of the operations possible for general lists are also poss ible for queues? for
} stacks?
} 12. List three operations possible for general lists that are not allowed for either stacks
Determine which of the operations on lists from this section will be simplified if or queues.
the order of entries in the lists can be changed as desired. Rewrite the associated
functions for these operations.
REFERENCES FOR FURTHER STUDY
The separation of prope nies of data structures and their operations from the implemen-
POINTERS AND PITFALLS tation of the data struc tures in memory and functions is called data abstraction. The
data abstraction follow ing book takes thi s point of view consistently and develops funher propenies of
I. Don't confuse lists with arrays.
lists:
2. Choose your data structures as you design your algorithms, and avoid making pre- J1M WELSH, JOHN ELDER, and DAVID BusTARD, Sequential Program Structures, Premice
mature decisions. Hall International. London, 1984. 385 pages.
3. Practice information hiding: Use functions to access your data structures. For many topics concerning data structures, the best source for additional information,
4. Postpone decisions on the details of implementing your data structures as long as historical notes, and mathematical analysis is the following series of books, which can
you can. be regarded almost like an encyclopredia for the aspects of computing science that they
5. Stacks are the simplest kind of lists; use stacks when possible. discuss:
encyclopredic DoNALD E. K NUTH, The Art of Compmer Programming published by Addison-Wesley,
6. Avoid tricky ways of storing your data; tricks usually will not generalize to new reference: KNUTH Reading, Mass.
situations.
Three volumes have appeared to date:
7. Be sure to initial.ize your data structures.
8. Always be careful about the extreme cases and handle them gracefully. Trace l. Fundamental Algorithms, second edi tion, 1973, 634 pages.
through your algorithm to determine what happens when a data stmcture is empty 2. Semi1111merical Algorithms, second edition, l 980, 700 pages.
or full.
3. Sorting and Searching, 1973, 722 pages.
9. Don't optimize your code until it. works perfect!)', and then only optimize it if
improvement in efficiency is definitely required. First try a si mple implementation From now on we shall often give references to this series of books, and for convenience
of your data struct.ures. Change to a more sophisticated implementation only if the we shall do so by specifying on ly the name K NUTH together with the volume and page
simple one proves too inefficient. numbers. In particular, stacks, queues, and deques are studied in K NUTH , Volume I ,
1O. When working with general lists, first decide exactly what operations are needed, pp. 234-25 I, with the inclusion of many interes ting extensions and exercises. The
then choose the implementation that enables those operations to be done most easily. algorithms are written both in English and in an assembler language, where K NUTH
calculates detailed counts of operations to com pare various algorithms.
In Volume 2, pp. 1-177, K NUTH studies the construction and testing of pseudorandom
REVIEW QUESTIONS number generators in g reat depth.
An elementary survey of computer si mulations appears in Byte 10 (October 1985),
1. What is the difference between an array and a list~ pp. 149-25 l. A simulation of the Nat ional Airpon in Washi ngton , D.C., appears on
pp. 186--190.
2. W hat are t.he operations that can be done on a s tack?
 S E CT ION 4 . 1 Dynamic Memory Allocation and Pointers 99
C HA P T E R 4
4.1 DYNAMIC MEMORY ALLOCATION AND POINTERS
4.1.1 The Problem of Overflow
In the examples we have studied in the previous chapters we have assumed that all items

Linked Lists fixed bounds

of data are kept wi thin arrays, arrays th at must be declared to have some size that is fixed
when the program is written, and that can therefore not be c hanged while the program
is running. When writing a program, we have had to decide on the maximum amount
of memory that would be needed for our arrays and set this aside in the declarations. If
we run the program on a small sample, then much of this space will never be used. If
we decide to run the program on a large set of data , then we may exhaust the space set
This chapter studies the implementation of lists by the use of links. Several aside and encou nter overfl ow, even when the computer memory itself is not full y used,
examples are developed, and the chapter closes with a discussion of the simply because our original bounds on the array were too small.
general principles of abstract data types and data structures. Even if we a re carefu l to declare our arrays large enough to use up all the available
problem of overflow memory, we can still encounter overflow, since one array may reach its limit while a great
deal of unused space remains in others. Since different runs of the same program may
cause different lists to grow or s hrink , it may be impossible to tell before the program
actua lly executes which lists will overflow.
4.1 Dynamic Memory Allocation and 4.4 Application: Polynomial We now exhibi t a way to keep lists and othe r data structu res in memory without
Pointers 99 Arithmetic 123 using arrays, whereby we can avoid these difficulties.
4.1 .1 The Problem of Overflow 99 4.4.1 Purpose of the Project 123
4.1 .2 Pointers 99 4.4.2 The Main Program 124 4.1.2 Pointers
4.1 .3 Further Remarks 100 4.43 Data Structures and Their The idea we use is that of a pointer. A pointer, also called a link or a reference,
4.1.4 Dynamic Memory Allocation 101 lr,plementation 128 is defined to be a variable that gives the location of some other variable, typically of a
4.4.4 F.eading and Writing structure containing data that we wish to use. If we use pointers to locate all the structures
4.1.5 Pointers and Dynamic Memory in Polynomials 130
C 101 in which we are inte rested, then we need not be concerned about where the structures
4.4.5 Addition of Polynomials 131
themselves are actua lly stored, since by using a pointer, we can let the computer system
4.4.6 Completing the Project 132
itself locate the structure when requi red.
4.2 Linked Stacks and Queues 106 4.5 Linked Lists in Arrays 135 Figure 4.1 shows pointers to several structures. Pointers are generally depicted as
4.2.1 Declarations 106 arrows and s tructures as rectangular boxes. In the diagrams, variables con tai ning pointers
4.2.2 Linked Stacks 107 4.6 Abstract Data Types and Their
Implementations 140 <'.
4.2.3 Linked Queues 111

4.3 Further Operations on linked

4.6.1 Introduction 140
4.6.2 General Definitions 141
4.6.3 Refinement of Data
·G ·I Lynn
0
lists 114
4.3.1 Algorithms for Simply Linked
Lists 114
Soecification 143
Pointers and Pittalls 145
sG -!-
Jack

~
4.3.2 Comparison of Review Questions 146
Implementations 120
4.3.3 Programming Hints 121 References for Further Study 146

u Marsha

Figure 4.1. Poi nters to structures

98
100 Linke d Lists CHAPTEP 4 S ECTION 4 . 1 Dynamic Memory Allocation and Pointers 101

2. Pointers for Contiguous Lists

;:.;.
,,;,
'e-
Fred
367-2205
Jan. 28
'
,,
b

~
Jackie
295-0603
Feb. 18
!:r~
~T
!ffl
A pointer is simply a variable giving the location of some item, and for contiguous lists,
we have in fact been using pointers informally throughout the last chapter. The variable
top is a pointer givi ng the location of the item on the top of a stack, and the variables
front and rear give the locations of the front and rear of a queue. To avoid possible
ill
confusion, however, we shall generally reserve the word pointer for use with linked lists
Carol '",. Tom
~

•;;.
Rene I

and continue 10 use the word index (and, later in this chapter, the word cursor) to refer
'- 628-5100 ' 286-2 139 342-5 153 ' !I

Feb. 23
"
if: ' Feb. 28 ffil i
Figure 4.2. A linked list
Mar. 15 111ff, ll * to a location within an array.

4.1.4 Dynamic Memory Allocation

are generally shown in shaded boxes. Hence in the diagram r is a pointer to the structure As well as preventing unnecessary overflow problems caused by running out of room in
"Lynn" and v is a pointer to the structure "Jack." As you can sec, the use of pointers is arrays, the use of pointers has advantages in a multitasking or time-sharing envi ronment.
quite flexible: two pointers can refer to the same structure, as t and u do in Figure 4.1, or time sharing If we use arrays to reserve in advance the maximum amount of memory that our program
a pointer can refer to no structure at all. We denote this latter situation within diagrams might need, then this memory is assigned to us and will be unavai lable for other tasks.
poimers referring hy the electrical grou11d symbol, as shown for pointer s. Care must. be exercised when If it is necessary to page ou r job out of memory, then there may be time lost as unused
nowhere using pointers, moreover, t.o be sure that, when they are moved, no structure is lost. In memory is copied 10 and from a disk. Instead of using arrays to hold all our items, we
the diagram, the structure "Dave" is lost., with no pointer referring to it, and therefore can begin very small, with space only for the program instructions and si mple variables,
there is no way to find it. and whenever we need space for an add itional item, we can request the system for the
linked list The idea of a /i11ked list is, for every structure in the list, to put a pointer into the needed memory. Similarly, when an item is no longer needed, its space can be retu rned
structure giving the location of the next structure in the list. T his idea is illustrated in to the system, wh ich can then assign it to another user. In this way a program can start
Figure 4.2. small and grow only as necessary, so that when it is small, it can run more efficiently,
As you can see from the illustration, a linked list is simple in concept. It uses the and when necessary it can grow to the limits of the computer system.
same idea as a children's treasure hunt, where each clue that is found tells where to find Even with only one user this dynamic control of memory can prove useful. During
the next one. Or consider friends passing a popular cassette around. Fred has it, and one part of a task a large amount of memory may be needed for some purpose, which can
has promised to give it to Jackie. Carol asks Jack ie if she can borrow it, and then will later be released and then all ocated agai n for another purpose, perhaps now containing
next share it with Tom. And so it goes. A linked list may be considered analogous data of a completely different type than before.
to following instructions where each instruction is gi ven out only upon completion of
the previous task. There is then no inherent limit on t:,e number of tasks to be done, 4.1.5 Pointers and Dynamic Memory in C
since each task may specify a new instruction, and there is no way to tell in advance
C provides powerfu l fac ilities for processing pointers and standard functions for request-
how many instructions there are. The list implementations studied in Chapter 3, on the
ing additiona l memory and for releasing memory during program execution.
other hand, arc analogous to a list of instructions written on a single sheet of paper. It
is then possible to see all the instructions in advance, but there is a limit to the numhcr 1. Static and Dynamic Variables
of instructions that can he written on the single sheet of paper.
With some practice in their use, you will find that linked lists are as easy to work Variables that can be used duri ng execution of a C program come in two varieties. Static
with as lists implemented within arrays. The methods differ substantially, however, so variables are those that are declared and named, as usual, while writing the program.
we must spend some t.ime developing new programming skills. Before we turn to th is Space for them exists as long as the program in wh ich they are declared is running.
work, let us consider a few more general observations. (There is a storage class for variables in C called static; the variables are known only
in the function where they are declared and their space exists for the duration of the
main program. We are us ing the tenn static variable here to denote any variable that
4.1.3 Further Remarks is dec lared while writing the program.) Dynamic variabl.es are created (and perhaps
destroyed) during program execution. Since dynamic variables do not exist while the
1. Contiguous and Linked Lists program is compiled, but onl y when it is run, they cannot be assigned names while it is
The word co11tiguous means i11 contact, touching, adj oining . The entries in an array are being written.
conti guous, and from now on we shall speak of a list kept in an array as a co11tig11ous The only way to access dynamic variables is by using pointers. Once it is created,
list. We can then distingui sh as desi red between contiguous lists and linked lists. and we however, a dynamic variable does contain data and must have a type like any other
shall use the unqualified word list only to include both. variable. Thus we can talk about creati ng a new dynamic variable of type x and selling
102 Linked Lists CHAPTER 4
SECTION 4 . 1 Dynamic Memory Allocation and Pointers 103
a poinLer to point to it, or of moving a pointer from one dynamic variable of type x to 4. NULL Pointers
another, or of returning a dynamic variable of type x to the system.
Static variables, on the other hand, cannot be created or destroyed during execution Sometimes a pointer variable p has no dynamic variable to which it curre ntly refers.
of the program in which they are declared, although pointer variables can be used to This situation can be established by the assignment
poinl to static variables. For example,
p = NULL;
void f(void)
{ and it can s ubsequently be checked by a condition such as
char c;
if (p ! = NULL) . . ..
}
In diagrams we use the electrical ground symbo l
The function f has a local variable c of type character. There will be space allocated for
c when the function f executes. The function itself cannot destroy the space reserved for
c or ask for more space for c. When f terminates, however, c is destroyed. The variable
c is a static variable as opposed to a dynamic variable, for which the program controls
the allocation and disposal of the space. If a dynamic variable is created in a function,
then it can continue to exist even after the function terminates. for a NULL pointer.
NULL is a symbolic constant defined in the include file stdio.h, and, in fact, the value
2. CNotation of NULL is the constant zero. This means that the constant NULL is generic in that it can
be assigned to a variable of any pointer type. It also means that the statements
C uses a star * to denoLe a poinLer. lf p is a pointer Lo a characLer, we declare it by
if (p ! = NULL) . . . and if ( p) ...
char *Pi
equiva/e111 forms do exactly the same thing. Both forms are commonly used in C programs. The first form
If NodeJype denotes the type of items in which we are inte rested, then we declare a shows more clearly that a pointer is being checked to see if it poillls to a dynamic variable.
pointer type Lhat. is bound Lo Lype NodeJype with the declaration The second form, being more compact, is often easier to read when it appears inside a
complicated expression. We shall use both forms interchangeably in the programs we
typedef struct nodeJag { write.
undefined poi111ers Note carefully the distinction between a pointer variable whose value is undefined
} NodeJ ype; versus NULL pointers and a pointer variable whose va lue is NULL. The assertion p == NULL means that p
Node_type *q; currently points to no dynamic variable. If the value of p is undefined, then p might
point to any random location in memory. As with all variables, when the program begins
The type NodeJype to which a pointer refers can be arbitrary, but in most applications execution, the values of pointer variables are undefined. Before we can use the value
it will be a structure. The words link and reference are also frequently used to designate of a pointer variable p, therefore, we must either assign p = NULL or create a dynamic
pointer types. variable to wh ich it points, as follows.

3. Type Binding 5. Creating and Destroying Dynamic Variables

C sets stringent rules for the use of pointers. Each pointer is bo11nd to the type of The creation and destruction of dynamic variables is done with standard functions in C.
variable Lo which it points, and the same pointer should not be used t.o point (at different If p has been declared as a pointer to type NodeJype, then the statement
times) to variables of different types. Variables of two d ifferent pointer types cannot be
mixed with each other; C will allow assignments between two pointer variablt:~ of th..: p = ( NodeJype *) malloc(sizeofC NodeJype ));
same type, but it will produce a warning when you assign pointers of different types. If
we have declarations creates a new dynamic variable of type NodeJype and assigns its location to the pointer
malloc p. The library function malloc allocates a block of memory and returns a pointer to
char *a, *b;
that block of memory, or it returns NULL if there is not enough remaining memory to
NodeJype *X, * Yi
satisfy the request. The argument to malloc indicates, in bytes, the size of the block of
then the assignments x = y; and a = b; are legal, buL the assignment x = a; is illegal. sizeof memory that is requested. For o ur application, we determine this size by using the unary
 C HAPTER 4 SECT I ON 4.1 Dynamic Memory Allocation and Pointers 105
104 Linked Lists

compile-time operator sizeof, which computes the size in bytes of any object or type.
Hence,
sizeof ( Node_type)
PG,__,,__,,1' Music O
calculates the number of bytes occupied by a variable of Node.type. The placement of
type cast (Node.type *) before the call to malloc is a type cast: The value returned by malloc
is a generic poimer; the type cast forces it to become Node-type.
q Gf------<•~1' Calculus O
If there is insufficient memory to create the new dynamic variable, mal loc will fail
and will return NULL. Your program should always check for a NULL pointer returned by
malloc. ,
~ PG 0
free When a dynamic variable is no longer needed, the function call

free(p);
p

P • o; • p = •q;
·I, Calculus

returns the space used by the dynamic variable to which p points to the system. After
the function free (p) is called, the pointer variable pis undefined, and so cannot be used
q Calculus qG ·I Calculus
D
until it is assigned a new value. 1l1ese actions are illustrated in Figure 4.3. Figure 4.4. Assignment of poi nter variables
Either a call p = malloc (. . . ) or an assignment such asp = q or p = NU LL is required
before p can be used. After a call free(p), the value of pis undefined, so it is wise to poimer operations checked for equali ty, can appear in calls to functions, and the programmer is allowed to do
set p = NULL immediately, to be sure that p is not used with an undefined value. some limited ari thmetic with pointers. Appendix C gives more information on pointers.
assig11me111 In regard to assignment statements, it is important to remember the difference be·
6. Following the Pointers
tween p = q and *P = *q, both of which are legal (provided that p and q are bound to
The star * that appears in the declaration of a C pointer can also be used in a statement the same type), but which have quite different effects. The first statement makes p point
that uses the pointer. For example, the declaration to the same object to which q points, but does not change the value of either that object,
or of the other object that p was pointing to. The latter object will be lost unless there is
char *P; some other pointer variable that still refers to it. The second statement, *P = *q, on the
contrary , copies the val ue of the object *q into the object *P, so that we now have two
is read "p is a pointer to char" and when we use *P in an expression we read "what p
dereferencing points to." Again, the words link and reference are often used in this connection. The objects wi th the same va lue, with p and q pointing to the two separate copies. Finally, the
two' assignment statements p = *q and *P = q have mix_ed types and are illegal (except
action of taking *P is sometimes called "dereferencing the pointer p."
in the case that both p and q point to pointers of their same type!). Figure 4.4 illustrates
7. Restrictions on Pointer Variables these assignments.
The only use of variables of type Item.type * is to find the location of variables of
type Item.type. Thus pointer variables can participate in assignment statements, can be Exercises These exercises are based on the following declarations, where the type Node.type is
4.1 declared as follows.

e---i p = NULL; typedef struct node. tag {

char c;

~----~
·~r- ???
O p = malloc {size of (Node._1ype)I;
struct nodeJag *next;
} NodeJype;
NodeJype *P, *q, *r;
NodeJype x, y, z;
~ - - -- -• ~ p-mombor = 1378; Et. For each of the following s1a1emems, ei ther describe its effect, or state why it is
illegal.

v
Aln
-:: · ~ ·- ??
00 "~'"'
Figure 4.3. Creating a nd disposing of dynamic variables
a. p = (Node.type * ) malloc(sizeof( NodeJype));
b. *q = ( NodeJype *) malloc (sizeof ( Node_type));
c. x = (Node.type * ) malloc(sizeof(Node_type));
d . p = r;
 CHAP T ER 4 S E C TION 4 .2 Linked Stacks and Queues 107
106 Linked Lists
Perhaps an analogy with reading a magazine article will help. If we are in the
e. q = y; j. free(*p) ;
middle of reading an article, then upon reaching the bottom of a page we often find the
= NULL;
f. r k. free(r);
instruction "Continued on page . .. ," and by following such instructions we can continue
g. z = *p; I. *q = NULL;
reading until we reach the end of the article. But how do we find the beginning? We look
h. p = *X; m. *P = *x;
i. free(y); II . z = tlULL; in the table of contents. which we expect to find in a fixed location near the beginning
of the magazine.
swap E2. Write a C function to interchange pointers p and q, so that after the function is For linked lists also we must refer to some fixed location to find the beginning;
performed, p will point ro the node to which q formerly pointed, and vice versa. that is, we shall use a static variable to locate the first node of the list. One method
E3. Write a C function to interchange the values in the dynamic variables to which p static head of doing this is to make the first node in the list a static variable, even though all the
and q point, so that after the function is perfonned * P will have the value formerly remaining nodes are dynamically all ocated. In this way the first node will have a unique
in *q and vice versa. name to which we can refer. Although we shall sometimes use this method, it has the
E4. Write a C function that makes p point to the same node to which q points, and disadvantage that the first node of the list is treated differently from all the others, a fact
disposes of the item to which p formerly pointed. that can sometimes complicate the algorithms.

ES. Write a C function that creates a new variable with p pointing to it, and with contents
the same as those of the node to which q points. 3. Headers
For linked stacks and queues and sometimes for other kinds of linked lists, we shall
employ another method that avoids these problems. The header for a linked list is a
pointer variable that locates the beginning of the list. The header will usually be a static
4.2 LINKED STACKS AND QUEUES variable, and by using its value we can arrive at the first (dynamic) node of the list. The
With these tools of pointers we can now begin to consider the implementation of linked header is also sometimes called the base or the a11chor of the list. These terms are quite
lists into C. Since stacks and queues are among the easiest lists ro process, we begin descriptive of providing a variable that ties down the beginning of the list, but si nce they
with them. are not so widely used, we shall generally employ the term header.
initialization When execution of the program starts we shall wish to initialize the linked list to
4.2.1 Declarations be empty; with a header pointer, this is now easy. The header is a static pointer; so it
exists when the program begins, and to set its value to indicate that its list is empty, we
need only the assignment
1. Nodes and Type Declarations
header= NULL;
Recall from Figure 4.2 that each entry of a linked list will be a structure containing
not only the items of infonnation but also a pointer to the next structure in the list.
Translating this requirement into C declarations yields
4. The End of the List
typedef struct node.tag {
ltem_type info; Finding the end of a linked list is a much easier task than is finding its beginning. Since
struct node.tag * next; each node contains a pointer to the next, the pointer field of the last node of the list has
} NodeJype; nowhere to point, so we give it the special value NULL. In this way we know that we are
at the end of the list if and only if the node we are using has a NULL pointer to the next.
use before Not.e that we have a problem of circularity in this declaration. struct nodeJag * appears Here we have one small advantage of linked lists over a contiguous implementation:
declaration in the declaration of the structure node. This is called a self-refere11tial structure. It There is no need to keep an explicit counter of the number of nodes in the list.
means that the pointer next may point to a structure of the same type as the structure
NodeJype.
4.2.2 Linked Stacks
2. Beginning of the List
Let us now tum to writing functions for processing linked stacks. As with the items of
In our linked list we shall use the pointer next to move from any one node in the contiguous stacks, we shall push and pop nodes from one end of a linked stack, called its
linked list to the next one, and thereby we can work our way through the list, once we top. We now face a small problem of inconsistency with the implementation of stacks in
have started. We must now, however, address a small problem that never arises with the last chapter: The entries of contiguous stacks were declared to have type ltemJype,
contiguous lists or other static variables and arrays: How do we find the beginning of items and nodes whereas the entries of linked stacks will have type Node_type, which we have already
the list?
108 Linked Lists CHAPTER 4 SECTION 4.2 Linked Stacks and Queues 109

declared to consist of an ltemJype together with a pointer. For some applications of Node processing Next let us turn to the processing of nodes in a linked stack. The first question to settle
linked stacks we wish to process nodes, but for other ipplications we wish to be able is to determine whether the beginning or the end of the linked list will be the top of the
t.o process items directly, so that we can substitute a linked implementation of stacks stack. At first glance it may appear that (as for contiguous lists) it might be easier to add
for a contiguous implementation without having to make any changes in the rest of the a node at the end of the list, but this method makes popping the stack difficult: There
program. is no quick wuy to find the node immediately before a given one in u linked list, since
For this reason we introduce two new functions, PushNode and PopNode, which the pointers stored in the list give only one-way directions. Thus, after we remove the
will process nodes in a linked stack. We can then use these functions to write linked last element, to find the new element at the end of the list it might be necessary to trace
versions of the functions Push and Pop, which, as in the last chapter, will process items all the way from the head of the list. To pop our linked stack it is better to make all
directly. If we have an it.em item that. we wish to push onto a linked stack, we must first additions and deletions at the beginning of the list. Each linked list has a header variable
make a new node and put item into the node, and the:1 push the node onto the stack. that points to its first node; for a linked stack we shall call this header variable top, and
Hence we obtain: it will always point to the top of the stack. Since each node of a linked list points to
the next one, the onl y information needed to keep track of a linked stack is the location

item processing
I* Push: make a new node with item and push it onto stack.
void Push ( ltemJype item, StackJype *Stack_ptr)
*' of its top. For consistency with other data structures, we shall put this information in a
simple structure, and hence we obtain the following declaration of a linked stack:
{
Push Node (MakeNode (item), stack_ptr); typedef struct stack.tag {
} NodeJype *lop;
} StackJype;
The function Push uses a function MakeNode that allocates enough space for a new
node and initializes it. This sequence of instructions i s used often, so it i s kept as a Then we can declare the stack and a pointer to it:
function for general use.
StackJype stack;
I* MakeNode: make a new node and insert item. *I StackJype *stack_ptr = &stack;
NodeJype *MakeNode(ltem.type item)
{ and a pointer node_ptr to a structure of the type Node_type
NodeJype *P;
NodeJype *node_ptr;
if ( (p = (NodeJype *) malloc(sizeof(Node_type))) == NULL)
Error ("Exhausted memory.") ;
else { Let us start with an empty stack, which now means
p->info = item;
p->next = NULL; stack_ptr->top = NULL;
}
return p; and add the first node. We shall assume that this node has already been made somewhere
} in dynamic memory, and we shall locate this node by using a pointer node_ptr. Pushing
node. ptr onto the stack consists of the instructions
The connection between the two functions for popping a node or an it.em from the stack
is just as close. stack_ptr->top = node_ptr;
node _ptr->next = NULL;
I* Pop: pop a node from the stack and return its item.
void Pop (ltemJype *item, StackJype *Stack_ptr)
*'
As we continue, let us suppose that we already have the stack and that we wish
{ to push a node node_ptr onto it. The required adjustments of pointers are shown in
NodeJype *node.ptr; Figure 4.5. First, we must set the pointer coming from the new node node_ptr to the old
PopNode( &node_ptr, stack_ptr); top of the stack, and then we must change the top to become the new node. The order
*item = node_ptr->info; of these two assignments is important: If we attempted to do them in the reverse order,
free(node_ptr); the change of top from its previous va lue would mean that we would lose track of the
} old part of the list. We thus obtain the following function.
110 Linked Lists CHAPTER 4 SECTION 4 .2 Linked Stacks and Queues 111

stack_ptr -.. top $l&ck_ptr - top ,,,::.===:::::::;; pop node

I* PopNode: pop node from the linked stack. *'
void PopNode( NodeJype **node_ptr, StackJype *Stack_ptr)
{
Node
if (stack_ptr->top == NULL)
Error ( 11 Empty stack 11 ) ;
Empty stack Stack o f si ze 1 else {
*node_ptr = stack_ptr->top;
stack_ptr->top = ( * node_ptr)->next;
node_ptr
}
L ink marked X has been removed.
}
New Heavy links have been added.
node
In the function PushNode the first parameter is

Node_type *node_ptr
stack_ptr ' t op
Old Old Old
top node se<:ond node bottom node It indicates that node_ptr is a pointer to a variable of type Node_type. In PopNode the
first parameter is
Figure 4.5. Pushing a node onto a linked stack NodeJype **node_ptr

push node
f* PushNode: push node onto the linked stack. *'
void PushNode ( NodeJype * node_ptr, StackJype *Slack _ptr)
It indicates that node_ptr is a pointer to a pointer to a variable of type Node_type. Re-
member that in a call by reference we pass 1he address of the variable. When we need
to make a call by reference and the variable involved is a pointer, we pass the address
{
of the pointer. The parameter to the function is then a pointer to a pointer to a variable.
if (node_ptr == NULL)
Note that the principal instructions for popping the linked stack are exactl y the
Error ("Attempted to push a nonexistent node 11 ) ;
reverse of those for pushing a node onto the stack. In popping the stack, it is necessary
else {
to check the stack for emptiness, but in pushing it, there is no need to check for overflow,
node_ptr->next = stack_ptr->top;
since the function itself does not call for any additional memory. The extra memory for
stack_ptr->top = node_ptr;
the new node is already assigned to the node to which node_ptr points.
}
}

In all our functions it is important to include error checking and to consider extreme
4.2.3 Linked Queues
cases. Hence we consider it an error to attempt to push a nonexistent node onto the In contiguous storage, queues were significantly harder to manipulate than were stacks,
stack. One extreme case for the function is that of an empty stack, which means top == because it was necessary to treat straight-line storage as though it were arranged in a
NULL. Note that in this case the function works just as well to add the first node to an circle, and the extreme cases of full queues and empty queues caused difficulties. It is
empty stack as to add another node to a nonempty stack. for queues that linked storage really comes into its own. Linked queues are just as easy
It is equally simple to pop a node from a linked stack. This process is illustrated in to handle as are linked stacks. We need only keep two pointers, front and rear, that
Figure 4 .6 and is implemented in the following function. will point, respectively, to the beginning and the end of the queue. The operations of
insertion and deletion are both illustrated in Figure 4.7.
rype queue To show the logical connection between the head and tai l pointers of a linked queue,
we shall introduce a structure type:

typedef struct queueJag {

Node_type •front;
node_ptr NodeJype *rear;
} QueueJype;
Figure 4.6. Popping a node from a linked stack
112 Linked Lists C H APT ER 4 SEC T I ON 4 .2 Linked Stacks and Queues 113

I* DeleteNode: delete a node from the front of the queue. *I

delete node void DeleteNode(NodeJype **node_ptr, QueueJype *queue_ptr)
{
if (queue.ptr->front == NULL)
fron t Error ( 11 Empty queue" );
else {
*node_ptr = queue_ptr->front;
queue_ptr->front = (*node_ptr)->next;
Added to if (queue _ptr->front == NULL)
rear of queue_ptr->rear = NULL;
queue
}
}
Again the possibility of an empty queue must be cons idered separately. It is an error
to attempt deletion from an empty queue. It is, however, not an error for the queue to
rear
become empty after a deletion, but then the rear and front should both become NULL to
Figure 4.7. Operations on a linked queue
indicate clearly that the queue is empty.
simplicity If you compare these algorithms for linked queues with those for contiguous queues,
A queue should be initialized to be empty with the function: you will see that the linked versions are both conceptua lly easier and easier to program.
i111ple111e111arions The functions we have developed process nodes; to enable us to change easily be-
f* Initialize: initialize the queue to be empty. * f tween contiguous and linked implementations of queues, we also need versions of func·
initialize void Initialize ( Queue_type * queue_ptr) tions AddQueue and DeleteOueue that wi ll process items directly for linked queues. We
{ l eave writing these functions as exercises.
queue_ptr->front = queue_ptr->rear = NULL;
} Exercises El. When deletmg an item from a linked stack or queue, we checked for emptiness, but
4.2 when adding an item, we did not check for overflow. Why?
To add a node to the rear of a queue, we then write E2. Write a C function to initialize a linked stack to be empty.

insert node
f* AddNode: add a node to the rear of the queue.
void AddNode(Node_type *node_ptr, QueueJype * queue_ptr)
*' E3. For cont iguous stacks and queues we wrote Boolean-valued functions Empty and
Full along with the various functions. Write analogous functions in C for (a) linked
stacks and (b) linked queues.
{
if (node _ptr == NULL) E4. By allocating and freeing new nodes, write functions (a) AddQueue and (b) Delete·
Queue that will process items directly for linked queues and that can be substituted
Error ( 11 Attempted to push a nonexistent node");
else if (queue_ptr->front == NULL) { directly for their contiguous counterparts.
queue_ptr->front = node_ptr; A circularly linked list, illustrated in Figure 4.8, is a linked list in which the node at
queue_ptr->rear = node_ptr; circularly linked lis1 the tail of the list, instead of having a NULL pointer, points back to the node at the head
} else { of the list. We then need only one pointer tail to access both ends of the list, since we
queue_ptr->rear->next = node _ptr; know that tail->next points back to the head of the list.
queue_ptr->rear = node_ptr;
}
}
tail
Note that this function includes error checking to prevent the insertion of a nonexistent .__..
node into the queue. The cases when the queue is empty or not must be treated separately,
since the addition of a node t.o an empty queue requires setting both the front and the
rear to the new node, while addition to a nonempty queue requires changing only the ( J
rear.
To remove a node from the front of a queue, we use the following function: Figure 4.8. A ci rcul arly linked list with tail pointer
114 Linked Lists CH AP TER 4 SECT I ON 4 .3 Further Operations on Linked Lists 115

ES. If we implement a queue as a circularly linked list then we need only one pointer
rear (or tail) to locate both the front and the rear. Write C functions to process a <' <'
queue stored in this way:
a. Initialize.
(a)
[ fl]Stacks
·I are
rrJ ·I lists.
Sh
b. AddNode.

ru 1~,}~" , ., . '1
c. DeleteNode.
J
r
<' <'
<'
deque E6. Recall (Section 3.5, Exercise 3) that a deque is a list in which additions or deletions
can be made at either the head or the tai1, but not elsewhere in the list.. With a
deq ue stored as a circularly linked list, three of the four algori thms to add a node to
(b)

I Stacks
·I are
f.[J lists.

either end of the deque and to delete a node from either end become easy to write,
but the fourth does not.
a. Which of the four operations is difficult? Why?
4i,tt,
(c) Stacks are
b. Write a C function to initialize a circularly linked deque 10 be empty. structures. simple

c. Write C functions for the three easy operations on a linked deque. -.

d. Write a C function for the fourth operation.
but important data

4.3 FURTHER OPERATIONS ON LINKED LISTS

For stacks and queues all the operations are performed at one of the ends of the list, but (d) Stacks are structures. simple
for more general linked lists, changes, insertions, or deletions may be made at any point..
In fact, all the operations listed in Section 3.5 apply equally well to linked lists as to
contiguous lists.
but important data
?

4.3.1 Algorithms for Simply Linked Lists

Figure 4.9. Actions on a linked list
To illustrate the kind of actions we can perform with linked lists, let us consider for
a moment the problem of editing text, and suppose that each node holds one word as of an empty list (for which the loop will not iterate at all), the correct form could be a
well as the link to the next node. The sentence "Stacks are lists" appears as in (a) of for loop. Tennination occurs when p points off the end of the list, whereupon we have
Figure 4.9. Tf we insert the word "simple" we obtain the list in (b). Next we decide to p = NULL. The funct ion then becomes
replace "lists" by "structures" and insert the three nodes " but important data" to obtain
(c). Afterward, we decide to delete "simple but" and so arrive at list (d). Finally, we I* Traverse: traverse the list visiting one node at a time. * I
traverse the list to prim its contents. linked traversal void Traverse (Node.type *head, void ( *Visit) (Node.type *))
{
1. List Traversal Node.type *P;

As a first example let us write a function to perform list. traversal, whic.h means to move
for (p =head; p; p = p->next)
( >1<Visit) (p);
through the list, visiting each node in tum. What we mean by visiting each node depends }
entirely on the application; it might mean printing out some information, or doing some
task that depends on the data in the node. Thus we leave the task unspecified and, as in Notice the close analogy between traversal of a linked list and traversal of a contiguous
Section 3.5, use a call to a function named Visit. To traverse the list, we shall need a list. If head and tail are indices marking the start and finish of a contiguous list inside
local pointer p that will start at the first node on the list and move from node to node. an array list of items, then traversal of the contiguous list is performed by the following
We need a loop to accomplish this movement, and since we wish to allow the possibility function:
116 linked lists CHAPTER 4 S ECTION 4 .3 Further Op erations on linked lists 117

I* Traverse: traverse the list visiting one node at a time. *I T he action of this function is illustrated in Figure 4.11.
comi11uous traversal void Tra verse ( int head, int tail, Node_type list [],
void ( *Visit) ( NodeJype *))
{
int p;
for ( p = head; p <= tail; p++)
( *Visit) ( &list [p));
}
Q ~ next
Comparing these versions of traversal, we see that the initialization is the same, the p -next
general structure is the same, and the instruction p = p->next replaces p + + as the way
p
to advance one node through the list. Figure 4.10 illustrates this process.

p ~ next q

Figure 4.11. Insertion after a node

p • p ~ next

p 3. Insertion Before a Node

Figure 4.10. Advancing one node
- Suppose now that p points to some node in the list, and we wish to insert a new node
The function Visit normally performs the necessary actions when we visit a node. before the node that p points to. We now have a difficulty, since the link that must be
As an example, we display the contents of the node. changed is the one coming into p, and there is no way to fi nd this link directly from p
and q, since we have no way to move backward through the list.
I* Visit: visit node p: print its information. *I
void Visit(NodeJype *P) One way we could use to find the link entering pis to start at the head of the list and
{ tracing the lisr traverse it to the desired point. but this is usually not a good method, si nce its running
pri nt! ( "p- >info: %c\n" , p- >info); time is proportional to the length of the list up to p, a length that we do not know in
} advance and that might be prohibitively large.
A second method, the details of which are left as an exercise, is to use a small
swap fields trick. Fi rst, insert the node q after p instead of before p. Then, by copying appropriate
2. Insertion After a Node information fields between the structures, swap the information in p and q so that the
Next let. us consider the problem of inserting a new node into an arbitrary position in information in q comes before that in p. This method, whi le it often runs faster than the
our list. If p is a pointer to some node in the list, and we wish to insert the new node first one, may become very slow if the infonnation fields are large and will be dangerous
after the node that p points to, then the method used for inserting a new node at the rear if not fatal if there are other variables elsewhere in the program that point to either of
of a queue works with little change: the two nodes that were swapped.
Hence we shall consider yet a third method to solve the problem of inserting q before
I* lnsertNode: insert node q after node p. * I p, a method requiring slightly more bookkeeping, but one that moves only pointers, never
void lnsertNode (NodeJype *P, Node_type *q) the information in the nodes, and whose running time does not depend on the length of
{ the list. What we do is to propose keepi ng a second pointer variable throughou t all our
if (p == NULL II q == NULL) rwo pointers processing of the list. This second pointer r wi ll move in lock step with p, with r always
Error ("At least one of nodes p and q is nonexistent ") ; kept exactly one node closer to the head of the list than p. Inserting the new node q
else { before p is now easy, since it is only inserting q after r, and then updating r by setting
q- >next = p->next; r = q . Inserting the new node before the first node of the list (in which case the trailing
p->next = q; pointer r is undefined) is now a special case, but an easy one, similar to adding a node
} to a linked stack. This process is illustrated in Figure 4.12, which leads to the following
} function.
 SEC TION 4 .3 Further Operations on Linked Lists 11 9
118 Linked Lists CHAPTER 4

node p that is not the first one, however, then to adjust the links, we must locate the link
comi ng into p. In a simply linked list with only one poi nter, this task is difficult, but
with a second pointer r o ne step behi nd p, it is easy. After includ ing appropriate e rror
checki ng, we obtain the following funct ion:

rwo-poimer dele1ion
I* Delete: delete node p from the list; r is in front of p.
void De lete ( Node.type *r, Node.type * P)
*'
{
if (r == NULL II p == NULL)
Error ( 11 At least one of nodes r and p is nonexistent 11 ) ;

q
else if (r->next ! = p)
Error( 11 Nodes rand p not in sequence") ;
else
r->next = p->next;
p
}
Figure 4.12. Insertion into a linked list with two pointers
This function as written keeps no pointer to the node bei ng deleted, bu t does not d ispose
of it either. Instead, the function assumes that the deleted node is to be used by the
f* lnsertBetween: insert q between the nodes r and p.
void lnsertBetween ( Node.type *q, Node_type * * head,
*' calling program and the ca ll ing program will keep some pointer o ther than p with which
insertion hetween to find the deleted node.
pointers Node.type **r, Node.type *P)
{ 6. Other Implementations
if (p == * head ) {
q- >next ~ p; Many variations are possible in the implementation of linked lists, some of which prov ide
*r = * head = q; advantages in certain situations. In addi tion to the one-pointer and two-poi nter simply
} else {
I* q is at the head of the list.
*' circularly linked lis1
linked lists, we might, for example, consider circularly linked lists in which the last node,
rather than containing a NULL link, has a link to the first node of the list (see Figure 4.8
q- >next = p;
( *r) ->next = q; and Exercise E6 of Section 4.2).
*r = q;
I* q is after rand before p.
*' doubly linked list Another form of data structure is a doubly linked list (like the one shown in
Figure 4. 13) in which each node contains two links, one to the next node in the list and
}
} one to the preceding node. It is thus possible to move either direction through the list
wh ile keeping only one pointer. With a doubly linked list, traversals in either di rection,
insert.ions, and deletions from arbitrary positions in the list can be programmed without
4. The Two-Pointer Implementation d ifficulty. The cost of a doubly linked list, of course, is the extra space requi red in each
In writing the function j ust finished we have introduced a subtle change in the structure node for a second li nk.
of o ur linked list, a change that reall y amounts to a ne w imple mentation of the list, Yet one more variation in implementation is to include a dummy node at the be-
new implememation o ne that requires keepi ng pointers to two adjacent nodes of the list at all times. In this dummy node ginning (or, less commonly, at the end) of a linked list. This d ummy node contains no
impleme ntation, some operations (like insertion) become easier, but others may become information and is used only to provide a link to the first true node of the list. It is never
harder. In list tra versa!, for e xample, we must be more careful to get the process s t.art.ed
correctly. When p poi nts to the head of the list, the n r is necessarily undefined. Thus the
first step of traversal m ust be considered separately. T he de tails are left as an exercise.
Similarl y, insertion of a new node before the curre nt head of the list is a special case, -
but an easy one already considered in s tudying linked stacks.
/ /
- -
5. Deletion - - -_,.._
Deletion of a node from a linked list is another o peration in which the implementation .L
makes a significant difference. From our study of linked s tacks and queues, we know
Figure 4.13. Doubly linked list with header
that it is never difficult to delete the first node on a linked list. If we wish to delete a
120 Linked Lists C HAPTER 4 S E CT I O N 4 .3 Further Operations on Linked Lists 121

deleted and, if desired, can even he a static variable (that is, one declared as the program need 10 be made in the middle of a list, and when random access is important. Linked
is written). Use of a dummy node al. the head of the list simplifies the form of some storage proves superior when the structures are large and flexibility is needed in inserting,
functions. Since the list is never empty, the special case of an empty list does not need deleting, and rearranging the nodes.
to be considered, and neither does the special case of inserting or deleting at the head of
the list. 4.3.3 Programming Hints
Some of the exercises at the end of this section request functions for manipulat-
ing doubly linked lists. We shall study linked lists with dummy header nodes in the To close this section we include several suggestions for programming with linked lists,
application in the next section. as well as some pitfalls to avoid.

poimers and pitfalls I. Draw "before" and "after" diagrams of the appropriate part of the linked list, showing
4.3.2 Comparison of Implementations the relevant pointers and the way in which they should be changed.
2. To determine in what order values should be placed in the pointer fields to implement
Now that we have seen several algorithms for manipulating linked lists and several the various changes, it is usuall y better first to assign the values to previously
variations in their implementation, let us pause to assess some relative advantages of undefined pointers. then to those with value NULL, and finally to the remaining
linked and of contiguous implementation of lists. pointers. After one pointer variable has been copied lo another, the first is free to
advantages The foremost advantage of dynamic storage for linked lists is flexibility. Overflow be reassigned to its new location.
is no problem until the computer memory is actually exhausted. Especially when the
undefined links 3. Be sure that no links are left undefi ned at the conclusion of your algorithm, either
overflow individual structures are quite large, it may be difficult to determine the amount of
as links in new nodes that have never been assigned, or links in old nodes that have
contiguous static storage that might be needed for the required arrays, while keeping
become dangling, that is, that point lo nodes that no longer are used. Such links
enough free for other needs. With dynamic allocation, there is no need to attempt to
should either be reassigned to nodes still in use or set to the value NULL.
make such decisions in advance.
changes Changes, especially insertions and deletions, can be made in the middle of a linked exrreme cases 4. Always verify that your algorithm works correctly for an empty list and for a list
list more easily than in the middle of a contiguous list. Even queues are easier to handle with only one node.
in linked storage. If the structures are large, then it is much quicker to change the values mulriple 5. Try 10 avoid constructions such as p->next->next, even though they are syntac-
of a few pointers than to copy the structures themselves from one location to another. dereferencing tically correct. A single variable should involve only a single pointer reference.
disadvantages The first drawback of linked lists is that the links themselves take space, space that Constructions with repeated references usually indicate that the algorithm can be
might otherwise be needed for additional data. In most systems, a pointer requires the improved by rethinking what pointer variables should be declared in the algorithm,
same amount of storage (one word) as does an integer. Thus a list of integers will require introducing new ones if necessary, so that no variable includes more than one pointer
double the space in linked storage that it would require in contiguous storage. On the reference (->).
other hand, in many practical applications the nodes in the list are quite large, with data alias variable 6. It is possi ble that two (or more) different pointer variables can point 10 the same
fields taking hundreds of words altogether. If each node contains I 00 words of data, node. Since this node can thereby be accessed under two different names, it is called
space me then using linked storage will increase the memory requirement by only one percent, an an alias variable. The node can be changed using one name and later used with the
insignificant amount. In fact, if extra space is allocated to arrays holding contiguous lists other name, perhaps wi thout the realization that it has been changed. One pointer
to allow for additional insertions, then linked storage will probably require less space can be changed to another node, and the second left dangling. Alias variables are
altogether. If each item takes I 00 words, then contiguous storage will save space only therefore dangerous and should be avoided as much as possible. Be sure you clearly
if all the arrays can be filled to more than 99 percent of capacity. understand whenever you must have two pointers that refer lo the same node, and
random access T he major drawback of Jinked lists is that they are not suited to random access. remember that changing one reference requires changing the other.
With contiguotis storage, the program can refer to any position within a list as quickly
as to any other posit.ion. With a linked list, it may be necessary to traverse a long path
to reach the desired node.
Finally, access to a node in linked storage may take slightly more computer time, Exercises El. Write a C function that counts the number of nodes in a linked list.
since it is necessary, first, to obtain the poimer and then go lo the address. This con- 4.3 E2. Draw a before-and-after diagram describing the main action of the Delete function
sideration, however, is usually of no importance. Similarly, you may find at lirsl that presented in the text.
programming writing functions t.o manipulate linked lists lakes a bit more programming effo1t, but,
with practice, this discrepancy will decrease. E3. Write a function that will concatenate two linked lists. The function should have
two parameters, pointers 10 the beginning of the lists, and the function should link
In summary, therefore, we can conclude that contiguous storage is generally prefer-
able when the structures are individually very small, when few insertions or deletions the end of the first list to the beginning of the second.
122 Linked Lists CHAPTER 4 SECTION 4 . 4 Application: Polynomial Arithmetic 123

E4. Write a function that will split a list in two. The function will use two pointers as E l4. Write functions for manipulating a doubly linked list as follows:
parameters; p will point to the beginning of the list, and q to the node at which it a. Add a node after p.
shou ld be spl it, so that all nodes before q are in the first list and all nodes after q
b. Add a node before p.
are in the second list. You may decide whether the node q itself will go into the
first list or the second. State a reason for your decision. c. Delete node p.
d . Traverse the list.
ES. Write a function that will insert a node before the node p of a linked list by the
following method . First, insert the new node after p, then copy the infom1ation EIS. A doubly linked list can be made circular by selling the values of links in the first
fields that p points to the new node, and then put the new information fields into and last nodes appropriately. Discuss the advantages and disadvantages of a c ircular
what p points to. Do you need to make a special case when p is the first node of doubly linked list in doing the various list operations.
the list?
El6. Make a chart that will compare the difficulties of doing various operations on dif-
E6. Write a function to delete the node p from a linked list when you are g iven only ferent implementations of lists. The rows should correspond to all the operations
the pointer p without a second pointer in lock s tep. on lists specified in Section 3.5.3 and the columns to (a) contiguous lists, (b) sim-
a. Use the dev ice of copying infonnation fields from one node to another in ply linked lists, and (c ) doubly linked lists. Fill in the entries to show the relative
designing your algorithm. difficulty of each operation for each implementation. Take into account both pro-
b. Will your function work when p is the first or the last node in the list? If gramming difficulty and expected running time.
not, either describe the changes needed or state why it cannot be done w ithout
providing additional information to your function.
c. Suppose that you are also given a pointer head to the first node of the list.
Write a deletion algorithm that does not copy information fields from node to
node.
4.4 APPLICATION: POLYNOMIAL ARITHMETIC
E7. Modify the function to traverse a linked list so that it will keep two pointers p and
r in lock step, with r always moving one node behir:d p (that is, r is one node closer
to the head of the list). Explain how your function gets started and how it handles 4.4.1 Purpose of the Project
the special cases of an empty list and a list with only one node. As an app lication of linked lists, this section outl ines a program for manipulating poly-
E8. Write a function that will reverse a linked list while traversing it only once. At the nomials. Our program will imitate the behavior of a simple calculator that does add ition,
conc lusion, each node should point to the node th at was previously its predecessor; calculator f or subtraction, multiplication, division, and perhaps some other operat ions, but one that
the head should point to the node that was formerly at the end, and the node that polynomials perfonns these operations for polynomials.
was formerly first should have a NULL link. There are many kinds of calculators avai lable, and we could model our program
after any of them. To provide a further illustration of the use of stacks, however,
E9. Write an algorithm that will sp lit a linked list into two linked lists, so that successive
let us choose to model what is often called a reverse Polish calculator. In such a
nodes go to differeru lists. (The first, third, and all odd-numbered nodes go to the
reverse Polish calculator, the operands (numbers usually, polynomials for us) are entered before the
first list, and the second, fourth, and a ll even-numbered nodes go t.o the second.)
calculations operation is specified. The operands are pushed onto a stack. When an operation
The following exercises concern circularly linked lists. Sec Exerc ise 6 of Section 4.2. is performed, it pops its operands from the stack and pushes its result back onto the
For each of these exercises, assume that the circularly linked list is specified by a pointer stack. If? denotes pushing an operand onto the stack, + , - , * , I represent arith-
rear to its last node, and e nsure that on concl usion your algorithm leaves the appropriate metic operations, and = means printing the top of the stack (but not popping it off),
pointer(s) pointing to the rear of the appropriate list(s). then? ? + = means reading two operands, then calculating and printing their sum.
ElO. Write a function to traverse a circularly linked list, visiting each node. First, do The instruction ? ? + ? ? + * = requests four operands. If these are a, b, c, d, then
the case where only a single pointer moves through the list, and then describe the the result printed is (a + b) * (c + d). S imilarly,? ? ? - = * ? + = pushes a, b, c
changes necessary to traverse the list with two pointers moving in lock step, one onto the stack, replaces b, c by b - c and prints its value, calculates a* (b - c), pushes
immediately behind the other. d on the stack., anti fiually calcu lates anti µriuts (a• ( b - c)) + d. The atlvantage of
a reverse Polish calculator is that any expression, no matter how complicated, can be
Ell. Write a function to delete a node from a circu larl y linked list. spec i tied without the use of parentheses.
El2. Write a function that will concatenate two circularly linked lists, producing a circu- This Polish notation is useful for compilers as well as for calculators. For the
larly linked list. present, however, a few minutes' practice with a reverse Polish calculator wi ll make you
E13. Write a function that will split a circularly linked li,1 into two circularly linked lists. quite comfortable with its use.
124 Linked Lists CHAPTER 4 SECTION 4.4 Application: Polynomial Arithmetic 125

4.4.2 The Main Program subtraction case ' - ':

Pop ( &p, sp) ;
f* Subtract two polynomials and push answer. *'
Pop ( &q, sp);
1. Outline
The task of the calculator program is quite simple in princ iple. It need only accept
Subtract(p, q, sp);
break; *'
new commands and perform them as long as desired. In preliminary oulline, the main
program takes the form
11111/tiplicarion case ' •':
Pop( &p, sp) ;
I* Multiply two polynomials and push answer.
*'
Pop ( &q, sp);
I* Preliminary outline: program for manupulating polynomials * I
first outline void main (void)
{
Multiply(p, q, sp);
break;
'* p * q
*'
Initialize ( stack) ;
while (there are more commands) {
division case ' !':
Pop( &p, sp);
I* Divide two polynomials and push answer.
*'
Pop( &q, sp);
GetCommand ( cmd) ;
DoCommand (cmd);
I* command to execute
*' Divide ( p, q, sp);
break;
'*q/p
*'
} }
} }
2. Performing Commands
We use three include files that contain the typedefs we need to build and evaluate the
To tum this outline into a C program, we must specify what. it means to obtain com- polynomials.
mands and how this will be done. Before doing so, Jet us make the decision to represent
the commands by the characters ? , ; , + , - , *, /. Given this decision, we can im- poly.h:
mediately write the function QoCommand in C, thereby speci fying exactly what each
stack operations command does: type polynomit,I typedef struct polynomial.tag {
double coef;
#include "poly.h"
int exp;
#include "node.h"
struct polynomial.tag * next;
#include "stack.h"
} Polynomial.type;
#include "calls.h "
I* DoCommand: do command cmd for polynomials. *; node.h:
void DoCommand (char cmd, Stack.type * Sp)
{ typedef struct polynomial.tag * Item.type;
Item.type item;
Polynomial.type *P, *q; type node typedef struct node. tag {
Item.type info;
switch(cmd ) { struct node.tag * next;
input case ' ?' : I* Read polynomial and push it onto stack.
Push(ReadPolynomial( ), sp); *' } Node.type;

break; stack.h:
output case ' ;': I* Write polynomial on the top of the stack. *I
TopStack( &item, sp); type stack typedef struct stack.tag {
Write Polynomial ( item) ; Node.type *lop;
break; } Stack.type;
addition case ' +' : f* Add top two polynomials and push answer. *f
Pop( &p, sp); 3. Reading Commands: The Main Program
Pop( &q, sp);
_Add(p,q,sp); f* p + g *I Now that we have decided th at the commands are to be denoted as single characters,
break; we could easily program function GetCommand to read one command at a time from
126 Linked Lists CHAPTER 4 SE CTION 4 . 4 Application: Polynomial Arithmetic 127

the tenninal. It is often convenient, however, to read a string of several commands at

once, such as ? ? + ? ? + * = , and then perform them all before reading more. To read commands
I* ReadCommand: read a command line and save it in command.
int Read Command ( char command [ J )
*'
allow for this possibility, let us read a whole line of commands at once and set up an {
array 10 hold them. With this decision we can now write the main program in its final int c, n;
form , except for the additional declarations that we shall insert after choosing our data
do {

*'*'
structures. We shall use a function ReadCommand to read the string of commands; this f* Read a valid command line.
function will also be responsible for error checking. n = O; I* number of characters read
Prompt ();
while ( (c = getchar( )) r = '\n')
#define MAXCOMMAND 10 if (strchr( 11 ,\t 11 , c) != NULL)

main program
I* Implement calculator for polynomials. *f
void main ( void) error checking
I* empty * I ; f* Skip white-space characters.
else if (strchr ( 11 ?+ - */= 11 , c) == NULL) *'
{
inti, n; else
break; I* non-command character
*'
Stack.type stack; command [ n++ J = c;
if (c == '!' )
char command [MAXCOMMAN[B ;
i11s1r11ctio11s Help();
Initialize C&stack) ;
do {
Geteol(c);
} while Cc!= ' \n') ;
I* Skip characters until new line.
*'
n = ReadCommand (command);
for Ci = O; i < n; i++)
DoCommand(command [i), &stack); }
command [n) = ' \O ';
return n;
I* Add end of string marker.
*'
} while (Enquire ( ) ) ;
}
The next function is a utility that skips all characters until the end of a line.

4. Input Functions I* Geteol: get characters until the end of the line. * I
void Geteol(int c)
Before we turn to our principal task (deciding how to represent polynomials and writing {
functions to manipulate them), let us complete the preliminaries by giving derails for the while Cc!= '\n')
input functions. The prompting function need only write one line, but note that this line c = getchar();
gives the user the opportunity r.o request further instruclions if desired. }

I* Prompt: prompt the user for command line. *I The following functi on provides help to the user when requested.
prompting user void Prompt(void)
{
int c; I* Help: provide instructions for the user. * I
instructions void Help ( void)
printf( 11 Enter a string of commands or ! for help.\n 11 ) ; {
while CCc = getchar()) == '\n') printf ("Enter a string of commands in reverse Polish form .\n 11 ) ;

}
f* empty * ! ;
ungetc Cc, stdin) ;
I* Discard leftover newlines, if any.
*' print! ( "The valid instructions are:\n 11 ) ;
printf("? Read a polynomial onto stack\n 11 ) ;
printf ( 11 + Add top two polynomials on stack \n 11 ) ;
printf(" - Subtract top two polynomials on stack\n 11 ) ;
Function ReadCommand must check that the symbols typed in represent legitimate printf( 11 • Multiply top two polynomials on stack\n");
operations and must provide instructions if desired, along with doing its main task. If print! (" I Divide top two polynomials on stack\n 11 ) ;
there is an error or the user requests instructions, then the command string must be printf ( 11 = Print polynomial on top of the stack\n 11 ) ;
re-entered from the start. }
128 Linked Lists CHAPTER 4 SECTION 4 . 4 Application: Polynomial Arithmetic 129

5. Stubs and Testing pairs will constitute a structure, so a polynomial will be represented as a list of structures.
We must then build into our functions ru les for perfonning arithmetic on two such lists.
At this point we have written quite enough of our program that we should pause to implementation of a Should we use contiguous or Iinked Iists? If, in advance, we know a bound on
compile it, debug it, and test it to make sure that what has been done so far is correct. polynomial the degree of the polynomials that can occur and if the polynomials that occur have
If we were 10 wail umil all remaining functions had been writlen, the program would nonzero coefficients in almost all the ir possible terms, then we should probably do better
become so long and complicated that debugging would be much more difficult. with contiguous lists. But if we do not know a bound on the degree, or if polynomials
For the task of compiling the program, we must, of course, supply stubs for all the with only a few nonzero tenns are li kely to appear, then we shall find linked storage
missing functions. At present, however, we have not even completed the type decla- preferable. To illustrate the use of linked lists, we adopt the latter implementation, as
rations: the most important one. that of a Polynomial, remains unspecified. We could illustrated in Figure 4.14.
temporary type make this type declaration almost arbitrarily and still be able to compile the program,
declarario11 but for testing, it is much better to make the temporary type declaration

.f ~ ·f a ~
typedef double Polynomial.type ; 1.0 5.0

and test the program by running it as an ordinary reverse Polish calculator. The following
G I
4
G 0
I

is then typical of the stubs that are needed:

x• 5 0

double Add (PolynomiaUype x, PolynomiaUype y)

{
stub
}
return x + y;
G
3.0
5
I
§.[ §J §.[ Q
- 2.0
3
I
1.0
2
I
4.0
0
I

In addition to stubs of the functions for doing arithmetic and the function Erase (which
stack package need do nothing), we need a package of functions to manipulate the stack. If you wish, 3x 5 - 2x 3 + x 2 + 4
you may use the package for linked stacks developed in chis chapter, but with the items in Figure 4.14. Polynomials as linked lists
the stack only real numbers, it is probably easier to use the contiguous stack algorithms
developed in Section 3.2. The functions Initialize and TopStack do not. appear there, but
assumptions We shall consider that each node represents one tenn of a polynomial, and we
are trivial to write. With these tools we can fully debug and test the part of the program
shall keep only nonzero terms in the list. The polynomial that is identically O will be
now wri tten, after which we can turn to the remainder of the project.
represented by an empty list. Hence each node will be a structure containing a nonzero
coefficient, an exponent, and, as usual for linked lists, a pointer to the next term of the
polynomial. To refer to polynomials, we shall always use header variables for the lists;
4.4.3 Data Structures and Their Implementation hence, it is sensible to make pointers of type Polyno miaUype and use it for the headers.
Moreover, the remaining tenns after any given one are again a (smaller) polynomial,
If we carefully consider a polynomial such as so the fie ld next again naturally has type PolynomiaUype. Refer to the include files in
Section 4.4.2.
We have not yet indicated the order of storing the tenns of the polynomial. If we
3x5 - 2x3 + x' + 4 all ow them to be stored in any order, then it might be difficult to recognize that

we see that the impo1tant information about the polynomial is contained in the coefficients x 5 + x2 - 3 and - 3 + x 5 + x 2 and x 2 - 3 + x5
essence of a and ex ponents of x; the variable x itself is really just a place holder (a dummy variable).
polynomial Hence, for purposes of calculation, we may think of a polynomial as a sum of t.enns,
restriction all represent the same polynomial. Hence we adopt the usual convention that the terms
each of which consists of a coefficient and an exponent. In a computer we can similarly
of every polynomial are stored in the order of decreasing exponent within the linked list,
implement a polynomial as a list of pairs of coefficients and exponents. Each of these
130 Linked Lists CHAPTER 4 SECTIO N 4.4 Application: Polynomial Arithmetic 131

and we further assume thal. no two terms have the same exponent and that no term has
reading
I* ReadPolynomial: read a polynomial and return its pointer.
PolynomiaUype *ReadPolynomial(void)
*'
a zero coefficient.
{
double coef;
4.4.4 Reading and Writing Polynomials int exp, lastexp;
PolynomiaUype *result, *!ail;
With polynomials implemented as linked lists, writing out a polynomial becomes simply
a traversal of the list, as follows. instmctions printf (" Enter coefficients and exponents for the polynomial. \n"

writing
I* WritePolynomial: write a polynomial to standard output.
void WritePolynomial(PolynomiaUype *P)
*' "Exponents must be in descending order.\n"
"Enter coefficient or exponent O to terminate. \n");
initialize lastexp =INT.MAX;
{
if ( !p)
print! ("zero polynomial\n");
I* Polynomial is an empty list.
*' read one term
tail= result= Make Term (0.0, 0); I* dummy head
while(1) { *'
print! ("coefficient? ") ;
else while (p) {
scant ( " %11 ", &coef) ;
print! ( "%5.21fx~% 1d", p->coef, p->exp);
if ( coef == 0.0)
p = p->next;
break;
if (p)
printf ("exponent? " );
print! ( "+" ) ;
scant( "%d" , &exp);
else
print!( "\n"); error checking if (exp>= lastexp II exp< 0) {
} printf("Bad exponent. Polynomial is terminated"
} "without its last term.\n");
break;
As we read in a new polynomial, we shall be constructing a new linked list, adding }
a node to the list for each term (coefficient-exponent pair) that we read. The process make one term tail= lnsertTerm(coef, exp, tail);
of creating a new node, attaching it to the tail of a !isl, pulling in the coefficient and if (exp== O)
exponent, and updating the tail pointer to point to the new term will reappear in almost break;
every function for manipulating polynomials. We therefore writ.e it as a separate utility. lastexp = exp;
}

making one term

I* lnsertTerm: insert a new term at the end of polynomial. *I
PolynomiaUype *lnsertTerm (double coef, int exp, Pol ynomiaUype *!ail)
{
conclude tail->next = NULL;
tail = result;
I*
f*
Terminate the polynomial.
Prepare to dispose of the head. *'*'
if ((tail->next = Make Term (coef, exp)) == NULL)
Error ("Cannot allocate polynomial term" );
resu lt = resu lt->next;
tree (tail) ;
f*
f*
Advance to first term.
Free dummy head. *'*'
return result;
return tail->next; }
}

We can now use this function t.o insert new terms as we read coefficient-exponent pairs. 4.4.5 Addition of Polynomials
lnsertTerm, however, expects to insert the new tern, after the term to which tail currently
points, so how do we make the first term of the list? One way is to write a separate The requirement that the tenns of a polynomial appear with descending exponents in the
dummy first node section of code. It is easier, however, to use a dummy header, as follows. Before starting list simplifies their addi tion. To add two polynomials we need only scan through them
to read, we make a new node at the head of lhe list, and we put dummy information once each. If we find tem,s with 1he same exponent in the two polynomials, then we
into it. We then insert all the actual terms, each one inserted after the preceding one. add the coefficients; otherwise, we copy the tern, of larger exponent into the sum and
\Vhen the function concludes the head pointer is advanced one position to the first actual go on. When we reach the end of one of 1he polynomials, then any remaining part of
term, and the dummy node is freed. This process is illustrated in Figure 4. 15 and is the other is copied to the sum. We must also be careful not to include tenns with zero
implemented in the following function: coefficient in the sum.
132 Linked Lists C HAPT ER 4 SECT I ON 4 . 4 Application: Polynomial Arithmetic 133

I* Add: add two polynomials and push the answer onto stack. *f 2
void Add(PolynomiaUype *P, Polynomial.type *q, Stack.type *SP)
{
double sum;
Preliminary
G ·[,;
head
tail
1 0
Polynomial.type *ptmp = p;

initialize
PolynomiaUype *qtmp = q;
PolynomiaUype *result, *tail;
tail = result= MakeTerm (0.0, 0);
while(p&&:q)
Term 1
G
head ·F 001n"'ll
1:0 ·F 1.0

tai l J
5 (0 x•

equal-exponent if (p->exp == q->exp) { f* Add coefficients. *I

terms if ((sum= p->coef + q->coef) ! = 0.0) / 2
tail = lnsertTerm (sum, p->exp, tail);
p = p->next;
Term 2
G ·I
head
~0111~¥
1:0 ·I/ 1.0
5 1:0 ·F -3.0
2
1 0 x 5 - 3x2

q = q->next; tail J
} else if (p->exp > q->exp) { I* Copy p to result.

.r ,:g. r
1Jnequal exponents *I
tail = lnsertTerm (p->coef, p->exp, tail); / 2

1:0 · I 1:0 ·[ 10
1.0 - 3.0
p = p->next; Term 3
G oo~n>>'
5 2
7.0
0
x5 - 3x 2 + 7
} else { I* Copy q to result.
tail= lnsertTerm (q->coef, q->exp, tail); *' head
tailJ
q = q->next;
}
remaining terms f* One or both of the summands has been exhausted. * f
I* At most one of the following loops will be executed.
for (; p; p = p->next)
*' Final
~
head
Lr 1.0
5 1:0 ·F
- 3.0
2 1:0 ·F 7.0
0 I~··-,,,.,
tail= lnsertTerm (p->coef, p->exp, tail);
for (; q; q = q->next) Figure 4.15. Construction of a linked lisl with dummy node
tail = lnsertTerm (q->coef, q->exp, tail);
conclude tail->next = NULL;
Push(result->next, sp);
I* Terminate polynomial.
*' 2. Group Project
Production of a coherenl package of algorithms for manipulating polynomials makes
free ( resu It) ;
Erase(ptmp);
Erase Cqtmp) ;
I* Free dummy head.
I* Erase summand. **'' an interesting group project. Different members of the group can write functions for
different operations. Some of these are indicated as projects at the end of thi s section,
but you may wish to include additional features as well. Any additional features should
}
be planned carefully to be sure that they can be implemented in a reasonable time,
without disrupting other parts of the program.
After deciding on the division of work among its members, the most important
4.4.6 Completing the Project
specifications decisions of the group relate to the exact ways in which the functions should communicate
with each other, and especially with the calling program. If you wish to make any
1_ The Missing Functions changes in the organization of the program, be certain that the precise details are spelled
At this point the remaining functions for the calculator project are sufficiently similar to out clearly and completely for all members of the group.
those already wriuen that they can be left as exercises. The function Erase need only Next, you will find that it is too much to hope that all members of the group will
traverse the list (as done in WrltePolynomlal) disposing of the nodes as it goes. Functions complete their work at 1he same time, or th ai all pans of che projec1 can be combined
for the remaining arithmetical operations have the same general form as our function for cooperation and debugged together. You will therefore need to use program stubs and drivers (see
addition. Some of these are easy: Subtraction is almost identical with addition. For Sections I .4.1 and 1.4.4) to debug and tesl the various parts of the project. One member
multiplication we can first write (a simple) function that multiplies a polynomial by a of the group might take special responsibility for these. In any case, you w ill find it very
monomial, where monomial means a polynomial with only one term. Then we combine effective for different members to read , help debug, and test each other's subprograms.
use of this function with the addition function to do a general multiplication. Division coordination Finally, there are the responsibilities of making sure that all members of the group
is a little more complicated. complete their work on time, of keeping track of the progress of various aspects of the
134 Linked Lists CHAPTER 4 SECTIO N 4 .5 Linked Lists in Arrays 135

project, of making sure that no subprograms are integrated into the project before they are 4.5 LINKED LISTS IN ARRAYS
thoroughly debugged and tested, and of combining all the work into the finished product.
Several of the o lder but widely-used computer languages, such as FORTRAN, COBOL, and
old languages BASIC, do not provide faci lities for dynamic sto rage allocation or pointers. Even when
Exercises El. Decide whether the stack for the calculator should be contiguous or linked. Justify
implemented in these languages. however. there are many problems where the methods
4.4 yvur t.lct:biv11. Incorporate the necessary functions to implement the stack in the
of linked lists are preferable to those of contiguous lists, where, for example, the ease
way you decide.
of c hang ing a pointer rather than copyi ng a large structure proves advantageous. This
E2. If polynomials are stored as circularly linked lists instead of si mply li nked lists, then
section shows how to implement linked lists using only simple integer variables and
a polynomial can be erased more quickly. What changes are needed to the addition
arrays.
function (and other subprograms) to implement circularly linked lists?
The idea is to begin with a large array (or several arrays to hold different parts of
E3. Consider generalizing the project of this section to polynomials in several variables. a structure) and regard the array as ou r allocation of unused space. We then set up our
own functions to keep track of which parts of the array are unused and to link entries of
Programming Pl. Write function Erase. the array toge1her in the desired order.
Projects P2. Write function Subtract. The one feature of linked lists that we must invariably lose in this implementation
4.4 P3. Write a function that will multiply a polynomial by a monomial (that is, by a dynamic memory method is the dynamic allocation of storage, since we must decide in advance how
polynomial consisting of a single term). much space to allocate to each array. All the remaining advantages of linked lists, such
as flexibility in rearranging large structures or ease in making insertions or deletions
P4. Use the function of the preceding problem, together with the function that adds
anywhere in the list. will st ill apply, and linked lists still prove a valuable method.
polynomials, to write the function Multiply.
The implementation of linked lists within arrays even proves valuable in languages
PS. Write function Divide.
like C that do provide pointer types and dynamic memory allocation. The applications
P6. The function ReadCommand, as writ.ten, will accept any sequence of commands, advantages where arrays may prove preferable are those whe re the number of items in a list is
but some sequences are illegal. If the stack begins empty, for example, then the known in advance, where the links are frequently rearranged , but relatively few add i-
sequence + ? ? is illegal, because it is impossible to add two polynomials before tions or deletions are made, or applications where the same data are sometimes best
reading them in. Modify function ReadCommand as follows so that it will accept treated as a linked list and other times as a contiguous list. An example of such an
only legal sequences of commands. The function should set up a counter and application is illustrated in Figure 4.16, wh ich shows a small pan of a student record
initialize it to the number of polynomials on the stack. Whenever the command? system. Identification numbers a re assigned to students first-come, first-served, so nei-
appears in the stream the counter is increased by one (since the read command ? ther the names nor the marks in any panicular course are in any special order. Given an
will push an additional polynomial onto the stack), and whenever one of+ , - , *, I
appears, it is decreased by one (since these commands will pop two polynomials '
and push one onto the stack). If the counter ever becomes zero or negative then the
sequence is iI legal. name next name math nextmath cs nextCS

P7. Many reverse Poli.s h calculators use not only a stack but also provide memory lo- 0 Clark, F. ,,.
cations where operands can be stored. Extend the project to provide for memory Smith. A. ,,.
locations for polynomials, and provide additional commands to store the top of the
stack into a memory location and to push the polynomial in a memory locati on onto
2 - ~

3 Garcia. T.
the stack.
PS. Write a function that will discard the top polynomial on the stack, and include th is 4 Ha l, W. ~

capability as a new command. 5 Evans. B. ,

P9. Write a function that will interchange the top two polynomials on the stack, and 6 - ,
include this capability as a new command. 7 - ~

PIO. Write a function that will add all the polynomials on the stack together, nod include 8 Arthur, t . ~

this capability as a new command. -

9
Pll. Write a function that will compute the derivative of a polynomial, and include this
capability as a new command.
Pl2. Write a function that, given a polynomial and a real number, evaluates the polyno-
mial at that number, and include this capability as a new command. Figure 4.16. Linked lists in arrays
136 Linked Lists CHAPTER 4 SECTION 4 . 5 Linked Lists in Arrays 137

info next
identification number, a student's records may be found immediately by using the iden-

multiple linkages
tification number as an index to look in the arrays. Sometimes, however, it is desired to
print out the student records alphabetically by name, and this can be done by following
0 Clark, F.

Sm ith, A.
-
_,,
the links stored in the array nextname. Similarly, student records can be ordered by
marks in any course by following the links in the appropriate array.
2 - -
In the implementation of linked lists in arrays, pointers become indices relative to 3 Garcia, T.
-
cursors the start of arrays, and the links of a list are stored in an array, each entry of which
gives the index where, within the array, the next entry of the list is stored. To distinguish
4

5
Hall, W.

Evans, 8 .
--
these indices from the pointers of a linked list in dynamic storage, we shall refer to links
within arrays as cursors and reserve the word pointer for links in dynamic storage.
For the sake of writing programs we shall use two arrays for each linked list, info [ ]
6

7
-
-
--
to hold the information in the nodes and next [ ] to give the cursor to the next node.
These arrays will be indexed from O 10 MAX - 1, where MAX is a symbolic constant.
8
9
Arth ur, E.

-
-
Since we begin the indices with 0, we can use the cursor value - 1 to indicate the end
of the list, just as the pointer value NULL is used in dynamic storage. This choice is also
illustrated in Figure 4.16.
10

11
- --
You should take a moment to trace through Figure 4.16, checking that the cursor
12
-
values as shown correspond to the arrows shown from each entry to its successor. 13
-
To obtain the flavor of implementing linked lists in arrays, let us rewrite several of
the algorithms of this chapter with th is implementation.
14
-
Our first task is to set up a list of available space and write functions to obtain a
new node and to return a node to available space. We shall set up a stack to keep track
malloc and tree of available space, but now this stack wi ll be linked by means of cursors in the array firstna,ne avail last node

next. To keep track of the stack "of available space, we need an integer variable avail that Figure 4.17. The available-space list
wi ll give the index of its top. If this stack is empty (which will be represented by avail=
- I) then we will need to obtain a new node, that is, a position withi n the array that has I* Initialize: initialize head and indices avail and lastnode. • I
not yet been used for any node. Thus we shall keep another integer variable lastnode initialization void Initialize ( int •head, int •avail, int •lastnode)
that will count the tota l number of positions within our array that have been used to hold {
list entries. When lastnode exceeds MAX-1 (the bound we have assumed for array size) •head = - 1; I* The list is empty.
*'
then we will have overflow and the program can proceed no further. When the main
program starts, both variables avail and lastnode should be initialized 10 - I, avail to
}
•avail = - 1;
•lastnode = - 1;
I* Stack of available nodes is empty.
I* None of the positions has been used. **''
indicate that the stack of space previously used but now available is empty, and lastnode
to indicate that no space from the array has yet been assigned. This available-space list
The following function NewNode allocates a new node from available space:
is illustrated in Figure 4.17. This figure, by the way, also illustrates how two linked lists
can coex ist in the same array. I* NewNode: select the index of first available position. * I
The decisions we have made translate into the follow ing declarations: allocate int NewNode (int •avail, int • lastnode, int next [ J )
{
int avail, lastnode; int n = -1;
int next [MAX] ; if ( •avail ! = - 1) {
We put MAX in an include file and call the file list.h: n = *avail;
*avail = next [ * avail] ;
#define MAX 5 } else if ( •lastnode < MAX) {
(*lastnode)++;
We take this small value for testing the program. In a typical application, MAX would be n = •lastnode;
as large as avai lable memory permits. With these declarations we can now rewrite the } else Error( "No available position left ");
functions for keeping track of unused space. At the start of the program, the lists should return n;
be initialized by invoking the follow ing: }
138 Linked Lists C HAP TE R 4 SECTIO N 4 .5 Linked Lists in Arrays 139

The purpose of the next function, called FreeNode, is to return a node that in no longer
needed to the list of avai lable space. This function now takes the form:
(a) (c) {d) (e)

I* FreeNode: return node at position n to available space. * I

Ji'ee void FreeNode (int *head, int *avail, int next[], int n)
{
inti; 5 5
6 6
if (n <= - 1)
Error(" Invalid node to return to available space"); 7 7
else { 8 8 8
if (*head== n) 9 9
*head = next [ *head] ; 10 10
else
11 11
for (i = *head; i < MAX; i++ ) { headl
if ( next [i] == n) { headl@ head l @ head2
next [i] = next [n] ;
break; head2@ head2 @ head3
}
} E2. Construct next tables showing how each of the following lists is linked into alpha-
next [n] = *avail; be1ical order. Also give the value of the variable head that startS the list.
*avail= n;
}
} {a} 1 array (cl 1 the (d) 1 London
2 stack 2 or 2 England
3 queue 3 and 3 Rome
4 list 4 to 4 Italy
The translation of other functions so as to manipulate linked lists implemented within 5 deqve 5 a 5 Madrid
arrays proceeds in much the same way as the functions already developed, and most of 6 scroll 6 in 6 Spain
these functions will be left as exercises. To provide further models, however, let us write 7 that 7 Oslo
a translation of the function to traverse a list. {b} 1 l)USh 8 is 8 Non,vay
2 pop 9 9 Paris
3 add 10 it 10 France
4 delete 11 for 1 t Warsaw
I* Traverse: traverse a linked list starting at head with links in the table next [ J . * I
5 inse,t 12 as 12 Poland
traverse void Traverse (int head, int next [ J, void ( *Visit) (int))
{ E3. For the list of cities and countries in part (d) of the previous question construct a
inti; next table 1ha1 produces lwo linked lisls, one conlaining all the cilies in alphabetical
order and the other all the countries in alphabetical order. Also give values to the
for (i = head; i ! = - 1; i = next [i] ) two header variables.
(*Visit) (i); E4. Write a function that counts the number of nodes in a linked list implemented in an
} array.
ES. Write a function that will concatenate two I.inked lists implemented in one next
The function Visit has the same purpose and is similar in form to the function Visit table. The function should have two parameters, cursors to the beginning of the
developed in Section 4.3. 1. lists, and the function should link the end of the first list to the begiru1ing of the
second.
E6. Write a function that will split a list in two. The function will use two parameters;
n will point to the node at which it should be split and next contains the indices. Is
Exercises El. Draw arrows showing how the list entries are linked together in each of the following it easier to require that n in itially point to the node that will be last in the first list
4.5 next tables. Some tables contai n more than one list. after spliuing or to the node that will be first in the second list?
140 Linked Lists C H APTE R 4 SECTION 4.6 Abstract Data Types and Their Implementations 141

E7. Write a function that will reverse a linked list within an array wh ile traversing it only implemenlation The way in which an underlying structure is implemented can have substantial effects
once. At the conclusion, each node s hould point to the node that was previously its on program development, and on the capabilities and usefulness of the result. Sometimes
predecessor; the header s hould point to the node that was formerly at the end, and these effects can be subtle. The underlying mathematical concept of a real number, for
the node that was formerly first s hould have a - 1 cursor. example. is usu2lly (but not always) implemented by computer as a floating-point number
with a ceitain degree of piecis iuu, aml tile iu1Jc1cu1 li111i1a1iu11~ i11 Lhb implt:mematiun
often produce difficulties with round-off error. Drawing a clear separation between the
logical structure of our data and its implementation in computer memory will help us
4.6 ABSTRACT DATA TYPES AND THEIR IMPLEMENTATIONS in designing programs. Our first step is to recogni7.e the logical connections among the
data and embody these connections in a log ical data s tructure. Later we can consider
our data structures and decide what is the best way to imp lement them for efficiency of
programming ar.d execution. By separating these decisions they both become easier, and
4.6.1 Introduction we avoid pitfalls that attend premature commitment.
Suppose that in deciphering a long and poorly documented program you found the To help us clarify this distinction and achieve greater generality let us now reconsider
following sets of instructions: some of the data structures we have s tudied from as general a perspective as we can.

xxt->xlnk = w; w->xlnk = NULL; xxt = w; 4.6.2 General Definitions

reading programs and 1. Mathematical Concepts
if ( (xxh == xxt + 1 && xxt >= 0) II (xxt == mxx && xxh == 0)) Mathematics is the quintessence of generalization and therefore provides the language
tryagain ( ) ; we need for our defi nitions. The place to start is the definition of a type:
else {
xxt + +; D EFINITION A type is a set. and the elements of the set are called the values of the type.
if (xxt > mxx)
xxt = O;
xx [xxt] = wi; We may therefore speak of the type int, meaning the set of all integers, the type double,
} meaning the se: of all real numbers, or I.he type char, meaning 1J1e set of symbols
(characters) that we wish to manipulate in our algorithms.
In isolation it may not be clear what either of these sections of code is intended to do, Notice that we can already draw a distinction between an abstract type and its
and without further explanation, it would probably lake a few minutes to realize that in implementation: 1l1e C type int, for example, is not the set of all integers; it consists
fact they have essentially the same function! Both segments are intended to add an item only of the set of those integers directly represented in a particular computer, the largest
to the end of a queue, the first queue in a linked implementation and the second queue of which is INT.MAX (see the system file lim its.h for your C compi ler).
in contiguous storage. Similarly, the C type double generally means a certain set of floating-point numbers
Researchers working in different subjects frequently have ideas that are fundamen- (separate mantissa and exponent) that is on ly a small subset of the set of all real numbers.
tally similar but are developed for different purposes and expressed in different language. The C type char also varies from computer to computer; sometimes ii is the ASCII
Often years will pass before anyone realizes the si milarity of the work, but when the character set; sometimes it is the EBCDIC character set; sometimes it is some other set
analogies observation is made, insight from one subject can help with the other. In computer sci- of symbols. Even so, all 1hese types, both abstract types and implementations, are sets
ence, even so, the same basic idea often appears in quite different disguises that obscure and hence fit the definition of a type.
the similarity. But if we can discover and emphasize the similarities, then we may be
able to generalize the ideas and obtain easier ways to meet the requirements of many
;2. Atomic and Structured Types
applications. Types such as int, double, and char are called atomic types because we think of their
When we first introduced stacks and queues in Chapter 3, we considered them only values as single entities only, not something we wish to subdivide. Computer languages
as they are implemented in contiguous storage, and yet upon introduction of linked stacks like C, however, provide tools such as arrays, structures, and pointers with which we can
similarity and queues in this chapter, we had no difficulty in recognizing the same underlying logical build new types, called structured types. A single value of a structured type (that is, a
s tructure. The obscurity of the code at the beginning of this section reflects the program- single element of its set) is an array or file or linked list. A value of a structured type
mer's failure to recogn ize the general concept of a queue and to distinguish between this has two ingredients: It is made up of compo11e11t elements, and there is a structure, a
general concept and the particular implementation needed for each application. set of rules for putting the components together.
142 Linked Lists C HAPTER 4 S E CT I ON 4 6 Abstract Data Types and Their Implementati ons 143

For our general point of view we shall use mathematical tools to provide the rules Dl:'rlNITIOI\' A stack of elements of type 1' is a finite sequence of elements of T together with
uz,iidf::;; types for building up structured types. Among these tools are sets, sequences, and functions.
the operations
For the study of lists the one that we need is the finite sequence, and for its definition
we use mathematical induction. A definition by induction (like a proof by induction) I. Initialize the stack to be empty.
has two parts: First is an initial case, and second is the defin ition of the general case in
2. Determine if the stack is empty or not.
terms of preceding cases.
3. Determine if the stack is full or not.
4. If the stack is not full, then insert a new node at one end of the stack.' called .-~~
DEFINITION A sequence of kngth O is empty. A sequence of length n 2:: I of elements from '·

its top.
a set Tis an ordered pair (Sn-1> t) where Sn-I is a sequence of length n - I of
elements from T, and t is an element of T. 5. If the