Opdracht 1: Een "homemade" gelinkte lijst.

© Harry Broeders.

Bij deze opdracht leer je zelf een dynamisch gelinkte lijst te maken. Later in deze cursus wordt de C++ standaard library besproken waarin ook een standaard implementatie van een dynamisch gelinkte lijst (genaamd list) is opgenomen. In de praktijk is het dus niet nodig om zelf een gelinkte lijst te maken maar het geeft wel veel inzicht om het één keer te doen. Tevens is het een goede herhaling van de OGOPRG stof.

In de propedeuse heb je datastructuren zoals array en struct leren gebruiken. Deze datastructuren worden statisch genoemd omdat hun grootte tijdens het compileren wordt bepaald en vast is. In de praktijk heb je al snel behoefte aan zogenaamde dynamische datastructuren waarvan de grootte tijdens het uitvoeren van het programma kan wijzigen. Later in deze cursus zul je leren dat in de standaard C++ library de class list is opgenomen die het gebruik van dynamische (gelinkte) lijsten erg eenvoudig maakt.

Dynamische geheugentoewijzing (herhaling uit OGOPRG).

Een pointer is een variabele die het adres kan bevatten van een eerder gedeclareerde variabele. Bij GESPRG heb je pointers als volgt leren gebruiken.

int i = 3;      // i wordt 3
int *pi = &i;   // pi wijst naar i
*pi = *pi + 5;  // i wordt 8

Het is nu dus mogelijk de waarde van de variabele i te benaderen met de dereferentie van pi: *pi

Bij OGOPRG heb je geleerd dat het ook mogelijk is voor een pointer een stuk geheugen te reserveren (met de new operator) dat niet direct gekoppeld is aan een eerder gedeclareerde variabele. De dereferentie van de pointer kan nu gebruikt worden als een gewone variabele. Dit is dan wel de enige manier om de waarde van deze "onbenoemde variabele" te benaderen. Voorbeeld van het gebruik van een pointer naar met new gereserveerd geheugen:

int* pi = new int; // pi wijst naar een onbenoemde variabele
*pi = 3;
*pi = *pi + 5;

Als het met new gereserveerde geheugen dat toegewezen is aan een bepaalde pointer niet meer nodig is moet het weer vrijgegeven worden met de operator delete. Voorbeeld van het met delete vrijgeven van met new gereserveerd geheugen:

delete pi;

Stel bijvoorbeeld dat de volgende declaratie van een class gegeven is:

class PlayTime {
public:
    PlayTime(int m = 0, int s = 0);
    void add(const PlayTime& t);
private:
    void normalize();
    int min;
    int sec;
    friend ostream& operator<<(ostream& out, const PlayTime& t);
};

int main() {
    PlayTime* pp;
    pp = new PlayTime(3, 20);
//  ...

Na de declaratie PlayTime* pp; is de variabele pp gecreëerd, zie figuur 1a. Deze variabele bevat echter nog een niet gedefinieerde waarde en er is nog geen geheugen gereserveerd voor een PlayTime object.

Na de toekenning pp = new PlayTime(3, 20); is een stuk geheugen gereserveerd dat groot genoeg is om één Playtime object te bevatten en dit object is geïnitialiseerd in de constructor. De variabele pp bevat nu het adres van dit gereserveerde stuk geheugen. Zie figuur 1b.

In figuur 1c is dit abstracter weergegeven omdat de waarde van het adres onbelangrijk is. De door pp aangewezen tijdsduur kan door middel van de notatie (*pp).add(*pp) bij zichzelf worden opgeteld. Dit kan ook als pp->add(*pp) genoteerd worden.

Na de instructie: deletepp; is het gereserveerde stuk geheugen weer vrijgegeven voor hergebruik, de variabele pp bestaat dan nog wel maar de inhoud hiervan is onbepaald. Zie weer figuur 1a.

Recursieve datastructuren.

Een recursieve class is een class die naar zichzelf verwijst. Bijvoorbeeld:

class PlayListElement {
public1:                   // Een PlayListElement bestaat uit:
   PlayTime pt;            // - een PlayTime
   PlayListElement* next;  // - een pointer naar het volgende PlayListElement
};

Door het gebruik van recursieve classes is het mogelijk recursieve datastructuren (bijvoorbeeld lijsten) te creëren van naar elkaar verwijzende objecten. Bijvoorbeeld:

PlayListElement e1, e2, e3;
PlayListElement* kop = &e1;
e1.next = &e2;
e2.next = &e3;
e3.next = 0;

Grafisch is direct duidelijk hoe zoiets eruit ziet:

Als in het vorige voorbeeld gebruik gemaakt wordt van dynamische geheugentoewijzing dan wordt de code als volgt:

PlayListElement* kop;
PlayListElement* staart;
PlayListElement* hulp;

kop = new PlayListElement; staart=kop;                          // eerste
hulp = new PlayListElement; staart->next = hulp; staart = hulp; // tweede
hulp = new PlayListElement; staart->next = hulp; staart = hulp; // derde
staart->next = 0;

Precies hetzelfde wordt bereikt met het onderstaande algoritme dat iets korter is:

PlayListElement* kop = new PlayListElement;
PlayListElement* staart = kop;
staart->next = new PlayListElement;
staart = staart->next;
staart->next = new PlayListElement;
staart = staart->next;
staart->next = 0;

Grafisch is dit als volgt weer te geven:

Merk op dat het enige verschil tussen figuur 2 en figuur 3 is dat in figuur 3 de variabelenamen e1, e2 en e3 niet voorkomen.

Voetnoot 1: Deze class bevat public datamembers en er is dus geen sprake van "encapsulation" of datahiding. Dit was tegen de regels van goed object georiënteerd programmeren! We zullen later zien dat deze class alleen als private class binnen een andere class wordt gebuikt waardoor toch een goed object-oriënted programma ontstaat.

Voorbeeldprogramma.

Tot slot van deze inleiding over dynamische gelinkte lijsten volgt nog een voorbeeld waarin een aantal manipulaties met lijsten is opgenomen. Dit programma kun je hier kopiëren: lijst.cpp .

#include  <iostream>
#include  <iomanip>
#include  <fstream>
using namespace std;

// =============================================================================

class PlayTime {
public:
    PlayTime(int m = 0, int s = 0);
    void add(const PlayTime& t);
private:
    void normalize();
    int min;
    int sec;
friend ostream& operator<<(ostream& out, const PlayTime& t);
};

istream& operator>>(istream& in, PlayTime& t);

PlayTime::PlayTime(int m, int s): min(m), sec(s) {
    normalize();
}

void PlayTime::add(const PlayTime& t) {
    min += t.min;
    sec += t.sec;
    normalize();
}

void PlayTime::normalize() {
    long long tsec = min * 60 + sec;
    min = tsec / 60;
    sec = tsec % 60;
}

ostream& operator<<(ostream& out, const PlayTime& t) {
    return out << setfill('0') << setw(2) << t.min << ":" << setw(2) << t.sec;
}

istream& operator>>(istream& in, PlayTime& t) {
    int i;
    if (in >> i) {
        if (in.peek() == ':') {
            in.get();
            int j;
            if (in >> j) {
                t = PlayTime(i, j);
            }
        }
        else {
            t = PlayTime(0, i);
        }
    }
    return in;
}

// =============================================================================

// De class PlayList bevat:
// -  een pointer naar een PlayListElement genaamd first dit is het eerste
//    element in de gelinkte lijst.
//    -  een PlayListElement bevat:
//       -  een PlayTime object genaamd pt.
//       -  een pointer naar een PlayListElement genaamd next.
//          (deze pointer is 0 als de lijst geen elementen meer heeft).

class PlayList {
public:
    PlayList();
    ~PlayList();
    void insert(const PlayTime& t);
    PlayTime total() const;
private:
    class PlayListElement {
    public:
        PlayTime pt;
        PlayListElement* next;
    };
    PlayListElement* first;
friend ostream& operator<<(ostream& out, const PlayList& l);
};

istream& operator>>(istream& in, PlayList& l);

PlayList::PlayList(): first(0) {
}

PlayList::~PlayList() {
    while (first != 0) {
        PlayListElement* listElement = first;
        first = first->next;
        delete listElement;
    }
}

PlayTime PlayList::total() const {
    PlayTime t;
    PlayListElement* pList = first;
    while (pList) {
        t.add(pList->pt);
        pList = pList->next;
    }
    return t;
}

void PlayList::insert(const PlayTime& t) {
    PlayListElement* newlistElement = new PlayListElement;
    newlistElement->pt = t;
    newlistElement->next = first;
    first = newlistElement;
}

ostream& operator<<(ostream& out, const PlayList& l) {
    PlayList::PlayListElement* pList = l.first;
    while (pList != 0) {
        out << pList->pt << endl;
        pList = pList->next;
    }
    return out;
}

istream& operator>>(istream& in, PlayList& l) {
    PlayTime pt;
    while (in >> pt) {
        l.insert(pt);
    }
    return in;
}

// =============================================================================

int main () {
    ifstream fin("playlist.txt");
    if (fin) {
        PlayList lijst;
        fin >> lijst;
        cout << "De lijst:" << endl << lijst;
        cout << "Totale speelduur: " << lijst.total() << endl;
    }
    else {
        cout << "De file playlist.txt kan niet worden geopend!" << endl;
    }
    cout << "Druk op de return-toets." << endl;
    cin.get();
    return 0;
}

Weet je de antwoorden op de volgende vragen nog?

   PlayTime t;

   fin >> lijst;

   istream& operator>>(istream& in, PlayList& l);

Opdrachtomschrijving.

Deze opdracht bestaat uit de deelopdrachten 1a t/m 1g. Alle deelopdrachten moet je laten nakijken door de practicumdocent.

In het voobeeldprogramma worden de speeltijden die zijn opgeslagen in de file playlist.txt in de functie main door middel van een zelf gedefinieerde operator>> ingelezen in een dynamisch gelinkte lijst. Een datafile waarmee het programma getest kan worden is hier beschikbaar: playlist.txt . De gelinkte lijst wordt in de operator>> als volgt gevuld:

istream& operator>>(istream& in, PlayList& l) {
    PlayTime pt;
    while (in >> pt) {
        l.insert(pt);
    }
    return in;
}

De memberfunctie insert is als volgt gedefinieerd:

void PlayList::insert(const PlayTime& t) {
    PlayListElement* newlistElement = new PlayListElement;
    newlistElement->pt = t;
    newlistElement->next = first;
    first = newlistElement;
}

Vervolgens wordt de lijst vanuit de functie main afgedrukt:

cout << "De lijst:" << endl << lijst;

Deze zelf gedefinieerde operator<< drukt de inhoud van de gelinkte lijst op het beeldscherm af:

ostream& operator<<(ostream& out, const PlayList& l) {
    PlayList::PlayListElement* pList = l.first;
    while (pList != 0) {
        out << pList->pt << endl;
        pList = pList->next;
    }
    return out;
}

Vanuit deze operator<< wordt een andere zelf gedefinieerde operator<< aangeroepen die er voor zorgt dat een PlayTime wordt afgedrukt. Het gebruik van twee operatoren (of functies) met dezelfde naam (maar met verschillende parametertypes) wordt operator overloading (of function overloading) genoemd.

Zorg ervoor dat je de werking van dit programma volledig begrijpt! Stel vragen aan de docent als er iets is wat je nog niet helemaal begrijpt.

   cout << "Aantal elementen: " << lijst.numberOfElements() << endl;

   int numberOfElements() const;

Aan het eind van de if in de functie main wordt de destructor van PlayList automatisch aangeroepen. Deze destructor geeft het met new dynamisch gereserveerde geheugen, door middel van delete, weer vrij voor hergebruik. Deze destructor kan niet als volgt gecodeerd worden:

PlayList::~PlayList() {
    while (first != 0) {
        delete first;
        first = first->next;
    }
}

Door de pointer naar het volgende PlayListElement in een hulp variabele op te slaan is de destructor in het voorbeeldprogramma wel correct gecodeerd:

PlayList::~PlayList() {
    while (first != 0) {
        PlayListElement* listElement = first;
        first = first->next;
        delete listElement;
    }
}

De destructor kan met behulp van een hulp functie dump ook als volgt gecodeerd worden:

void PlayList::dump(PlayListElement* p) {
    if (p != 0) {
        dump(p->next);
        delete p;
    }
}

PlayList::~PlayList() {
    dump(first);
}

De functie dump is een recursieve functie. Dat wil zeggen dat deze functie zichzelf aanroept.

Als je een element uit een gelinkte lijst moet verwijderen dan is dit best wel lastig. Als je bijvoorbeeld het tweede element uit een gelinkte lijst moet verwijderen dan moet je er eerst voor zorgen dat het eerste element naar het derde element verwijst. Pas daarna kun je het tweede element met behulp van delete opruimen. Het verwijderen van het eerste element heeft tot gevolg dat de pointer naar het begin van de lijst wijzigd.

   void verwijder(int n)

   lijst.verwijder(3);
   lijst.verwijder(1);
   lijst.verwijder(55);
   cout << "Na verwijderen: " << endl << lijst;

Na verwijderen:
10:09

Verder met opgave 2...