Beste allemaal, Bij de tweede programmeeropdracht Datastructuren, najaar 2007 (Implementatie en toepassing van de Trie) hebben jullie al een hele beschrijving op papier gekregen, de officiele opdrachtspecificatie. Voor onderdeel 2A van de opdracht moet je bestanden `trie.cc' en `trie.h' maken die de Trie implementeren. Om te kunnen testen of die een beetje doen wat je mag verwachten, is er een aantal testbestanden beschikbaar. De werking daarvan zullen we hier uitleggen. Aan het eind maken we ook nog een paar kleine opmerkingen over onderdeel 2B. We beseffen dat het een heel verhaal is, net als de opdrachtspecificatie zelf, maar het is toch verstandig om het door te lezen. Je kunt er meer tijd mee uitsparen dan dat het lezen je kost. ******************************************************************************** * Er zijn 12 testbestanden voor onderdeel 2A: general0.h -> hernoemen tot general.h showlist0.h -> hernoemen tot showlist.h showlist0.cc -> hernoemen tot showlist.cc leestekst0.h -> hernoemen tot leestekst.h leestekst0.cc -> hernoemen tot leestekst.cc testtrie0.cc -> hernoemen tot testtrie.cc Makefile0 -> hernoemen tot Makefile test0.dat -> hernoemen tot test.dat test1.inv test1.con test2.inv test2.con De reden dat we 0-versies in het pakketje hebben gestopt, die jullie dan weer moeten hernoemen, is om ongewenste overschrijvingen te voorkomen bij het uitpakken van het pakketje. Je weet bijvoorbeeld maar nooit of jullie zelf ook al een bestand `testtrie.cc' hebben geschreven. * Het belangrijkste bestand is `testtrie.cc' Dit programma biedt de gebruiker een menu aan waarin de verschillende methodes van de Trie aangeroepen kunnen worden. In het testprogramma is gekozen voor integers als informatieveld. * Bij de methode GotoNode is het handig om te weten dat dan naar de knoop gegaan wordt die de laatste keer met GetNode verkregen is, tenzij deze knoop inmiddels met RemoveChild verwijderd is. * Naast het aanroepen van de standaard methodes zijn er nog drie andere opties in het menu: `Show', `Show (2)' en `Opnieuw beginnen'. Deze laatste optie houdt in dat je opnieuw begint met een lege Trie. De andere twee opties zullen we wat uitgebreider toelichten. * Allereerst: in principe doen `Show' en `Show (2)' exact hetzelfde. Alleen bij de automatische Test (zie daarover verderop) zijn ze een beetje verschillend, maar daar hoeven jullie niet over in te zitten. * Tijdens het testen van het programma is het prettig als je de Trie die je in de loop van de tijd hebt opgebouwd, kunt afbeelden op het scherm. Daarvoor is de optie `Show' aanwezig. De optie maakt gebruik van een datastructuur die in `showlist.cc' en `showlist.h' is ge-implementeerd. Om de werking van de optie `Show' te demonstreren, bekijk de volgende uitvoer van de methode: 0, 0,a 1,b 2,c 3,d 6,a 4,b 5,a 8*a 9,a 7,c 10,a Op het eerste niveau staat de wortel. Op het volgende niveau staan de kinderen van de wortel. In het voorbeeld zijn dit er vier. Bij deze kinderen stelt het getal voor de komma de waarde van het infoveld voor, het karakter na de komma geeft de tak aan via welke de knoop bereikt kan worden, de vader-tak zogezegd. Het eerste kind van de wortel heeft dus een infoveld 0 en kan vanuit de wortel bereikt worden via de tak `a', het tweede kind heeft een infoveld 1 en kan vanuit de wortel bereikt worden via de tak `b', enzovoort. 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 `0,a' zijn dus `6,a' en `4,b'. Ofwel van de knoop `0,a' gaan uit: een tak `a' die eindigt in een knoop met infoveld 6 en tak `b' die eindigt in een knoop met infoveld 4. De knoop `6,a' heeft zelf geen kinderen, maar knoop `4,b' heeft weer twee kinderen: `9,a' en `7,c'. Om het allemaal van de andere kant te bekijken: `10,a' is een kind van `9,a', `9,a' is een kind van `4,b', `4,b' is een kind van `0,a' en `0,a' is ten slotte een kind van de wortel van de Trie. Omdat de wortel geen vader-tak heeft, zul je daar na de komma nooit een karakter zien staan (d.w.z.: er staat een spatie). Bij een (1) knoop in de Trie worden infoveld en karakter niet door een komma gescheiden, maar door een sterretje `*'. Dit betekent dat deze knoop de huidige knoop is, d.w.z.: hier bevindt zich het venster van de Trie. Niet geheel toevallig komt het gegeven voorbeeld overeen met de Trie in Figuur 1 van de opdrachtspecificatie. Alleen de wortel, die in de specificatie geen infoveld heeft, heeft hier een infoveld 0. 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. N.B.: de optie `Show' maakt gebruik van een heleboel methodes van de Trie. Het is dus mogelijk dat ze pas werkt als je voor al die methodes een fatsoenlijke implementatie hebt. * `testtrie.cc' maakt gebruik van enkele algemene constantes in `general.h'. Desgewenst kun je deze constantes ook in je eigen implementatie van de Trie gebruiken. * Om `testtrie.cc' te compileren is er `Makefile'. Het compileren begint met het commando `make'. Vervolgens kun je het testprogramma aanroepen met `Test' * De default is dat je je Trie interactief test. Dat kun je zien in het bestand `test.dat', waarin de variabele `InterActief' op 1 staat. Het is aan te raden om eerst op deze wijze een tijdje met het testprogramma te spelen en de verschillende opties uit te proberen. * Als je het na een tijdje zat bent om steeds maar weer zelf menukeuzes en karakters in te typen, kun je `InterActief' op 0 zetten. Daarmee kies je voor een automatische Test. Bij de automatische Test 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'). Verder wordt de uitvoer behalve naar het scherm ook voor een deel naar een bestand (`test1.uit') geschreven. Met behulp van `test1.inv' wordt de Trie uit ons voorbeeld, die uit Figuur 1 van de opdrachtspecificatie dus, opgebouwd en afgebeeld. * Als dan de parameter `Controleren=0', gebeurt er niets met het uitvoerbestand `test1.uit'. * 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. * Om de implementatie van de Trie nog wat serieuzer te testen, is er ten slotte nog een tweede testinstantie meegegeven, bestaande uit `test2.inv' en `test2.con'. Als je in `test.dat' de naam van het invoerbestand even aanpast, kun je het testprogramma voor deze instantie draaien. Ook dit is echter geen ultieme test. Het kan best zijn je ook bij `test2.inv' GELIJK krijgt, terwijl de corrector nog fouten in je code ontdekt. Er kunnen bijvoorbeeld instanties zijn waar jullie implementatie de mist mee ingaat, en waar we van tevoren niet aan gedacht hebben. * We raden je aan om niet te snel tot de automatische Test over te gaan. Zorg er eerst voor dat je weet wat alle opties in het menu doen. Zorg er vervolgens voor dat je begrijpt wat er zoal in `test1.uit' geschreven wordt. Als je zover bent, is het gemakkelijker om eventuele foutmeldingen te begrijpen. * Overigens: de code van een aantal bestanden is een beetje versleuteld, omdat het eigenlijk niet de bedoeling is dat jullie daarin gaan kijken. Ze zijn puur bedoeld om te gebruiken. * In principe zou het testprogramma (en ook de automatische Test) op ieder platform moet werken, dus bijvoorbeeld ook met Visual C++. ******************************************************************************** Om dubbele include-s te voorkomen is het in het algemeen aan te raden om je code in `trie.h' en `trie.cc' te omgeven met een `ifndef'-constructie, dus iets in de trant van: #ifndef TrieHVar #define TrieHVar ... code ... #endif ******************************************************************************** Het heeft geen zin om een implementatie van de Trie in te leveren die niet door de automatische Test komt. Die krijg je linea recta terug. Vooralsnog gaan we er namelijk vanuit dat er geen fouten in de automatische Test zitten. Denk je dat er toch fouten in de testprogramma's of de testinstanties zitten, dan kun je dit aankaarten bij Robert Brijder. Wanneer je denkt dat je implementatie van de Trie goed is, kun je haar electronisch inleveren bij de corrector, Ruben van Bodegom. In de opdracht- specificatie staat aangegeven hoe je dat precies moet / kunt doen. ******************************************************************************** Het is de bedoeling dat je implementatie van de Trie gebruik maakt van templates om verschillende types informatieveld mogelijk te maken. Een neveneffect daarvan is dat je, bij gebruik van de Trie in een bepaalde toepassing (ZLW compressie en decompressie bijvoorbeeld) de complete code (`trie.cc' dus) moet includen in je programma van die toepassing. Wanneer je gewoon de Trie los compileert naar een bestand `trie.o' en je probeert dat te linken met een object bestand waarin variabelen van type `Trie' gebruikt worden, krijg je allemaal foutmeldingen. ******************************************************************************** * Er zijn 2 testbestanden voor onderdeel 2B: testzlw.in testzlw3.in Het eerste bestand is gewoon het voorbeeldbestand uit de opdracht- specificatie, het tweede bestand is een iets groter bestand. Na comprimeren en decomprimeren van deze bestanden, moet je exact dezelfde bestanden weer teruggekregen hebben. Uiteraard testen jullie je compressie- en decompressie ook nog met echt grote tekstbestanden. * Wanneer je een origineel bestand vergelijkt met het uiteindelijke bestand, is het verstandig om ze niet alleen in een editor te bekijken, maar ook even naar de groottes van de beide bestanden te kijken. Sommige verschillen (spaties, End-of-Lines) zie je namelijk niet altijd in een editor, terwijl ze wel tot uiting kunnen komen in de bestandsgrootte.