home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Simtel MSDOS 1992 September
/
Simtel20_Sept92.cdr
/
msdos
/
pascal
/
pasctxt.arc
/
CHAP12.TXT
< prev
next >
Wrap
Text File
|
1988-01-15
|
31KB
|
719 lines
CHAPTER 12 - Pointers and Dynamic Allocation
For certain types of programs, pointers and dynamic
allocation can be a tremendous advantage, but many programs
do not need such a high degree of data structure. For that
reason, it would probably be to your advantage to lightly
skim over these topics and come back to them later when you
have a substantial base of Pascal programming experience.
It would be good to at least skim over this material rather
than completely neglecting it, so you will have an idea of
how pointers and dynamic allocation work and that they are
available for your use when needed.
A complete understanding of this material will require
deep concentration as it is complex and not at all
intuitive. Nevertheless, if you pay close attention, you
will have a good grasp of pointers and dynamic allocation in
a short time.
WHAT ARE POINTERS, AND WHAT GOOD ARE THEY?
Examine the program named POINT for your first example
of a program using pointers. In the var declaration you
will see two variables named Where and Who that have the
symbol ^ in front of their types. This defines them, not as
variables, but as pointers to integer type variables. In
line 12 of the program, the variable Index is assigned the
value of 17 for purposes of illustration. The pointer named
Where is then assigned the address of the variable Index
which means that it does not contain the value of 17, it
contains the address of the storage location where the
variable Index is stored. In like manner, we assign the
address of Index to the pointer named Who. It should be
obvious to you that Addr is a TURBO Pascal function that
returns the address of its argument.
HOW DO WE USE THE POINTERS?
It should be clear to you that we now have a single
variable named Index with two pointers pointing at it. If
the pointers are useful, we should be able to do something
with them now, so we simply print out the same variable
three different ways in line 15. When we write "Where^", we
are telling the system that we are not interested in the
pointer itself but instead we are interested in the data to
which the pointer points. This is referred to as
dereferencing the pointer. Careful study of the output
fields in line 15 will reveal that we first display the
value of Index, then the value to which the pointer Where
points, and finally the value to which the pointer Who
points. Since both pointers point to the variable Index, we
are essentially displaying the value of Index three times.
You will confirm this when you compile and run this program.
Page 73
CHAPTER 12 - Pointers and Dynamic Allocation
In line 17, we tell the system to assign the value of
23 to the variable to which the pointer Where points as an
illustration. If you understood the discussion in the
previous paragraph, you will understand that we are actually
assigning the variable named Index the value of 23 because
that is where the pointer named Where is pointing. In line
18, we once again display the value of the variable Index 3
times just as we did in line 15. It would be to your
advantage to compile and run this program to see that the
value of 17 is output three times, then the value of 23 is
output three times.
In a program as simple as this, the value of pointers
is not at all clear but a simple program is required in
order to make the technique clear. Display the program
named POINT on your monitor again because we are not yet
finished with it.
A FEW MORE POINTERS
In line 4, we define a new type named Int_Point which
is a pointer to an integer type variable. We use this new
type in line 9 to define three more pointers and in line 20,
we assign one of them the address of the variable named
Index. Since the pointers are of identical types, in line
21 we can assign Pt2 the value of Pt1, which is actually the
address of the variable named Index. Likewise, the pointer
Pt3 is assigned the value of Pt2, and we have all three
pointers pointing to the variable named Index. If you are
using TURBO Pascal version 4.0, you are allowed to assign
pointers like this only if they have the same type, which
these three do. However, since the pointers named Where and
Who are assigned individually, they are not of the same type
according to the rules of Pascal and if line 14 were changed
to read "Who := Where;", a compilation error would occur
with TURBO Pascal version 4.0. This error would not occur
with TURBO Pascal 3.0 since it is a little less stringent in
its type checking.
Finally, we assign the only variable in this program
which is named Index the value of 151 in line 23 and display
the value 151 three times as we did above. Compile and run
this program again to see that it does indeed display the
value 151 three times.
THIS IS JUST FOR TURBO PASCAL VERSION 4.0
If you are using TURBO Pascal version 4.0, you should
display the program named POINT4 on your monitor for an
example of another new extension to the Pascal programming
Page 74
CHAPTER 12 - Pointers and Dynamic Allocation
language by Borland. This program is identical to the last
except in lines 13, 14 and 20, where the symbol @ is used to
denote the address of the variable index rather than the
function "Addr". This is only available in TURBO Pascal
version 4.0 as a convenience to you. In ANSI standard
Pascal the @ symbol is used as a synonym for the ^ symbol
but Borland chose to use it for a completely different
purpose. If you are using TURBO Pascal 3.0, you will not be
able to compile and run this program, but nothing is lost
because it is identical to the previous one.
OUR FIRST LOOK AT DYNAMIC ALLOCATION
If you examine the file named POINTERS, you will see a
very trivial example of pointers and how they are used with
dynamically allocated variables. In the var declaration,
you will see that the two variables have a ^ in front of
their respective types once again, defining two pointers.
They will be used to point to dynamically allocated
variables that have not yet been defined.
The pointer My_Name is a pointer to a 20 character
string. The pointer actually points to an address somewhere
within the computer memory, but we don't know where yet.
Actually, there is nothing for it to point at because we
have not defined a variable. After we assign it something
to point to, we can use the pointer to access the data
stored at that address.
Your computer has some amount of memory installed in
it. If it is an IBM-PC or compatible, it can have up to 640K
of RAM which is addressable by various programs. The
operating system requires about 60K of the total, and if you
are using TURBO Pascal version 3.0, it requires about 35K,
but if you are using version 4.0, it requires about 110K.
The TURBO Pascal program can use up to 64K. Adding those
three numbers together results in about 159K or 234K. Any
memory you have installed in excess of that is available for
the stack and the heap. The stack is a standard area
defined and controlled by DOS that can grow and shrink as
needed. Many books are available to define the stack and
its use if you are interested in more information on it.
WHAT IS THE HEAP?
The heap is a Pascal defined entity that utilizes
otherwise unused memory to store data. It begins
immediately following the program and grows as necessary
upward toward the stack which is growing downward. As long
as they never meet, there is no problem. If they meet, a
run-time error is generated. The heap is therefore outside
Page 75
CHAPTER 12 - Pointers and Dynamic Allocation
of the 64K limitation of TURBO Pascal and many other Pascal
compilers.
TURBO Pascal version 4.0 does not limit us to 64K, but
there are other reasons for using the heap in addition to
the 64K limitation. These should be evident as we learn how
the heap works.
If you did not understand the last few paragraphs,
don't worry. Simply remember that dynamically allocated
variables are stored on the heap and do not count in the 64K
limitation placed upon you by some compilers.
Back to our example program, POINTERS. When we
actually begin executing the program, we still have not
defined the variables we wish to use to store data in. The
first executable statement in line 10 generates a variable
for us with no name and stores it on the heap. Since it has
no name, we cannot do anything with it, except for the fact
that we do have a pointer My_Name that is pointing to it.
By using the pointer, we can store up to 20 characters in
it, because that is its type, and later go back and retrieve
it.
WHAT IS DYNAMIC ALLOCATION?
The variable we have just described is a dynamically
allocated variable because it was not defined in a var
declaration, but with a "New" procedure. The "New"
procedure creates a variable of the type defined by the
pointer, puts it on the heap, and finally assigns the
address of the variable to the pointer itself. Thus
My_Name contains the address of the variable generated. The
variable itself is referenced by using the pointer to it
followed by a ^, just like in the last program, and is read,
"the variable to which the pointer points".
The statement in line 11 assigns a place on the heap to
an integer type variable and puts its address in My_Age.
Following the "New" statements we have two assignment
statements in which the two variables pointed at are
assigned values compatible with their respective types, and
they are both written out to the video display in much the
same manner as we did in the program named POINT.
GETTING RID OF DYNAMICALLY ALLOCATED DATA
The two statements in lines 19 and 20 are illustrations
of the way the dynamically allocated variables are removed
from use. When they are no longer needed, they are disposed
Page 76
CHAPTER 12 - Pointers and Dynamic Allocation
of with the Dispose procedure which frees up their space on
the heap so it can be reused.
In such a simple program, pointers cannot be
appreciated, but it is necessary for a simple illustration.
In a large, very active program, it is possible to define
many variables, dispose of some of them, define more, and
dispose of more, etc. Each time some variables are disposed
of, their space is then made available for additional
variables defined with the "New" procedure.
The heap can be made up of any assortment of variables,
they do not have to all be the same. One point must be kept
in mind. Anytime a variable is defined, it will have a
pointer pointing to it. The pointer is the only means by
which the variable can be accessed. If the pointer to the
variable is lost or changed, the data itself is lost for all
practical purposes.
Compile and run this program and examine the output.
DYNAMICALLY STORING RECORDS;
The next example program, DYNREC, is a repeat of one we
studied in an earlier chapter. For your own edification,
review the example program BIGREC before going ahead in this
chapter. Assuming that you are back in DYNREC, you will
notice that this program looks very similar to the earlier
one, and in fact they do exactly the same thing. The only
difference in the type declaration is the addition of a
pointer Person_Id, and in the var declaration, the first
four variables are defined as pointers here, and were
defined as record variables in the last program.
A point should be made here. Pointers are not
generally used in very small programs. This program is a
good bit larger than the last and should be a clue to you as
to why such a trivial program was used to introduce pointers
in this tutorial. A very small, concise program can
illustrate a topic much better that an large complex
program, but we must go on to more useful constructs of any
new topic.
WE JUST BROKE THE GREAT RULE OF PASCAL
Notice in the type declaration that we used the
identifier Person in line 18 before we defined it in line
19, which is illegal to do in Pascal. Foreseeing the need
to define a pointer prior to the record, the designers of
Pascal allow us to break the rule in this one place. The
pointer could have been defined after the record in this
Page 77
CHAPTER 12 - Pointers and Dynamic Allocation
particular case, but it was more convenient to put it
before, and in the next example program, it will be required
to put it before the record. We will get there soon.
Since Friend is really 50 pointers, we have now defined
53 different pointers to records, but so far have defined no
variables other than Temp and Index. We immediately use the
New procedure to dynamically allocate a record with Self
pointing to it, and use the pointer so defined to fill the
dynamically allocated record. Compare this to the program
named BIGREC and you will see that it is identical except
for the addition of the "New" and adding the ^ to each use
of the pointer to designate the data pointed to.
THIS IS A TRICK, BE CAREFUL
Now go down to line 48 where Mother is allocated a
record and is then pointing to the record. It seems an easy
thing to do then to simply assign all of the values of self
to all the values of mother as shown in the next statement,
but it doesn't work. All the statement does, is make the
pointer Mother point to the same place where Self is
pointing because we did a pointer assignment. The data that
was allocated to the pointer Mother is now somewhere on the
heap, but we don't know where, and we cannot find it, use
it, or deallocate it. This is an example of losing data on
the heap. The proper way is given in the next two
statements where all fields of Father are defined by all
fields of Mother which is pointing at the original Self
record. Note that since Mother and Self are both pointing
at the same record, changing the data with either pointer
results in the data appearing to be changed in both because
there is, in fact, only one field where the data is stored.
In order to Write from or Read into a dynamically
assigned record it is necessary to use a temporary record
since dynamically assigned records are not allowed to be
used in I/O statements. This is illustrated in lines 57
through 63 of the program where some data is written to the
monitor.
Finally, the dynamically allocated variables are
disposed of prior to ending the program. For a simple
program such as this, it is not necessary to dispose of them
because all dynamic variables are disposed of automatically
when the program is terminated and we return to DOS or the
TURBO Pascal integrated environment. Notice that if the
"Dispose(Mother);" statement was included in the program,
the data could not be found due to the lost pointer, and the
program would be unpredictable, probably leading to a system
crash.
Page 78
CHAPTER 12 - Pointers and Dynamic Allocation
SO WHAT GOOD IS THIS ANYWAY?
Remember when you were initially studying BIGREC? I
suggested that you see how big you could make the constant
Number_Of_Friends before you ran out of memory. At that
time we found that it could be made slightly greater than
1000 before we got the memory overflow message at
compilation. Try the same thing with DYNREC to see how many
records it can handle, remembering that the records are
created dynamically, so you will have to run the program to
actually run out of memory. The final result will depend on
how much memory you have installed, and how many memory
resident programs you are using such as "Sidekick". If you
have a full memory of 640K, I would suggest you start
somewhere above 8000 records of Friend.
Now you should have a good idea of why Dynamic
Allocation can be used to greatly increase the usefulness of
your programs. There is, however, one more important topic
we must cover on dynamic allocation. That is the linked
list.
WHAT IS A LINKED LIST?
Understanding and using a linked list is by far the
most baffling topic you will confront in Pascal. Many
people simply throw up their hands and never try to use a
linked list. I will try to help you understand it by use of
an example and lots of explanation. Examine the program
named LINKLIST for an example of a linked list. I tried to
keep it short so you could see the entire operation and yet
do something meaningful.
To begin with, notice that there are two types defined
in lines 4 and 6, a pointer to the record and the record
itself. The record, however, has one thing about it that is
new to us, the last entry, Next is a pointer to another
record of this type. This record then, has the ability to
point to itself, which would be trivial and meaningless, or
to another record of the same type which would be extremely
useful in some cases. In fact, this is the way a linked
list is used. I must point out, that the pointer to another
record, in this case called Next, does not have to be last
in the list, it can be anywhere it is convenient for you.
A couple of pages ago, we discussed the fact that we
had to break the great rule of Pascal and use an identifier
before it was defined. This is the reason the exception to
the rule was allowed. Since the pointer points to the
record, and the record contains a reference to the pointer,
Page 79
CHAPTER 12 - Pointers and Dynamic Allocation
one has to be defined after being used, and by rules of
Pascal, the pointer can be defined first, provided that the
record is defined immediately following it. That is a
mouthful but if you just use the syntax shown in the
example, you will not get into trouble with it.
STILL NO VARIABLES?
It may seem strange, but we still will have no
variables defined, except for our old friend Index. In fact
for this example, we will only define 3 pointers. In the
last example we defined 54 pointers, and had lots of storage
room. Before we are finished, we will have at least a dozen
pointers but they will be stored in our records, so they too
will be dynamically allocated.
Lets look at the program itself now. In line 20, we
create a dynamically allocated record and define it by the
pointer Place_In_List. It is composed of the three data
fields, and another pointer. We define Start_Of_List to
point to the first record created, and we will leave it
unchanged throughout the program. The pointer Start_Of_List
will always point to the first record in the linked list
which we are building up.
WHAT IS "nil" AND WHAT IS IT USED FOR?
We define the three variables in the record to be any
name we desire for illustrative purposes, and set the
pointer in the record to "nil". The word nil is another
reserved word that doesn't give the pointer an address but
defines it as empty. A pointer that is currently nil cannot
be used to manipulate data because it has no value, but it
can be tested in a logical statement to see if it is nil.
It is therefore a dummy assignment. With all of that, the
first record is completely defined.
DEFINING THE SECOND RECORD
When you were young you may have played a searching
game in which you were given a clue telling you where to
find the next clue. The next clue had a clue to the
location of the third clue. You kept going from clue to
clue until you found the prize. You simply exercised a
linked list. We will now build up the same kind of a list
in which each record will tell us where the next record is
at.
In lines 27 through 33 we will define the second
record. Our goal will be to store a pointer to the second
record in the pointer field of the first record. In order
Page 80
CHAPTER 12 - Pointers and Dynamic Allocation
to keep track of the last record, the one in which we need
to update the pointer, we will keep a pointer to it in
Temp_Place. Now we can dynamically allocate another New
record and use Place_In_List to point to it. Since
Temp_Place is now pointing at the first record, we can use
it to store the value of the pointer which points to the new
record which we do in line 29. The 3 data fields of the new
record are assigned nonsense data for our illustration, and
the pointer field of the new record is assigned nil.
Lets review our progress to this point. We now have
the first record with a person's name and a pointer to the
second record, and a second record with a different person's
name and a pointer assigned nil. We also have three
pointers, one pointing to the first record, one pointing to
the last record, and one we used just to get here since it
is only a temporary pointer. If you understand what is
happening so far, lets go on to add some additional records
to the list. If you are confused, go back over this
material again.
TEN MORE RECORDS
The next section of code is contained within a for loop
so the statements are simply repeated ten times. If you
observe carefully, you will notice that the statements are
identical to the second group of statements in the program
(except of course for the name assigned). They operate in
exactly the same manner, and we end up with ten more names
added to the list. You will now see why the temporary
pointer was necessary, but pointers are cheap, so feel free
to use them at will. A pointer only uses 4 bytes of memory.
FINALLY, A COMPLETE LINKED LIST
We now have generated a linked list of twelve entries.
We have a pointer pointing at the first entry, and another
pointer pointing at the last. The only data stored within
the program itself are three pointers, and one integer, all
of the data is on the heap. This is one advantage to a
linked list, it uses very little local memory, but it is
costly in terms of programming. (Keep in mind that all of
the data must be stored somewhere in memory, and in the case
of the linked list, it is stored on the heap.) You should
never use a linked list simply to save memory, but only
because a certain program lends itself well to it. Some
sorting routines are extremely fast because of using a
linked list, and it could be advantageous to use in a
database.
Page 81
CHAPTER 12 - Pointers and Dynamic Allocation
Following is a graphical representation of what the
linked list looks like.
Start_Of_List---->John
Q
Doe
Next---->Mary
R
Johnson
Next---->William
S
Jones
Next---->
.
.
.
---->William
S
Jones
Next---->nil
HOW DO WE GET TO THE DATA NOW?
Since the data is in a list, how can we get a copy of
the fourth entry for example? The only way is to start at
the beginning of the list and successively examine pointers
until you reach the desired one. Suppose you are at the
fourth and then wish to examine the third. You cannot back
up, because you didn't define the list that way, you can
only start at the beginning and count to the third. You
could have defined the record with two pointers, one
pointing forward, and one pointing backward. This would be
a doubly-linked list and you could then go directly from
entry four to entry three.
Now that the list is defined, we will read the data
from the list and display it on the video monitor. We begin
by defining the pointer, Place_In_List, as the start of the
list. Now you see why it was important to keep a copy of
where the list started. In the same manner as filling the
list, we go from record to record until we find the record
with nil as a pointer.
There are entire books on how to use linked lists, and
most Pascal programmers will seldom, if ever, use them. For
this reason, additional detail is considered unnecessary,
but to be a fully informed Pascal programmer, some insight
is necessary.
Page 82
CHAPTER 12 - Pointers and Dynamic Allocation
PROGRAMMING EXERCISE
1. Write a program to store a few names dynamically, then
display the stored names on the monitor. As your first
exercise in dynamic allocation, keep it very simple.
Page 83
