[ Pobierz całość w formacie PDF ]
be used later. The structure is nearly the same as that used in the last two programs except for
the addition of another field within the structure, the pointer. This pointer is a pointer to another
structure of this same type and will be used to point to the next structure in order. To continue
the above analogy, this pointer will point to the next note, which in turn will contain a pointer
to the next note after that.
We define three pointers to this structure for use in the program, and one integer to be used as
a counter, and we are ready to begin using the defined structure for whatever purpose we desire.
In this case, we will once again generate nonsense data for illustrative purposes.
12-6 C Tutorial Dynamic Allocation
12.13 The First Field
Using the "malloc" function, we request a block of storage on the "heap" and fill it with data.
The additional field in this example, the pointer, is assigned the value of NULL, which is only
used to indicate that this is the end of the list. We will leave the pointer "start" at this structure,
so that it will always point to the first structure of the list. We also assign "prior" the value of
"start" for reasons we will see soon. Keep in mind that the end points of a linked list will always
have to be handled differently than those in the middle of a list. We have a single element of
our list now and it is filled with representative data.
12.14 Filling Additional Structures
The next group of assignments and control statements are included within a "for" loop so we
can build our list fast once it is defined. We will go through the loop a number of times equal
to the constant "RECORDS" defined at the beginning of our program. Each time through, we
allocate memory, fill the first three fields with nonsense, and fill the pointers. The pointer in
the last record is given the address of this new record because the "prior" pointer is pointing to
the prior record. Thus "prior->next" is given the address of the new record we have just filled.
The pointer in the new record is assigned the value "NULL", and the pointer "prior" is given
the address of this new record because the next time we create a record, this one will be the prior
one at that time. That may sound confusing but it really does make sense if you spend some
time studying it.
When we have gone through the "for" loop 6 times, we will have a list of 7 structures including
the one we generated prior to the loop. The list will have the following characteristics.
1. "start" points to the first structure in the list.
2. Each structure contains a pointer to the next structure.
3. The last structure has a pointer that points to NULL and can be used to detect the end
as shown below.
start->struct1 name breed age point->struct2 name breed age
point->struct3 name breed age point-> . . . . struct7 name breed age
point->NULL
It should be clear to you, if you understand the above structure, that it is not possible to simply
jump into the middle of the structure and change a few values. The only way to get to the third
structure is by starting at the beginning and working your way down through the structure one
record at a time. Although this may seem like a large price to pay for the convenience of putting
so much data outside of the program area, it is actually a very good way to store some kinds of
data.
A word processor would be a good application for this type of data structure because you would
never need to have random access to the data. In actual practice, this is the basic type of storage
used for the text in a word processor with one line of text per record. Actually, a program with
any degree of sophistication would use a doubly linked list. This would be a list with two
pointers per record, one pointing down to the next record, and the other pointing up to the record
just prior to the one in question. Using this kind of a record structure would allow traversing
the data in either direction.
12.15 Printing The Data Out
To print the data out, a similar method is used as that used to generate the data. The pointers
are initialized and are then used to go from record to record reading and displaying each record
one at a time. Printing is terminated when the NULL on the last record is found, so the program
[ Pobierz całość w formacie PDF ]