Opdracht 1: Een "homemade" gelinkte lijst.

© Harry Broeders.

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 dit kwartaal zul je leren dat in de standaard C++ library de class list is opgenomen die het gebruik van dynamische (gelinkte) lijsten erg eenvoudig maakt. Om een goed begrip te krijgen van de werking van dynamische datastructuren is het toch leerzaam om zelf eens een eenvoudige gelinkte lijst te maken.

Dynamische geheugentoewijzing (herhaling uit H1).

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

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

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

In H1 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 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);
};
// ...
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 object.

Na de toekenning pp=new PlayTime(3,20); is een stuk geheugen gereserveerd dat groot genoeg is om 1 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: delete pp; 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 zou worden van dynamische geheugentoewijzing dan 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 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!=0) {
      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?

Q: Noem twee voordelen van het gebruik van een ADT PlayTime in plaats van een struct PlayTime.
A: Doordat de datamembers in een ADT private zijn en dus alleen bereikbaar via de memberfuncties van de ADT (we noemen dit datahiding) kun je de implementatie van een ADT wijzigen zonder dat de rest van het programma daar iets van merkt. Het gebruik van een ADT maakt het programma beter aanpasbaar en uitbreidbaar. Doordat in een ADT niet alleen de structuur van de data is vastgelegd maar ook de bewerkingen die op of met deze data kunnen worden uitgevoerd (de memberfuncties) is een ADT eenvoudiger herbruikbaar.
-
Q: De parameter t van de memberfunctie add is van het type const PlayTime&. Kan hier ook het type PlayTime gebruikt worden? Wat is dan het voordeel/nadeel?
A: Ja dat kan. Bij het gebruik van het type PlayTime wordt dan wel een kopie van de parameter die bij aanroep meegegeven wordt gebruikt. Het aanmaken en weer verwijderen van deze kopie kost tijd en heeft dus als nadeel dat het trager is. Bij het gebruik van een PlayTime& wordt geen kopie gemaakt van de parameter die bij aanroep wordt meegegeven maar wordt een reference naar (andere naam voor) deze parameter gebruikt. Omdat we deze reference alleen willen gebruiken om de waarde van de bij aanroep meegegeven parameter te lezen gebruiken we een const PlayTime &.
-
Q: Kun je een object van de class PlayTime als volgt definiëren? 
   PlayTime t;

Zo nee, waarom niet? Zo ja, wat is dan de waarde?
A: Ja dat kan. De class PlayTime moet dan wel een constructor hebben zonder argumenten of een constructor waarbij alle parameters een default waarde hebben. PlayTime heeft de volgende constructor PlayTime(int m=0, int s=0);. Als je deze constructor aanroept zonder parameters mee te geven dan wordt m gelijk aan 0 en s ook gelijk aan 0. In de implementatie van deze constructor kun je zien dat de private variabele min geïnitialiseerd wordt met m en dat de private variabele sec geïnitialiseerd wordt met s. De waarde van t is dus 00:00.
-
Q: De operator<< voor het afdrukken van objecten van de class PlayTime heeft als tweede parameter een const PlayTime&. De operator>> voor het inlezen van objecten van de class PlayTime heeft als tweede parameter een PlayTime&. Verklaar dit verschil.
A: De als parameter van operator>> moet veranderd (ingelezen) kunnen worden en kan dus geen const zijn. Bij het afdrukken mag de operator<< het af te drukken object niet wijzigen de parameter moet dus const zijn.
-
Q: De operator<< voor het afdrukken van objecten van de class PlayTime is als friend van PlayTime gedeclareerd. De operator>> voor het inlezen van objecten van de class PlayTime is niet als friend gedeclareerd. Verklaar dit verschil.
A: In de implementatie van de operator<< kun je zien dat in deze code de private variabelen van de class PlayTime gebruikt worden dit kan alleen als deze operator<< een memberfunctie van PlayTime is (maar dat is niet zo) of als deze operator<< een friend is van de class PlayTime. In de implementatie van de operator>> kun je zien dat deze operator de private variabelen van PlayTime helemaal niet nodig heeft.
-
Q: De class PlayListElement heeft public member variabelen. Dit mag toch niet als je het programma goed uitbreidbaar en aanpasbaar wil maken? Zie ook het antwoord op de eerste vraag.
A: In dit geval mag het wel omdat de class PlayListElement als private class binnen PlayList gedefinieerd is. De class PlayListElement is dus alleen in memberfuncties (of fiends) van de class PlayList te gebruiken. In dit geval zou je dus net zo goed een struct kunnen gebruiken.
-
Q: In de vierde regel van main staat: 
   fin>>lijst;

De operator>> die wordt aangeroepen is als volgt gedeclareerd: 

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

De eerste parameter is echter van het type ifstream in plaats van istream. Waarom geeft de compiler hier geen foutmelding?
A: Er wordt gebruik gemaakt van polymorphism. De class ifstream is afgeleid van de class istream. Er geldt een ifstream is een istream.

Opdrachtomschrijving.

Deze opdracht bestaat uit de deelopdrachten 1a t/m 1g. Opgave 1a t/m 1f moet je laten nakijken door de practicumdocent. Opgave 1g is niet verplicht maar wel leerzaam.

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;
}

Opdracht 1a.

Loop stap voor stap het inlezen van de file door en teken daarbij de gelinkte lijst die ontstaat. Je kunt met C++ Builder het programma stap voor stap volgen door een breakpoint te zetten op de eerste regel (met de sneltoets F5) en daarna met de sneltoetsen F7 en F8 het programma regel voor regel uit te voeren:

  • F7 = Stap naar de volgende C++ regel die wordt uitgevoerd. Als de huidige regel een of meer (member)functies aanroept dan wordt gesprongen naar de eerste regel van de eerste (member)functie die wordt aangeroepen.
  • F8 = Stap naar de volgende C++ regel in de code. Als de huidige regel een of meer (member)functies aanroept dan worden deze (member)functies zonder te stoppen uitgevoerd.

Je kunt de objectstructuren mooi zichbaar maken door op een objectnaam (variabelenaam) te gaan staan met de muis en dan rechts te klikken en de popup menu optie Debug, Inspect... te kiezen (sneltoets Alt+F5). Als een datamember van het object een pointer is dan kun je het object waar die pointer naar wijst bekijken door deze datamember te selecteren en dan via de rechtermuis optie Inspect (sneltoets Ctrl+I) te kiezen.

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.

Opdracht 1b.

Loop stap voor stap het uitvoeren van de operator<< door. Maak daarbij gebruik van de in opgave 1a gemaakte tekening.

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.

Opdracht 1c.

Ontwerp nu zelf een memberfunctie van PlayList die het aantal elementen in een lijst telt. Deze functie moet vanuit de functie main als volgt aangeroepen worden: 

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

De declaratie van de memberfunctie is dus: 

   int numberOfElements() const;

Aan het eind van de if 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;
   }
}

Opdracht 1d.

Bedenk waarom de bovenstaande destructor niet correct is. Als je de bovenstaande destructor probeert uit te voeren zul je merken dat deze destructor toch goed lijkt te werken. Bedenk waarom dat dit erg gevaarlijk is!

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.

Opdracht 1e.

Speel stap voor stap het uitvoeren van de destructor na. Maak daarbij gebruik van de in opgave 1a gemaakte tekening. In welke volgorde worden de elementen vrijgegeven?

Opdracht 1f.

Ontwerp en implementeer een memberfunctie die de inhoud van de gelinkte lijst van achter naar voor afdrukt met behulp van een recursieve hulp functie.

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.

Opdracht 1g(niet verplicht).

Ontwerp en implementeer een functie waarmee element n uit een gelinkte lijst kan worden verwijderd. 

   void remove(int n)

Deze memberfunctie moet element n verwijderen uit de lijst. Het element dat verwijderd moet worden, moet natuurlijk netjes met delete worden vrijgegeven. Als de gelinkte lijst minder dan n elementen bevat mag de functie de lijst niet wijzigen. De functie mag dan natuurlijk ook niet "vastlopen".

Test deze functie door in het hoofdprogramma toe te voegen: 

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

De juiste uitvoer is: 

Na verwijderen:
10:09

Verder met opgave 2...