[hand]
1. Een linked list (met behulp van objectgerinteerd programmeren)
Inhoud
- [linkje]Vereiste voorkennis[/linkje]
- [linkje]Wat is een linked list?[/linkje]
- [linkje]Wat moet een linked list allemaal kunnen?[/linkje]
- [linkje]Achtergrond[/linkje]
- [linkje]Opzet van de implementatie[/linkje]
- [linkje]De lijst[/linkje]
- [linkje]Itereren[/linkje]
- [linkje]Terug naar de lijst[/linkje]
- [linkje]Het controleren van de geschreven code[/linkje]
Opdrachten
- [linkje]Opdracht 1.1[/linkje]
- [linkje]Opdracht 1.2[/linkje]
- [linkje]Opdracht 1.3[/linkje]
- [linkje]Opdracht 1.4[/linkje]
- [linkje]Opdracht 1.5[/linkje]
- [linkje]Opdracht 1.6[/linkje]
- [linkje]Opdracht 1.7[/linkje]
- [linkje]Opdracht 1.8[/linkje]
In deze handleiding zullen we een datastructuur maken in C++ die het makkelijk maakt om de elementen van een lijst bij te houden. Deze structuur is met name makkelijk als we vaak ergens een element moeten toevoegen of verwijderen. Het is minder geschikt om een element uit de lijst op een willekeurige positie in de lijst op te zoeken.
In de tutorial staan een aantal opdrachten. Deze komen er in feite op neer dat je de precieze implementatie van wat we hebben besproken moet uitvoeren. Dit houdt dus in dat je niet alles voorgekauwd krijgt, maar het wel duidelijk zal zijn wat je zelf nog moet doen. Mocht je er niet uitkomen (wat overigens helemaal niet gek is) of wil je commentaar op de code die je hebt geschreven, maak dan even een postje in het Programmeren deelforum (
http://www.nationaalcomputerforum.nl/forumdisplay.php?f=37).
[kopje]Vereiste voorkennis[/kopje]
Om deze handleiding goed te kunnen volgen, moet je het volgende al kennen:
- Je moet weten wat objectgerinteerd programmeren (OOP) inhoudt. (Zie http://nl.wikipedia.org/wiki/OOP)
- Je moet kunnen omgaan met pointers. Dit moet je eigenlijk redelijk goed beheersen. Dat is, je moet goed begrijpen wat een pointer precies is, hoe je bij de data waarnaar de pointer verwijst komt en waar je bij pointers op moet letten (op 0 initialiseren, enz.). We zullen geen gebruik maken van operaties op pointers, zoals verhogen of verlagen van pointers of het verschil van twee pointers nemen.
- Je moet om kunnen gaan met het dynamisch alloceren van geheugen (new en delete).
- Je moet weten hoe een klasse (class) werkt en wat friends zijn. We zullen geen overerving (inheritance), oftewel afgeleide klassen gebruiken.
- Je moet zelf een programma kunnen maken in C++. Dat houdt in dat ik je niet precies ga vertellen wat je moet intypen of aanklikken. De code die we maken, kun je allemaal in 1 .h bestand zetten, dan is het makkelijker om het later aan te passen naar een template versie. Je mag natuurlijk ook eigenwijs zijn en de implementatie in een .cpp bestand zetten.
[kopje]Wat is een linked list?[/kopje]
Een linked list is een lijst (duh!) die op een speciale manier is gemaakt, zodat je snel een element aan de lijst kunt toevoegen op een willekeurige plek en snel een element uit de lijst kunt verwijderen. Verder is het mogelijk om snel over de elementen van de lijst te lopen (in volgorde), maar het is niet mogelijk om snel een willekeurig element van de lijst te benaderen.
Het principe is dat we bij ieder element dat we in de lijst opslaan een verwijzing opslaan naar het volgende element. Op die manier kunnen we over alle elementen van de lijst 'lopen' als we het eerste element kennen. Zie ook
http://nl.wikipedia.org/wiki/Linked_list tot en met het stuk over enkelvoudig gelinkte lijsten.
[kopje]Wat moet een linked list allemaal kunnen?[/kopje]
Het is natuurlijk allemaal leuk en aardig om een datastructuur te verzinnen, maar het is wel zo prettig als we die vervolgens ook kunnen gebruiken. Laten we dus even heel precies bedenken wat we allemaal met die datastructuur willen doen.
- We willen een lijst van elementen van hetzelfde type bijhouden (bijvoorbeeld een lijst van getallen). De volgorde waarin we de getallen zetten moet behouden blijven.
- We willen elementen kunnen toevoegen aan het begin of het einde van de lijst.
- We willen het eerste element van de lijst kunnen opvragen en verwijderen. Samen met de vereiste hierboven kunnen we dan een FIFO of LIFO systeem maken (de vakkenvullers weten waar ik het over heb , voor de rest http://nl.wikipedia.org/wiki/Fifo en http://nl.wikipedia.org/wiki/Lifo).
- We willen het aantal elementen in de lijst kunnen opvragen.
- We willen over de elementen van de lijst kunnen itereren ('lopen').
[kopje]Achtergrond[/kopje]
Het idee van een linked list is al behoorlijk oud. Het werd ook al in C gebruikt, maar in die tijd was het idee van OOP nog niet zo ver doorgedrongen (en de taal staat het niet zo goed toe), dus wat je meestal zag was dat mensen de datastructuur telkens opnieuw implementeerden als ze die nodig hadden. Het is natuurlijk makkelijker als je de algemene operaties maar 1 keer hoeft te (laten) implementeren en ze dan telkens kunt gebruiken.
In veel C++ programma's zie je nog sporen van C programmeerstijlen. Zo ook bij linked lists. Je kunt bijvoorbeeld
hier (klikbaar) zien dat de abstractie en OO te wensen overlaat (een element van de lijst (Node) is tegelijk de lijst zelf :blink: wat gebeurt er dan als ik een Node kopieer; kopieer ik dan het element of de hele lijst?). Bovendien is de implementatie onveilig, ingewikkeld en inefficient door het gebruik van pointers naar de data. Verder is de gebruikte naamgeving dubbelzinnig en de implementatie inefficient (met name de functie addNode(...)).
Kortom, dit kan (veel) beter.
[kopje]Opzet van de implementatie[/kopje]
We maken dus een lijst die de bovengenoemde operaties moet kunnen uitvoeren. Maar wat slaat die lijst dan op? Elementen (what's in a name?
). Een element is gewoon een object van een bepaald vooraf gedefinieerd type. Laten we er even vanuit gaan dat we een lijst van integers gaan opslaan (we kunnen dit type later veranderen).
Code:
typedef int elemType; // het type van een element in de lijst
Een element slaat dus een int op, maar vanwege de structuur van een linked list, moet bij die int een verwijzing naar het volgende element in de lijst worden opgeslagen. Omdat de int en verwijzing bij elkaar moeten worden opgeslagen, maken we er een apart object van. Dit object vormt dan een 'schakel' in de lijst, dus laten we het een Link noemen.
De gebruiker van de list hoeft echter niks van dit object af te weten, omdat die alleen genteresseerd is in wat de lijst kan doen, niet hoe het gemplementeerd is. Dus is het een goed idee om alleen het list object toegang te geven tot het element.
Code:
class Link
{
friend class List; // alleen de list mag dit element gebruiken
private:
Link(elemType data, Link* pNext); // kan alleen door een list gemaakt worden
elemType m_Element;
Link* m_pNext;
};
Aangezien alleen de lijst van het bestaan van een link hoeft te weten, is het het beste om de klassedefinitie van Link (straks) in het protected gedeelte van de List klasse (die we nog moeten maken) te zetten.
[kopje]Opdracht 1.1[/kopje]: Implementeer de constructor van Link, die de opgegeven argumenten in de member variabelen opslaat.
[kopje]De lijst[/kopje]
Onze lijst is dus opgebouwd uit allemaal links die naar elkaar verwijzen. Als we dus bij de eerste link zijn, kunnen we via die verwijzingen naar iedere link in de lijst 'lopen' en dus ieder element van de lijst benaderen. Dat betekent dus dat we alleen maar een verwijzing naar de eerste link hoeven bij te houden, om bij alle elementen te kunnen komen. Laten we deze variabele de kop van de lijst (head) noemen.
Code:
class List
{
public:
List();
~List();
List(const List& that); // copy constructor
List& operator =(const List& that); // assignment operator
private:
Link* m_pHead; // owned; begin van de lijst
};
Achter de definitie van m_pHead zie je het commentaar 'owned' staan. Dit is om te verduidelijken dat m_pHead verwijst naar een dynamisch gealloceerd object en dat de klasse List verantwoordelijk is voor het vrijgeven van de gealloceerde geheugenruimte (delete m_pHead; ). De Link objecten die we gebruiken om de elementen van de lijst op te slaan worden dus dynamisch gealloceerd.
Omdat m_pHead een dynamisch gealloceerd object is, moeten we de destructor, copy constructor en assignment operator van de klasse List zelf implementeren (de default implementatie kopieert alleen de waarde van de pointer). We zullen dit later doen. Laten we eerst even kijken naar hoe we over de lijst kunnen itereren, dan wordt het waarschijnlijk wat duidelijker hoe de datastructuur precies in elkaar zit.
[kopje]Itereren[/kopje]
De lijst heeft een verwijzing naar de eerste link in de lijst en iedere link heeft een verwijzing naar de volgende link in de lijst. Dat betekent dus dat de laatste link in de lijst naar niets verwijst. Dit kunnen we aangeven door de pointer m_pNext in die link de waarde 0 te geven (goed onthouden!).
Als we een verwijzing naar een link hebben, kunnen we bij het element dat in die link wordt opgeslagen komen. Herinner je dat we eerder al hebben gezegd dat de gebruiker van de klasse niet van het bestaan van de klasse Link hoeft te weten, omdat die daar niet in is genteresseerd. Wel moet het mogelijk zijn om over de elementen van de lijst te 'lopen'. We noemen dit itereren en dit doen we met een
iterator. Een iterator is een object waarmee we over de elementen van de lijst kunnen lopen en toegang hebben tot het element waar we 'op staan'. Het moge duidelijk zijn dat een iterator dus in feite neerkomt op een verwijzing naar een Link object. Echter, omdat het iterator object door de gebruiker van de List klasse gebruikt zal worden, moeten we er een aparte klasse van maken, die de vereiste functionaliteit biedt.
Wat is die functionaliteit dan precies? Wat willen we precies allemaal kunnen doen, als we over de lijst willen itereren.
- We willen bij het eerste element in de lijst kunnen beginnen.
- We willen naar het volgende element in de lijst kunnen gaan, als we op een element staan.
- We willen weten wanneer we moeten ophouden met itereren, dat is, wanneer we bij het einde van de lijst zijn aangekomen.
- We willen het element waar we op staan kunnen benaderen.
We hebben het in deze vereisten telkens over 'de lijst'. Dat betekent dus dat een iterator moet weten over welke lijst we het hebben, oftewel de klasse Iterator moet een verwijzing hebben naar een List object. Nu zouden we voor die verwijzing een pointer naar een List kunnen nemen, maar wat zou het dan betekenen als de waarde van die pointer 0 is? Dan zou de iterator naar geen lijst verwijzen, dus zouden we het in de vereisten hierboven telkens hebben over een lijst die helemaal niet bestaat.
We kunnen dus beter een reference gebruiken voor de verwijzing naar de lijst, want die verwijst altijd naar een valide object.
Verder hebben we al eerder gezien dat een iterator dus in feite een verwijzing naar een Link is. Ook hier kunnen we ons weer afvragen of we een pointer of een reference willen gebruiken. Daarvoor stellen we weer de vraag: is het zinnig als een iterator naar geen Link verwijst? (dit is geen simpele vraag, neem er gerust ff de tijd voor)
Het antwoord op de vraag zal wat duidelijker worden door een andere vraag te stellen: Naar welk Link object verwijst een iterator van een lijst die leeg is (dus geen elementen bevat)?
Kijk nu ff in de spiegel. Als je zoiets ziet :wacko:, geeft niks, gewoon later nog een keer lezen.
Voor de verwijzing naar een link nemen we dus een pointer. Onze klasse definitie komt er dan ongeveer zo uit te zien:
Code:
class Iterator
{
public:
Iterator(List& rList);
// assignment operator kan alleen worden uitgevoerd als de iterators naar dezelfde lijst verwijzen
Iterator& operator =(const Iterator& that);
void GotoBegin(); // gaat naar het begin van de lijst
void GotoNext(); // gaat naar het volgende element; alleen aanroepen als AtEnd() false teruggeeft
bool AtEnd() const; // geeft aan of we klaar zijn met itereren (voorbij het einde van de lijst zijn)
elemType& GetElement() const;
private:
List& m_rList;
Link* m_pLink;
};
De functie AtEnd() is een zogenaamde const functie. Dit houdt in dat de functie de member variabelen van het object niet kan veranderen. Het is goed om bij het programmeren alle dingen die constant kunnen zijn, ook constant te maken (dit heet 'const correctness').
Omdat het misschien nog niet helemaal duidelijk is hoe het itereren in zijn werk gaat, zullen we de implementatie van de functie AtEnd() alvast geven.
Code:
bool Iterator::AtEnd() const
{
return (m_pLink == 0);
}
We zijn dus bij het einde van de lijst beland, als de verwijzing naar de link 0 is. Dit komt overeen met wat we eerder hebben gezegd: de verwijzing naar de volgende Link in het Link object is 0 voor de laatste link in de lijst. Het werkt ook prima als we itereren over een lege lijst (ga dit na!).
[kopje]Opdracht 1.2[/kopje]: Implementeer de overige functies van de klasse Iterator, behalve de assignment operator. De implementatie van de assignment operator krijg je cadeau. Deze is wellicht wat te ingewikkeld, als je het goed wilt doen.
Code:
Iterator& Iterator::operator =(const Iterator& that)
{
if (this != &that) {
if (&m_rList != &that.m_rList)
{
assert(false); // kan geen iterator van een andere lijst kopiren
throw("Iterator assignment operator failed.");
}
m_pLink = that.m_pLink;
}
return *this;
}
Om de functie assert(...) te kunnen gebruiken moet je de STL header 'cassert' includeren. Na die assertion wordt een exceptie gegooit met throw. Dit zorgt ervoor dat de executie van het programma stopt en teruggaat naar een bepaald punt (waar een 'catch' staat). Het is niet nodig om dit precies te begrijpen om verder te kunnen. Het gaat erom dat we hier controleren dat de twee Iterator objecten (this en that) naar dezelfde lijst verwijzen.
Omdat we van Iterator een apart object hebben gemaakt en de functionaliteit niet direct in de lijst hebben gestopt, is het mogelijk om met meer dan 1 iterator tegelijk door de lijst te lopen. Dit is bijvoorbeeld nodig om naar alle paren van elementen in de lijst te kijken. Bijv.:
Code:
List myList;
Iterator it1(myList);
for (it1.GotoBegin(); !it1.AtEnd(); it1.GotoNext())
{
Iterator it2(myList);
for (it2.GotoBegin(); !it2.AtEnd(); it2.GotoNext())
{
std::cout << "(" << it1.GetElement() << ", " << it2.GetElement() << ")" << std::endl;
}
}
Hier kun je vrij goed zien wat het nut is van OOP.
[kopje]Terug naar de lijst[/kopje]
Ok, hopelijk heeft het implementeren van de Iterator wat meer inzicht gegeven in hoe de lijst werkt. Zo niet, vraag dan gerust om meer uitleg van de dingen die je niet snapt in het deelforum Programmeren.
We hebben al een klassedefinitie van de klasse List. We hebben ook al gezien dat de Link objecten die we daarin opslaan dynamisch gealloceerde objecten zullen zijn. Daardoor kunnen we niet met de default impelementatie van destructor, copy constructor en assignment operator volstaan. We zullen deze dus nog moeten implementeren. Maar laten we eerst naar het wat leukere deel gaan; het implementeren van de functionaliteit die we bovenaan hebben genoemd. Hiervoor kunnen we de volgende functiedeclaraties aan de klasse List toevoegen (public natuurlijk).
Code:
void AddAtBegin(elemType data);
void AddAtEnd(elemType data);
elemType RemoveFirst();
int GetSize() const;
All deze operaties moeten we in O(1) (constante) tijd kunnen uitvoeren. Dat houdt in dat we in de implementatie niet mogen itereren over de links van de lijst. Dit betekent dus dat we wat member variabelen zullen moeten toevoegen voor de functies AddAtEnd(...) en GetSize(). Voor de functie GetSize() is dit simpel; we slaan gewoon in de lijst op hoeveel elementen erin zitten.
[kopje]Opdracht 1.3[/kopje]: Implementeer de functie GetSize().
Als de lijst leeg is, is er geen eerste element waarnaar m_pHead kan verwijzen. In dat geval moet de waarde van m_pHead dus 0 zijn. Dit kunnen we alvast in de contructor van de klasse List implementeren.
[kopje]Opdracht 1.4[/kopje]: Implementeer de constructor van de klasse List. Zorg ervoor dat de functie GetSize() het juiste aantal elementen teruggeeft, nadat een List object is gecreerd.
In de functie AddAtBegin(...) moeten we een link maken waarin we het opgegeven element opslaan (onthoud dat de Link objecten dynamisch gealloceerd moeten worden). Deze link wordt het nieuwe begin van de lijst en de verwijzing naar het volgende element zal dus verwijzen naar het oude begin van de lijst.
[kopje]Opdracht 1.5[/kopje]: Implementeer de functie AddAtBegin(...). Zorg ervoor dat de functie GetSize() nog altijd het juiste aantal elementen teruggeeft.
De functie RemoveFirst() verwijdert de eerste link uit de lijst en retourneert een kopie van het element dat in die link zat. De functie mag alleen aangeroepen worden als de lijst niet leeg is, dus is het makkelijk om een functie te maken die dat controleert, laten we zeggen de functie IsEmpty.
[kopje]Opdracht 1.6[/kopje]: Voeg de functie IsEmpty toe aan de klasse List en implementeer de functie RemoveFirst(). Let erop dat gealloceerd geheugen ook weer wordt vrijgegeven.
We hebben eerder al gezegd dat we niet willen dat de functie AddAtEnd(...) over alle elementen van de lijst moet itereren. Als we direct iets aan het einde van de lijst willen toevoegen, moeten we dus een verwijzing naar het laatste element bijhouden. We moeten dan ook in de andere functies erop letten dat die verwijzing naar het juiste element blijft verwijzen.
[kopje]Opdracht 1.7[/kopje]: Voeg de verwijzing naar het laatste element in de lijst toe aan de klasse List en noem dit m_pTail (de staart van de lijst). Pas de reeds gemplementeerde functies aan. Implementeer de functie AddAtEnd(...). Hiervoor kun je veel spieken van de functie AddAtBegin(...).
Nu we alle vereiste functionaliteit hebben gemplementeerd, kunnen we schematisch weergeven hoe de lijst werkt. Zo'n tekening kan erg behulpzaam zijn bij het controleren van de implementatie en het implementeren van extra functionaliteit. Zo'n schema kan er bijvoorbeeld zo uitzien:
Bovenaan zie je de verschillende links van de lijst (in dit geval 3). De pijltjes zijn de verwijzingen naar de volgende link in de link. De laatste link in de lijst verwijst niet naar een volgende link, maar naar 0. De lijst heeft 2 verwijzingen naar een link, namelijk m_pHead en m_pTail. De eerste verwijst naar het eerste element van de lijst en de tweede naar het laatste element.
Dan rest ons alleen nog de implementatie van de destructor, copy constructor en assignment operator. Hierbij is het van belang dat we goed omgaan met het dynamisch gealloceerde geheugen. De klasse List is in dit geval verantwoordelijk voor het verwijderen van alle aangemaakte objecten, aangezien die ook in de klasse List dynamisch worden gealloceerd. We kunnen dit controleren door na te gaan dat voor iedere
aanroep van new precies 1 keer delete wordt aangeroepen.
Als je niet al het gealloceerde geheugen vrijgeeft in een stuk code (dit heet een memory leak), kan dat grote gevolgen hebben: je applicatie zal belachelijk veel geheugen nodig hebben, waardoor je pc zal gaan swappen (en het programma ontzettend langzaam wordt) en uiteindelijk zal het programma gaan klagen dat er niet genoeg geheugen is en crashen. Tegelijk is het opsporen van memory leaks erg moeilijk als je er niet de juiste tools voor hebt. Het is dus raadzaam om op het web op zoek te gaan naar dergelijke tools. Anderzijds is het gebruiken van je eigen verstand ook een goed hulpmiddel.
Het implementeren van deze drie functies kunnen we een stuk vergemakkelijken door gebruik te maken van de functies die we al hebben.
[kopje]Opdracht 1.8[/kopje]: Implementeer deze functies.
[kopje]Het controleren van de geschreven code[/kopje]
De code die we nu hebben geschreven, moeten we natuurlijk eerst nog eens grondig testen om enige zekerheid te krijgen dat ie daadwerkelijk doet wat die moet doen. We kunnen dit het makkelijkst doen met een zogenaamd driver programmaatje. Dat is een simpel zelfgemaakt programma wat je uitsluitend gebruikt om te controleren of de code die je hebt geschreven correct werkt.
Een voorbeeldje:
Code:
#include "list.h"
#include <iostream>
void DisplayList(List& l)
{
std::cout << "List size: " << l.GetSize() << std::endl;
Iterator it(l);
for (it.GotoBegin(); !it.AtEnd(); it.GotoNext()) {
std::cout << it.GetElement() << ", ";
}
std::cout << std::endl;
}
int main()
{
List l;
for (int i = 0; i < 10; ++i) {
l.AddAtBegin(i);
}
DisplayList(l);
int n;
for (int i = 0; i < 3; ++i) {
n = l.RemoveFirst();
l.AddAtEnd(n);
}
DisplayList(l);
return 0;
}
Controleer of je code goed werkt en, zo niet, gebruik dan de debugger om na te gaan waar het fout gaat. Kom je ergens niet uit, vraag het dan gerust.
[/hand]