een lange titel

Struct en gelinkte lijst in C

Enkele mindere bekende constructies zijn struct en de gelinkte lijst die met struct gebouwd wordt.

Dit is enkele voorbeelden dat het gebruik van de C struct uitlegt. De struct hoef je in praktijk niet meer te gebruiken omdat de C++ class een beter alternatief is.

De struct in C

Dit is een zeer eenvoudig voorbeeld:

struct persoon
{
   char naam[30];
   int nummer;
};

Een C struct lijkt op een C++ class maar heeft beperkingen. Methoden zijn niet toegelaten omdat die niet bestaan in C. En alle datavelden zijn public omdat er in C geen beveiligingen mogelijk zijn.

De gelinkte lijst in C

Het eerste voorbeeld toont hoe je een gelinkte lijst kan maken met struct. Het nadeel van deze oplossing is dat je in de struct een pointer moet voorzien die naar het volgende element wijst. In C was dit de enige manier om dynamisch gelinkte lijsten te kunnen maken.

  • linked-list.c

Broncode: linked-list.c

#include <stdlib.h>
#include <stdio.h>

struct point
{
  int x;
  int y;
  
  point()
  {
  }
  struct point *volgende;
};


// C
typedef struct point POINT;

// POINT is nu een type.
// Dit is een array van 10 punten.
POINT[10] lijst;


// recursieve functie
// die de lijst toont
void toon(POINT *p)
{
  if (p != NULL)
  {
    printf("x %d, y %d\n", p->x, p->y);
    toon(p->volgende);
  }
}


int main()
{
  // niet in C, wel in C++
  //struct point *p = new point();

  // C++  
  //point *p2 = new point();

  // Dit is dynamisch geheugen reserveren in C.
  POINT *p3 = (POINT *) malloc(sizeof(POINT));
  POINT *p4 = (POINT *) malloc(sizeof(POINT));
  POINT *p5 = (POINT *) malloc(sizeof(POINT));

  // Hier maken we de ketting.
  p3->x = 1;
  p3->y = 2;
  p3->volgende = p4;
  
  p4->x = 3;
  p4->y = 4;
  p4->volgende = p5;

  p5->x = 5;
  p5->y = 6;
  p5->volgende = NULL;

  toon(p3);

  // Het vrijgeven met free() ontbreekt nog
}

In het voorbeeld wordt de lijst met dynamisch gereserveerde struct’s expliciet aan elkaar geregen. Normaal gezien maken we daarvoor een functie. Deze functie kan een nieuw element aan het begin van de lijst bijvoegen. Dit is de snelst werkende oplossing; je hoeft hiervoor niet naar het einde van de lijst te lopen.

Een groot nadeel van de gelinkte lijst in C is dat je voor elk type een nieuwe implementatie moet maken. Daarom is het beter om vector<int> of list<int> te gebruiken; hier kan je het inhoudstype naar believen kiezen bij de declaratie van de lijst. Dit betekent dan ook dat we dan niet in C maar wel in C++ programmeren.