TOPIC O: pointers
Contents :
POINTER, NEW, DISPOSE.
Theory
Exercises :
SOME HINTS!
Theory about pointers
Why pointers? So far we could make all our programs without ever using
them.
"What so convenient about pointers?" is the question you should ask
yourself.
"Don't I have everything I need?"
- I can declare all the variables I want (as much as I want!).
- I can make my own types to suite my needs.
- Using open arrays for procedure parameters I can make my
procedure
flexible.
All that is true! But is real life problems you can not always foresee
how
much data you will have. Ok, the primitive strategy is to take enough
space.
For example, huge arrays. But what a waste of memory! And there still
is
a maximum whatever value you chose there will always be a point where
you
program will have to report something like : "The phonebook is full."
And that can happen really quickly for real programs. Just think if
you would make a MP3 catalogue. Files in this format are easy to find,
you
can download tons of them everyday. Result, after 2 months you have
recompile
your program! How convenient... Except if you could increase the memory your
program needs during its execution!!!
Well you can do that! With POINTERS, can you believe it!! Pointers
are not difficult, you need to handle them just a little differently
compared to normal variables.
In Modula-2 :
Facts about pointers in Modula-2:
- a pointer = an address in the
memory of the computer
- a variable!
- you usually do not give it a
value! (you can)
- you use the value (see later)
- NIL is a special value
- pointer are not memory!
(a browser is not the internet...)
Declaration :
The declaration does not differ a
lot from the declaration of normal variables. You just put POINTER
TO in front of the type. Declaration of a normal integer:
i : INTEGER;
Declaration of pointer to an integer:
i_ptr : POINTER TO INTEGER;
That was not so hard, was it? There is
nothing
more to it! The same goes for you own types, just put POINTER TO in
front.
How to use it :
The big difference with pointers
is their usage. A pointer contains an address. That is thet number of
one of the memory cells of the computer. What you care about is not
that number but the content of the memory cell. After all that were you
put or get your
data.
FACTS:
- no-one cares about the
pointers
themselves
- you care about the data which
can be accessed using the pointer
Ok, how do I access the memory cells
then? Well, you need to tell Modula-2 you want the data not the
address. This is
done very easily using 1 character: ^
. No typo here, it is the little hat
that we need. You put it behind the pointer
and all the sudden the combination can be used like a normal variable.
Consider
this little piece of Modula-2.
BEGIN
(* Some initial stuff ... *)
i :=
i_ptr^; (* A *)
i_ptr^ :=
0; (* B *)
END;
How to understand this?
- A) Say that i_ptr contained a valid address to some memory
cell containing a integer. We want to transfer the value of that memory
cell
in our integer i. Well the little ^ is the way in Modula-2 the access
the
memory cell. So the value of that cell is put into i.
- B) And since we are it we will store a new value (0) into
that memory cell.
A last important point: getting addresses in memory. Pointer are just
addresses. They are only useful for accessing memory. Pointers do not
give memory. You need to get memory
separately (called allocation).
FACTS
- you can not do this yourself!
- use the procedures provided by the SYSTEM module.
- you can reserve memory (ALLOCATION)
- you can release memory you reserved previously (DEALLOCATION)
There are special procedures which can reserve memory for you. You
should use these otherwise you can damage data in very strange location
in memory. Once you do not use some memory anymore you should
cancel your reservation. There is again a special function for that.
Example :
MODULE memory;
FROM SYSTEM IMPORT NEW, DISPOSE;
FROM IO IMPORT WrStr, WrLn;
VAR
i_ptr : POINTER TO INTEGER;
i : INTEGER;
BEGIN
WrStr("Start");
WrLn;
(* We reserve some memory for 1 integer *)
NEW(i_ptr);
i_ptr^ := 9;
i := i_ptr^;
(* We tell the computer we will not use
this
memory anymore *)
DISPOSE(i_ptr);
WrStr("Stop");
WrLn;
END memory.
CHECK SYNTAX
FAQ:
- I get a invalid
location error when I execute my program: your are accessing an address
you
did not reserve!
- Why use DISPOSE ? It allows the system to recycle the
unused memory. If you keep reserving
memory your computer will soon run out of memory.
- Suddenly NEW returns a NIL value. There is no free
memory left, so the computer lets
you know that with this special value.
- I get a mistake
when my program uses DISPOSE : you probably specify an address
which
isn't reserved anymore.
My program suddenly give invalid location errors but it worked a few
lines
before with the same pointer. : Is this pointer still valid? Didn't you
dispose
the memory or change the value of the pointer?
D1:
See S4
for a demo, but that's already a complex program.
S1: Dynamic Memory Allocation
Hint / topic :
Declaring pointers is not
so different from normal variables. Using them
neither. But remember you now need to ask for memory yourself. This is
referred
to as dynamic memory allocation.
Question :
Make a program which will
use 2 arrays of REALs of the same size (e.g. 10).
But the first one will be a normal variable (just like before) and the
second
a dynamically allocated array. Give the standard array some values
(whatever)
and copy them in the second array.
Print the values of the different
array
in order to compare on screen. Use the open-array print procedure of Topic
F.
Do not forget to deallocate the
array when your program does not need it
anymore.
S2: Linked Lists
Hint / topic :
In the previous exercise
we could decide upon the size of an array at runtime. Here we will make
a structure
which uses pointers which can grow in size dynamically. This is the
kind of stuff we
are interested in when we use pointers.
Typical for the use of pointers
are recursive data structures. In
other words structures which seem to be made of well the same
structures
(again). Example are linked lists and trees.
- LinkedL := Link + LinkedL';
- Tree := Node + Tree' + Tree";
HINT: recursive procedure are very
handy in combination with recursive data structures.
Question :
Make a program which will
uses a linked list (LL) containing information
about MP3 music files. Put some information about the size, artist,
title,
bit rate of each file in the list. Get some inspiration in your theory
book
on how to do this. Write several procedures:
- to add files to the list (to
create the linkd list)
- find the biggest file (size)
- print the entire list
- give the length of the list
- deallocate the entire list.
this should be done at the end of the program.
First draw on paper how this
procedures should be done.
Remark: these procedures will be
similar for all kinds of linked lists.
S3: Binary Tree
Hint / topic :
Trees are frequently used
because the offer a good performance for search
operations. But they require more attention while programming as things
get
messed up very quickly.
Question :
- Start with this code, it
defines a tree for characters and creates an initial tree.
- Create a procedure that prints the tree from left to right
(leftmost node first). Is the tree in alphabetical order?
- The
purpose of this exercise is to write a function which takes a tree as
parameter
and reverse it (mirror). So after calling your function the tree has
changed.
It is not so the you make a new tree.
(Again try to solve this problem on paper first. Try to discover the
necessary step first, then program them.)
S4: Plot Figures
- Run
de demo & bestudeer ze
- Is
het programma niet zo geschreven dat je boven-links begint met je
figuurtjes te tekenen?
- Hoe
komt het dat ze van het midden naar buiten worden getekend?
- Laat
de figuurtjes groter worden, verander de kleurtjes of de richting naar
believen.
- De
gecreerde records moeten gedelete worden op het einde (met de DISPOSE).
- Schrijf
een procedure die dit doet.
- Operaties
op Linked Lists worden dikwijls geimplementeerd met recursie.
Herschrijf
de procedure PlotFigureList mbv recursie.
- Je
zal in de volgende stap zien waarom het soms niet ander kan dan met
recursie.
- Ik
wil nu een 'tree' (boom) van figuren ipv een linked list.
- Verander
het type FigureRc in een tree-node.
- Verander
de Plot procedure.
- Verander
de dispose procedure.
- Creeer
zulk een 'tree' van figuren. Verzin een leuke tekening, bvb fractalen
kunnen
zo gemaakt worden.
X1:
H1:
H2:
T1: Output