Beste allemaal, Bij de tweede opgave Datastructuren najaar 2005 (implementeer een Fibonacci rij) hebben jullie al een hele beschrijving op papier gekregen. Toch valt er nog meer te zeggen en dat wil ik bij deze doen. Eerst zal ik ingaan op deel A) van de opgave, dan kort op deel B) en ten slotte heb ik nog enkele algemene mededelingen. ******************************************************************************** ****** 2A: * ****** Voor opdracht 2A) krijgen jullie een aantal bestanden cadeau, die het (goed) maken van de opgave moeten vergemakkelijken. Ik zal eerst uitleggen waar deze bestanden voor dienen, vervolgens geef ik nog enkele algemene aanwijzingen voor bij het programmeren. * Voor deel A) van de opgave hoef je alleen bestanden `fiboqueue.cc' en `fiboqueue.h' te maken die de Fibonacci rij implementeren. Om te kunnen testen of die een beetje doen wat je mag verwachten, is een eerste testprogramma `test.cc' bijgeleverd. Jullie wordt aangeraden om ook het commentaar bovenin dat programma te lezen. * Tijdens het testen van het programma is het prettig als je de boom die je in de loop van de tijd hebt opgebouwd kunt afbeelden op het scherm. Daarvoor is een methode `Show' voor de klasse `FiboQueue' geschreven, samen met enkele bijbehorende functies. Deze functies vind je in de bestanden `fiboqueue.cc' en `fiboqueue.h' (dat wil zeggen: ik heb deze bestanden voor de zekerheid maar even `fiboqueue0.cc' en `fiboqueue0.h' genoemd; stel namelijk dat je zelf al met het implementeren van de Fibonacci rij was begonnen in eigen bestanden `fiboqueue.cc' en `fiboqueue.h', dan worden die niet meteen overschreven door mijn bestanden). Het is dus de bedoeling dat je deze functies in je eigen implementatie kopieert. De functies maken gebruik van een datastructuur die in `showlist.cc' en `showlist.h' is ge-implementeerd. Daarom moet je `showlist.h' in je eigen `fiboqueue.h' include-n. Om de werking van de methode `Show' te demonstreren, bekijk de volgende uitvoer: 124 363 225 171 176 308 969 491 274 514 533 698 385 943 Deze Fibonacci rij bestaat uit drie bomen, een met wortel 124, een met wortel 363 en een met wortel 225. De wortels staan dus op het bovenste niveau. De eerst genoemde wortel is het minimum van de Fibonacci rij. De kinderen van een knoop x0 staan een niveau lager dan x0 zelf. Het eerste kind staat onmiddellijk onder x0; het tweede kind staat daar rechts van, het derde kind daar weer rechts van, enz. totdat je voorbij de broer van x0 loopt. De kinderen van 124 in ons voorbeeld zijn 171, 176 en 308. Knoop 969 is het enige kind van 363. Knoop 225 heeft weer twee kinderen: 491 en 274. Om het allemaal van de andere kant te bekijken: 943 is een kind van 698, 698 is een kind van 308 en 308 is een kind van 124. Uiteraard is deze vorm van presenteren slechts overzichtelijk bij een beperkt aantal knopen. Als je te veel knopen hebt, kan een niveau meerdere regels beslaan en is het niet meer eenvoudig na te gaan hoe de vader-kind relaties lopen. * Om `test.cc' te compileren is er `Makefile1'. Deze moet je even naar `Makefile' copyeren, waarna met het commando `make' het compileren begint. Vervolgens kun je het testprogramma aanroepen met `Test' Door met de bovenstaande programma's te testen, kun je denken dat je implementatie van de Fibonacci rij correct is. Juich echter niet te vroeg. Voordat je de bestanden `fiboqueue.cc' en `fiboqueue.h' inlevert, is het verstandig om ze eerst ook te testen met het tweede testprogramma. Dit kan teleurstellingen voorkomen. Voor de tweede test zijn meegestuurd: * Negen C++ bestanden (`storelist.h', `storelist.cc', `standaard.h', `standaard.cc', `leestekst.h', `leestekst.cc', `communiceer.h', `communiceer.cc' en `test2.cc'). * Om deze bestanden samen met je implementatie van de Fibonacci rij te compileren, is er `Makefile2'. Even naar `Makefile' kopieren en je kunt compileren. Ook nu kun je het testprogramma aanroepen met `Test'. /***********/ /* LET OP: */ /***********/ - Om een succesvolle compilering uit te kunnen voeren, moet het veld `Min' van de klasse `FiboQueue' (de wijzer naar de FiboNode met de laagste waarde) publiek gedeclareerd zijn. Dit is weliswaar strijdig met het concept van informatie-verhulling, maar dat moet dan maar. - Verder dient het bestand `fiboqueue.h' omgeven te zijn door een `ifndef'- constructie. Anders wordt het namelijk dubbel ge-include in `test2.cc' en krijg je een foutmelding. Zo'n constructie ziet er als volgt uit ifndef FiboQueueVar #define FiboQueueVar // de normale code #endif Om het jullie gemakkelijk te maken, is met deze twee zaken al rekening gehouden in het meegeleverde bestand `fiboqueue0.h' * Het testprogramma leest enkele parameters uit het bestand `test.dat'. - Als de parameter `InterActief=1', verwacht het programma invoer van de gebruiker. Het is aan te raden om dat eerst een paar keer te proberen. - Met `InterActief=0', wordt de invoer uit een bestand gelezen, in het bijzonder uit het bestand dat op de volgende regel staat (in principe is dat `test1.inv'). In dat geval wordt de uitvoer behalve naar het scherm ook naar een bestand `test1.uit' geschreven. - Als dan de parameter `Controleren=0', gebeurt er niets met dit uitvoerbestand. - Met `Controleren=1' wordt echter gekeken of het uitvoerbestand gelijk is aan het controlebestand `test1.con'. Zo ja, dan wordt er `GELIJK' op het scherm afgedrukt. Zo nee, dan wordt aangegeven waar het verschil zit. Het tweede testprogramma heeft de volgende werking: er worden twee Fibonacci rijen tegelijkertijd bijgehouden. Op ieder moment is een van de twee actief. - Met behulp van `Switch' uit het menu kun je de andere rij actief maken. - De optie `Merge' zorgt ervoor dat de niet-actieve Fibonacci rij bij de actieve Fibonacci rij gevoegd wordt. - Met `Reset' kun je opnieuw beginnen, met twee nieuwe, lege Fibonacci rijen. - Ten slotte is er de optie `Empty'. Die is een beetje listig. In hoofdzaak bestaat die eruit dat de actieve Fibonacci rij element voor element wordt leeggemaakt. Er gebeuren echter ook nog wat andere dingen. Wat precies, dat merk je wel bij het testen. Het is mogelijk dat je implementatie van de Fibonacci rij niet door deze test heenkomt. Wellicht kunnen de volgende aanwijzingen dan nog wat helpen: - houd bij de methodes van de Fibonacci rij die je implementeert rekening met randgevallen. Zo kan een Fibonacci rij waarop of waarmee je een operatie wilt uitvoeren, leeg zijn. In dat geval kun je (bijvoorbeeld) niet zomaar de inhoud van de `Min'-pointer inspecteren. Misschien dat dit door het meegeleverde testprogramma `test.cc' al keurig werd afgevangen, maar van `test2.cc' kan ik dat niet beloven ... - op blz. 3 van de specificatie staat als uitleg bij de methode `Merge': "Verplaatst alle elementen van *Fqptr naar de huidige queue." Dat betekent dus dat de Fibonacci rij aangeduid met Fqptr, leeg wordt. - controleer of je overal waar nodig de velden `Mark' en `Degree' aanpast. Door de fixatie op de pointer structuur van de Fibonacci rij, zou je deze velden namelijk gemakkelijk over het hoofd kunnen zien. Los van de testprogramma's is er nog een andere, veelgemaakte fout. Die bestaat eruit dat je geheugen reserveert met `new', maar dat je het niet (op tijd) weer vrijgeeft met `delete'. Hierdoor zou het geheugen van de computer vol kunnen lopen. Je zult merken dat veel van de meegeleverde programma's enigszins versleuteld zijn. De reden hiervoor is dat het eigenlijk niet de bedoeling is dat je je in die bestanden gaat verdiepen, laat staan dat je ze gaat wijzigen. De uitvoer die de bestanden produceren, zou voldoende moeten zijn. Wanneer je implementatie van de Fibonacci rij de tweede test overleeft, heb je een goede kans dat ie goed is, hoewel ik het niet bij voorbaat wil garanderen. Het is dan wel de moeite om de bestanden `fiboqueue.cc' en `fiboqueue.h' in te leveren. Je kunt dit doen met behulp van het commando: tar cvzf - fiboqueue.cc fiboqueue.h | uuencode opdracht2A.gz | elm -s 'opdracht2A' svhaastr@liacs.nl (dit alles op een regel) Een print van de programma's is niet nodig. Stuur alsjeblieft geen executables of zelfs maar object-bestanden mee !!!!! ******************************************************************************** ****** 2B: * ****** Jullie zullen merken dat jullie oplossing voor deel A) van de opdracht aan hoge eisen moet voldoen, wil die door het tweede testprogramma heenkomen, wat toch wel een vereiste lijkt voor goedkeuring. Bij deel B) zullen we minder streng zijn bij de beoordeling. Hoewel we het leuk zou vinden als jullie oplossing voor deel B) met alle mogelijke invoerbestanden (grafen, die aan de opgegeven specificatie voldoen) rekening houdt, zullen we haar niet afkeuren als ze op een randgeval faalt. Het is echter wel de bedoeling dat jullie het algoritme van Dijkstra op een fatsoenlijk manier implementeren. Bij dit onderdeel krijg je twee hulpbestanden mee: * `fibo.grf', dat een graaf van 500 knopen bevat * `fibo.con', de gewenste uitvoer bij `fibo.grf' (uitgaande van beginknoop 1) Hiermee kun je je implementatie van het algoritme van Dijkstra een beetje testen. Bedenk echter dat de nakijker de beschikking heeft over nog veel meer testinstanties. Dus als je programma de juiste uitvoer geeft voor `fibo.grf', zou het nog best verkeerd kunnen werken voor een andere instantie. In te leveren: alle bestanden die je nodig hebt om het programma te kunnen draaien. Testinstanties zijn echter niet nodig. Zoals gezegd, die hebben we zelf genoeg. Zorg ervoor dat je een directory hebt waarin alle benodigde bestanden staan en ga in deze directory staan. Stel dat je alleen `.cc' en `.h' bestanden en een Makefile nodig hebt, dan kun je met de volgende opdracht alles naar de corrector sturen: tar cvzf - *.cc *.h Makefile | uuencode opdracht2B.gz | elm -s 'opdracht2B' svhaastr@liacs.nl Ook nu is een print van de programma's niet nodig en stuur ook nu geen executables en object-bestanden mee !!! ******************************************************************************** Ten slotte: niemand is verplicht de opdrachten op de universiteit te maken. Het is echter wel de bedoeling dat jullie oplossingen gecompileerd kunnen worden (en werken) met g++ op de `beast' of op een Linux-pc in de computerzalen beneden. Dan hoeft de nakijker niet eerst het meest geschikte C++ platform uit te zoeken. Daarom, voordat jullie iets inleveren, kijk even of het hier op de `beast' of op een Linux-pc net zo goed werkt als (eventueel) thuis. Omdat opdracht 2B) voortbouwt op 2A) is het aan te raden om eerst 2A) netjes af te ronden en in te leveren (als je denkt dat ie goed is) en dan pas aan 2B) te beginnen. Als er namelijk fouten in de implementatie van de kale Fibonacci rij zitten, hoef je die niet dubbel te verbeteren. ******************************************************************************** Mochten jullie na deze uitleg nog vragen hebben, dan kun je die uiteraard altijd stellen. Voor vragen over de bedoeling van de opdracht (of over deze uitleg zelf), kun je je wenden tot mij, Robert Brijder (kamer 156a, telefoonnummer 071-527 7143, rbrijder@liacs.nl). Voor vragen over je eigen programma, kun je je wenden tot Sven van Haastregt. Succes Robert Brijder