| 1 |
|
|---|
| 2 | Beste allemaal,
|
|---|
| 3 |
|
|---|
| 4 | Bij de tweede programmeeropdracht Datastructuren, najaar 2007 (Implementatie
|
|---|
| 5 | en toepassing van de Trie) hebben jullie al een hele beschrijving op papier
|
|---|
| 6 | gekregen, de officiele opdrachtspecificatie.
|
|---|
| 7 | Voor onderdeel 2A van de opdracht moet je bestanden `trie.cc' en `trie.h'
|
|---|
| 8 | maken die de Trie implementeren. Om te kunnen testen of die een beetje doen
|
|---|
| 9 | wat je mag verwachten, is er een aantal testbestanden beschikbaar. De werking
|
|---|
| 10 | daarvan zullen we hier uitleggen.
|
|---|
| 11 | Aan het eind maken we ook nog een paar kleine opmerkingen over onderdeel 2B.
|
|---|
| 12 |
|
|---|
| 13 | We beseffen dat het een heel verhaal is, net als de opdrachtspecificatie zelf,
|
|---|
| 14 | maar het is toch verstandig om het door te lezen. Je kunt er meer tijd mee
|
|---|
| 15 | uitsparen dan dat het lezen je kost.
|
|---|
| 16 |
|
|---|
| 17 | ********************************************************************************
|
|---|
| 18 |
|
|---|
| 19 | * Er zijn 12 testbestanden voor onderdeel 2A:
|
|---|
| 20 | general0.h -> hernoemen tot general.h
|
|---|
| 21 | showlist0.h -> hernoemen tot showlist.h
|
|---|
| 22 | showlist0.cc -> hernoemen tot showlist.cc
|
|---|
| 23 | leestekst0.h -> hernoemen tot leestekst.h
|
|---|
| 24 | leestekst0.cc -> hernoemen tot leestekst.cc
|
|---|
| 25 | testtrie0.cc -> hernoemen tot testtrie.cc
|
|---|
| 26 | Makefile0 -> hernoemen tot Makefile
|
|---|
| 27 | test0.dat -> hernoemen tot test.dat
|
|---|
| 28 | test1.inv
|
|---|
| 29 | test1.con
|
|---|
| 30 | test2.inv
|
|---|
| 31 | test2.con
|
|---|
| 32 | De reden dat we 0-versies in het pakketje hebben gestopt, die jullie dan
|
|---|
| 33 | weer moeten hernoemen, is om ongewenste overschrijvingen te voorkomen bij
|
|---|
| 34 | het uitpakken van het pakketje. Je weet bijvoorbeeld maar nooit of jullie
|
|---|
| 35 | zelf ook al een bestand `testtrie.cc' hebben geschreven.
|
|---|
| 36 |
|
|---|
| 37 | * Het belangrijkste bestand is `testtrie.cc'
|
|---|
| 38 | Dit programma biedt de gebruiker een menu aan waarin de verschillende
|
|---|
| 39 | methodes van de Trie aangeroepen kunnen worden. In het testprogramma is
|
|---|
| 40 | gekozen voor integers als informatieveld.
|
|---|
| 41 |
|
|---|
| 42 | * Bij de methode GotoNode is het handig om te weten dat dan naar de knoop
|
|---|
| 43 | gegaan wordt die de laatste keer met GetNode verkregen is, tenzij deze
|
|---|
| 44 | knoop inmiddels met RemoveChild verwijderd is.
|
|---|
| 45 |
|
|---|
| 46 | * Naast het aanroepen van de standaard methodes zijn er nog drie andere
|
|---|
| 47 | opties in het menu: `Show', `Show (2)' en `Opnieuw beginnen'. Deze laatste
|
|---|
| 48 | optie houdt in dat je opnieuw begint met een lege Trie. De andere twee
|
|---|
| 49 | opties zullen we wat uitgebreider toelichten.
|
|---|
| 50 |
|
|---|
| 51 | * Allereerst: in principe doen `Show' en `Show (2)' exact hetzelfde.
|
|---|
| 52 | Alleen bij de automatische Test (zie daarover verderop) zijn ze een
|
|---|
| 53 | beetje verschillend, maar daar hoeven jullie niet over in te zitten.
|
|---|
| 54 |
|
|---|
| 55 | * Tijdens het testen van het programma is het prettig als je de Trie die
|
|---|
| 56 | je in de loop van de tijd hebt opgebouwd, kunt afbeelden op het scherm.
|
|---|
| 57 | Daarvoor is de optie `Show' aanwezig.
|
|---|
| 58 | De optie maakt gebruik van een datastructuur die in `showlist.cc' en
|
|---|
| 59 | `showlist.h' is ge-implementeerd.
|
|---|
| 60 | Om de werking van de optie `Show' te demonstreren, bekijk de volgende
|
|---|
| 61 | uitvoer van de methode:
|
|---|
| 62 | 0,
|
|---|
| 63 | 0,a 1,b 2,c 3,d
|
|---|
| 64 | 6,a 4,b 5,a 8*a
|
|---|
| 65 | 9,a 7,c
|
|---|
| 66 | 10,a
|
|---|
| 67 | Op het eerste niveau staat de wortel. Op het volgende niveau staan de
|
|---|
| 68 | kinderen van de wortel. In het voorbeeld zijn dit er vier. Bij deze
|
|---|
| 69 | kinderen stelt het getal voor de komma de waarde van het infoveld voor,
|
|---|
| 70 | het karakter na de komma geeft de tak aan via welke de knoop bereikt kan
|
|---|
| 71 | worden, de vader-tak zogezegd.
|
|---|
| 72 | Het eerste kind van de wortel heeft dus een infoveld 0 en kan vanuit
|
|---|
| 73 | de wortel bereikt worden via de tak `a', het tweede kind heeft een
|
|---|
| 74 | infoveld 1 en kan vanuit de wortel bereikt worden via de tak `b',
|
|---|
| 75 | enzovoort.
|
|---|
| 76 |
|
|---|
| 77 | De kinderen van een knoop x0 staan een niveau lager dan x0 zelf.
|
|---|
| 78 | Het eerste kind staat onmiddellijk onder x0; het tweede kind staat daar
|
|---|
| 79 | rechts van, het derde kind daar weer rechts van, enz. totdat je voorbij
|
|---|
| 80 | de broer van x0 loopt. De kinderen van `0,a' zijn dus `6,a' en `4,b'.
|
|---|
| 81 | Ofwel van de knoop `0,a' gaan uit: een tak `a' die eindigt in een knoop
|
|---|
| 82 | met infoveld 6 en tak `b' die eindigt in een knoop met infoveld 4.
|
|---|
| 83 | De knoop `6,a' heeft zelf geen kinderen, maar knoop `4,b' heeft weer
|
|---|
| 84 | twee kinderen: `9,a' en `7,c'.
|
|---|
| 85 |
|
|---|
| 86 | Om het allemaal van de andere kant te bekijken: `10,a' is een kind van
|
|---|
| 87 | `9,a', `9,a' is een kind van `4,b', `4,b' is een kind van `0,a' en
|
|---|
| 88 | `0,a' is ten slotte een kind van de wortel van de Trie.
|
|---|
| 89 |
|
|---|
| 90 | Omdat de wortel geen vader-tak heeft, zul je daar na de komma nooit een
|
|---|
| 91 | karakter zien staan (d.w.z.: er staat een spatie).
|
|---|
| 92 |
|
|---|
| 93 | Bij een (1) knoop in de Trie worden infoveld en karakter niet door een
|
|---|
| 94 | komma gescheiden, maar door een sterretje `*'. Dit betekent dat deze knoop
|
|---|
| 95 | de huidige knoop is, d.w.z.: hier bevindt zich het venster van de Trie.
|
|---|
| 96 |
|
|---|
| 97 | Niet geheel toevallig komt het gegeven voorbeeld overeen met de Trie in
|
|---|
| 98 | Figuur 1 van de opdrachtspecificatie. Alleen de wortel, die in de
|
|---|
| 99 | specificatie geen infoveld heeft, heeft hier een infoveld 0.
|
|---|
| 100 |
|
|---|
| 101 | Uiteraard is deze vorm van presenteren slechts overzichtelijk bij een
|
|---|
| 102 | beperkt aantal knopen. Als je te veel knopen hebt, kan een niveau meerdere
|
|---|
| 103 | regels beslaan en is het niet meer eenvoudig na te gaan hoe de vader-kind
|
|---|
| 104 | relaties lopen.
|
|---|
| 105 |
|
|---|
| 106 | N.B.: de optie `Show' maakt gebruik van een heleboel methodes van de Trie.
|
|---|
| 107 | Het is dus mogelijk dat ze pas werkt als je voor al die methodes een
|
|---|
| 108 | fatsoenlijke implementatie hebt.
|
|---|
| 109 |
|
|---|
| 110 | * `testtrie.cc' maakt gebruik van enkele algemene constantes in `general.h'.
|
|---|
| 111 | Desgewenst kun je deze constantes ook in je eigen implementatie van de
|
|---|
| 112 | Trie gebruiken.
|
|---|
| 113 |
|
|---|
| 114 | * Om `testtrie.cc' te compileren is er `Makefile'. Het compileren begint
|
|---|
| 115 | met het commando `make'. Vervolgens kun je het testprogramma aanroepen met
|
|---|
| 116 | `Test'
|
|---|
| 117 |
|
|---|
| 118 | * De default is dat je je Trie interactief test. Dat kun je zien in het
|
|---|
| 119 | bestand `test.dat', waarin de variabele `InterActief' op 1 staat.
|
|---|
| 120 | Het is aan te raden om eerst op deze wijze een tijdje met het
|
|---|
| 121 | testprogramma te spelen en de verschillende opties uit te proberen.
|
|---|
| 122 |
|
|---|
| 123 | * Als je het na een tijdje zat bent om steeds maar weer zelf menukeuzes
|
|---|
| 124 | en karakters in te typen, kun je `InterActief' op 0 zetten. Daarmee kies
|
|---|
| 125 | je voor een automatische Test.
|
|---|
| 126 | Bij de automatische Test wordt de invoer uit een bestand gelezen, in het
|
|---|
| 127 | bijzonder uit het bestand dat op de volgende regel staat (in principe is
|
|---|
| 128 | dat `test1.inv'). Verder wordt de uitvoer behalve naar het scherm ook voor
|
|---|
| 129 | een deel naar een bestand (`test1.uit') geschreven.
|
|---|
| 130 | Met behulp van `test1.inv' wordt de Trie uit ons voorbeeld, die uit
|
|---|
| 131 | Figuur 1 van de opdrachtspecificatie dus, opgebouwd en afgebeeld.
|
|---|
| 132 |
|
|---|
| 133 | * Als dan de parameter `Controleren=0', gebeurt er niets met het
|
|---|
| 134 | uitvoerbestand `test1.uit'.
|
|---|
| 135 |
|
|---|
| 136 | * Met `Controleren=1' wordt echter gekeken of het uitvoerbestand gelijk is
|
|---|
| 137 | aan het controlebestand `test1.con'. Zo ja, dan wordt er `GELIJK' op
|
|---|
| 138 | het scherm afgedrukt. Zo nee, dan wordt aangegeven waar het verschil zit.
|
|---|
| 139 |
|
|---|
| 140 | * Om de implementatie van de Trie nog wat serieuzer te testen, is er ten
|
|---|
| 141 | slotte nog een tweede testinstantie meegegeven, bestaande uit `test2.inv'
|
|---|
| 142 | en `test2.con'. Als je in `test.dat' de naam van het invoerbestand even
|
|---|
| 143 | aanpast, kun je het testprogramma voor deze instantie draaien.
|
|---|
| 144 | Ook dit is echter geen ultieme test. Het kan best zijn je ook bij
|
|---|
| 145 | `test2.inv' GELIJK krijgt, terwijl de corrector nog fouten in je code
|
|---|
| 146 | ontdekt. Er kunnen bijvoorbeeld instanties zijn waar jullie implementatie
|
|---|
| 147 | de mist mee ingaat, en waar we van tevoren niet aan gedacht hebben.
|
|---|
| 148 |
|
|---|
| 149 | * We raden je aan om niet te snel tot de automatische Test over te gaan.
|
|---|
| 150 | Zorg er eerst voor dat je weet wat alle opties in het menu doen.
|
|---|
| 151 | Zorg er vervolgens voor dat je begrijpt wat er zoal in `test1.uit'
|
|---|
| 152 | geschreven wordt.
|
|---|
| 153 | Als je zover bent, is het gemakkelijker om eventuele foutmeldingen te
|
|---|
| 154 | begrijpen.
|
|---|
| 155 |
|
|---|
| 156 | * Overigens: de code van een aantal bestanden is een beetje versleuteld,
|
|---|
| 157 | omdat het eigenlijk niet de bedoeling is dat jullie daarin gaan kijken.
|
|---|
| 158 | Ze zijn puur bedoeld om te gebruiken.
|
|---|
| 159 |
|
|---|
| 160 | * In principe zou het testprogramma (en ook de automatische Test) op ieder
|
|---|
| 161 | platform moet werken, dus bijvoorbeeld ook met Visual C++.
|
|---|
| 162 |
|
|---|
| 163 | ********************************************************************************
|
|---|
| 164 |
|
|---|
| 165 | Om dubbele include-s te voorkomen is het in het algemeen aan te raden om je
|
|---|
| 166 | code in `trie.h' en `trie.cc' te omgeven met een `ifndef'-constructie, dus
|
|---|
| 167 | iets in de trant van:
|
|---|
| 168 | #ifndef TrieHVar
|
|---|
| 169 | #define TrieHVar
|
|---|
| 170 |
|
|---|
| 171 | ... code ...
|
|---|
| 172 |
|
|---|
| 173 | #endif
|
|---|
| 174 |
|
|---|
| 175 | ********************************************************************************
|
|---|
| 176 |
|
|---|
| 177 | Het heeft geen zin om een implementatie van de Trie in te leveren die niet
|
|---|
| 178 | door de automatische Test komt. Die krijg je linea recta terug. Vooralsnog
|
|---|
| 179 | gaan we er namelijk vanuit dat er geen fouten in de automatische Test zitten.
|
|---|
| 180 | Denk je dat er toch fouten in de testprogramma's of de testinstanties zitten,
|
|---|
| 181 | dan kun je dit aankaarten bij Robert Brijder.
|
|---|
| 182 |
|
|---|
| 183 | Wanneer je denkt dat je implementatie van de Trie goed is, kun je haar
|
|---|
| 184 | electronisch inleveren bij de corrector, Ruben van Bodegom. In de opdracht-
|
|---|
| 185 | specificatie staat aangegeven hoe je dat precies moet / kunt doen.
|
|---|
| 186 |
|
|---|
| 187 | ********************************************************************************
|
|---|
| 188 |
|
|---|
| 189 | Het is de bedoeling dat je implementatie van de Trie gebruik maakt van
|
|---|
| 190 | templates om verschillende types informatieveld mogelijk te maken.
|
|---|
| 191 |
|
|---|
| 192 | Een neveneffect daarvan is dat je, bij gebruik van de Trie in een bepaalde
|
|---|
| 193 | toepassing (ZLW compressie en decompressie bijvoorbeeld) de complete code
|
|---|
| 194 | (`trie.cc' dus) moet includen in je programma van die toepassing.
|
|---|
| 195 | Wanneer je gewoon de Trie los compileert naar een bestand `trie.o' en je
|
|---|
| 196 | probeert dat te linken met een object bestand waarin variabelen van type
|
|---|
| 197 | `Trie<int>' gebruikt worden, krijg je allemaal foutmeldingen.
|
|---|
| 198 |
|
|---|
| 199 | ********************************************************************************
|
|---|
| 200 |
|
|---|
| 201 | * Er zijn 2 testbestanden voor onderdeel 2B:
|
|---|
| 202 | testzlw.in
|
|---|
| 203 | testzlw3.in
|
|---|
| 204 | Het eerste bestand is gewoon het voorbeeldbestand uit de opdracht-
|
|---|
| 205 | specificatie, het tweede bestand is een iets groter bestand. Na comprimeren
|
|---|
| 206 | en decomprimeren van deze bestanden, moet je exact dezelfde bestanden
|
|---|
| 207 | weer teruggekregen hebben.
|
|---|
| 208 | Uiteraard testen jullie je compressie- en decompressie ook nog met echt
|
|---|
| 209 | grote tekstbestanden.
|
|---|
| 210 |
|
|---|
| 211 | * Wanneer je een origineel bestand vergelijkt met het uiteindelijke bestand,
|
|---|
| 212 | is het verstandig om ze niet alleen in een editor te bekijken, maar ook
|
|---|
| 213 | even naar de groottes van de beide bestanden te kijken. Sommige verschillen
|
|---|
| 214 | (spaties, End-of-Lines) zie je namelijk niet altijd in een editor, terwijl
|
|---|
| 215 | ze wel tot uiting kunnen komen in de bestandsgrootte.
|
|---|
| 216 |
|
|---|
