Dynamische Lijsten in C++

Hier de basis van de een recursieve structuur in C++, lijsten. Lijsten verwijzen naar zichzelf en om te snappen hoe ze werken kun je het beste onderstaand plaatje goed bestuderen.

Dit plaatje zegt alles over hoe de lijsten in elkaar steken. Dit zijn pointers die verwijzen naar een Knoop die op zijn beurt een lijst bevat met een element (de daadwerkelijke informatie, hierboven 1,2,3) en de volgende knoop. Nu eerst de basis, het bouwen van lijsten, het recursief berekenen van de lengte en het afdrukken.

Dynamische lijsten – basis code C++

#include <iostream>

using namespace std;

typedef class Knoop* Lijst; //de pointer naar knoop heet lijst.
typedef int Element; // het element is een integer.

const Lijst LegeLijst = NULL;

class Knoop{
    Element kop;         // eerste onderdeel van een Knoop.
    Lijst staart;   //pointer naar volgende
public:
    Knoop (Element hd, Lijst tl = LegeLijst ) : kop (hd), staart (tl) {}

    friend Element&  kop (Lijst);   //access funties op de velden.
    friend Lijst& staart (Lijst);
};

//Geeft de kop van de lijst.
Element& kop (Lijst l){
    assert (l != LegeLijst);
    return l-> kop;
}

//Geeft de staart van de lijst, dat ook weer een lijst is.
Lijst& staart (Lijst l){
    assert (l != LegeLijst);
    return l-> staart;
}

//Maakt een nieuwe knoop met kop en staart.
Lijst bouw (Element hd, Lijst tl = LegeLijst){
    return new Knoop (hd,tl);
}

//Berekent recursief de lengte van de lijst.
int lengteLijst (Lijst l){
    if (l == LegeLijst)
        return 0;
    else
        return 1 + lengteLijst (staart (l));
}

//Afdrukken van de lijsten met behulp van << operator
ostream& operator << ( ostream& os, Lijst l ){
    os << "[";
    for ( ; l != LegeLijst; l = staart ( l ))
        os << kop ( l ) << ( staart ( l ) == LegeLijst ? "" : "," );
    return os << "]";
}

//De main functie bouwt en drukt af.
int main (){
    Lijst l1 = bouw (2,bouw (1));
    Lijst l2 = bouw (2, bouw (1));
    Lijst l3 = bouw (3, l2);
    cout << l1 << " en " << l2 << " en " << l3 << endl;
    cout << "Lengte lijst 1: " << lengteLijst(l1) << endl;
    cout << "Lengte lijst 2: " << lengteLijst(l2) << endl;
    cout << "Lengte lijst 3: " << lengteLijst(l3) << endl;
    return 0;
}

Be Sociable, Share!

•