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 thenewitem'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.