Laboration 2a: Telefontabell

Inledning

Laborationen går ut på att implementera en typ för tabell, dels som m h a fält och dels m h a binärt sökträd, samt ett interaktivt program som använder en tabell.

Syftet med laborationen är att ni ska få hantera lite större datatyper, dynamiska datastrukturer, samt att jämföra olika implemantationer av samma sak.

Uppgift 1

Skriv en modul som implementerar en datatyp för en telefontabell. Tabellenen ska representeras m h a ett fält. Det som ska sparas i tabellen är personer bestående av namn och ett sjusiffrigt telefonnummer (detta bara för enkelhetens skull, det finns ingenting som hindrar att det finns betydligt mer information om en person, att en person bara har namn och telnr är viktigt för en test som kommer senare).

Följande operationer ska åtminstone finnas:

initiering
insättning:: Givet namn och telnr, sätt in motsv person i tabellen. Om en person med det namnet redan finns, ändra då till det nya telnumret. Felutskift om tabellen är full.
uttagning:: Givet namn, tag bort motsv person från tabellen.
sökning:: Givet namn, finn telnr.
utskrift:: Skriv ut tabellen i bokstavsordnig.

(Tips: Det kanske kan löna sig att göra insättningar och uttagningar så att tabellen är sorterad.)

Uppgift 2

Skriv ett kommandostyrt program som använder en variabel av tabelltypen. Programmet ska upprepade gånger läsa kommandon, i form av tecken, från terminalen. Programmet ska fungera på följande sätt:

muppet36>falttabell --pgmnamn i Rogardt 7725408 --sätt in f Ilona --finn telnr Ilona finns ej i tabellen i Ilona 7725402 i Jan 7725409 i Bengt 7725404 u Jan --tag ut f Bengt 7725404 p --skriv ut Bengt 7725404 Ilona 7725402 Rogardt 7725408 muppet36> --Ctrl-d avslutar programmet

Att ni använder i/u för insättning/uttagning och att Ctrl-d avslutar progmammet är viktigt för den kommande testen (se uppgift 4).

Det är också viktigt att ni inte använder representationen av tabelltypen i programmet.

Uppgift 3

Gör om uppg 1, men låt tabelltypen vara abstrakt och representeras med av ett binärt sökträd. Programmet i uppg 2 ska nu fungera utan förändring med den nya typen.

Tips

För att sökning i ett binärt sökträd ska gå snabbt är det viktigt att det är väl balanserat och en dålig algoritm för uttagning kan snabbt leda till obalans. Nedan är en bra uttagningsalgoritm beskriven.

Finn noden som ska tas bort (vi kan kalla den nod A).
- Om nod A inte har några barn så tag bort den.
- Om nod A har precis ett barn så ersätt A med dess barn.
- Om nod A har två barn så finn den nod i vänster delträd som har störst värde (nod B) och ersätt A:s värde med B:s värde och tag bort nod B.

Uppgift 4

I kursbiblioteket finns ett program slumpnamn som skiver några slumpmässiga insättningar och uttagningar på skärmen. Utskriften kan dirigeras om till en fil genom att man skriver slumpnamn>slumpfil. Inläsningen till huvudprogrammet dirigeras om till filen genom att man skriver tabell<slumpfil. Lägger man sen till unix-kommandot time (dvs time tabell<slumpfil) så får man reda på hur lång tid exekveringen tar.

Jämför på detta sätt de båda implementeringarna av tabell för några olika slumpfiler. Är det någon skillnad? Försök förklara varför. Vad skulle hända om indatafilen var sorterad?

(För att testen ska fungera för fält-varianten bör längden av fältet vara ca 8000.)

Redovisning

Redovisningen skall bestå av en programkod med kommentarer samt en redovisning av resultaten och svar från uppgift 4.