the final is coming up soon. there's going to be a review session saturday afternoon... when i know details about location and time, i'll let you know. today, i'm going to review stuff that seems to be confusing for lots of students.
here's a function that takes two integer inputs, and returns the larger one:
/* prototype */
int max(int a, int b);
/* definition */
int max(int a, int b)
{
if(a > b)
return a;
else
return b;
}
let's review the parts of the function. first, we have the prototype, which is just a copy of the first line of the definition, with a semicolon at the end [don't forget the semicolon!]. remember that the prototype must always match the first line of the definition, so if you change one, you must change the other.
next, we have the definition of the function. the int at
the beginning tells the computer that this function will return an
integer. next we have max, which specifies the name of
this function. after that, we have a pair of parentheses, with
int a, int b inside. which tells the computer that this
function takes two integers as input, and whatever those two integers
happen to be, we're going to refer to them as "a" and
"b".
after that, we have some curly braces with an if
statement inside. this part tells the computer what to do with the
inputs when the function is called. in our case, the computer will
check if a is bigger than b. if so, the
function returns a, otherwise the function returns
b.
after defining a function, we can call it as many times as we
want. so, after i define the max function above, i can do
all this crazy stuff:
void main()
{
int a,b,c,d;
a=5;
b=7;
c=max(a,b);
d=max(b,a);
}
let's look at what this stuff does. the first line just declares a few
integer variables. the second and third lines put some values in
a and b. the fourth line contains
max(a,b), which is a function call. the computer knows it
is a function call, because we mention the name of a function
[max], and we follow it by a pair of parentheses with
some stuff in between [(a,b)]. so, this tells the
computer that we want to run the max function with inputs
a and b, and the c= part tells
the computer that we want to save the output of the function in the
variable called c.
before running a function, the first thing the computer does is
determine the actual value of all the inputs. so, in our case, the
computer will figure out the actual values of a and
b, which are 5 and 7,
respectively.
the next thing the computer needs to do is to run the max
function with inputs 5 and 7. to do this,
first a new scope ["bubble", if you prefer] is created, and this scope
contains the inputs to the function.
back when we defined the function, we said "int a, int b"
between the parentheses on the first line of the function definition.
this tells the computer that the two inputs to the function need to be
available in integer variables called a and
b, so the computer needs to create two integer variables
in the new scope called a and b, with values
5 and 7, respectively.
it's very important to note that the a in
max is not the same variable as the a in
main. there are two variables called a, but
one is in main's scope, and the other is in
max's scope.
next, the computer runs the stuff in the body of the function
definition within the scope that we just created. so, in our case, the
if statement will be run, it will realize that the value
in b is bigger than the value in a [because
7 is bigger than 5], so it returns the value
in b, which is 7. we are done running the
stuff in the body of the function, so the newly created scope
gets erased, and we return to main, where c
receives the value 7.
so what does the second call ["d=max(b,a)"] do? don't
forget that the first thing the computer does is figure out the actual
values of all inputs to the function. so, the first step is to
determine that b is 7 and a is
5. next, another new scope is created, but this time, the
actual values of the inputs are 7 and 5, so
the variables a and b in the
max scope will have values 7 and
5, respectively.
in other words, the a in max contains the
value of the b in main, and the
b in max contains the value of
a in main!
next, we run the stuff in the body of the function definition, which
is the if statement. we find that the value in
a is bigger than the value in b
[7 is bigger than 5, so we
return the value in a, which is 7.
to summarize, these are the steps involved in calling a function:
now tell me what these function calls do, if i add them to the
main above:
int e,f,g; e=max(c,d); f=max(5+1,7); g=max(9,max(a,c));
there are no special rules for calling functions that accept pointers as inputs. just remember that the value of a pointer is the address of the thing it's pointing to. let's take a look at what the following program does:
void square(int* x);
void main()
{
int x = 5;
square(&x);
}
void square(int* x)
{
(*x) = (*x) * (*x);
}
let's start in main. we create an integer variable called
x, and we set its value to be 5. after that,
we have a call to the square function.
the first step is to figure out the actual value of all the inputs. in
our case, the actual value of &x is the address of the
variable x that's defined in main.
next, we create a scope for square, and we create an
integer pointer called x in the new scope. the value of
this pointer is going to be the address of the variable x
that's defined in main, because that's the actual value
of the input to this function.
in other words, the x in square points at
the x in main.
now we need to run the stuff in the curly braces in the definition of
square in the new scope. (*x) means to look
at the value in the variable that x points at, so we look
at the value of the x in main, which is
5, we multiply that value by itself and get
25, then we store that value back in the x
in main.
here are some example structs:
/* this is not good */
struct bad
{
int x;
struct bad evil;
};
let's think about why the definition above is not good. we are
declaring a new type called "struct bad". this type
consists of two components: an integer called x, and
another struct bad called evil. so we have
another struct within our struct.
what's inside evil? well, it's another struct
bad, so it's got an integer x, and it also has its
own struct bad called evil. what's inside
this new evil? well, it's got an integer x,
and ...
hopefully you see where this is going. this struct has infinite size
[which means you can't have one, since our computers don't have
infinite memory], because each struct bad contains
another struct bad, which contains another struct
bad, etc.
here's another struct:
struct node
{
int x;
struct node* next;
};
this struct is okay. it contains an integer, and a pointer to another
struct node. since a pointer is just the address of
something else [and you can think of an address as a positive
integer], a struct node has a finite size. structs like
these are the building blocks for linked lists. as you can see, there
is a big difference between a struct and a pointer to a struct.
it's not always bad to have structs within structs. in fact, sometimes it cam make a lot of sense. consider this:
struct point
{
int x;
int y;
};
struct line
{
struct point start;
struct point end;
};
this says that points consists of an x and y coordinate, and that
lines consist of starting and ending points. it's okay to have structs
within structs, as long as you're not trying to put a struct inside
itself, like we did with bad above.
so how do we use these line things? here's an example:
void main()
{
struct line myline;
myline.start.x = 0;
myline.start.y = 0;
myline.end.x = 5;
myline.end.y = 5;
}
myline.start.x is just the name of an integer
variable. it's got a really long name, but it can still be used in all
the ways any other integer variable can be used.
malloc
by using malloc, our programs can ask the computer for
more memory when they are running. here's an example.
#include <stdio.h>
#include <stdlib.h>
void main()
{
int n,i;
int* a;
/* get an integer from the user */
scanf("%d", &n);
/* ask malloc for a piece of memory big enough to hold n integers,
* and use this piece of memory as an array of n integers */
a = (int*) malloc(n * sizeof(int));
/* get n integers from the keyboard, and store them in the array */
for(i=0; i < n; i++)
{
scanf("%d", &(a[i]));
}
/* print out the n integers */
for(i=0; i < n; i++)
{
printf("%d\n", a[i]);
}
/* tell the computer we don't need the piece of memory anymore */
free(a);
}
let's see what this program does. first, we make a couple of integer
variables, and a pointer to an integer. next, we read a value of
n from the keyboard.
now we have the malloc. let's look at this one piece at a
time. we have to tell malloc how many bytes of memory we
want. in our case, we want n * sizeof(int) bytes. this
means "use sizeof to figure out how many bytes are needed
for a single integer variable, then multiply that number by
n." so this is asking the computer for enough space to
hold n integer variables.
so malloc will go and get us a piece of memory big enough
for n integer variables, and it will return us a pointer
to this piece of memory. the (int*) in front of malloc
tells the computer that we want to treat the pointer returned by
malloc as a pointer to an integer.
finally, we set a to contain the pointer returned by
malloc.
a is now an array of n integers. why?
an array is just a whole bunch of variables of one type, arranged
back-to-back in memory, and we are asking malloc for a
piece of memory big enough to hold n integer variables
back-to-back. so we can use the piece of memory returned by
malloc as an array of integers.
the name of an array is just a pointer to the first element in the
array. in our program, malloc will return us a pointer to
the beginning of a piece of memory, and we save this pointer in
a, so a points to the beginning of the
array.
after we do this malloc, we can use a just like any other
array of integers.
feof
feof returns true if we have read past the end of
the file.feof returns false if we are within the file, or if we are
at the end of the file.
this means that you should check feof right after every
fscanf, in case the fscanf just went past
the end of the file.
here's an example that counts the number of words in a file.
#include <stdio.h>
void main()
{
char buffer[256];
int n=0;
FILE* fp = fopen("input.txt", "r");
while(1)
{
fscanf(fp, "%s", buffer);
if(feof(fp))
break;
n++;
}
printf("%d\n", n);
}
trace this program if the input file contains "hello there", and verify that the word count comes out right.