Programmering för Naturvetare, vt-95
Institutionen för Datavetenskap
Thomas Hallgren

Laboration 6a: Telefontabell

Inledning

Laborationen går ut på att implementera en typ för tabeller, dels m h a fält och dels m h a binära 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, man att en person bara har namn och telnr är viktigt för en test som kommer senare).

Följande operationer ska åtminstone finnas:

initiering: Skapar en tom tabell.
insättning:: Givet namn och telnr, sätt in motsv person i tabellen. Om en person med samma namn 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 och skriv ut telnr.
utskrift:: Skriv ut tabellen i bokstavsordning.

(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 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 det kommande testet (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 av ett binärt sökträd. Programmet i uppg 2 ska nu fungera utan förändring med den nya typen. (Det ska alltså räcka att man ändrar vilken tabell-modul som importeras.)

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 kommandot 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 ert program kan 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 körningen 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.