Het laatste voorbeeld van het vorige hoofdstuk, p12_5, ziet er aardig uit, maar heeft een heel groot nadeel.
We hebben daar te maken met een array van records, en dit zijn zogenaamde statische variabelen.
Dat betekent dat ze vooral al een bepaalde hoeveelheid geheigenruimte innemen, en wel binnen dezelfde ruimte als het programma zelf. Dit brengt dan ook een beperking met zich mee.
In mijn situatie kan ik maar maximaal 207 records in het array kwijt. Voor een beetje adres-boek te weinig.
Vervelend dus, zeker als je bedenkt dat er nog genoeg geheugen over is (het zgn. heap-geheugen).
Om daar echter bij te komen moet je gebruik maken van dynamische variabelen. Dat zijn variabelen die in de heap hun waarde krijgen.
Het lastige is echter dat Pascal geen boekhouding doet met dynamische variabelen. Dit zullen we dus zelf moeten doen.
Het voordeel van Pascal is echter wel dat we dat kunnen doen en wel door middel van pointers.
Voorbeeld.
Het voorbeeld dat in dit hoofdstuk centraal staat is wat simpeler dat p12_5.
We gaan een aantal willekeurige namen genereren en die via een invoeg-procedure op de juiste, alfabetische plaats invoegen in de tot dan toe bestaande lijst.
Hierna geven we de lijst weer op het scherm.
Tevens bouwen we een procedure om de lijst leeg te maken en een procedure om 1 specifiek item uit de lijst te verwijderen.
Tot slot maken we een functie die de lengte van de lijst berekent.
Het voorbeeld gaan we zowel uitwerken met statische variabelen (zie opdrachten) als met dynamische variabelen.
Pointer-definitie.
Dynamische variabelen dienen op specifieke wijze te worden gedefinieerd.
Kijk naar het volgende voorbeeld:
type
S20 = String[20];
TNaamPointer = ^TNaam;
TNaam = record
Naam: S20;
Volgende: TNaamPointer;
end;
Twee dingen die (hopelijk) direct opvallen:
het dakje (^) voor TNaam, en
TNaam wordt al als type gebruikt voordat het is gedefinieerd!
Dit is 1 van de 2 gevallen waarin het is toegestaan om al iets te gebruiken alvorens het is gedefinieerd. (Het andere geval is d.m.v. een forward-clausule).
Simpel gezegd is het de hond die zich in zijn eigen staart bijt.
En dat is ook eigenlijk wat hier gebeurt.
Door deze constructie krijgen we een ketting van variabelen, waarbij de inhoud in Naam staat, en
de verwijzing naar de volgende schakel in Volgende staat.
Het woordje “verwijzing” in de vorige zin refereert natuurlijk aan het engelse “pointer”.
In Pascal is een pointer niets meer en niets minder dan een (geheugen) adres. Voor de programmeur is het niet van belang hoe dit adres eruit ziet, alleen maar dat het een adres is.
Wel van belang is het speciale adres nil, dat zeg maar als randaarde funcgeert. Zonder de nil is de lijst niet compleet. Je moet per slot weten waar de lijst eindigd.
Voorstelling van een (pointer-)lijst.
Vaak wordt een (pointer-)lijst voorgesteld als een gedeeld rechthoekje, met links de waarde-variabele en rechts de pointer, die met een pijl naar de volgende rechthoek wijst.
Een deel van onze lijst zou als volgt kunnen worden weergegeven:
De lijst start met ‘Naam 1’ en verwijst naar de volgende plaats, die als waarde ‘Naam 2’ heeft en weer verwijst naar de volgende, die als waarde ‘Naam 3’ heeft en naar nil verwijst, ofwel het einde van de lijst aangeeft.
Pointer-variabelen.
Om uiteindelijk met een pointer-structuur te kunnen werken hebben we pointer-variabelen nodig.
Hierbij dient men altijd onderscheid te maken tussen de pointer-variabele zelf en de waardes die hier achter schuil gaan.
Stel we hebben de volgende definities:
type
t = ^integer
var
a,b: t;
De variabelen a en b, mits niet nil, hebben als waarde een geheugenadres.
Om nu bij de velden of waardes van a en b te komen, gebruiken we het dakje (^).
Stel we willen aan a de waarde 2 en aan b de waarde 3 toekennen, dan gaat dat als volgt:
a^ := 2;
b^ := 3;
Dus a en b wijzen naar een geheugenadres, en a^ en b^ hebben een waarde!
Dan gaan we het nu wat lastiger maken.
De toekenningsopdracht a := b, is totaal verschillend van de toekenningsopdracht a^ := b^.
Bij a := b, wordt de verwijzing van a ‘afgebogen’ naar b.
Bij a^ := b^ wordt de waarde van b^ de waarde van a^.
Nogmaals voor alle duidelijkheid: de variabelen a en b bevatten geheugenadressen en staan in hetzelfde geheugenblok als alle andere ‘normale’ variabelen. De waardes a^ en b^ staan in het heap-geheugen.
Bij de toekenning a := b, gaat de waarde a^(=2) onherstelbaar verloren!
New en Dispose.
Om in Pascal goed met pointer-variabelen te kunnen werken, moet er voor deze variabelen geheugen worden gereserveerd (ge-allokkeerd).
Dit gebeurt met de opdracht New([pointer-variabele]).
Om dit geheugen weer vrij te maken (de-allokkeren) gebruikt Pascal de opdracht Dispose([pointer-variabele]).
Het is de taak van de programmeur hier zorgvuldig mee om te gaan, en ervoor zorg te dragen dat al het ge-allokkeerde geheugen weer netjes wordt vrij gegeven!
Terug naar het voorbeeld.
Om met de lijst namen te kunnen gaan werken hebben we een variabele nodig. Deze variabele geeft niets anders aan dan de start van de lijst en zullen we daarom ook LijstHoofd noemen.
Als de lijst leeg is heeft LijstHoofd de waarde nil, anders verwijst LijstHoofd naar het eerste element in de lijst.
De lijst schrijven.
Om de lijst te schrijven beginnen we gewoon bij het LijstHoofd en eindigen wanneer het veld Volgende de waarde nil heeft:
procedure Schrijf;
var
ref: TNaamPointer;
begin
ref := LijstHoofd;
while ref <> nil do
with ref^ do
begin
write(Naam:40);
ref := Volgende;
end;
end;
De lijst leegmaken.
Om de lijst weer leeg te maken zou je kunnen denken dat de opdracht LijstHoofd := nil; afdoende zou zijn.
Maar dat is helaas niet zo. Het enige dat je dan doet is de eerste schakel met de lijst verbreken, waardoor de lijst inderdaad niet meer bereikbaar is. Het ernstige nadeel is nu echter dat er wel geheugen ge-allokkeerd blijft, en dat is dus niet netjes.
We zullen dus iedere gebruikte variabele weer moeten vrijmaken:
procedure Leeg;
var
ref,refp: TNaamPointer;
begin
ref := LijstHoofd;
while ref <> nil do
with ref^ do
begin
refp := ref;
ref := Volgende;
Dispose(refp)
end;
LijstHoofd := nil;
end;
We lopen de lijst weer door vanaf LijstHoofd. Als de Volgende bestaat dan moeten we die even onthouden, refp, alvorens we naar de volgende gaan, ref. Als we bij de volgende zijn (ref), dan kunnen we de vorige (refp) veilig weghalen.
Pas op het einde kennen we de waarde nil aan LijstHoofd toe.
Lengte van de lijst
Vaak is het handig om te weten uit hoeveel elementen een lijst bestaat, ofwel de lengte van de lijst.
Helaas is er geen snellere methode dan de lijst vanaf het eerste element totaan het laatste element te doorlopen en steeds een tellertje op te hogen:
function Lengte: Integer;
var
ref: TNaamPointer;
a: Integer;
begin
ref := LijstHoofd;
a := 0;
While ref <> nil do
begin
a := a + 1;
ref := ref^.Volgende;
end;
Lengte := a;
end;
Toevoegen nieuw element.
De voorgaande procedures en functie waren redelijk eenvoudig. Nu begint het echte werk.
In ons voorbeeld willen we een element op de juiste alfabetische plaats toevoegen.
De hier gevolgde strategie is als volgt:
Doorloop de lijst totdat er een naam wordt gevonden die groter is dan de nieuwe toe te voegen naam.
Als de naam kleiner is dan de toe te voegen naam moeten we die plaats onthouden, want die plaats is belangrijk als we de nieuwe naam moeten invoegen.
Hebben we de juiste plaats, dan maken we een nieuw element met daarin de waarde van de nieuwe naam.
Vervolgens laten we dit nieuwe element naar de volgende wijzen, en het vorige element naar dit nieuwe element.
Het volgende element is logischerwijs bekend, omdat we de lijst doorlopen totaan de eerste naam groter dan de nieuwe naam.
Het vorige element is bekend, omdat we deze expliciet hebben onthouden.
Hier is de code:
procedure VoegToe(NieuweNaam: S20);
var
ref,voorgaanderef,nieuweref: TNaamPointer;
bepaald: Boolean;
begin
ref := LijstHoofd;
bepaald := false;
while not bepaald and (ref <> nil) do
with ref^ do
if nieuwenaam <= naam then
bepaald := true
else
begin
voorgaanderef := ref;
ref := volgende;
end;
new(nieuweref);
nieuweref^.Naam := NieuweNaam;
nieuweref^.Volgende := ref;
if ref = LijstHoofd then
LijstHoofd := nieuweref
else
voorgaanderef^.Volgende := nieuweref;
end;
Schematisch ziet e.e.a. er als volgt uit:
Juiste plaats gevonden, nieuw element aangemaakt met nieuwe naam.
Laat nieuw element naar volgende element wijzen.
Laat vorige element naar nieuw element wijzen.
Element verwijderen.
Om een specifiek element uit de lijst te verwijderen volgen we min of meer dezelfde methode als bij het invoegen van een nieuw element.
Doorloop de lijst met elementen.
Is het huidige element niet het te verwijderen element, onthoud dan (de plaats van) dat element en ga naar de volgende.
Is het huidige element het te verwijderen element, laat dan het vorige element naar het volgende wijzen en verwijder het huidige element (Dispose).
Analoog aan de vorige paragraaf zijn het vorige, huidige en volgende element bekend.
Hier is de code:
procedure Verwijder(VNaam: S20);
var
ref,refp: TNaamPointer;
bepaald: Boolean;
begin
ref := LijstHoofd;
bepaald := false;
while not bepaald and (ref <> nil) do
with ref^ do
if Naam = VNaam then
bepaald := true
else
begin
refp := ref;
ref := Volgende;
end;
if bepaald then
begin
if ref = LijstHoofd then
LijstHoofd := ref^.Volgende
else
refp^.Volgende := ref^.Volgende;
Dispose(ref);
end;
end;
De test.
Om één en ander te kunnen testen gaan we het volgende doen:
We vullen de lijst,
we verwijderen daarna het eerste element uit de lijst,
en dan maken we de lijst weer leeg.
Om te experimenteren maken we gebruik van een Constante Max die aan het begin van het programma wordt gedefinieerd.
Het hele programma ziet er als volgt uit:
program dynamis;
const
MaxNamen = 3000;
type
S20 = String[20];
TNaamPointer = ^TNaam;
TNaam = record
Naam : S20;
Volgende: TNaamPointer;
end;
var
LijstHoofd: TNaamPointer;
procedure Schrijf;
var
ref: TNaamPointer;
begin
ref := LijstHoofd;
while ref <> nil do
with ref^ do
begin
write(Naam:40);
ref := Volgende;
end;
end;
procedure Verwijder(VNaam: S20);
var
ref,refp: TNaamPointer;
bepaald: Boolean;
begin
ref := LijstHoofd;
bepaald := false;
while not bepaald and (ref <> nil) do
with ref^ do
if Naam = VNaam then
bepaald := true
else
begin
refp := ref;
ref := Volgende;
end;
if bepaald then
begin
if ref = LijstHoofd then
LijstHoofd := ref^.Volgende
else
refp^.Volgende := ref^.Volgende;
Dispose(ref);
end;
end;
procedure Leeg;
var
ref,refp: TNaamPointer;
begin
ref := LijstHoofd;
while ref <> nil do
with ref^ do
begin
refp := ref;
ref := Volgende;
Dispose(refp)
end;
LijstHoofd := nil;
end;
procedure VoegToe(NieuweNaam: S20);
var
ref,voorgaanderef,nieuweref: TNaamPointer;
bepaald: Boolean;
begin
ref := LijstHoofd;
bepaald := false;
while not bepaald and (ref <> nil) do
with ref^ do
if nieuwenaam <= naam then
bepaald := true
else
begin
voorgaanderef := ref;
ref := volgende;
end;
new(nieuweref);
nieuweref^.Naam := NieuweNaam;
nieuweref^.Volgende := ref;
if ref = LijstHoofd then
LijstHoofd := nieuweref
else
voorgaanderef^.Volgende := nieuweref;
end;
function Lengte: Integer;
var
ref: TNaamPointer;
a: Integer;
begin
ref := LijstHoofd;
a := 0;
While ref <> nil do
begin
a := a + 1;
ref := ref^.Volgende;
end;
Lengte := a;
end;
procedure Lijst(aantal: Integer);
var
i,j: Integer;
s: S20;
begin
Leeg;
for i := 1 to aantal do
begin
s := ”;
for j := 1 to 20 do
s := s + Chr(97+Random(26));
VoegToe(s);
end;
Schrijf;
end;
procedure Test;
begin
clrscr;
Lijst(MaxNamen);
writeln(‘Lengte=’,Lengte);
Verwijder(LijstHoofd^.Naam);
writeln(‘Lengte=’,Lengte);
Leeg;
writeln(‘Lengte=’,Lengte);
end;
begin
LijstHoofd := nil;
Test;
end.
Oefeningen.
13.1
Maak hetzelfde test-programma als in dit hoofdstuk, maar nu met statische variabelen, ofwel met een record-structuur.
Vergelijk beide programma’s op uitvoer en tijds-duur.
[Antwoord]
[Gestructureerde types] <– –> [Rijen en stapels]