Dynamisk hukommelses reservation
Lad os antage, at der skal indlæses en stor fil fra disken til maskinens hukommelse. Filen indeholder f.eks. et stort antal personoplysninger. Når man skal konstruere programmet til at håndtere disse oplysninger, har man ingen ide om, hvor mange personer der skal håndteres og således ingen ide om, hvor stor datafilen ender med at blive. Når man ikke ved, hvor mange data, man skal håndtere, er det også svært at vide, hvor meget plads der skal sættes af i hukommelsen.

En mulig løsning er at definere et array, som er stort nok til at indeholde det størst mulige antal variabler. Der er blot nogle ulemper ved denne løsning. En af dem er, at når programmet konstrueres defineres den store hukommelse og alt er OK, men når en anden bruger, derpå skal anvende programmet, er der måske andre programmer i hukommelsen, hvorefter maskinen melder "Out of memory", hvilket er meget uhensigtsmæssigt. En anden ulempe er, at det antal data, som programmet skal indeholde, er meget mindre end den plads, der er afsat, i det tilfælde spildes en masse plads i hukommelsen, som kunne have været anvendt af et andet formål.

En meget bedre løsning til denne type problemer er, at reservere hukommelse efter at programmet er startet. Man kan lade programmet undersøge, hvor stor en fil, der ligger på disken og derpå reservere netop den mængde hukommelse, som det er nødvendigt at anvende. Kun hvis der rent faktisk er for mange data i forhold til den aktuelle maskine, vil der komme en melding om, at hukommelsen er brugt op.

Hvad betyder det, at man reserverer hukommelse? Det betyder, at man anmoder styresystemet (Windows/DOS/Unix) om at levere en "klump" hukommelse til programmet. Hvorfor skal vi i det hele tager anmode om hukommelse? Hvorfor tager man det ikke bare? Man kunne jo bare ved hjælp af en pointervariabel dirigere variablerne derhen, hvor man vil have dem. Problemet er, at der kan ligge nogle andre data eller et andet program på den pågældende adresse. Det er styresystemets job at holde styr på, at der ikke kommer konflikter mellem de forskellige programmer, derfor er man nød til at overholde de regler, som styresystemer sætter op for brugen af hukommelsen. Styresystemet kan f.eks. fortælle, hvor meget hukommelse der er ledigt.

I det følgende vil jeg lave nogle eksempler på reservering (allokering) af hukommelse.

I praksis gør man det, at man kalder en funktion, som kan returnere en pointer til den plads i hukommelsen, vi må anvende. Funktionen, vi anvender, skal have et argument, som fortæller operativsystemet, hvor meget plads vi ønsker at reservere. Derpå finder operativsystemet en sammenhængende blok, som er stor nok til at dække vores anmodning. Hvis den ikke kan finde en blok, der er stor nok, får vi en fejlmelding. Når vi har fået tildelt hukommelsen, kan vi anvende den tilhørende pointer til af pege på den pågældende blok.

I C hedder arbejdshesten malloc(). For at anvende funktionen skal man enten #include stdlib.h eller alloc.h.

Lad os se på et eksempel.

Eksempel 1
void main(void)
{
   unsigned mem_ints = 20000; // antal heltal som skal gemmes
   unsigned mem_bytes;   // nødvendige hukommelsens størrelse i bytes

   int *ptr;   // pointer til første plads i hukommelsen
   unsigned j; // tæller til løkke
   char a;

   mem_bytes = mem_ints * sizeof(int); // Find hukommelsens størrelse

   ptr = (int *)malloc(mem_bytes);   //Få hukommelsen reserveret

   for(j=0; j<mem_ints; j++)     // fyld hukommelsen med data
      ptr[j] = j;

   free(ptr);      // Frigør hukommelsen
   a = getch();
} // Slut på programmet

Hvor meget hukommelse?
Man vil reservere plads til 20.000 heltal. Hvis det er under DOS, vil et heltal fylde 2 bytes, men det er faktisk meget sjældent, at man arbejder med et DOS-system, i f.eks. Windows kan heltalsstørrelsen være anderledes. Man anvender derfor sizeof() til at bestemme, hvor mange bytes et heltal anvender. Derpå ganger vi antallet af bytes med antallet for at få den samlede hukommelses størrelse.

Argumentet til malloc() er navngivet size_t, variablen er defineret som unsigned (faktisk unsigned int). I et DOS-system er den maximale hukommelseblok på 65.535 bytes. I et Windows-system kan denne blok være meget større, størrelsen vil afhænge af maskinen og den mængde RAM, som maskinen har installeret.

Data Pointer
Funktionen malloc() returnerer en pointer til en hukommelsesblok med den størrelse, som er defineret ved kaldet til funktionen. Man skal huske, at den pointer man definere skal være af samme type, som de data man vil gemme i blokken. I det foreliggende tilfælde skal der gemmes data af typen int, dette betyder at pointeren skal være af typen "pointer-to-int" eller int*.

Funktionen malloc() returnerer typen void*, dvs. en pointer til "anything". Mange programmører anvender et explicit cast for at convertere til den aktuelle type, et sådan cast kunne se således ud:

ptr = (int *)malloc(mem_bytes);

Dette er med nogle compilere overflødigt, idet compileren automatisk vil udføre cast'et for os.

Tilgang til hukommelsen
Man kan anvende enten pointernotation eller array-notation for at få tilgang til hukommelsen som er reserveret med malloc(). Eksempel 1 viser, hvorledes man kan anvende et array med ptr[j], men man kunne lige så godt have anvendt pointervariablen: *(ptr+j). Begge metoder vil arbejde med den tildelte hukommelse.

Funktionen
for (j = 0; j < mem_ints; j++)
ptr[j] = j;

vil fylde array'et med tal i stigende orden. Det er ikke særligt brugbart, men det viser, hvordan man kan fylde tal ind i en reserveret hukommelse.

Frigørelse af hukommelsen
Det er altid en god ide selv at frigøre en reserveret hukommelse, når man er færdig med at bruge den. Hvis ikke den frigøres, vil der ikke kunne læses andre data eller programmer ind i det område, der er reserveret. Funktionen til at frigøre hukommelse med hedder free(). Argumenter til funktionen er den pointeradresse, vi fik af malloc().

Lænkedede lister
Indtil videre har vi anvendt dynamisk hukommelses tildeling til at gemme data i et array, vi gemte rent faktisk data i en hukommelsesblok, som vi fik tildelt ved hjælp af kommandoen malloc(). Der er andre måder at gemme data på. En af de mest almindelige af disse andre måder er lænkede lister (af og til kaldes de blot lister, andre forfattere kalder dem også hægtede lister).

Hvorfor er det ikke hensigtsmæssigt altid at anvende array's til at holde data. Hvis man antager, at der skal oprettes 2000 kartotekskort med oplysninger om de ansatte i et firma. Dvs. der skal være personnummer, fornavn, efternavn, adresse osv. Hvis man nu vil slette en af medarbejderne og den pågældende står som nummer 50 i listen. Array's arbejder ikke særlig godt, hvis der er tomme felter i array'et, det er derfor nødvendigt at flytte alle de efterfølgende felter et felt frem. Dvs. 51 flyttes til nr. 50, 52 flyttes til 51 osv. op til det sidste element. Samme problem opstår også, hvis man vil indsætte et element i array'et, hvis man f.eks. vil have medarbejderne til at stå i alfabetisk orden i databasen. En sådan database vil komme til at virke meget langsomt pga. den megen omflytning af data.

Hjælpeværktøjet hedder Lænkede lister
En lænket liste løser dette problem på en elegant måde, idet det er muligt at indsætte og slette elementer fra en lænket liste uden at flytte alle de øvrige data. En lænket liste består af en struktur, hvor de enkelte elementer er forbundet til hinanden ved hjælp af pointere, i stedet for at være et element i et array. For at demonstrere denne sammenhæng vil jeg vende tilbage til opgaven fra lektionen med strukturer (dataposter). Det er eksemplerne med agent.c og agentptr.c jeg vil omskrive til at anvende pointere i stedet for statiske arrays.

I en lænket liste kan hvert element være en post (struct) på samme måde, som vi gemte elementerne i agent.c. Ved brug af lænkede lister skal vi udvide posten med en pointer, som skal pege på det efterfølgende element. Det er denne pointer, som opretholder forbindelsen mellem de enkelte elementer. Pointeren i det sidste element peger ikke på noget, så den får tildelt værdien NULL. Figuren viser, hvorledes det virker.

Eksempel 2
#include <stdlib.h>
#define Sand 1

void newname(void);
void listall(void);

struct prs
{
   char navn[30]; // agentens navn
   int agnum; // agentens nummer
   float hoej; // agentens højde
   struct prs *ptrnext; // pointer ril den næste post
}; // slut på posten

struct prs *ptrfirst = NULL;

void main(void)
{
   char ch;
   while (Sand)
   {
      printf("\nTast 'e' for at indtaste en ny agent"); // print
      printf("\n 'l' for at udskrive alle agenterne"); // muligheder
      printf("\n 'q' for at afslutte programmet");
      ch = getche(); // Modtager valget.
      switch(ch)
      {
         case 'e': newname(); break;
         case 'l': listall(); break;
         case 'q': exit(0);
         default : puts("\nIndtast kun et af de bogstaver,
                                                                     som er nævnt i listen");
      } // Slut på switch
   } // Slut på while
} // Slut på main

void newname(void)
{
   struct prs *ptrthis; // pointer til den aktelle post
   char numstr[81]; // variabel som holder et tal som en streng
   ptrthis = (prs*)malloc(sizeof(struct prs));// få tildelt 
   if(ptrthis == NULL)                      // hukommelseplads
   { printf("\nFejl under tildelingen!"); return; }
   ptrthis -> ptrnext = ptrfirst;
   ptrfirst = ptrthis;

   printf("\nIndtast et agentnavn: ");
   gets(ptrthis -> navn);
   printf("\nIndtast et agentnummer: ");
   gets(numstr);
   ptrthis -> agnum = atoi(numstr);
   printf("\nIndtast agentens højde: ");
   gets(numstr);
   ptrthis -> hoej = atof(numstr);
}

void listall(void)
{
   struct prs *ptrthis;

   if(ptrthis == NULL)
   { printf("\nListen er tom!"); return; }
   ptrthis = ptrfirst;
   do
   {
      printf("\nAgentnavn : %s\n", ptrthis -> navn);
      printf("\nAgentnummer : %03d\n", ptrthis -> agnum);
      printf("\nAgentens højde: %4.2f\n", ptrthis -> hoej);
      ptrthis = ptrthis -> ptrnext;
   }
   while(ptrthis != NULL);
}

Set fra brugeren virker dette program på samme måde som agent.c programmet, med en undtagelse. Forskellen er at informationen om agenterne bliver vist i omvendt rækkefølge af den de blev indtastet. Dvs. den sidst indtastede står først i listen. Dette er kun for at gøre programmeringen så enkel som muligt. Principielt kan vi indsætte en ny post hvor i rækken man ønsker det kræver blot lidt mere programmering. Bemærk at ved malloc() udføres et typecast til en pointer til en post (struct).

Udfordringen i ovenstående program er at forsøge at forstå, hvad der sker med pointerne i eksemplet. Vi husker, at der er tilføjet en pointer til posten, denne pointer fik navnet prtnext, idet den havde til opgave at pege på den næste post.

Ud over ptrnext, som findes i hver post, har vi brug for to pointere mere. Den ene er ptrfirst. Dette er en global variabel, som indeholder adressen til det første element i listen. Dvs. det er den, som gør, at vi kan finde listen, så denne adresse må ikke ændres under afviklingen af programmet. Når vi starter programmet peger ptrfirst på "posten" NULL. Den blev defineret som:

struct prs *ptrfirst = NULL;

Når ptrfirst peger på NULL er listen tom, når vi derpå indsætter poster i listen flyttes ptrfirst til at pege på den sidst indsatte post og NULL vil derefter markere enden af listen.

Den anden pointer er ptrthis, det er den pointer, som peger på den post der arbejdes med. Denne pointer er lokal, den defineres i hver af de funktioner, hvor den skal anvendes. Den anvendes til at holde den hukommelsesadresse, hvor den aktuelle post er beliggende.

Tilføjelse af en Agent til listen
Hvis brugeren ønsker at til føje en agent til listen, kalder programmet funktionen newname(). Det første denne funktion gør er at bruge malloc() for at få en pointer til et hukommelsesområde, som er stort nok til at holde den nye post. (I et 16 bit system vil det være 38 bytes.) Denne pointeradresse bliver hæftet på ptrthis. Tricket er nu ved hjælp af ptrthis, at få den nye post hæftet sammen med resten af listen.

Når brugeren indtaster sine data for den nye agent, er posten blevet placeret som den første post i listen. Dette kan se lidt bagvendt ud, men det gør programmeringen lidt mere enkel, idet det er meget lettere at finde starten af listen, end det er at finde slutningen.

For at hæfte en post på listen skal vi gøre to ting:

Først skal vi have flyttet ptrfirst så den peger på den nye post.

Dernæst skal vi have ptrnext fra den nye post til at pege på den første post i den eksisterende liste.

Princippet i dette kan ses i figuren herunder

I programmet laver vi den anden operation først. Den ser således ud:

ptrthis -> ptrnext = ptrfirst;

Derpå sættes ptrfirst til at pege på den nye post.

ptrfirst = ptrthis;

Når sammenhængen er tilvejebragt, kan brugeren fylde sine data ind i posten, det gøres med
ptrthis -> name, ptrthis -> agnum
osv.

Visning af indholdet i en liste
Agentlisten bliver fremvist med funktionen listall(). Funktionen starter med at undersøge om listen er tom. Hvis listen ikke er tom sættes ptrthis til at pege på ptrfirst, som er adressen til den første post i listen. Derpå startes en do - while-løkke. I løkken udskrives den post, som peges på af ptrthis. Pointeren ptrthis flyttes igennem listen indtil den møder NULL, når det sker stopper løkken.

Frigørelse af hukommelse
I eksempel 2 "glemmer" jeg at anvende free(). Det er en meget dårlig programmering. I dette tilfælde gør jeg det fordi, jeg skal følge lænken fra post til post og frigøre området for hver af posterne en efter en. Det er kun en lille database, der arbejdes med her og når programmet stoppes, frigøres hukommelsen alligevel automatisk.

Øvelse 1
Konstruer en funktion, som kan fjerne en post fra listen. Funktionen kan indsættes i eksempel 2 og menuen udvides til understøtte dette valg.
Husk i denne funktion skal hukommelsen frigives, når en post fjernes.

Eksempler og løsningerne kan hentes her
Eksempel 1
Eksempel 2
Øvelse 1