Stian Søiland, IT 112, øvingsgruppe 15 (stud.ass. Helle Haugenes)
Stian Søiland, IT 112, øvingsgruppe 15 (stud.ass. Helle Haugenes)
unit telefonkatalog;
// Abstrakt datatype-enhet for telefonkatalog
// ADTen oppretter og vedlikeholder en telefonkatalog.
// Vi antar på forhånd at det alltid vil finnes bare ett telefonnummer
// til hvert navn, og kun en oppf¢ring av hvert navn.
// Vi antar også, noe naivt, at ingen har samme telefonnummer.
// offentlig del av ADT
interface
// Antall siffer i telefonnummer. Antas alltid brukt, dvs. ingen
// telefonnummer har verken FÆRRE eller FLERE siffer enn dette.
const sifferitelefonnummer = 8;
type
// Typedeklarasjon for navn. Indre formattering med hensyn til fornavn,
// etternavn, etc. defineres ikke av ADT.
navntype = string;
// Typedeklarasjon for telefonnummer. Konstanten sifferitelefonnummer er
// gitt tidligere i enheten.
nummertype = string[sifferitelefonnummer];
// Typedeklarasjoner for lenket resultatliste med navn og nummer
oppforingpeker = ^oppforing;
oppforing = record
navn : navntype;
nummer : nummertype;
neste : oppforingpeker;
end;
// Prosedyren initier oppretter telefonkatalogen, resultat er sann ved
// suksess.
procedure initier(var resultat:boolean);
// Prosedyren legginn legger til oppf¢ring med navn og nummer til
// telefonkatalogen og resultat er sann hvis prosedyren var vellykket.
// Dersom en oppf¢ring med 'navn' finnes fra f¢r vil prosedyren
// feile og resultat blir negativt.
procedure legginn(navn:navntype; nummer:nummertype;
var resultat:boolean);
// Prosedyren finnnummer returnerer telefonnummeret til navn. Navnet
// må være fullstendig. Resultat er sann dersom navnet ble funnet,
// i alle andre tilfeller er den usann.
procedure finnnummer(navn:navntype; var nummer:nummertype;
var resultat:boolean);
// Prosedyren finntelefonnummer returnerer det
// navnet som har telefonnummer likt nummer. Nummeret må
// være fullstendig. Resultat er sann dersom nummeret ble funnet,
// i alle andre tilfeller er den usann.
procedure finnnavn(nummer:nummertype;var navn:navntype;
var resultat:boolean);
// Prosedyren slettnavn sletter oppf¢ringen med det gitte navnet.
// Resultat er sann hvis prosedyren usann og navnet ble funnet,
// er navnet ikke oppf¢rt, er resultat usann.
procedure slettnavn(navn:navntype; var resultat:boolean);
// Prosedyren listalle returnerer en peker til en lenket liste,
// alfabetisk sortert etter navn, over alle oppf¢ringene i
// telefonkatalogen. Resultat er sann dersom listingen er vellykket.
procedure listalle(var resultatliste:oppforingpeker;
var resultat:boolean);
// Privat del av ADT
implementation
// Global variabel hode for å holde fast i den lenkede listen som utgj¢r
// telefonkatalogen. Bruker samme datatype som listalles resultatliste.
// Den lenkede listen er usortert.
var hode:oppforingpeker;
// Oppretter telefonkatalogen. Eventuelle eksisterende
// noder i den lenkede listen blir slettet.
// Hode-parameteren blir nullstilt i initialization-delen av
// enheten slik at den aldri vil peke til en ikkeeksisterende
// dynamisk variabel.
procedure initier(var resultat:boolean);
var temp:oppforingpeker;
begin
if hode <> nil then
begin
temp := hode;
hode := hode^.neste;
dispose(temp);
// rekursivt kall
initier(resultat);
end
else
// degenerert tilfelle
begin
resultat := true;
end;
end; // slutt initier
// Funksjonen posisjonnavn returnerer en peker til noden i den
// lenkede listen som er F¥R navn. Dersom navn ikke er oppf¢rt
// vil pekeren være NIL.
function posisjonnavn(posisjon:oppforingpeker;
navn:navntype):oppforingpeker;
begin
if (posisjon = nil) or (posisjon^.navn <> navn) then
begin
// rekursivt kall
posisjonnavn := posisjonnavn(posisjon^.neste,navn);
end
else
begin
// degenrert tilfelle
posisjonnavn := posisjon;
end;
end; // slutt posisjonnavn
// Funksjonen posisjonnummer returnerer en peker til noden i den
// lenkede listen som er F¥R nummer. Dersom nummer ikke er oppf¢rt
// vil pekeren være NIL.
function posisjonnummer(posisjon:oppforingpeker;
nummer:nummertype):oppforingpeker;
begin
if (posisjon = nil) or (posisjon^.nummer <> nummer) then
begin
// rekursivt kall
posisjonnummer := posisjonnummer(posisjon^.neste,nummer);
end
else
begin
// degenrert tilfelle
posisjonnummer := posisjon;
end;
end; // slutt posisjonnavn
procedure legginn(navn:navntype; nummer:nummertype;
var resultat:boolean);
// Prosedyre for å lage ny node
procedure nynode;
var temp:oppforingpeker;
// Lager ny node i begynnelsen av den lenkede listen
begin
new(temp);
temp^.neste := hode;
hode := temp;
end; // slutt nynode
begin
// Sjekker om navn eller nummer finnes fra f¢r i listen
if (posisjonnavn(hode,navn) <> nil) or
(posisjonnummer(hode,nummer) <> nil) then
begin
nynode;
hode^.navn := navn;
hode^.nummer := nummer;
resultat := true;
end
else
begin
// Navnet eller nummeret fantes fra f¢r, kunne ikke legge til
resultat := false;
end;
end; // slutt legginn
procedure slettnavn(navn:navntype; var resultat:boolean);
var temp1,temp2:oppforingpeker;
begin
temp1 := posisjonnavn(hode,navn);
if temp1 <> nil then
begin
temp2 := temp1^.neste;
// Linker forbi noden som skal slettes
temp1^.neste := temp2^.neste;
dispose(temp2);
resultat := true;
end
else
begin
// Navnet fantes ikke, kunne ikke slette
resultat := false;
end;
end; // slutt slettnavn
procedure finnnummer(navn:navntype; var nummer:nummertype;
var resultat:boolean);
var temp:oppforingpeker;
begin
temp := posisjonnavn(hode,navn);
if temp <> nil then
begin
// Returnerer telefonnummeret
nummer := temp^.neste^.nummer;
resultat := true;
end
else
begin
// Navnet fantes ikke, nummer kan ikke returneres
resultat := false;
end;
end; // slutt finnnummer
procedure finnnavn(nummer:nummertype; var navn:navntype;
var resultat:boolean);
var temp:oppforingpeker;
begin
temp := posisjonnummer(hode,navn);
if temp <> nil then
begin
// Returnerer navnet
navn := temp^.neste^.navn;
resultat := true;
end
else
begin
// Nummeret fantes ikke, navnet kan ikke returneres
resultat := false;
end;
end; // slutt finnnavn
procedure listalle(var resultatliste:oppforingpeker;
var resultat:boolean);
function posisjon(navn:navntype; listehode:oppforingpeker):oppforingpeker;
begin
if listehode <> nil and listehode^.navn > navn then
begin
// rekursivt kall
posisjon := posisjon(navn,listehode^.neste);
end;
else
begin
// Degenerert tilfelle
posisjon := listehode;
end;
end;
procedure settinn(navn:navntype; nummer:nummertype;
var listehode:oppforingpeker);
var temp:oppforingpeker;
begin
new(temp);
temp^.navn := navn;
temp^.nummer := nummer;
temp^.neste := listehode;
listehode := temp;
end;
function sorter(gammel,ny:oppforingpeker):oppforingpeker;
var temp:oppforingpeker;
begin
if gammel <> nil then
begin
settinn(gammel^.navn,gammel^.nummer,posisjon(gammel^.navn,ny));
sorter := sorter(gammel^.neste,ny);
end
else
begin
sorter := gammel;
end;
end; // slutt sorter
begin
resultatliste := sorter(hode,nil);
end; // slutt listalle
initialization
// Nullstiller global parameter hode
hode := nil;
end.
