Eerste Programmeeropgave Datastructuren 2007

werkcollege maandag 3 september.
Inleveren vrijdag 14 september, graag in tweetallen, de bestanden queue.cc en queue.h bij Sven van Haastregt, svhaastr@liacs.nl, met in het subject de tekst "Opdracht 1" en de na(a)m(en) van de auteur(s). Een print is niet nodig; stuur geen andere bestanden mee, hooguit een READ.ME. Ook voor vragen: svhaastr@liacs.nl.

Een queue met virtuele methoden

In deze eerste opdracht moet een viertal verwante datastructuren als objecten geïmplementeerd worden: de fifo-queue (of rij), de lifo-queue (of stapel), de min-queue en de max-queue (vgl. de priority-queue). Maak daartoe een programma queue.cc (met header-bestand queue.h) met de klassen Fifo, Lifo, MinQ, en MaxQ. Elk van deze typen heeft (tenminste) de volgende methoden (al dan niet via overerving), waarvan we alleen de prototypen geven:
bool IsEmpty (void);
test of de queue leeg is.
void Insert (int item);
voegt een element aan de queue toe.
int Get (void);
verwijdert een element uit de queue, en levert de waarde op. Het verwijderde element is (i) het langst aanwezige element bij een fifo-queue, (ii) het laatst toegevoegde element bij een lifo-queue, (iii) het kleinste, resp. grootste element bij min- en max-queue.
Via WWW is een programma beschikbaar dat de gebruiker de mogelijkheid biedt om de werking van de vier queue-varianten te testen. Het vraagt de gebruiker een van de datastructuren te kiezen, en biedt deze structuur dan aan een testprocedure aan. Met nadruk wordt gesteld dat dit slechts een simpele testprocedure is. De datastructuren dienen ook bij serieuzere testen aan de specificatie te voldoen.

Om het testprogramma de mogelijkheid te geven om op alle queue-varianten te werken, moeten deze afstammelingen zijn van een gemeenschappelijk klasse Queue. Door op de juiste manier met virtuele methoden te werken worden dan na aanroep de methoden van het juiste objecttype gebruikt.

Het is niet de bedoeling de objecten van de grond af op te bouwen. Een algemeen lijsttype (genaamd List) is (in gecompileerde versie) beschikbaar via WWW, en dient gebruikt te worden. Het in te leveren C++ programma gebruikt list.o en wordt op zijn beurt gebruikt door het programma test.cc. Wellicht ten overvloede: aan de klasse List mag absoluut niets veranderd worden. Het object-bestand list.o is gecompileerd met g++ op een Linux-pc. Als bonus zijn er nog twee versies voor Visual C++ 6.0: list-visual6.obj en list-visual6nt.obj. Het in te leveren programma moet echter gecompileerd kunnen worden met g++ op een Linux-pc of de beast.

Informele specificatie van de datastructuur List

list.cc (alleen gecompileerd beschikbaar) implementeert een lijst van integers. De lijst heeft een zgn. cursor die naar een van de elementen van de lijst wijst (als de lijst tenminste niet leeg is). Deze cursor kan door de lijst bewogen worden. Operaties op de lijst (toevoegen, veranderen waarden etc.) worden uitgevoerd daar waar de cursor zich bevindt. De lijst exporteert de volgende methoden (alle aanwezige private methoden en datavelden zijn weggelaten):
List (void);
initialiseert een lege lijst.
~List (void);
ruimt een bestaande lijst op.
int Get (void);
levert de waarde van het door de cursor aangewezen lijstelement; indien de lijst leeg is wordt de waarde 0 teruggegeven.
void Change (int item);
verandert de waarde van het aangewezen lijstelement; geen effect bij lege lijst.
void Insert (int item);
voegt element toe aan de lijst; indien lijst niet leeg, dan voorafgaand aan het element dat door de cursor wordt aangewezen; na afloopt wijst de cursor naar het toegevoegde element.
void Append (int item);
idem, nu ná het aangewezen element.
void Delete (void);
verwijdert het aangewezen element; geen effect op lege lijst; na verwijderen wijst de cursor naar het element ná het verwijderde element, of het laatste indien het verwijderde element zich achteraan de lijst bevond.
bool IsEmpty (void);
test of lijst leeg is.
bool IsBegin (void);
bool IsEnd (void);
tests of cursor naar eerste, resp. laatste element van de lijst wijst; ook true bij lege lijst.
void GoToBegin (void);
void GoToEnd (void);
void GoToPrevious (void);
void GoToNext (void);
functies om de cursor door de lijst te bewegen; geen effect op lege lijst.

Materiaal

Op de Datastructuren webpagina zijn de volgende bestanden beschikbaar, die ter voorkoming van ongewenste overschrijvingen een andere naam hebben gekregen dan ze uiteindelijk moeten hebben (dus even hernoemen):