Transcription
ProgrammingAbstractions in C Eric S. Roberts and Julie ZelenskiThis course reader has had an interesting evolutionary history that in some ways mirrorsthe genesis of the C language itself. Just as Bjarne Stroustup’s first version of C was implemented on top of a C language base, this reader began its life as Eric Roberts’stextbook Programming Abstractions in C (Addison-Wesley, 1998). In 2002-03, JulieZelenski updated it for use with the C programming language, which we began usingin CS106B and CS106X during that year.Although the revised text worked fairly well at the outset, CS106B and CS106X haveevolved in recent years so that their structure no longer tracks the organization of thebook. This year, we’re engaged in the process of rewriting the book so that students inthese courses can use it as both a tutorial and a reference. As always, that process takes aconsiderable amount to time, and there are likely to be some problems as we update thereader. At the same time, we’re convinced that the material in CS106B and CS106X istremendously exciting and will be able to carry us through a quarter or two of instability,and we will end up with an even better course in the future.We want to thank our colleagues at Stanford, several generations of section leaders (withspecial thanks to Dan Bentley and Keith Schwarz), and so many students over theyears—all of whom have helped make it so exciting to teach this wonderful material.
Programming Abstractions in C Chapter 1. An Overview of C 11.1 What is C ? 2The object-oriented paradigm; The compilation process1.2 The structure of a C program 5Comments; Library inclusions; Program-level definitions; Function prototypes;The main program; Function definitions1.3 Variables, values, and types 9Naming conventions; Local and global variables; The concept of a data type;Integer types; Floating-point types; Text types; Boolean type; Simple input andoutput1.4 Expressions 16Precedence and associativity; Mixing types in an expression; Integer division andthe remainder operator; Type casts; The assignment operator; Increment anddecrement operators; Boolean operators1.5 Statements 24Simple statements; Blocks; The if statement; The switch statement; The whilestatement; The for statement1.6 Functions 32Returning results from functions; Function definitions and prototypes; Themechanics of the function-calling process; Passing parameters by referenceSummary 38Review questions 39Programming exercises 41Chapter 2. Data Types in C 452.1 Enumeration types 46Internal representation of enumeration types; Scalar types2.2 Data and memory 49Bits; bytes; and words; Memory addresses2.3 Pointers 51Using addresses as data values; Declaring pointer variables; The fundamentalpointer operations2.4 Arrays 56Array declaration; Array selection; Effective and allocated sizes; Initialization ofarrays; Multidimensional arrays2.5 Pointers and arrays 64The relationship between pointers and arrays2.6 Records 67Defining a new structure type; Declaring structure variables; Record selection;Initializing records; Pointers to records2.7 Dynamic allocation 71Coping with memory limitations; Dynamic arrays; Dynamic recordsii
Summary 74Review questions 74Programming exercises 77Chapter 3. Libraries and Interfaces 853.1 The concept of an interface 86Interfaces and implementations; Packages and abstractions; Principles of goodinterface design3.2 A random number interface 89The structure of the random.h interface; Constructing a client program; The ANSIfunctions for random numbers; The random.cpp implementation3.3 Strings 98The data type string; Operations on the string type ; The strutils.hinterface; An aside about C-style strings3.4 Standard I/O and file streams 105Data files; Using file streams in C ; Standard streams; Formatted stream output;Formatted stream input; Single character I/O; Rereading characters from an inputfile; Line-oriented I/O3.5 Other ANSI libraries 112Summary 113Review questions 113Programming exercises 116Chapter 4. Using Abstract Data Types 1234.1 The Vector class 125Specifying the base type of a Vector; Declaring a new Vector object; Operationson the Vector class; Iterating through the elements of a Vector; Passing a Vectoras a parameter4.2 The Grid class 1314.3 The Stack class 133The structure of the Stack class4.4 The Queue class 136Simulations and models; The waiting-line model; Discrete time; Events insimulated time; Implementing the simulation4.5 The Map class 146The structure of the Map class; Using maps in an application; Maps as associativearrays4.6 The Lexicon class 151The structure of the Lexicon class; A simple application of the Lexicon class;Why are lexicons useful if maps already exist4.7 The Scanner class 154Setting scanner options4.8 Iterators 156The standard iterator pattern; Iteration order; A simple iterator example;Computing word frequenciesiii
Summary 163Review questions 164Programming exercises 165Chapter 5. Introduction to recursion 1735.1 A simple example of recursion 1745.2 The factorial function 176The recursive formulation of Fact; Tracing the recursive process; The recursiveleap of faith5.3 The Fibonacci function 181Computing terms in the Fibonacci sequence; Gaining confidence in the recursiveimplementation; Recursion is not to blame5.4 Other examples of recursion 187Detecting palindromes; Binary search; Mutual recursion5.5 Thinking recursively 192Maintaining a holistic perspective; Avoiding the common pitfallsSummary 194Review questions 195Programming exercises 197Chapter 6. Recursive procedures 2016.1 The Tower of Hanoi 202Framing the problem; Finding a recursive strategy; Validating the strategy;Coding the solution; Tracing the recursive process6.2 Generating permutations 211The recursive insight6.3 Graphical applications of recursion 213The graphics library; An example from computer art; FractalsSummary 224Review questions 225Programming exercises 226Chapter 7. Backtracking algorithms 2357.1 Solving a maze by recursive backtracking 236The right-hand rule; Finding a recursive approach; Identifying the simple cases;Coding the maze solution algorithm; Convincing yourself that the solution works7.2 Backtracking and games 245The game of nim; A generalized program for two-player games; The minimaxstrategy; Implementing the minimax algorithm; Using the general strategy tosolve a specific gameSummary 269Review questions 270Programming exercises 271iv
Chapter 8. Algorithmic analysis 2778.1 The sorting problem 278The selection sort algorithm; Empirical measurements of performance; Analyzingthe performance of selection sort8.2 Computational complexity and big-O notation 282Big-O notation; Standard simplifications of big-O; Predicting computationalcomplexity from code structure; Worst-case versus average-case complexity; Aformal definition of big-O8.3 Recursion to the rescue 288The power of divide-and-conquer strategies; Merging two vectors; The merge sortalgorithm; The computational complexity of merge sort; Comparing N 2 and N logN performance8.4 Standard complexity classes 2948.5 The Quicksort algorithm 296Partitioning the vector; Analyzing the performance of Quicksort8.6 Mathematical induction 301Summary 304Review questions 305Programming exercises 307Chapter 9. Classes and objects 3139.1 A simple example of a class definition 314Defining a Point class; Implementing methods in a class; Constructors anddestructors; The keyword this9.2 Implementing a specialized version of the Stack class 319Defining the CharStack interface; Representing the stack data; The advantages ofobject encapsulation; Removing the maximum size limitation; Object copying9.3 Implementing the Scanner class 328Summary 328Review questions 334Programming exercises 335Chapter 10. Efficiency and Data Representation 33910.1 The concept of an editor buffer 34010.2 Defining the buffer abstraction 341The public interface of the EditorBuffer class; Coding the editor application10.3 Implementing the editor using arrays 345Defining the private data representation; Implementing the buffer operations;Assessing the computational complexity of the array implementation10.4 Implementing the editor using stacks 352Defining the private data representation for the stack-based buffer; Implementingthe buffer operations; Comparing computational complexitiesv
10.5 Implementing the editor using linked lists 357The concept of a linked list; Designing a linked-list data structure; Using a linkedlist to represent the buffer; Insertion into a linked-list buffer; Deletion in a linkedlist buffer; Cursor motion in the linked-list representation; Linked-list idioms;Completing the buffer implementation; Computational complexity of the linkedlist buffer; Doubly linked lists; Time-space tradeoffsSummary 371Review questions 372Programming exercises 373Chapter 11. Linear Structures 38111.1 Reimplementing stacks as a template class 382The interface of a class template11.2 Reimplementing stacks using linked lists 38311.3 Implementing queues 391An array-based implementation of queues; Linked-list representation of queues11.4 Implementing vectors 404Supporting insertion and deletion at arbitrary index positions; Implementingselection brackets; Implementing iteratorsSummary 414Review questions 415Programming exercises 416Chapter 12. Implementing Maps 41912.1 An array-based implementation of the map interface 42012.2 The advantage of knowing where to look 42712.3 Hashing 429Implementing the hash table strategy; Choosing a hash function; Determining thenumber of buckets; Using the typename keyword12.4 Functions as data 438A general plotting function; Declaring pointers to functions and functiontypedefs; Implementing Plot; A generic sorting function12.5 Mapping functions 444Mapping over entries in a map; Implementing mapAll; Passing client informationto a callback function; A note on function types and methodsSummary 448Review questions 449Programming exercises 450Chapter 13. Trees 45513.1 Family trees 456Terminology used to describe trees; The recursive nature of a tree; Representingfamily trees in C vi
13.2 Binary search trees 459The underlying motivation for using binary search trees; Finding nodes in abinary search tree; Inserting new nodes in a binary search tree; Tree traversals13.3 Balanced trees 466Tree-balancing strategies; Illustrating the AVL idea; Single rotations; Doublerotations; Implementing the AVL algorithm13.4 Defining a general interface for binary search trees 477Allowing the client to define the node data; Generalizing the types used for keys;Removing nodes; Implementing the binary search tree package; Implementing themap.h interface using binary trees; Using the static keywordSummary 488Review questions 489Programming exercises 492Chapter 14. Expression Trees 49914.1 Overview of the interpreter 50014.2 Understanding the abstract structure of expressions 505A recursive definition of expressions; Expression trees14.3 Class hierarchies and inheritance 50914.4 Defining an inheritance hierarchy for expressions 510Defining the interface for the expression subclasses14.5 Implementing the node classes 518Implementing the methods14.6 Parsing an expression 522Parsing and grammars; Parsing without precedence; Adding precedence to theparserSummary 528Review questions 528Programming exercises 530Chapter 15. Sets 53515.1 Sets as a mathematical abstraction 536Membership; Set operations; Identities on sets15.2 Designing a set interface 539Defining the element type; Writing the set interface; Character sets; Using sets toavoid duplication15.3 Implementing the set class 54415.4 Enhancing the efficiency of integer sets 548Characteristic vectors; Packed arrays of bits; Bitwise operators; Implementingcharacteristic vectors using the bitwise operators; Implementing the high-level setoperations; Using a hybrid implementationSummary 555Review questions 556Programming exercises 558vii
Chapter 16. Graphs 56316.1 The structure of a graph 564Directed and undirected graphs; Paths and cycles; Connectivity16.2 Implementation strategies for graphs 568Representing connections using an adjacency list; Representing connections usingan adjacency matrix; Representing connections using a set of arcs16.3 Designing a low-level graph abstraction 571Using the low-level graph.h interface16.4 Graph traversals 575Depth-first search; Breadth-first search16.5 Defining a Graph class 580Using classes for graphs, nodes, and arcs; Adopting an intermediate strategy16.6 Finding minimum paths 58916.7 An efficient implementation of priority queues 593Summary 596Review questions 597Programming exercises 599Appendix A. Library Interfaces 2623627630634638642644646652656657658660662Index 657viii
Chapter 1An Overview of C Out of these various experiments come programs. This isour experience: programs do not come out of the minds ofone person or two people such as ourselves, but out of dayto-day work.— Stokely Carmichael and Charles V. Hamilton,Black Power, 1967
An Overview of C –2–In Lewis Carroll’s Alice’s Adventures in Wonderland, the King asks the White Rabbit to“begin at the beginning and go on till you come to the end: then stop.” Good advice, butonly if you’re starting from the beginning. This book is designed for a second course incomputer science and therefore assumes that you have already begun your study ofprogramming. At the same time, because first courses vary considerably in what theycover, it is difficult to rely on any specific material. Some of you, for example, willalready have experience programming in C or C . Many of you, however, are comingfrom a first course taught in some other language.Because of this wide disparity in background, the best approach is to adopt the King’sadvice and begin at the beginning. The first three chapters in this text therefore movequickly through the material I consider to be essential background for the later chapters.Chapters 1 and 2 discuss C in general and may be skimmed if you’ve had experiencewith C . Chapter 3 discusses standard interfaces and some interfaces particular to thistext. By the end of these three chapters, you will be up to speed on the fundamentals ofC programming.1.1 What is C ?In the early days of computing, programs were written in machine language, whichconsists of the primitive instructions that can be executed directly by the machine.Machine-language programs are difficult to understand, mostly because the structure ofmachine language reflects the design of the hardware rather than the needs ofprogrammers. In the mid-1950s, a group of programmers under the direction of JohnBackus at IBM had an idea that profoundly changed the nature of computing. Would itbe possible, they wondered, to write programs that resembled the mathematical formulasthey were trying to compute and have the computer itself translate those formulas intomachine language? In 1955, this team produced the initial version of Fortran (whosename is an abbreviation of formula translation), which was the first example of a higherlevel programming language. Since that time, many new programming languages havebeen invented, as shown in the evolutionary diagram in Figure 1-1.Figure 1-1 Evolutionary tree of several major programming languages
An Overview of C –3–As Figure 1-1 illustrates, C represents the coming together of two branches in theevolution of programming languages. One of its ancestors is a language called C, whichwas designed at Bell Laboratories by Dennis Ritchie in 1972 and then later revised andstandardized by the American National Standards Institute (ANSI) in 1989. But C alsodescends from another line of languages that have dramatically changed the nature ofmodern programming.The object-oriented paradigmOver the last decade or so, computer science and programming have gone throughsomething of a revolution. Like most revolutions—whether political upheavals or theconceptual restructurings that Thomas Kuhn describes in his 1962 book The Structure ofScientific Revolutions—this change has been driven by the emergence of an idea thatchallenges an existing orthodoxy. Initially, the two ideas compete. For a while, the oldorder maintains its dominance. Over time, however, the strength and popularity of thenew idea grows, until it begins to displace the older idea in what Kuhn calls a paradigmshift. In programming, the old order is represented by the procedural paradigm, inwhich programs consist of a collection of procedures and functions that operate on data.The challenger is the object-oriented paradigm, in which programs are viewed insteadas a collection of data objects that exhibit particular behavior.The idea of object-oriented programming is not really all that new. The first objectoriented language was SIMULA, a language for coding simulations designed in 1967 bythe Scandinavian computer scientists Ole-Johan Dahl, Björn Myhrhaug, and KristenNygaard. With a design that was far ahead of its time, SIMULA anticipated many of theconcepts that later became commonplace in programming, including the concept ofabstract data types and much of the modern object-oriented paradigm. In fact, most ofthe terminology used to describe object-oriented systems comes from the original 1967report on SIMULA.For many years, however, SIMULA mostly just sat on the shelf. Few people paidmuch attention to it, and the only place you were likely to hear about it would be in acourse on programming language design. The first object-oriented language to gain anysignificant level of recognition within the computing profession was Smalltalk, whichwas developed at the Xerox Palo Alto Research Center (more commonly known as XeroxPARC) in the late 1970s. The purpose of Smalltalk, which is described in the bookSmalltalk-80: The Language and Its Implementation by Adele Goldberg and DavidRobson, was to make programming accessible to a wider audience. As such, Smalltalkwas part of a larger effort at Xerox PARC that gave rise to much of the modern userinterface technology that is now standard on personal-computers.Despite many attractive features and a highly interactive user environment thatsimplifies the programming process, Smalltalk never achieved much commercial success.The profession as a whole took an interest in object-oriented programming only when thecentral ideas were incorporated into variants of C, which had already become an industrystandard. Although there were several parallel efforts to design an object-orientedlanguage based on C, the most successful was the language C , which was designed inthe early 1980s by Bjarne Stroustrup at AT&T Bell Laboratories. By making it possibleto integrate object-oriented techniques with existing C code, C enabled largecommunities of programmers to adopt the object-oriented paradigm in a gradual,evolutionary way.Although object-oriented languages are undeniably gaining popularity at the expenseof procedural ones, it would be a mistake to regard the object-oriented and proceduralparadigms as mutually exclusive. Programming paradigms are not so much competitive
An Overview of C –4–as they are complementary. The object-oriented and the procedural paradigm—alongwith other important paradigms such as the functional programming style embodied inLISP—all have important applications in practice. Even within the context of a singleapplication, you are likely to find a use for more than one approach. As a programmer,you must master many different paradigms, so that you can use the conceptual model thatis most appropriate to the task at hand.The compilation processWhen you write a program in C , your first step is to create a file that contains the textof the program, which is called a source file. Before you can run your program, youneed to translate the source file into an executable form. The first step in that process isto invoke a program called a compiler, which translates the source file into an object filecontaining the corresponding machine-language instructions. This object file is thencombined with other object files to produce an executable file that can be run on thesystem. The other object files typically include predefined object files, called libraries,that contain the machine-language instructions for various operations commonly requiredby programs. The process of combining all the individual object files into an executablefile is called linking. The process is illustrated by the diagram shown in Figure 1-2.Unfortunately, the specific details of the compilation process vary considerably fromone machine to another. There is no way that a general textbook like this can tell youexactly what commands you should use to run a program on your system. Because thosecommands are different for each system, you need to consult the documentation thatcomes with the compiler you are using on that machine. The good news, however, is thatthe C programs themselves will look the same. One of the principal advantages ofprogramming in a higher-level language like C is that doing so often allows you toignore the particular characteristics of the hardware and create programs that will run onmany different machines.Figure 1-2 The compilation processsource fileobject file/* File: count.c 010101100#include stdio.h #include "genlib.h"#define N 10main(){int i;}compilerexecutable filefor (i 1; i N; i ) {printf("%d\n", 101101011010100101other 0010110110101101011010100101linker
An Overview of C –5–1.2 The structure of a C programThe best way to get a feeling for the C programming language is to look at a sampleprogram such as the one shown in Figure 1-3. This program generates a table comparingthe values of N 2 and 2N for various values of N—a comparison that will prove to beimportant in Chapter 8. The output of the program looks like this:PowerTable 2 NN N 2---- ----- -----0 0 11 1 22 4 43 9 84 16 165 25 326 36 647 49 1288 64 2569 81 51210 100 102411 121 204812 144 4096As the annotations in Figure 1-3 indicate, the powertab.cpp program is divided intoseveral components, which are discussed in the next few sections.CommentsMuch of the text in Figure 1-3 consists of English-language comments. A comment istext that is ignored by the compiler but which nonetheless conveys information to otherprogrammers. A comment consists of text enclosed between the markers /* and */ andmay continue over several lines. Alternatively, a single-line comment is begun by themarker // and continues until the end of the line. The powertab.cpp program includes acomment at the beginning that describes the operation of the program as a whole, onebefore the definition of the RaiseIntToPower function that describes what it does, and acouple of one-line comments that act very much like section headings in English text.Library inclusionsThe lines beginning with #include such as#include "genlib.h"#include iostream #include iomanip indicate that the compiler should read in definitions from a header file. The inclusion ofa header file indicates that the program uses facilities from a library, which is acollection of prewritten tools that perform a set of useful operations. The differentpunctuation in these #include lines reflects the fact that the libraries come from differentsources. The angle brackets are used to specify a system library, such as the standardinput/output stream library (iostream) or the stream manipuator library (iomanip) that issupplied along with C . The quotation marks are used for private libraries, includingthe general library (genlib), which was designed for use with the programs in this text.Every program in this book will include at least this library most will require otherlibraries as well and must contain an #include line for each one.
An Overview of C –6–Figure 1-3 Sample program powertab.cpp/** File: powertab.cpp* -----------------* This program generates a table comparing values* of the functions n 2 and 2 n.*/programcomment#include "genlib.h"#include iostream #include iomanip libraryinclusions/** Constants* --------* LOWER LIMIT -- Starting value for the table* UPPER LIMIT -- Final value for the table*/sectioncommentconstantdefinitionsconst int LOWER LIMIT 0;const int UPPER LIMIT 12;/* Private function prototypes */functionprototypeint RaiseIntToPower(int n, int k);/* Main program */int main() {cout " 2 N" endl;cout " N N 2" endl;cout "---- ----- ------" endl;for (int n LOWER LIMIT; n UPPER LIMIT; n ) {cout setw(3) n " " ;cout setw(4) RaiseIntToPower(n, 2) " " ;cout setw(5) RaiseIntToPower(2, n) endl;}return 0;}/** Function: RaiseIntToPower* Usage: p RaiseIntToPower(n, k);* --------------------------------* This function returns n to the kth power.*/int RaiseIntToPower(int n, int k) {int result;}result 1;for (int i 0; i k; i ) {result * n;}return result;mainprogramfunctioncommentlocal variabledeclarationsstatementsforming bodyof functionfunctiondefinition
An Overview of C –7–Program-level definitionsAfter the #include lines for the libraries, many programs define constants that apply tothe program as a whole. In the powertab.cpp program, the following linesconst int LOWER LIMIT 0;const int UPPER LIMIT 12;introduce two constants named LOWER LIMIT and UPPER LIMIT.The syntax for declaring a constant resembles that for declaring a variable (discussedin section 1.3) that includes the type modifier const. The general form isconst type name value ;which defines the constant name to be of type type and initialized to value. A constant mustbe initialized when it is defined and once initialized, it cannot be assigned a new value orchanged in any way. Attempting to do so will result in a compiler error. After a namedconstant is defined, it is available to be used anywhere in the rest of the program. Forexample, after encountering the lineconst double PI 3.14159265;any subsequent use of the name PI refers to the constant value 3.14159265.Giving symbolic names to constants has several important advantages in terms ofprogramming style. First, the descriptive names give readers of the program a bettersense of what the constant value means. Second, centralizing such definitions at the topof the file makes it easier to change the value associated with a name. For example, allyou need to do to change the limits used for the table in the powertab.cpp program ischange the values of the constants. And lastly, a const declaration protects from thevalue from any unintended modification.In addition to constants, programs often define new data types in this section of thesource file, as you will see in Chapter 2.Function prototypesComputation in a C program is carried out in the context of functions. A function is aunit of code that (1) performs a specific operation and (2) is identified by name. Thepowertab.cpp program contains two functions—main and RaiseIntToPower—whichare described in more detail in the next two sections. The lineint RaiseIntToPower(int n, int k);is an example of a function prototype, a declaration that tells the compiler theinformation it needs to know about a function to generate the proper code when thatfunction is invoked. This prototype, for example, indicates that the functionRaiseIntToPower takes two integers as arguments and returns an integer as its result.You must provide the declaration or definition of each function before making anycalls to that function. C requires this in order for the compiler to check whether calls tofunctions are compatible with the corresponding prototypes and can therefore aid you inthe process of finding errors in your code.
An Overview of C –8–The main programEvery C program must contain a function with the name main. This function specifiesthe starting point for the computation and is called when the program starts up. Whenmain has finished its work and returns, execution of the program ends.The first three statements of the main function in the powertab.cpp program aresending information to the cout stream to display output on the screen. A few usefulnotes about streams are included in the section on “Simple input and output” later in thischapter and more features are explored in detail in Chapter 3. At this point, you need tohave an informal sense of how to display output to understand any programming examplethat communicates results to the user. In its simplest form, you use the insertion operator to put information into the output stream cout . If you insert a string enclosed indouble quotes, it will display that string on the console. You must indicate explicitly thatyou want to move on to the next line by inserting the stream manipulator endl. Thus,the first three lines in main display the header for the table.The rest of the function main consists of the following code, which is responsible fordisplaying the table itself:for (intcoutcoutcout}n LOWER LIMIT; n UPPER LIMIT; n ) { setw(3) n " " ; setw(4) RaiseIntToPower(n, 2) " " ; setw(5) RaiseIntToPower(2, n) endl;This code is an example a for loop, which is used to specify repetition. In this case, thefor statement indicates that the body of the loop should be repeated for each of thevalues of n from LOWER LIMIT to UPPER LIMIT. A section on the detailed structure ofthe for loop appears later in the chapter, but the example shown here represents acommon idiomatic pattern that you can use to count between any specified limits.The body of the loop illustrates an important new feature: the ability to include valuesas part of the output display. Rathe
Abstractions in C Eric S. Roberts and Julie Zelenski T his course reader has had an interesting evolutionary history that in som e w ays m irrors the genesis of the C language itself. Just as B jarne S troustupÕs first version of C w as im plem ented on top of a C lang
