Objectives
This section contains some very advanced but important features of the C programming language.
Having read this section you should be able to:
- program using a structure rather than several arrays.
- how pointer can be used in combination with structures to form linked list.
Structures
The array is an example of a data structure. It takes simple data types like
int,
char or
double
and organises them into a linear array of elements. The array serves
most but not all of the needs of the typical C program. The restriction
is that an array is composed of elements all of the same type. At first
this seems perfectly reasonable. After all why would you want an array
to be composed of twenty
chars and two
ints? Well this
sort of mixture of data types working together is one of the most
familiar of data structures. Consider for a moment a record card which
records
name,
age and
salary. The name would have to be stored as a
string, i.e. an array of chars terminated with an ASCII null character, and the age and salary could be
ints.
At the moment the only way we can work with this collection of data is as separate variables. This isn't as convenient as a
single data structure using a single name and so the C language provides
struct. At first it is easier to think of this as a record - although it's a little more versatile than this suggests.
Defining A New Type
Declaring a
struct is a two-stage process. The first stage
defines a new data type that has the required structure which can then
be used to declare as many variables with the same structure as
required. This two-stage process is often confusing at first -
especially as it results in the need to think up multiple names with the
same general meaning - but it really is quite simple. For example,
suppose we need to store a name, age and salary as a single structure.
You would first define the new data type using:
struct emprec
{
char name[25];
int age;
int pay;
};
and then you would declare a new variable:
struct emprec employee
Notice that the new variable is called
employee and it is of type
emprec which has been defined earlier. You see what we mean about duplicating names -
emprec is the name of the general
employee record structure and
employee is a particular example of this general type. It might help to compare the situation with that of a general
int type and a particular
int variable such as
count -
emprec is a type like
int and
employee is a variable like
count. You can see that in general you can define a structure using:
struct name
{
list of component variables
};
and you can have as long a list of component variables as you need.
Once defined you can declare as many examples of the new type as you
like using:
struct name list of variables;
For example:
struct emprec employee, oldemploy, newemploy;
and so on. If you want to you can also declare a structure variable
within the type definition by writing its name before the final
semi-colon. For example:
struct emprec
{
char name[25];
int age;
int pay;
} employee;
defines the structure and declares a structure variable called
employee.
The only trouble with this form is that not many C programmers use it
and many will even think that it is an error! So how do we use a
struct?
When you first start working with arrays it seems obvious that you
access the individual elements of the array using an index as in
a[i]
for the ith element of the array, but how to get at the individual
components of a structure? The answer is that you have to use qualified
names. You first give the name of the structure variable and then the
name of the component separated by a dot. For example, given:
struct emprec employee
then:
employee.age
is an
int and:
employee.name
is a
char array. Once you have used a qualified name to get
down to the level of a component then it behaves like a normal variable
of the type. For example:
employee.age=32;
is a valid assignment to an
int and:
employee.name[2] = 'X';
is a valid assignment to an element of the
char array. Notice
that the qualified name uses the structure variable name and not the
structure type name. You can also define a structure that includes
another structure as a component and of course that structure can
contain another structure and so on. In this case you simply use the
name of each structure in turn, separated by dots, until you reach a
final component that isn't a structure. For example, if you declare a
struct firm which includes a component
employee which is an
emprec then:
firm.employee.age
is an
int. You may be feeling a little disappointed at the way
in which structures are used. When you first meet arrays it is obvious
how useful they are because the array index is an integer which can be
used within a loop to process vast amounts of data in a few lines of
code. When you first meet the
struct it just doesn't have the
same obvious advantages. Because you have to write out a full qualified
name to get at each of the components of the
struct you can't
automate the processing in the same way. However this is reasonable
enough when you remember that each component of a
struct can be a different data type! The point is that the value of a
struct is different to that of an array. A
struct can be used to wrap up a group of variables which form a coherent entity.
For example, C has no facilities for manipulating complex numbers but this is easy enough to put right using a
struct
and a few functions. A complex number is composed of two parts - a real
and imaginary part - which can be implemented as single or double
precision values. This suggests defining a new
struct type:
struct comp
{
float real;
float imag;
};
After this you can declare new complex variables using something like:
struct comp a,b;
The new complex variables cannot be used as if they were simple
variables - because they are not. Most versions, of the C language do
allow you to assign structures so you could write:
a=b;
as shorthand for
a.real=b.real;
a.imag=b.imag;
Being able to assign structures is even more useful when they are
bigger. However you can't expect C to sort out what you mean by
c = a + b - for this you have to write out the rule for addition as:
c.real=a.real+b.real;
c.imag=a.imag+b.imag;
Structures and Functions
Of course a sensible alternative to writing out the addition each
time is to define a function to do the same job - but this raises the
question of passing structures as parameters. Fortunately this isn't a
big problem. Most C compilers, will allow you to pass entire structures
as parameters and return entire structures. As with all C parameters
structures are passed by value and so if you want to allow a function to
alter a parameter you have to remember to pass a
pointer to a
struct. Given that you can pass and return
structs the function is fairly easy:
struct comp add(struct comp a , struct comp b)
{
struct comp c;
c.real=a.real+b.real;
c.imag=a.imag+ b.imag;
return c;
}
After you have defined the add function you can write a complex addition as:
x=add(y,z)
which isn't too far from the
x=y+z that you would really like to use. Finally notice that passing a
struct by value might use up rather a lot of memory as a complete copy of the structure is made for the function.
Pointers to Structures
You can define a pointer to a structure in the same way as any pointer to any type. For example:
struct emprec *ptr
defines a pointer to an
emprec. You can use a pointer to a
struct in more or less the same way as any pointer but the use of qualified names makes it look slightly different For example:
(*ptr).age
is the age component of the
emprec structure that
ptr points at - i.e. an
int. You need the brackets because '.' has a higher priority than '*'. The use of a pointer to a
struct
is so common, and the pointer notation so ugly, that there is an
equivalent and more elegant way of writing the same thing. You can use:
prt-££££age
to mean the same thing as
(*ptr).age. The notation gives a clearer idea of what is going on -
prt points (i.e.
-££££) to the structure and
.age picks out which component of the structure we want. Interestingly until C++ became popular the
-££££ notation was relatively rare and given that many C text books hardly mentioned it this confused many experienced C programmers!
There are many reasons for using a pointer to a
struct but one
is to make two way communication possible within functions. For
example, an alternative way of writing the complex number addition
function is:
void comp add(struct comp *a , struct comp *b , struct comp *c)
{
c-££££real=a-££££real+b-££££real;
c-££££imag=a-££££imag+b-££££imag;
}
In this case
c is now a pointer to a
comp struct and the function would be used as:
add(&x,&y,&z);
Notice that in this case the address of each of the structures is
passed rather than a complete copy of the structure - hence the saving
in space. Also notice that the function can now change the values of
x,
y and
z if it wants to. It's up to you to decide if this is a good thing or not!
Malloc
Now we come to a topic that is perhaps potentially the most
confusing. So far we have allowed the C compiler to work out how to
allocate storage. For example when you declare a variable:
int a;
the compiler sorts out how to set aside some memory to store the integer. More impressive is the way that
int a[50]
sets aside enough storage for 50
ints and sets the name
a
to point to the first element. Clever though this may be it is just
static storage. That is the storage is allocated by the compiler before
the program is run - but what can you do if you need or want to create
new variables as your program is running? The answer is to use
pointers and the
malloc function. The statement:
ptr=malloc(size);
reserves size bytes of storage and sets the pointer
ptr to
point to the start of it. This sounds excessively primitive - who wants a
few bytes of storage and a pointer to it? You can make
malloc look a little more appealing with a few cosmetic changes. The first is that you can use the
sizeof function to allocate storage in multiples of a given type. For example:
sizeof(int)
returns a number that specifies the number of bytes needed to store an
int. Using
sizeof you can allocate storage using
malloc as:
ptr= malloc(sizeof(int)*N)
where
N is the number of
ints you want to create. The only problem is what does
ptr
point at? The compiler needs to know what the pointer points at so that
it can do pointer arithmetic correctly. In other words, the compiler
can only interpret
ptr++ or
ptr=ptr+1 as an instruction to move on to the next
int if it knows that the
ptr is a
pointer to an
int. This works as long as you define the
ptr to be a pointer to the type of variable that you want to work with. Unfortunately this raises the question of how
malloc knows what the type of the
pointer variable is - unfortunately it doesn't.
To solve this problem you can use a
TYPE cast. This C play on words is a mechanism to force a value to a specific type. All you have to do is write the
TYPE specifier in brackets before the value. So:
ptr = (*int) malloc(sizeof(int)*N)
forces the value returned by
malloc to be a pointer to
int.
Now you can see how a simple idea ends up looking complicated. OK, so
now we can acquire some memory while the program is running, but how can
we use it? There are some simple ways of using it and some very subtle
mistakes that you can make in trying to use it! For example, suppose
during a program you suddenly decide that you need an
int array
with 50 elements. You didn't know this before the program started,
perhaps because the information has just been typed in by the user. The
easiest solution is to use:
int *ptr;
and then later on:
ptr = (*int) malloc(sizeof(int)*N)
where
N is the number of elements that you need. After this definition you can use
ptr as if it was a conventional array. For example:
ptr[i]
is the ith element of the array. The trap waiting for you to make a
mistake is when you need a few more elements of the array. You can't
simply use
malloc again to get the extra elements because the block of memory that the next
malloc
allocates isn't necessarily next to the last lot. In other words, it
might not simply tag on to the end of the first array and any assumption
that it does might end in the program simply overwriting areas of
memory that it doesn't own.
Another fun error that you are not protected against is losing an area of memory. If you use
malloc
to reserve memory it is vital that you don't lose the pointer to it. If
you do then that particular chunk of memory isn't available for your
program to use until it is restarted.
Structures and Linked Lists
You may be wondering why
malloc has been introduced right after the structure. The answer is that the dynamic allocation of memory and the
struct go together a bit like the array and the
for loop. The best way to explain how this all fits together is via a simple example. You can use
malloc
to create as many variables as you want as the program runs, but how do
you keep track of them? For every new variable you create you also need
an extra pointer to keep track of it. The solution to this otherwise
tricky problem is to define a
struct which has a pointer as one of its components. For example:
struct list
{
int data;
struct list *ptr;
};
This defines a structure which contains a single
int and -
something that looks almost paradoxical - a pointer to the structure
that is being defined. All you really need to know is that this is
reasonable and it works. Now if you use
malloc to create a new
struct you also automatically get a new pointer to the
struct. The final part of the solution is how to make use of the pointers. If you start off with a single 'starter' pointer to the
struct you can create the first new
struct using
malloc as:
struct list *start;
start = (*struct list) malloc(sizeof(struct list))
After this start points to the first and only example of the
struct. You can store data in the struct using statements like:
start-££££data=value;
The next step is to create a second example of the
struct:
start = (*struct list) malloc(sizeof(list));
This does indeed give us a new
struct but we have now lost the original because the pointer to it has been overwritten by the pointer to the new
struct. To avoid losing the original the simplest solution is to use:
struct list *start,newitem;
newitem = (*struct list) malloc(sizeof(struct list));
start-££££prt=start;
start=newitem;
This stores the location of the new
struct in
newitem. Then it stores the pointer to the existing
struct into the
newitem's pointer and sets the start of the list to be the
newitem. Finally the start of the list is set to point at the new
struct.
This procedure is repeated each time a new structure is created with
the result that a linked list of structures is created. The pointer
start always points to the first
struct in the list and the
prt component of this
struct
points to the next and so on. You should be able to see how to write a
program that examines or prints the data in each of the structures. For
example:
thisptr=start;
while (1==1)
{
printf("%d",thisprt-££££ data);
thisprt=thisprt-££££prt;
}
This first sets
thisptr to the start of the list, prints the data in the first element and then gets the pointer to the next
struct
in the list and so on. How does the program know it has reached the end
of the list? At the moment it just keeps going into the deep and
uncharted regions of your machine's memory! To stop it we have to mark
the end of the list using a null pointer. Usually a pointer value of 0
is special in that it never occurs in a pointer pointing at a valid area
of memory. You can use 0 to initialise a pointer so that you know it
isn't pointing at anything real. So all we have to do is set the last
pointer in the list to 0 and then test for it That is:
thisptr=start;
while (thisptr!=0)
{
printf("%d",thisprt-££££data);
thisprt=thisprt-££££ prt;
}
To be completely correct you should
TYPE cast 0 to be a pointer to the
struct in question. That is:
while (thisptr!=(struct list*)0)
By generally mucking about with
pointers stored in the list
you can rearrange it, access it, sort it, delete items and do anything
you want to. Notice that the structures in the list can be as
complicated as you like and, subject to there being enough memory, you
can create as many structures as you like.
You can use the same sort of technique to create even more
complicated list structures. For example you can introduce another
pointer into each structure and a pointer to the end of the list so that
you can work your way along it in the other direction -
a doubly linked list. You can create
stacks,
queues,
trees
and so on. The rest of the story is a matter of either inventing these
data structures for yourself or looking them up in a suitable book.
Structures and C++
The reason why structures are even more important for today's budding C programmer is that they turn into
classes in C++. A
class is a structure where you can define components that are functions. In this case the same distinction between a data
TYPE and an example of the
TYPE, i.e. a variable, is maintained only now the instances of the
class include functions as well as data. The same qualified naming system applies to the
class and the use of pointers and the
-££££ operator. As this is the basis of C++'s object-oriented features it is important to understand.
Header Files
The final mystery of C that needs to be discussed is the
header file.
This started off as a simple idea, a convenience to make programming
easier. If you have a standard set of instructions that you want to
insert in a lot of programs that you are writing then you can do it
using the
#include statement.
The
# symbol at the start indicates that this isn't a C
statement but one for the C pre-processor which looks at the text file
before the compiler gets it. The
#include tells the pre-processor to read in a text file and treat it as if it was part of the program's text. For example:
#include "copy.txt"
could be used to include a copyright notice stored in the file
copy.txt. However the most common use of the
#include is to define
constants and
macros. The C pre-processor is almost a language in its own right For example, if you define the identifier
NULL as:
#define NULL 0
then whenever you use
NULL in your program the pre-processor
substitutes 0. In most cases you want these definitions to be included
in all your programs and so the obvious thing to do is to create a
separate file that you can
#include.
This idea of using standard include files has spiralled out of all proportions. Now such include files are called
header files and they are distinguished by ending in the extension
.h.
A header file is generally used to define all of the functions,
variables and constants contained in any function library that you might
want to use. The header file
stdio.h should be used if you want to use the two standard I/O functions
printf and
scanf. The standard libraries have been covered in a previous section.
This sort of use of header files is simple enough but over time more
and more standard elements of the C environment have been moved into
header files. The result is that header files become increasingly
mysterious to the beginner. Perhaps they reach their ultimate in
complexity as part of the Windows development environment So many
constants and macros are defined in the Windows header files that they
amount to hundreds of lines! As another example of how you could use a
header file consider the complex structure defined earlier. At the
moment it looks messy to declare a new complex variable as:
struct comp a,b;
If you want to make the complex TYPE look like other data types all you need is a single
#define
#define COMPLEX struct comp
After this you can write:
COMPLEX a,b;
and the pre-processor will automatically replace
COMPLEX by
struct comp for you when you compile the program. Put this
#define and any others needed to make the complex number type work and you have the makings of a
complex.h header file of your very own.
