The Art and Science of C:A Library-Based Introduction to Computer SciencePDF电子书下载

1 lntduction 1

1.1 A brief history of computing 2

1.2 What is computer science 4

1.3 A brief tour of computer hardware 6

The CPU 7

Memory 7

Secondary storage 8

l/O devices 8

1.4 Algorithms 9

1.5 Programming languages and compilation 10

1.6 Programming errors and debugging 12

1.7 Software maintenance 13

1.8 The importance of software engineering 14

1.9 Some thoughts on the C programming language 15

Summary 16

REVIEW QUESTIONS 17

PART ONE The Basics of C Programming 19

2 Learning by Example 21

2.1 The ”Hello world” program 22

Comments 22

library inclusions 23

The main program 24

2.2 A program to add two numbers 26

The input phase 28

The computation phase 30

The output phase 30

2.3 Perspectives on the programming process 32

2.4 Data types 33

Floating-point data 34

String data 34

2.5 Expressions 37

Constants 38

Variables 39

Assignment statements 41

Operatorsand operands 43

Combining integers and floating-point numbers 44

Integer division and the remainder operator 45

Precedence 45

Applying precedence rules 48

ype conversion 48

Summa 51

REVIEW QUESTIONS 52

PROGRAMMING EXERCISES 55

3 Problem Solving 59

3.1 Programming idioms and paradigms 60

Shorthand assignment idioms 61

Increment and decrement operators 62

3.2 Solving problems on a larger scale 63

3.3 Control statements 65

The repeat-N-times idiom 65

Iteration and loops 67

Indexvariables 67

The importance of initialization 69

The read-until-sentinelidiom 69

Building a more practical application 71

Conditionalexecution and the if statement 74

3.4 An exercise in debugging 76

3.5 Formatted output 80

Format codes for printf 82

Controlling spacing alignmentand precision 83

3.6 Craing a program 86

Programming style 86

Designing for change 88

The #define mechanism 89

Summa 89

REVIEW QUESTIONS 91

PROGRAMMING EXERCISES 93

4 Statement Forms 99

4.1 Simple statements 100

Embedded assignments 102

Multiple assignments 102

Blocks 103

4.2 Control statements 104

4.3 Boolean data 105

Relational operators 106

Logical operators 107

Short-circuitevaluation 109

Flags 110

Avoiding redundancy in Booleanexpressions 110

An example of Boolean calculation 111

4.4 The if statement 112

Singleline if statements 114

Multiline if statements 114

The if-else statement 114

Cascading if statements 115

The ?: operator 115

4.5 The switch statement 117

4.6 The while statement 119

Using the while loop 120

Infinite loops 122

Solving the loop-and-half problem 123

4.7 The for statement 125

Nested for loops 126

The relationship between forand while 129

Using for with floating-point data 129

Summary 131

REVIEW QUESTIONS 132

PROGRAMMING EXERCISES 133

5 Functions 137

5.1 Using libra functions 138

5.2 Function declarations 140

5.3 Writing your own functions 141

The return statement 142 Pu 143

ing functions together with mainprograms 143

Functions involving internal control structures 145

Functions that return nonnumeric values 146

Predicate functions 148

A predicate function to test for string equality 149

5.4 Mechanics of the function-calling process 150

Parameter passing 151

Calling functions from withinother functions 156

5.5 Procedures 163

5.6 Stepwise refinement 165

Starting at the top 166

Implementing Printcalendar 167

Implementing PrintCalendarmonth 167

Completing the finalpieces 171

Summa 176

REVIEW QUESTIONS 177

PROGRAMMING EXERCISES 178

6 Algorithms 185

6.1 Testing for primality 186

A simple version of IsPrime 187

Verifying that a strategy representsan algorithm 187

Demonstrating the correctness of the IsPrimealgorithm 188

Improving algorithmic efficiency 189

Choosingbetween alternative implementations 192

6.2 Computing the greatest common divisor 193

Brute-force algorithms 194

Euclids algorithm 195

Defending thecorrectness of Euclids algorithm 195

Comparing the efficiency of theGCD algorithms 197

6.3 Numerical algorithms 197

Successive approximation 198

Reporting errors 200

6.4 Series expansion 201

Zenos paradox 201

Using a series expansion for the squareroot function 203

The Taylor series expansion for approximatinga square root 204

Implementing the Taylor series approximation 205

Staying within the radius of convergence 207

6.5 Specifying the size of numeric types 210

Integer types 210

Unsigned types 211

Floating-point types 212

Summary 212

REVIEW QUESTIONS 213

PROGRAMMING EXERCISES 214

PART TWOLibraries and Modular Development 219

7 Libraries and Interfaces:A Simple Graphics Library 221

7.1 The concept of an interface 222

Interfaces and header files 224

7.2 An introduction to the graphics library 225

The underlying model for graphics.h 225

The functions in thegraphics. h interface 227

Initializing the package 231

Drawingstraight lines 231

Drawing circles and arcs 233

Obtaining informa-tion about the graphics window 235

7.3 Building your own tools 235

Defining DrawBox 236

Defining DrawCenteredcircle 237

Switching between absolute and relative coordinates 239

The advantages of defining procedures 240

7.4 Solving a larger problem 240

Using stepwise refinement 241

Implementing the DrawHouseprocedure 242

looking for common patterns 243

Finishing thedecomposition 245

Summa 250

REVIEW QUESTIONS 251

PROGRAMMING EXERCISES 252

8 Designing Interfaces: A Random Number Library 259

8.1 Interface design 260

The importance of a unifying theme 261

Simplicity and the principleof information hiding 261

Meeting the needs of your clients 263

The advantages of general tools 263

The value of stability 264

8.2 Generating random numbers by computer 265

Deterministic versus nondeterministic behavior 265

Random versuspseudrandom numbers 265

Generating pseudrandom numbersin ANSI C 266

Changing the range of random numbers 267

Generalizing the problem 272

8.3 Saving tools in libraries 274

The contents of an interface 275

Writing the random.h interface 276

The random.c implementation 277

Constructing a client program 278

Initializing the random number generator 280

8.4 Evaluating the design of the random.h interface 283

Generating random real numbers 284

Simulating a probabilisticevent 285

Including header files in an interface 286

Completingthe implementation of the random-number package 286

8.5 Using the random-number package 286

Summa 290

REVIEW QUESTIONS 291

PROGRAMMING EXERCISES 292

9 Strings and Characters 301

9.1 The principle of enumeration 302

Representing enumeration types inside the machine 303

Representingenumeration types as integers 304

Defining new enumerationtypes 304

Operations on enumeration types 307

Scalar types 307

9.2 Characters 308

The data type char 308

The ASCII code 308

Character constants 310

Important propeies of the ASCII coding scheme 310

Special characters 311

Character arithmetic 312

The ctype.h interface 314

Controlstatements involving characters 315

Character input and output 316

9.3 Strings as abstract data 316

layered abstractions 317

The concept of an abstract type 319

9.4 The strlib.h interface 319

Determining the length of a string 320

Selecting characters froma string 321

Concatenation 321

Conveing characters to strings 322

Extracting parts of a string 323

Comparing one string with another 324

Searching within a string 325

Case conversion 327

Numericconversion 329

Efficiency and the strlib.h library 330

Summa 331

REVIEW QUESTIONS 332

PROGRAMMING EXERCISES 334

10 Modular Development 339

10.1 Pig Latin—a case study in modular development 342

Applying topown design 342

Using pseudocode 343

Implementing TranslateLine 344

Taking spaces and punctuationinto account 345

Refining the definition of a word 347

Designing the token scanner 348

Completing the TranslateLineimplementation 349

Specifying the scanner module interface 352

10.2 Maintaining internal state within a module 352

Global variables 355

The dangers of using global variables 356

Keeping variables private to a module 356

Initializing globalvariables 357

Private functions 359

10.3 Implementing the scanner abstraction 359

Summa 366

REVIEW QUESTIONS 366

PROGRAMMING EXERCISES 367

PART THREE 373

Compound Data Types 373

11 Arrays 375

11.1 Introduction to arrays 376

Array declaration 377

Array selection 378

Example of asimple array 379

Changing the index range 381

11.2 internal representation of data 382

Bits bytes and words 382

Memory addresses 383

The sizeof operator 385

Allocation of memoto variables 385

References to elements outside the array bound 386

11.3 Passing arrays as parameters 388

Generalizing the number of elements 390

The mechanics of arrayparameter transmission 392

Implementing Print iritegerArray andGetIntegerArray 394

Implementing ReverseIntegerArray 396

Implementing SwapIntegerElements 397

11.4 Using arrays for tabulation 398

11.5 Static initialization of arrays 404

Automatic determination of array size 408

Determining the size of aniniioiized array 409

Initialized arrays and scalarpes 409

11.6 Multidimensional arrays 410

Passing multidimensional arrays to functions 411

Initializing multidimensional arrays 412

Summary 413

REVIEW QUESTIONS 414

PROGRAMMING EXERCISES 416

12 Searching and Sor 425

12.1 Searching 426

Searching in an integer array 426

A more sophisticated exampleof searching 429

linear search 431

Binasearch 433

Relativeefficiency of the search algorithms 435

12.2 Sorting 437

Sorting an integer array 437

The selection sort algorithm 438

Evaluating the efficiency of selection so 442

Measuring the runningtime of a program 442

Analyzing the selection sort algorithm 445

Summary 446

REVIEW QUESTIONS 446

PROGRAMMING EXERCISES 447

13 Pointers 453

13.1 Using addresses as data values 455

13.2 Pointer manipulation in C 457

Declaring pointer variables in C 457

The fundamentalpointer operations 458

The special pointer NULL 461

13.3 Passing parameters by reference 461

Designing a SaapInteger function 465

Using call by reference toreturn multiple results 466

The danger of overusing call by reference 467

13.4 Pointers and arrays 468

Pointer arithmetic 469

New capabilities of the ++ and -- operators 473

Incrementing and decrementing pointers 475

The relationshipbetween pointers and arrays 476

13.5 Dynamic allocation 478

The type void 478

Dynamic arrays 480

Detecting errors inmalloc 481

Freeing memory 481

Summary 482

REVIEW QUESTIONS 483

PROGRAMMING EXERCISES 486

14 Strings Revisited 491

14.1 Conceptual representations of the type string 491

Strings as arrays 491

Strings as pointers 495

Strings as anabstract type 496

String parameters 497

String variables 497

Differences between pointer and array variables 499

Deciding ona strategy for string representation 502

14.2 The ANSI string libra 502

The strcpy function 504

The strncpy function 507

The strcat and st 507

cat functions 508

The strien strcrrp 510

and st 510

ccnp functions 510

The strchr strrchr andstrstr functions 510

An application of the ANSI string functions 510

14.3 Implementing the strlib libra 511

Implementing the pass-through functions 511

Implementing thestrlib allocation functions 514

Summa 516

REVIEW QUESTIONS 517

PROGRAMMING EXERCISES 517

15 Files 523

15.1 Text files 524

15.2 Using files in C 525

Declaring a FILE variable 526

Opening a file 526

PerformingI/O operations 527

Closing files 528

Standard files 528

15.3 Character l/O 529

Updating a file 531

Rereading characters in the input file 533

15.4 line-oriented l/O 536

15.5 Formatted l/O 539

The three forms of printf 539

The scanf functions 539

Reading strings with scanf 541

An example of formatted l/O 543

limitations on the use of scanf 546

Summary 547

REVIEW QUESTIONS 548

PROGRAMMING EXERCISES 549

16 Records 557

16.1 The concept of the data record 558

16.2 Using records in C 559

Defining a new structure type 560

Declaring structure variables 560

Record selection 561

Initializing records 561

Simple records 562

16.3 Combining records and arrays 563

16.4 Pointers to records 566

Defining a pointer-to-record type 566

Allocating storage forrecord data 568

Manipulating pointers to records 569

16.5 Building a database of records 570

Creating the employee database 570

Using the database 573

16.6 Designing a record-based application 574

The importance of using a database 575

Framing theproblem 575

Designing the internal representation 576

Designing the external structure 580

Coding the program 581

The value of a data-driven design 588

Summa 589

REVIEW QUESTIONS 592

PROGRAMMING EXERCISES 593

17 looking Ahead 601

17.1 Recursion 602

A simple illustration of recursion 603

The Factorial function 604

The recursive leap of faith 609

The recursive paradigm 610

Generating permutations 611

Thinking recursively 614

17.2 Abstract data types 614

The queue abstraction 615

Representing types in the queueabstraction 616

The queue. h interface 618

Implementingthe queue abstraction 620

Alternative implementation of thequeue abstraction 622

17.3 Analysis of algorithms 628

Evaluating algorithmic efficiency 628

Bignotation 629

Selectionsort revisited 630

Divide-andonquer strategies 631

Merging twoarrays 632

The merge sort algorithm 633

The computationalcomplexity of merge sort 635

Comparing quadratic and N log Nperformance 636

Summa 637

REVIEW QUESTIONS 638

PROGRAMMING EXERCISES 639

Appendix A. Summary of G Syntax and Structure 647

A.1 An oveiew of the compilation process 648

A.2 The C preprocessor 648

A.3 The lexical structure of C programs 650

A.4 Expressions 652

A.5 Statements 653

A.6 Functions 657

A.7 Declarations 658

A.8 Data types 659

A.9 ANSI libraries 662

Appendix B. Library Sources 669

Index 696