Structures

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
{
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.

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.

For example:
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. 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.

Structures and Functions

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

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.

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. The statement:

ptr=malloc(size);

reserves size bytes of storage and sets the pointer ptr to point to the start of it. 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 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.

Structures and Linked Lists

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. 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. 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 *star;
start = (*struct list) malloc(sizeof(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(list));
start->prt=start;
start=newitem;

This stores the location of the new struct in new item. Then it stores the pointer to the existing struct into the new item's pointer and sets the start of the list to be the new item. 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.

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. 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;
}