Embed Size (px)
Citation preview
23/03/05 SE Info2 - S. L'haire UNIGE 1
TP 7PROCEDURE Inserer(VAR a, crt : AgendaPtr; j, h :
INTEGER; IN s : Chaine);
VAR nouveau, temp : AgendaPtr;
BEGIN
NEW(nouveau);nouveau.jour := j;nouveau.heure := h;
nouveau.sujet := s;nouveau.suivant := NIL;
crt:= nouveau;
IF a = NIL THEN a := nouveau;
ELSIF
(a.jour > j) OR ((a.jour = j) & (a.heure > h)) THEN
nouveau.suivant := a; a := nouveau;
23/03/05 SE Info2 - S. L'haire UNIGE 2
TP 7 suiteELSE (*insertion en ordre*)
temp := a; WHILE (temp.suivant # NIL) & ((nouveau.jour > temp.suivant.jour)
OR ((nouveau.jour = temp.suivant.jour) & (nouveau.heure > temp.suivant.heure)))
DOtemp := temp.suivant;
END;(*insertion au point d'insertion*)nouveau.suivant := temp.suivant;temp.suivant := nouveau;
END;END Inserer;
23/03/05 SE Info2 - S. L'haire UNIGE 3
TP 7 suitePROCEDURE GetPrecedent(tete, crt : AgendaPtr; VAR p :
AgendaPtr);
BEGIN
p := tete;
IF p = crt THEN
p := NIL;
ELSE
WHILE (p.suivant # NIL) & (p.suivant # crt) DO
p := p.suivant;
END;
END;
END GetPrecedent;
23/03/05 SE Info2 - S. L'haire UNIGE 4
TP 7 suitePROCEDURE DetruireCrt(VAR a, crt : AgendaPtr): BOOLEAN;VAR prec : AgendaPtr;BEGIN
IF a # NIL THENGetPrecedent(a, crt, prec); IF prec = NIL THEN
a := a.suivant; crt := a;
ELSEprec.suivant := crt.suivant;crt := prec;
END;RETURN TRUE
ELSE RETURN FALSE END;END DetruireCrt;
23/03/05 SE Info2 - S. L'haire UNIGE 5
Liste doublement chaînée
ListeDoublePtr = POINTER TO ListeDouble;
ListeDouble = RECORD
cle : blabla
prec,
suivant : ListeDoublePtr;
END;
23/03/05 SE Info2 - S. L'haire UNIGE 6
Enregistrement auxiliaire pour gérer liste
tetequeue
courant
MaListe = RECORD
tete,
queue
courant: ListeDoublePtr;
taille : INTEGER;
END;
taille
23/03/05 SE Info2 - S. L'haire UNIGE 7
Insertion La liste doit être initialisée tous
les pointeurs à NIL (créer procédure propre)
Ne pas oublier qu'il y a des pointeurs dans les 2 sens
Toujours penser à tete, queue et courant de l'enr. auxiliaire
23/03/05 SE Info2 - S. L'haire UNIGE 8
Insertion en têteNEW(el);
el.cle:= … el.precedent:= NIL; el.suivant:= l.tete; IF l.taille = 0 THEN l.queue:= el
ELSEl.tete.precedent:= el
END; l.tete:= el; INC(l.taille); l.courant := …
23/03/05 SE Info2 - S. L'haire UNIGE 9
Insertion en queueNEW(el); el.cle:= i; el.precedent:= l.queue; el.suivant:= NIL; IF l.taille = 0 THEN l.tete:= el
ELSE l.queue.suivant:= el
END; l.queue:= el; INC( l.taille);
l.courant :=…
23/03/05 SE Info2 - S. L'haire UNIGE 10
Insertion avant courantNEW(el); el.cle:= i; el.suivant:= NIL;
el.precedent:= NIL;
IF (l.taille = 0) OR (l.courant = l.tete) THEN
InsererEnTete( l, i)
ELSE
el.suivant:= l.courant;
el.precedent:= l.courant.precedent;
l.courant.precedent.suivant := el;
l.courant.precedent := el;
INC( l.taille)
END;
23/03/05 SE Info2 - S. L'haire UNIGE 11
DestructionPROCEDURE DetruireCourant(VAR l : ListeDouble):BOOLEAN;BEGIN
IF l.courant # NIL THENDEC(l.taille);IF l.taille = 0 THEN CreerListe(l); RETURN TRUE;ELSIF l.courant = l.tete THEN l.tete := l.courant.suivant; l.tete.precedent := NIL;ELSIF l.courant = l.queue THEN l.queue :=l.courant.precedent;l.queue.suivant := NIL;ELSE
l.courant.precedent.suivant := l.courant.suivant;
l.courant.suivant.precedent :=l.courant.precedent;END; l.courant := …RETURN TRUE;
END;RETURN FALSE;
END DetruireCourant;
23/03/05 SE Info2 - S. L'haire UNIGE 12
Parcours de liste 3 procédures: 1) Procédure pour placer
le pointeur courant sur la têtePROCEDURE CourantSurTete(VAR l : ListeDouble):
BOOLEAN;BEGIN
IF l.taille # 0 THENl.courant := l.tete;RETURN TRUE
ELSEl.courant := NIL;RETURN FALSE
END;
23/03/05 SE Info2 - S. L'haire UNIGE 13
Parcours (2) 2) Procédure pour sélectionner élément
suivantPROCEDURE ElementSuivant(VAR l : ListeDouble): BOOLEAN;
BEGINIF l.courant.suivant # NIL THENl.courant := l.courant.suivant;RETURN TRUE;
ELSERETURN FALSE;
END;
23/03/05 SE Info2 - S. L'haire UNIGE 14
Parcours (3) 3) Procédure de parcoursIF CourantSurTete(l) THEN
REPEAT
l.courant.cle …
UNTIL~ElementSuivant(l);
23/03/05 SE Info2 - S. L'haire UNIGE 15
Liste objet On transforme l'enregistrement
MaListe en lui ajoutant un pointeurMaListe = POINTER TO RECORD
tete,
queue
courant: ListeDoublePtr;
taille : INTEGER;
END;
23/03/05 SE Info2 - S. L'haire UNIGE 16
Initialisation de la liste Ajouter une méthode Procédure
précédée du nom de l'objet auquel elle est rattachée et suivie du mot-clé NEW
PROCEDURE (l : MaListe)Initialise():BOOLEAN, NEW;
BEGINl.tete := NIL; l.queue := NIL; l.courant:= NIL; l.taille := 0;
END Initialise;…NEW(liste); liste.Initialise();
23/03/05 SE Info2 - S. L'haire UNIGE 17
Méthode ListeVide Très utile dans beaucoup de casPROCEDURE (l: MaListe)ListeVide(): BOOLEAN;
BEGINRETURN taille = 0;
Ou varianteRETURN tete = NIL;
…IF l.ListeVide() THEN …
23/03/05 SE Info2 - S. L'haire UNIGE 18
Méthode ParcoursPROCEDURE (l : Liste)Parcours(), NEW;VAR temp : Liste;BEGIN
IF ~l.ListeVide() THENtemp := l.courant;IF l.CourantSurTete() THENREPEAT
l.courant …UNTIL ~l.AllerSuivant();l.courant := temp;
Attention: courant est parfois utilisé par plusieurs procédures le sauver dans temp
