|
Dynamisch geheugen aanvragen
Een beschrijving van dynamisch geheugen aanvragen
Dynamisch geheugen aanvragen lijkt op het eerste gezicht nogal
moeilijk, zeker voor iemand die daar voor het eerst mee in aanraking
komt. Wees niet bang, lees dit hoofdstuk aandachtig door en je zult
een goede basis hebben voor een belangrijke programmeertechniek.
De variabelen die we tot nu toe gebruikten, waren steeds aanwezig, dat
wil zeggen er was direct ruimte voor gereserveerd in het geheugen. In
dit hoofdstuk zullen we variabelen gebruiken waarvoor dynamisch
geheugen wordt aangevraagd. Dit zijn variabelen die niet bestaan als
het programma wordt gestart, maar worden aangemaakt op het moment dat
ze nodig zijn. Met deze techniek is het mogelijk net zoveel variabelen
aan te maken als je nodig hebt op een bepaald moment en ze weer weg te
gooien als je er mee klaar bent. Ook hier zal een voorbeeld weer veel
meer duidelijkheid geven. Bestudeer daarom programma DYNVELD.C.
<![CDATA[
typedef struct _field {
int sRow; /* field row */
int sColumn; /* field column */
int sLength; /* field length */
} VELD;
main ()
{
VELD *pv1, *pv2;
pv1 = (VELD *) malloc (sizeof (VELD));
pv1->sRow = 6;
pv1->sColumn = 12;
pv1->sLength = 20;
pv2 = (VELD *) malloc (sizeof (VELD));
pv2->sLength = 32;
pv2->sColumn = 12;
pv2->sRow = pv1->sRow + 2;
printf ("veld1 staat op rij %d, kolom %d en is %d tekens lang\n",
pv1->sRow, pv1->sColumn, pv1->sLength);
printf ("veld2 staat op rij %d, kolom %d en is %d tekens lang\n",
pv2->sRow, pv2->sColumn, pv2->sLength);
free (pv1);
free (pv2);
}
]]>
Het programma begint met de definitie van een nieuw type,
VELD, zijnde een structuur genaamd _field,
bestaande uit drie integers. We hebben in het vorige hoofdstuk
variabelen van deze structuur gedeclareerd. Nu echter wordt niets
gedeclareerd, alleen gedefinieerd. We hebben nu dus een eigen type. Van
dit type worden geen variabelen gedeclareerd, maar wel twee pointers.
We hebben dus nergens geheugen lokaties beschikbaar om gegevens in op
te slaan. Het enige wat we ter beschikking hebben zijn de twee
pointers. Om toch gegevens op te kunnen slaan, zullen we geheugen aan
moeten vragen.
Het eerste statement in het programma is een funktie aanroep, waarvan
het resultaat wordt toegekend aan een van de twee pointers. Deze
funktie, de malloc() funktie, is het hart van de dynamische
geheugen techniek. Het is de afkorting van Memory
Allocation. De malloc() funktie reserveert een stuk
geheugenruimte ter grootte van het aantal bytes dat als parameter wordt
meegegeven. Het adres van de eerste byte wordt toegekend aan de
pointer. In het voorbeeld zal pv1 gaan wijzen naar de eerste
byte van de aangemaakte structuur van het type VELD. De
ruimte waarin variabelen gecre‰erd worden, wordt de heap
genoemd.
Wat is nu eigenlijk een heap? Elke compiler kent
grenswaarden voor een aantal zaken, zoals maximale programma grootte,
maximum aantal variabelen, enz.. Een veel voorkomende grenswaarde voor
de IBM-PC is een limiet van 64K voor de uitvoerbare code. Dit komt
omdat de microprocessor van de IBM-PC met geheugen segmenten werkt ter
grootte van 64K.
Een heap is een gebied buiten de 64K grenzen van het
programma, alwaar het programma gegevens kan opslaan. De gegevens
worden in de heap geplaatst door het systeem, wanneer het
programma daar middels de funktie malloc() om vraagt. Het
systeem houdt daar een administratie van bij. De gegevens kunnen weer
worden vrijgegeven. Dit leidt tot gaten in de heap. Het
systeem houdt ook van deze gaten een administratie bij en zal deze
zoveel mogelijk hergebruiken. De structuur en inhoud van de
heap is dus zeer dynamisch en voortdurend onderhevig aan
veranderingen.
Wellicht gaf bovenstaande uitleg je wat meer inzicht omtrent de werking
van de malloc() funktie. Er wordt dus ruimte aangevraagd ter
grootte van het aantal bytes wat wordt opgegeven en een pointer naar de
eerste byte van het gereserveerde gebied wordt teruggegeven. In het
voorbeeld vragen we een blok aan ter grootte van een structuur. Middels
de sizeof() funktie wordt de grootte opgegeven. Deze laatste
funktie geeft als resultaat het aantal bytes van hetgeen als parameter
wordt meegegeven. In dit geval is dat het aantal bytes dat de structuur
_field groot is. Dit is een veilige manier. Op sommige
computers zal 3 maal 2 is 6 bytes aangevraagd worden, op 386- en 486
systemen zal 3 maal 4 is 12 bytes gereserveerd worden.
De malloc() funktie is een universele funktie. In vorige
lessen hebben we geleerd dat een pointer van een bepaald type is. De
malloc() funktie geeft standaard een pointer terug van het
type char. Meestal echter is de ontvangende pointer van een
ander type. In het voorbeeld is de ontvangende pointer van het type
VELD. We kunnen de compiler meedelen dat deze type conversie
plaats moet vinden middels een cast. De cast
bestaat dus uit het expliciet noemen van het type en wordt aan de
compiler medegedeeld door hem tussen haakjes te plaatsen.
Als we een pointer hebben, wijzend naar een structuur, dan kunnen we
via die pointer alle structuur members benaderen. In de drie
statements die volgen, wordt aan de integers een fantasie waarde
toegekend. Deze toekenningen maken geen enkel verschil met die aan
direct gedeclareerde variabelen.
Vervolgens wordt nog een blok geheugen aangevraagd en wordt aan de
componenten van die structuur een waarde toegekend. Om te laten zien
dat de dynamisch aangevraagde variabelen ook echt een waarde hebben,
worden ze alle afgedrukt. Het zal je opvallen dat de twee
printf() statements niet anders zijn dan in de vorige
programma's.
Tenslotte moet het aangevraagde geheugen weer worden vrijgegeven, zodat
dit opnieuw kan worden gebruikt. De funktie waarmee dit kan worden
gedaan, heet free(). De funktie wordt aangeroepen met als
parameter de pointer naar het gereserveerde gebied.
Als een pointer verloren gaat, bijvoorbeeld omdat deze wordt
overschreven, is het niet meer mogelijk het dynamisch aangevraagde
gebied te benaderen. Het kan dan ook niet meer worden vrijgegeven,
waardoor er computer geheugen wordt verspild. Pas hier dus voor op.
Wanneer het programma eindigt, zal het systeem de totale heap
vrijgeven, waardoor alles netjes wordt opgeruimd.
Compileer en test het programma.
Geheugen aanvragen voor tabellen
Bestudeer het programma VELDEN.C. Dit programma is vrijwel gelijk aan
het vorige programma. Nu echter is een tabel van pointers gedeclareerd,
in plaats van een enkele pointer naar ieder individueel gebied. Om het
voorbeeld eenvoudig te houden bevat het programma een tabel van slechts
8 elementen en een index op de tabel.
<![CDATA[
typedef struct _field {
int sRow; /* field row */
int sColumn; /* field column */
int sLength; /* field length */
} VELD;
main ()
{
int index;
VELD *ptr[8];
for (index = 0; index < 8; index++) {
ptr[index] = (VELD *) malloc (sizeof (VELD));
ptr[index]->sRow = index + 4;
ptr[index]->sColumn = 12;
ptr[index]->sLength = 20;
} /* endfor */
ptr[1]->sLength = 32; /* verander veld 2 */
ptr[3]->sLength = 32; /* verander veld 4 */
ptr[5]->sLength = 32; /* verander veld 6 */
for (index = 0; index < 8; index++) {
printf ("veld %d: rij %2d, kolom %2d, %2d tekens\n",
index+1,
ptr[index]->sRow,
ptr[index]->sColumn,
ptr[index]->sLength);
free (ptr[index]);
} /* endfor */
}
]]>
De constructie *ptr[8]; is nieuw en zal daarom
nader worden toegelicht. Hier wordt een tabel van 8 pointers aangeduid,
waarvan ptr[0] de eerste is en
ptr[7] de laatste. Omdat een tabel ook een pointer
is, is de variabele ptr een pointer naar een pointer. Dit is
toegestaan in C en het mag nog een aantal niveaus dieper. Er is in
feite geen limiet. Zorg dat je bij dit soort declaraties de draad niet
kwijtraakt. Begin aan dit soort constructies zodra je genoeg ervaring
hebt.
Nu we de beschikking hebben over 8 pointers, die geen onderscheid
vormen met de tot nu toe behandelde pointers, is het niet zo moeilijk
een programma te schrijven waarin, middels een iteratie, dynamisch
geheugen wordt aangevraagd en de respectievelijke structuren een waarde
krijgen. In dit programma wordt slechts aan drie integers per structuur
een eenvoudige waarde toegekend. Je kunt je echter voorstellen dat je
op deze manier ook de gegevens van een kaartenbak in het geheugen leest
en daar onderhoud op pleegt.
Een drietal willekeurig gekozen velden krijgt een andere waarde, om aan
te tonen dat gewone toekenning ook mogelijk is. Vervolgens worden de
gegevens met behulp van een iteratie afgedrukt en vrijgegeven.
Compileer en test dit programma. Om de techniek extra goed onder de
knie te krijgen, kun je proberen het programma zodanig aan te passen
dat niet meer wordt gewerkt met een index op de tabel maar met een
extra pointer naar de tabel.
Lijsten
Op dit moment zijn we toe aan de behandeling van een belangrijke
programmeertechniek, die van de enkel- of dubbel geketende lijst.
Bestudeer het programma BUBBLE.C voor een voorbeeld van de toepassing
van een enkel geketende lijst, ook wel lijst of Linked List
genoemd. Het maakt gebruik van een recursieve datastructuur, dat wil
zeggen een lijst waarvan de laatste component naar een lijst wijst.
Door structuren naar elkaar te laten wijzen, ontstaat als het ware een
ketting van structuren, een ketting die kan worden afgelopen.
<![CDATA[
/** BUBBLE.C - Bubble sort programma ******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define RECSIZE 14
typedef struct _lijst {
char *prec;
struct _lijst *next;
} LIJST;
int iCnt;
FILE *pf;
LIJST *plS, *plC, *plH;
char szFileID[] = "BUBBLE.DAT";
void DrukAf ();
void GeefVrij ();
void Lees ();
void Sorteer ();
/** Hoofdprogramma ************************************************/
int main ()
{
if ((pf = fopen (szFileID, "r")) == NULL) {
printf ("Het bestand '%s' is niet gevonden.", szFileID);
exit (9);
} /* endif */
Lees ();
Sorteer ();
DrukAf ();
GeefVrij ();
fclose (pf);
return (0);
}
/** Druk de gesorteerde lijst af **********************************/
void DrukAf ()
{
printf ("Afdruk van de gesorteerde lijst:\n");
plC = plS;
for (iCnt = 1; plC; iCnt++) {
printf ("Record # %02d: '%s'\n", iCnt, plC->prec);
plC = plC->next;
} /* endfor */
printf ("\n");
return;
}
/** Geef het aangevraagde geheugen weer vrij **********************/
void GeefVrij ()
{
printf ("Bezig met opschonen ...\n\n");
while (plS) {
plC = plS;
plS = plC->next;
free (plC->prec);
free (plC);
} /* endwhile */
return;
}
/** Lees het Invoer bestand ***************************************/
void Lees ()
{
char szBuf[RECSIZE+1];
iCnt = 0;
plS = plC = plH = NULL;
while (fgets (szBuf, RECSIZE, pf) != NULL) {
iCnt++;
plH = (LIJST *) malloc (sizeof (LIJST));
plH->prec = (char *) malloc (RECSIZE);
plH->next = NULL;
*(plH->prec) = '\0';
strncat (plH->prec, szBuf, (RECSIZE - 2));
if (iCnt == 1) {
plS = plH;
} else {
plC->next = plH;
} /* endif */
plC = plH;
} /* endwhile */
printf ("Totaal aantal records is %d\n\n", iCnt);
return;
}
/** Sorteer de lijst **********************************************/
void Sorteer ()
{
int iSw = 1;
char *pch;
printf ("De Invoer wordt gesorteerd ...\n\n");
while (iSw) {
iSw = 0;
plC = plS;
while (plC->next) {
plH = plC->next;
if (strcmp (plC->prec, plH->prec) > 0) {
pch = plC->prec;
plC->prec = plH->prec;
plH->prec = pch;
iSw = 1;
} /* endif */
plC = plH;
} /* endwhile */
} /* endwhile */
return;
}
/** End of File ***************************************************/
]]>
Dit programma sorteert records uit een invoerbestand volgens de
Bubble Sort methode en drukt die af.
Het programma begint met het toevoegen van wat standaard bestanden.
Vervolgens wordt een record lengte gedefinieerd als symbolische
constante. Dan volgt de definitie van het datatype LIJST.
Dit is een lijst van pointers naar characters, omdat hij een pointer
naar zichzelf bevat. Met variabelen van dit type kan een ketting van
pointers naar records worden gebouwd.
Tot dan is er nog geen enkele variabele gedeclareerd, alleen
gedefinieerd. Dat wordt vervolgens gedaan. Er worden een record teller,
een pointer naar een invoer bestand en drie pointers naar de te bouwen
lijst gedeclareerd. De pointers hebben de volgende betekenis:
| Pointer | Betekenis |
| plS | Start pointer, pointer naar de eerste
structuur van de lijst. |
| plC | Current pointer, pointer waarmee de lijst kan
worden afgelopen, pointer naar de structuur die behandeld wordt. |
| plH | Hulp pointer. |
Dan volgt de definitie van de funkties die het programma aanroept, ook
wel de Function Prototypes genoemd.
Het hoofdprogramma begint met de declaratie van een string, waarin de
naam van het invoerbestand staat. Dat bestand wordt geopend. Als dat
lukt, wordt achtereenvolgens het bestand gelezen, de lijst gesorteerd,
de records afgedrukt en het aangevraagde geheugen vrijgegeven.
Tenslotte wordt het invoerbestand gesloten en het programma be‰indigd.
Laten we in deze volgorde verder naar het programma kijken. De vier
funkties zijn in alfabetische volgorde in het programma opgenomen om
het zoeken ernaar te vergemakkelijken.
Invoer bestand lezen
De funktie Lees() zal een lijst opbouwen, die er als
volgt uit komt te zien:
<![CDATA[
plS--->Lijst#1
prec--->Record#1
next--->Lijst#2
prec--->Record#2
next--->Lijst#3
prec--->Record#3
next---> . . . Lijst#n
prec--->Record#n
next--->NULL
]]>
De funktie begint met de declaratie van een buffer. De lengte is het
aantal tekens in een record plus twee tekens einde record informatie
plus een teken voor het NULL karakter. Vervolgens wordt de record
teller op nul gezet en worden de pointers ge‹nitialiseerd.
Uit vorige programma's weten we inmiddels hoe we records kunnen lezen.
Middels een while lus worden een voor een de records uit het invoer
bestand gelezen in de buffer, tot einde bestand. De gelezen records
worden geteld in variabele iCnt.
Om een element aan de lijst toe te voegen, wordt eerst geheugen
aangevraagd voor een structuur element. De pointer naar dit element
wordt bewaard en middels deze pointer worden de componenten van de
structuur gevuld. De variabele prec krijgt de waarde van de
pointer die wijst naar een geheugen gebied, ter grootte van een record,
dat ook dynamisch wordt aangevraagd. De variabele next
krijgt de waarde NULL, ten teken dat dit het laatste element uit de
ketting wordt.
Er is dus nu ruimte aangevraagd voor een structuur element en voor een
record. De structuur is gevuld, het record nog niet. Met behulp van
de strncat() funktie wordt het exacte aantal tekens uit de
buffer gekopieerd.
Nu moet de administratie nog worden bijgewerkt. Indien het om het
eerste record gaat, moet de Start pointer een waarde krijgen. Voor alle
andere records mag de waarde van de Start pointer niet meer worden
aangetast. De eerste keer hebben we nog geen ketting! Bij het tweede,
derde, enzovoort tot en met het laatste record moeten we een schakel
aan de ketting toevoegen. De Current pointer wijst naar de laatste
schakel tot nu toe. We laten de next pointer van dit laatste
element nu naar het nieuwe element wijzen, waarvan de waarde in de Hulp
pointer staat. Dat is alles! De Current pointer wijst daarmee naar de
voorlaatste. Om deze weer naar het laatste element te laten wijzen,
wordt het laatste statement van de while lus uitgevoerd. Ter afsluiting
wordt het aantal getelde records afgedrukt en de funktie verlaten.
Lijst sorteren
De funktie begint met de declaratie van twee hulp variabelen. De
variabele iSw geeft aan of een verwisseling heeft
plaatsgevonden (0=Nee, 1=Ja), de variabele pch is een hulp
variabele om twee pointers van waarde te doen wisselen. De lijst is
gesorteerd als geen verwisseling meer heeft plaatsgevonden.
De funktie start dus een iteratie die telkens vooraan de lijst begint
te vergelijken en daar mee stopt als de lijst gesorteerd is. In elke
iteratie slag wordt de lijst helemaal doorlopen. Omwille van de eenvoud
is geen verdere verbetering aan het sorteer algoritme aangebracht. Het
is echter denkbaar na elke iteratie de te doorlopen lijst met een te
verminderen, omdat het grootste element telkens achteraan komt te
liggen.
Middels de strcmp() funktie wordt record#1 met record#2,
record#2 met record#3 vergeleken, enzovoort tot en met record#n-1 met
record#n. Vervolgens worden de pointers verwisseld en niet de records
zelf. Dit programma zal dus verschrikkelijk snel sorteren, omdat geen
enkel gegeven wordt verplaatst. De in de lijst geadministreerde
pointers kunnen direct als parameters voor de strcmp()
funktie worden gebruikt. Ook dit zal snelheidswinst opleveren.
Bestudeer het voorbeeld goed en probeer de funktie te begrijpen.
Records afdrukken
Het afdrukken van de lijst is nu een peuleschil. De funktie heeft
hiervoor geen extra variabelen nodig. De Current pointer wordt gelijk
aan de Start pointer gemaakt. Dan wordt er een iteratie gestart. Omdat
het aardig leek ook het record nummer af te drukken, wordt dat hier
met behulp van een for lus gedaan.
Eigenlijk staat hier: positioneer op de eerste schakel en druk
zolang er nog een schakel aan de ketting zit het record nummer en het
record zelf af en positioneer op de volgende schakel. Dat is alles.
Geheugen vrijgeven
De funktie GeefVrij() tenslotte geeft het dynamisch
aangevraagde geheugen weer vrij. De Start pointer wordt hiervoor
gebruikt, omdat we als het ware telkens een schakel van de voorkant van
de ketting afknippen. Zolang er nog een schakel aan de ketting zit,
wordt dit gedaan. De Current pointer krijgt de waarde van de Start
pointer en wijst daardoor naar de eerste schakel. De Start pointer
wijst naar de volgende schakel, waardoor de eerste er wordt
afgeknipt. De beide geheugen gebieden, d.w.z. eerst het
record en daarna de structuur, worden vrijgegeven waardoor als het ware
de losse schakel netjes wordt opgeruimd.
Probeer voor jezelf goed te beredeneren wat de feitelijke betekenis
is van de expressie: while (plS).
Compileer en test dit programma uitgebreid.
|
