PREFACE
Problem Solving and Program Design in C teaches a disciplined approach to problem
solving, applying widely accepted software engineering methods to design
program solutions as cohesive, readable, reusable modules. We present as an
implementation vehicle for these modules a subset of ANSI C—a standardized,
industrial-strength programming language known for its power and portability. This
text can be used for a first course in programming methods: It assumes no prior
knowledge of computers or programming. The text’s broad selection of case studies
and exercises allows an instructor to design an introductory programming course in
C for computer science majors or for students from a wide range of other disciplines.
New to this Edition
Several changes to this edition are listed below:
• Chapters 3 (Functions), 5 (Loops), and 7 (Arrays) include optional sections on
graphics programming
• Chapter 6 (Pointers and Modular Programming) includes a new section 6.1
on pointers
• New complete programs show use of if statements in Chapter 4
• New complete program shows use of switch statement in Chapter 4
• Chapter 7 (Simple Data Types) in previous edition is eliminated and its
contents integrated into other chapters of the book
• Hardware examples in Chapter 1 are updated to reflect current technology
• Several chapters contain new programming project homework problems
More About Graphics Many Computer Science faculty have recommended the
use of graphics to help motivate the study of introductory programming and as a
vehicle to help students understand how to use libraries and to call functions. We
agree with this viewpoint and have included three optional sections with graphics
examples in this edition. The new graphics sections include:
Section 3.6 : Introduction to Computer Graphics
Section 5.11 : Loops in Graphics Programs
Section 7.10 : Graphics Programs with Arrays
To reduce the overhead required to introduce graphics, we decided to use
WinBGIm (Windows BGI with mouse), which is a package based on the Turbo
Pascal BGI (Borland Graphics Interface) library. WinBGIm was created to run
on top of the Win32 library by Michael Main and his students at the University of
Colorado. Several development platforms appropriate for CS 1 courses have incorporated
WinBGIm. Quincy (developed by Al Stevens) is an open-source studentoriented
C++ IDE that includes WinBGIm as well as more advanced libraries
( http://www.codecutter.net/tools/quincy ). Figure 1 shows the Quincy new project
window (File → New → Project) with WinBGIm Graphics application selected.
A command-line platform based on the open-source GNU g++ compiler and
the emacs program editor is distributed by the University of Colorado ( http://www.
codecutter.net/tools/winbgim ). WinBGIm is also available for Bloodshed Software’s
Dev-C++ and Microsoft’s Visual Studio C++.
Using C to Teach Program Development
Two of our goals—teaching program design and teaching C—may be seen by some
as contradictory. C is widely perceived as a language to be tackled only after one has
learned the fundamentals of programming in some other, friendlier language. The
perception that C is excessively difficult is traceable to the history of the language.
Designed as a vehicle for programming the UNIX operating system, C found its
original clientele among programmers who understood the complexities of the operating
system and the underlying machine and who considered it natural to exploit
this knowledge in their programs. Therefore, it is not surprising that many textbooks
whose primary goal is to teach C expose the student to program examples requiring
an understanding of machine concepts that are not in the syllabus of a standard
introductory programming course.
In this text, we are able to teach both a rational approach to program development
and an introduction to ANSI C because we have chosen the first goal as
our primary one. One might fear that this choice would lead to a watered-down
treatment of ANSI C. On the contrary, we find that the blended presentation of
programming concepts and of the implementation of these concepts in C captures
a focused picture of the power of ANSI C as a high-level programming language,
a picture that is often blurred in texts whose foremost objective is the coverage of
all of ANSI C. Even following this approach of giving program design precedence
over discussion of C language features, we have arrived at coverage of the essential
constructs of C that is quite comprehensive.
Pointers and the Organization of the Book
The order in which C language topics are presented is dictated by our view of the
needs of the beginning programmer rather than by the structure of the C programming
language. The reader may be surprised to discover that there is no chapter entitled
“Pointers.” This missing chapter title follows from our treatment of C as a high-level
language, not from an absence of awareness of the critical role of pointers in C.
Whereas other high-level languages have separate language constructs for output
parameters and arrays, C openly folds these concepts into its notion of a pointer,
drastically increasing the complexity of learning the language. We simplify the
learning process by discussing pointers from these separate perspectives where such
topics normally arise when teaching other programming languages, thus, allowing
a student to absorb the intricacies of pointer usage a little at a time. Our approach
makes possible the presentation of fundamental concepts using traditional highlevel
language terminology—output parameter, array, array subscript, string—and
makes it easier for students without prior assembly language background to master
the many facets of pointer usage.
Therefore, this text has not one but four chapters that focus on pointers.
Chapter 6 (Pointers and Modular Programming) begins with a discussion of pointers,
indirect reference, and the use of pointers to files (moved from Chapter 2 ). It
then discusses the use of pointers as simple output and input/output parameters,
Chapter 7 deals with arrays, Chapter 8 presents strings and arrays of pointers.
Chapter 11 discusses file pointers again. Chapter 13 describes dynamic memory
allocation after reviewing pointer uses previously covered.
Software Engineering Concepts
The book presents many aspects of software engineering. Some are explicitly discussed
and others are taught only by example. The connection between good problem-solving
skills and effective software development is established early in Chapter 1 with a section
that discusses the art and science of problem solving. The five-phase software
development method presented in Chapter 1 is used to solve the first case study and is
applied uniformly to case studies throughout the text. Major program style issues are
highlighted in special displays, and the coding style used in examples is based on guidelines
followed in segments of the C software industry. There are sections in several
chapters that discuss algorithm tracing, program debugging, and testing.
Chapter 3 introduces procedural abstraction through selected C library functions,
parameterless void functions, and functions that take input parameters and
return a value. Chapters 4 and 5 include additional function examples including the
use of a function as a parameter and Chapter 6 completes the study of functions
that have simple parameters. The chapter discusses the use of pointers to represent
output and input/output parameters.
Case studies and sample programs in Chapters 6 , 7 , and 10 introduce by example
the concepts of data abstraction and encapsulation of a data type and operators.
Chapter 12 presents C’s facilities for formalizing procedural and data abstraction
in personal libraries defined by separate header and implementation files. Chapter
14 (on the textbook website) introduces essential concepts of multiprocessing, such
as parent and child processes, interprocess communication, mutual exclusion locking,
and dead lock avoidance. Chapter 15 (on the textbook website) describes how
object-oriented design is implemented by C++.
The use of visible function interfaces is emphasized throughout the text. We do
not mention the possibility of using a global variable until Chapter 12 , and then we
carefully describe both the dangers and the value of global variable usage.
Pedagogical Features
We employ the following pedagogical features to enhance the usefulness of this
book as a learning tool:
End-of-Section Exercises Most sections end with a number of Self-Check
Exercises. These include exercises that require analysis of program fragments as
well as short programming exercises. Answers to selected Self-Check Exercises
appear online at www.aw.com/cssupport in the directory for “Hanly”.
Examples and Case Studies The book contains a wide variety of programming
examples. Whenever possible, examples contain complete programs or functions
rather than incomplete program fragments. Each chapter contains one or more
substantial case studies that are solved following the software development method.
Numerous case studies give the student glimpses of important applications of
computing, including database searching, business applications such as billing and
sales analysis, word processing, and environmental applications such as radiation
level monitoring and water conservation.
Syntax Display Boxes The syntax displays describe the syntax and semantics of
new C features and provide examples.
Program Style Displays The program style displays discuss major issues of good
programming style.
Error Discussions and Chapter Review Each chapter concludes with a
section that discusses common programming errors. The Chapter Review includes
a table of new C constructs.
End-of-Chapter Exercises Quick-Check Exercises with answers follow each
Chapter Review. There are also review exercises available in each chapter.
End-of-Chapter Projects Each chapter ends with Programming Projects giving
students an opportunity to practice what they learned in the chapter.
Appendices
Reference tables of ANSI C constructs appear on the inside covers of the book.
Because this text covers only a subset of ANSI C, the appendices play a vital role
in increasing the value of the book as a reference. Throughout the book, array
referencing is done with subscript notation; Appendix A is the only coverage
of pointer arithmetic. Appendix B is an alphabetized table of ANSI C standard
libraries. The table in Appendix C shows the precedence and associativity of all
ANSI C operators; the operators not previously defined are explained in this
appendix. Appendix D presents character set tables, and Appendix E lists all ANSI
C reserved words.
Supplements
The following supplemental materials are available to all readers of this book at
www.pearsonhighered.com/irc :
• Source code
• Known errata
• Answers to odd-numbered Self-Check exercises.
The following instructor supplement is available only to qualified instructors
at the Pearson Instructor Resource Center. Visit www.pearsonhighered.com/irc or
contact your local Pearson sales representative to gain access to the IRC.
• Solutions Manual
CONTENTS
0. Computer Science as a Career Path 1
Section 1 Why Computer Science May be the Right Field for You 2
Section 2 The College Experience: Computer Disciplines
and Majors to Choose From 4
Section 3 Career Opportunities 9
1. Overview of Computers and Programming 13
1.1 Electronic Computers Then and Now 14
1.2 Computer Hardware 17
1.3 Computer Software 25
1.4 The Software Development Method 33
1.5 Applying the Software Development Method 36
Case Study: Converting Miles to Kilometers 36
1.6 Professional Ethics for Computer Programmers 39
Chapter Review 41
2. Overview of C 45
2.1 C Language Elements 46
2.2 Variable Declarations and Data Types 53
2.3 Executable Statements 59
2.4 General Form of a C Program 69
2.5 Arithmetic Expressions 72
Case Study: Supermarket Coin Processor 82
2.6 Formatting Numbers in Program Output 87
2.7 Interactive Mode, Batch Mode, and Data Files 90
2.8 Common Programming Errors 93
Chapter Review 99
3. Top-Down Design with Functions 107
3.1 Building Programs from Existing Information 108
Case Study: Finding the Area and Circumference of a Circle 109
Case Study: Computing the Weight of a Batch of Flat Washers 112
3.2 Library Functions 117
3.3 Top-Down Design and Structure Charts 124
Case Study: Drawing Simple Diagrams 124
3.4 Functions without Arguments 126
3.5 Functions with Input Arguments 136
3.6 Introduction to Computer Graphics (Optional) 146
3.7 Common Programming Errors 163
Chapter Review 164
4. Selection Structures: if and switch Statements 173
4.1 Control Structures 174
4.2 Conditions 175
4.3 The if Statement 185
4.4 if Statements with Compound Statements 191
4.5 Decision Steps in Algorithms 194
Case Study: Water Bill Problem 195
4.6 More Problem Solving 204
Case Study: Water Bill with Conservation Requirements 205
4.7 Nested if Statements and Multiple-Alternative Decisions 207
4.8 The switch Statement 217
4.9 Common Programming Errors 223
Chapter Review 224
5. Repetition and Loop Statements 235
5.1 Repetition in Programs 236
5.2 Counting Loops and the while Statement 238
5.3 Computing a Sum or a Product in a Loop 242
5.4 The for Statement 247
5.5 Conditional Loops 256
5.6 Loop Design 261
5.7 Nested Loops 268
5.8 The do-while Statement and Flag-Controlled Loops 273
5.9 Iterative Approximations 276
Case Study: Bisection Method for Finding Roots 278
5.10 How to Debug and Test Programs 287
5.11 Loops in Graphics Programs (Optional) 289
5.12 Common Programming Errors 296
Chapter Review 299
6. Pointers and Modular Programming 315
6.1 Pointers and the Indirection Operator 316
6.2 Functions with Output Parameters 320
6.3 Multiple Calls to a Function with Input/Output Parameters 328
6.4 Scope of Names 334
6.5 Formal Output Parameters as Actual Arguments 336
6.6 Problem Solving Illustrated 340
Case Study: Collecting Area For Solar-Heated House 340
Case Study: Arithmetic with Common Fractions 347
6.7 Debugging and Testing a Program System 356
6.8 Common Programming Errors 359
Chapter Review 359
7. Arrays 375
7.1 Declaring and Referencing Arrays 376
7.2 Array Subscripts 379
7.3 Using for Loops for Sequential Access 381
7.4 Using Array Elements as Function Arguments 386
7.5 Array Arguments 388
7.6 Searching and Sorting an Array 401
7.7 Parallel Arrays and Enumerated Types 406
7.8 Multidimensional Arrays 414
7.9 Array Processing Illustrated 419
Case Study: Summary of Hospital Revenue 419
7.10 Graphics Programs with Arrays (Optional) 428
7.11 Common Programming Errors 437
Chapter Review 438
8. Strings 453
8.1 String Basics 454
8.2 String Library Functions: Assignment and Substrings 460
8.3 Longer Strings: Concatenation and Whole-Line Input 469
8.4 String Comparison 474
8.5 Arrays of Pointers 477
8.6 Character Operations 483
8.7 String-to-Number and Number-to-String Conversions 488
8.8 String Processing Illustrated 495
Case Study: Text Editor 495
8.9 Common Programming Errors 504
Chapter Review 506
9. Recursion 517
9.1 The Nature of Recursion 518
9.2 Tracing a Recursive Function 524
9.3 Recursive Mathematical Functions 532
9.4 Recursive Functions with Array and String Parameters 538
Case Study: Finding Capital Letters in a String 538
Case Study: Recursive Selection Sort 541
9.5 Problem Solving with Recursion 545
Case Study: Operations on Sets 545
9.6 A Classic Case Study in Recursion: Towers of Hanoi 553
9.7 Common Programming Errors 558
Chapter Review 560
10. Structure and Union Types 567
10.1 User-Defined Structure Types 568
10.2 Structure Type Data as Input and Output Parameters 574
10.3 Functions Whose Result Values Are Structured 580
10.4 Problem Solving with Structure Types 583
Case Study: A User-Defined Type for Complex Numbers 584
10.5 Parallel Arrays and Arrays of Structures 592
Case Study: Universal Measurement Conversion 594
10.6 Union Types (Optional) 603
10.7 Common Programming Errors 610
Chapter Review 610
11. Text and Binary File Processing 623
11.1 Input/Output Files: Review and Further Study 624
11.2 Binary Files 634
11.3 Searching a Database 640
Case Study: Database Inquiry 641
11.4 Common Programming Errors 650
Chapter Review 651
12. Programming in the Large 659
12.1 Using Abstraction to Manage Complexity 660
12.2 Personal Libraries: Header Files 663
12.3 Personal Libraries: Implementation Files 668
12.4 Storage Classes 671
12.5 Modifying Functions for Inclusion in a Library 675
12.6 Conditional Compilation 678
12.7 Arguments to Function main 682
12.8 Defining Macros with Parameters 685
12.9 Common Programming Errors 690
Chapter Review 691
13. Dynamic Data Structures 699
13.1 Pointers 700
13.2 Dynamic Memory Allocation 704
13.3 Linked Lists 710
13.4 Linked List Operators 716
13.5 Representing a Stack with a Linked List 721
13.6 Representing a Queue with a Linked List 725
13.7 Ordered Lists 731
Case Study: Maintaining an Ordered List of Integers 732
13.8 Binary Trees 743
13.9 Common Programming Errors 753
Chapter Review 754
14. Multiprocessing Using Processes and Threads (Online at www.pearsonhighered.com/irc)
14.1 Multitasking
14.2 Processes
14.3 Interprocess Communications and Pipes
14.4 Threads
14.5 Threads Illustrated
Case Study: The Producer/Consumer Model
14.6 Common Programming Errors
Chapter Review
15. On to C++(Online at www.pearsonhighered.com/irc )
15.1 C++ Control Structures, Input/Output, and Functions
15.2 C++ Support for Object-Oriented Programming Chapter Review
Appendices
A More about Pointers A-1
B ANSI C Standard Libraries B-1
C C Operators C-1
D Character Sets D-1
E ANSI C Reserved Words E-1
Answers to Odd-Numbered Self-Check Exercises (Online at www.pearsonhighered.com/irc )
Glossary G-1
Index I-1
