CSCI1300 Notes 3: Control Flow
Purpose: Make sure you can accurately envision the order in which the statements in a program will be executed. Be able to write programs that process the elements of arrays.
A computer does what it does by executing instructions (also called operations )which are stored in its memory.
It normally executes these instructions in the order in which they are stored in memory, one right after another.
Some operations, called branch or jump operations, cause the computer to break the normal sequence and jump to somewhere else in memory and execute instructions from there.
Some branch or jump operations are conditional, in that they cause the computer either to jump or to continue the normal sequence depending on some test, called a condition. The availability of conditional branches means that the computer does not always do the same sequence of operations in executing a given sequence of instructions. Rather, the sequence often is different for different data values, because the tests that determine whether the conditional branches jump or not will have different results for different data. that the program may be given to work on.
The statements you put in your C programs are translated into machine instructions, which are then executed by the computer. These instructions are placed in memory in the order in which you arranged the statements in your program, and so normally the statements you write are executed in the order in which they appear in your program.
You can vary this normal sequence of execution by including in your program statements which work in more or less the same way as jump instructions do. The sequence in which the statements are executed, based on the order of the statements in your program, and on the effect of any special statements that modify the sequence, is called control flow. The image is that the statements in your program take over the control of the computer when your program runs, and they pass this control around among themselves. So you can think of the control flowing from one statement to another as your program runs.
Conditional statements. To arrange for control flow to be influenced by the data your program is working on, you use conditional statements , also called if statements, like this one:
These statements have this general form:
if (some test)
The way they work is this: the test is evaluated, and if it is true the statement we are calling "some statement" is executed. If the test is not true the statement "some statement" is not executed. Thus in the example the assignment a=b; will be executed if the value in foo is greater than zero, and not executed otherwise.
A slightly more complex conditional has this form:
if (some test)
else some other statement;
An example of the use of this is this little program fragment which puts the maximum of a and b in c:
The idea of the else is that the statement following the else is executed only when the test is not true.
After either form of conditional statement control flows on to whatever the next statement in line is.
Very often you want to have more than one statement being controlled by a test. It might be tempting to write something like this:
hoping that the three indented statements will all be executed only if the value of foo is greater than zero. But in fact the compiler pays no attention to what is indented and what is not. It treats this fragment exactly as if you had written this:
Here you can see that c=d; and e=f; will be executed whether or not the test is true: the test in the conditional controls only the single statement following, a=b; in this case.
Fortunately there is an easy way to get the effect you want. You can always combine any collection of statements into one compound statement just by putting curly brackets around them:
The curly brackets turn the three assignments into one compound statement, and that compound statement is what the test controls.
Loops. It is very common to need to execute some part of your program over and over again. For example, you may want to get some numbers from the user, calculate something, get some more numbers, do the same calculation on those numbers, and so on until the user gets tired. Doing this means you need some way to make the control in your program flow back up to some earlier point. Such an arrangement is called a loop, because if you draw a line tracing the flow of control the line will form a loop.
The simplest way to get this effect is a while loop:
while (some test)
As you can see, this looks a lot like a conditional, and it is somewhat similar. The statement we're calling 'some statement' only gets executed if the test is true. The key difference is what happens next: after 'some statement' is executed, the whole while statement is executed again. That is, the test is evaluated again, and if it's still true, some statement is executed again, and the process repeats. Only if the test eventually turns up false will the process stop, and allow control to flow on the rest of the program.
Here's a simple example:
Here's what happens when this is executed:
We put 6 into foo
We test if foo is greater than 1.
It is, so we execute foo=foo-2; That is, we take the value in foo, subtract 2, and put the result in foo. So foo now contains 4.
Since we are in a while, we test foo again.
It is still greater than one, so we execute foo=foo-2; again. This puts 2 into foo.
Since we are in a while, we test foo again.
It is still greater than one, so we execute foo=foo-2; again. This puts 0 into foo.
Since we are in a while, we test foo again.
It is not greater than 1, so the test fails. So we do not execute the statement foo=foo-2; again. Rather, we let control flow on to whatever comes next in the program.
You can get an intuitive feel for all this by reading a while statement something like this: "as long as this test is true, keep executing this statement".
Exactly as in a conditional, you often want to have more than one statement being controlled by a while. You use the same trick: you turn any collection of separate statements into a single compound statement by putting curly brackets around them.
For loops. An especially common kind of loop is one that processes the elements of an array. Suppose for example that we want to put 37 into all the elements of an array foo. This while loop will do the trick.
Think through this example carefully to see how it works. Notice that the assignment i=i+1; may look odd, but it has a simple meaning: take the value of i, add 1, and put the result into i. Draw a set of boxes for foo and one for i and work through the execution. You'll see that i starts at 0 and works its way up to 5, and that the assignment foo[i]=37; gets executed once when i contains 0, again when i contains 1, again when i contains 2, again when i contains 3, again when i contains 4, and not when i contains 5. That is, 37 gets put into foo, foo, foo, foo, and foo, just as we want.
This kind of loop is so common that the designers of C have provided a special shorthand, called a for loop, to make writing them easier. We can write the above program fragment this way:
This has exactly the same meaning as the while loop above (that is, exactly the same instructions are generated)! More generally, the form
for(initial statement;test;advance statement)
does exactly the same thing as this form that uses a while loop:
Processing arrays. One kind of for loop is so useful and so common that I've given it a name: the Generic Array Processing Plan, or GAPP. Anytime you need to do something with an array you want to think first of this idea. Actually, you've already seen it in the example of putting 37 into all the elements of foo. Here is the general pattern:
To do something to all the elements of an array foo that has N elements in it, create an information holder to hold the subscript, say i, and write this loop:
put here statements that operate on foo[i]
All you have to do is replace N by whatever the size of foo is. If foo is declared as (say) float foo then N is 534. You don't even need the curly brackets unless it takes more than one statement to do what you want with foo[i].
We'll see many, many examples of the use of this plan, and you'll create many of your own. Here's an example to give you a feel for the possibilities.
Suppose we want to add up the numbers in foo. The thing we want to do with each element of foo is to add it to a running total we will use to hold the sum. So here's all there is to it, assuming that foo has (say) 376 elements.
//some code omitted that puts numbers into the array foo
Here's another example. To find the largest number in foo what we can do is compare each number in foo to the largest number we have found so far. If it's bigger, we replace the largest so far with the new value. This is sometimes called the knockout plan: the largest number so far is the current champion, but will be knocked out by a new, bigger number, who becomes the new champion. Here's how, assuming foo has 217 elements:
//some code omitted that puts numbers into the array foo
if (foo[i]>biggest)//the challenge
biggest=foo[i];//the new champion
A couple of notes about this example; First, why start by putting the value of foo into biggest? Well, we have to put something into biggest to get started, and if we put in something that's not among the values in foo there's a chance that the value we choose would be bigger than any element in foo, and therefore we would not find the actual maximum of the values in foo. We could have used any value in foo to avoid this problem, so why not foo?
Second, you may notice that this simple program wastes a little tiny amount of work, because after we put foo in biggest we then test foo against biggest. We know that this test will fail, so why do it? If you wish you can work out how to change the for loop slightly to eliminate this tiny waste. But I don't recommend doing that, because it moves you away from the plain, simple, and utterly stereotyped Generic Array Processing Plan. As we will discuss at length, the first thing to worry about is getting a program you are completely sure will work, and for which it is as obvious as possible how it works. That goal is best attained by using the simplest, most obvious constructions that will do the job, even if these may be a bit wasteful.
Break. While most things that you need to do with arrays can be done using the GAPP, there is one fairly common variant that uses one more piece of C control flow apparatus, the break statement. Putting break; into a loop has the effect of dropping out of the loop and going ahead with the rest of the program whenever you execute the break. Here's an example of its use.
Suppose we want to know whether the array foo contains the value 37 or not. We could compare each element of foo with 37, using the simple GAPP, but that would be more than a little wasteful. After all, 37 could be right there in foo, and any looking beyond there would be unnecessary. Here's how to vary the GAPP to eliminate the extra checking:
//some code omitted that puts numbers into the array foo.
int foundit=0; //a value of 0 in foundit means we haven't found 37 yet
// 1 means we have
If we find what we are looking for, we note that we've found it by setting foundit to 1, and then we execute break; to get out of the loop without further processing.
Incidentally, an information holder that is used the way foundit is used in this example is often called a flag. The image is that the flag is up or down, and its position signals something; in this case, the flag signals whether we have found what we are looking for. Thought question: why do we need a flag here? Why not just break out of the loop when we find 37, without setting a flag?
Did you notice the double equal signs in the test in that example? It's not a misprint. In fact, it's one of the most often confused features of C. If you want to compare two values to see if they are equal, you have to use 2 equals signs and not one. If we wrote (foo[i]=37) as our test this would not at all mean what we want. In fact, believe it or not, this would be an assignment that would put 37 into foo[i]. Pretty bizarre, what? We'll talk more about this oddity, why it happens, and how to live with it. For now, just try hard to remember to use 2 equals when you are comparing things.
A little more about tests. You've seen things in the examples like (foo[i]==0) and (i<245), which are pretty clear. Other possible comparisons are (i<=j), (i>245) and (i>=j). Another is (a!=b) is true when a is not equal to b (the exclamation point is used to mean ‘not’). You also should note that as far as C is concerned any expression that produces an int value is a suitable test: a zero value is interpreted as false, and a 1 or any other non-zero value as true. This means we can use variables like foundit in tests in a simple way:
a statement to do if we found a 37
a statement to do if didn't find a 37
The test (foundit) will be true if there's a 1 in foundit and false if there's a zero.
Is it really worth bothering with the GAPP pattern? Yes. You avoid lots of problems, including possible out-of-range subscripts, by learning and using a simple, reliable standard way of processing your arrays. If you try to create your own loops from scratch you'll constantly be doing things like not processing the first element, because you started with 1 and not 0, or processing an element that's not there by using i<=N as your test. I know, because that happened to me all the time until I buckled down and learned how to handle the standard form by reflex.
A final bit of trivia, one that marks a part of your initiation into C. Because statements like i=i+1; are so common, the designers created a special abbreviation for them. Writing i++; will add one to i. This works for any suitable information holder, not just i; you could write foo[i]++ to add one to foo[i], for example. Using this form, the for-loop in the GAPP is even simpler: for(i=0;i<N;i++). You should practice this enough to write it in your sleep!
The idea of this first part of your assignment is for you to develop your ability to envision in advance what will happen when your program runs, rather than being dependent on trial and error. So answer these questions WITHOUT creating and running programs.
If the following program fragments were run, each of the printf() statements would print a message on the screen. Your task is to say which messages will be printed and in what order.
Note: Normally some of the statements in these program fragments would be indented. BUT the indentation has no effect on how the programs run. You need to be able to determine what will happen without relying on indentation for clues.
total=total+i*j; //note: * means multiply,
//so this adds the
//product of i and j to total
a=a/2; //this divides the value of a by 2
Problem 3-9 Reach agreement in your team about what will happen when this program is run. Then type it in (be sure to type it as it is written here, or, better, use copy and paste), compile it, and run. Is your prediction right? If not, why not? If your prediction is correct, can you suggest what aspects of this program might make the prediction tricky?
Problems 3-10,11. All bus stops in the Duckburg bus system are identified by whole numbers, so a bus route can be represented by an array of ints, as in
This declaration says that route203 is an array of 6 ints, and places the indicated numbers in the array, representing the fact that route203 has the 6 stops indicated.
Problem 3-10. Write a program that asks the user to type in a number, and prints "yes" if the stop with that number is on route203 and "no" if it is not.
As you've seen in various examples so far, there's a common form for a program that you'll want to use:
//here's where the meat of your program goes...
// put your declarations in first
//then the statements that make your program do whatever it does
return 0; //we don’t care about this but the system wants it
In this program, you'll want to include the declaration above for route203.
Your program will be easier to work with if you follow the good practice of always printing some kind of prompt message just before the user is supposed to type something in. Use a statement like printf("Type in a number:"); to do this.
Remember that the statement scanf("%d",&i); will let you type a number into i when your program runs. Don’t forget the &!
Incidentally, the lines that start with // are comments: the compiler pays no attention to them, so you can use them for explanations. You can also put // in the middle of line: the part of the line after the // is treated as a comment. That way you can put a comment that also has a program statement on it.
Use the GAPP to determine whether the number the user types in is in the array route203.
Compile and test your program to be sure it works properly.
Turn in a listing of your code and a screen snapshot that shows your program being compiled and run. Be sure you use the –Wall flag when you compile, and that you are getting no warnings when you compile. Here's how to make a screen snapshot. (a) Compile and run your program. (b) Be sure the console is the active window (the bar at the top should be blue; click the mouse somewhere in the window to be sure.) (c) Use alt print screen to copy a picture the active window to the clipboard. On my machine, that means I hold down the ALT and FN keys while pressing a key labelled Prnt Scrn. The keys may be different on your machine. (d) Open up a file in Word or Paint or Outlook or any other application that allows this (try it) and paste your picture into it.
Problem 3-11.Write a program that asks the user to type in a number. If the number is a stop on route203, other than the last stop, the program should print out the number of the next stop. If the number is the last stop, the program should print "Last stop". If the number is not a stop on the route, the program should print "Not a stop on route203". Compile and test your program to be sure it works properly. Turn in a listing of your code and a screen snapshot that shows your program being compiled and run. Be sure you use the –Wall flag when you compile, and that you are getting no warnings when you compile.
Don't forget your time report, covering all work since your last time report.