Définition des listes généralisées · Définition des listes généralisées (2/2) Les listes sont ... Les spécifications de ces 5 opérations sont les termes de contrat pour

© ÉTS - GPA - GPA665 2

Définition des listes généralisées Définition des listes généralisées (1/2)(1/2)

Selon le Selon le Dictionnaire de lDictionnaire de l’’informatiqueinformatique de de LarousseLarousse, une liste se d, une liste se dééfinit finit comme suit :comme suit :

Ensemble de donnEnsemble de donnéées relies reliéées par une partie lien, qui permet des par une partie lien, qui permet d’é’établir un chemin tablir un chemin pour passer de lpour passer de l’’une une àà ll’’autre.autre.

Ainsi, une liste correspond Ainsi, une liste correspond àà une collection de donnune collection de donnéées relies reliéées entre elles.es entre elles.Cette collection est essentiellement constituCette collection est essentiellement constituéée de e de nn groupes de groupes de mm donndonnéées. es. On dit aussi que la liste possOn dit aussi que la liste possèède de nn enregistrements de enregistrements de mm donndonnéées chacun.es chacun.

Liste d’appartements à louerType maison DuplexeNbr. pieces 7 ½

Chauffé Non

Cartier Rosemont

Garage inclu NonMeublé Non

Cours inclu Non

Prix mensuel 900 $

Étage 3ième

Type maison DuplexeNbr. pieces 3 ½

Chauffé Non

Cartier Rosemont

Garage inclu OuiMeublé Non

Cours inclu Oui

Prix mensuel 650 $

Étage 1ier

Type maison TriplexeNbr. pieces 4 ½

Chauffé Non

Cartier Verdun


Cours inclu Non

Prix mensuel 550 $

Étage 2ième

Type maison MaisonNbr. pieces 10 ½

Chauffé Non

Cartier Outremont

Garage inclu OuiMeublé Oui

Cours inclu Oui

Prix mensuel 2200 $

Étage 1ier - 2ième

Type maison TriplexeNbr. pieces 6 ½

Chauffé Non

Cartier Petite-Patrie


Cours inclu Non

Prix mensuel 750 $

Étage 1ier

9 do

nnée

s par

enr

egis

trem

ent

Liste de 5 enregistrements

1 enregistrement


Définition des listes généralisées Définition des listes généralisées (2/2)(2/2)

Les listes sont certainement les TDA Les listes sont certainement les TDA lesles plus utilisplus utiliséées.es.

Les listes les plus simples contiennent seulement Les listes les plus simples contiennent seulement quelques donnquelques donnéées par enregistrement.es par enregistrement.

LorsquLorsqu’’on parle de listes gon parle de listes géénnééralisraliséées, on fait res, on fait rééfféérence rence au fait que chaque enregistrement de ces listes peut au fait que chaque enregistrement de ces listes peut contenir dcontenir d’’autres listes parmi ses donnautres listes parmi ses donnéées es (cette d(cette dééfinition finition peut être appliqupeut être appliquéée re réécursivement pour chacune des sous liste)cursivement pour chacune des sous liste). .


Un exemple : Une liste d’épicerie! Un exemple : Une liste d’épicerie! (1/4)(1/4)

Pour Pour éélaborer la notion dlaborer la notion d’’un type de donnun type de donnéées abstrait, es abstrait, considconsidéérer la liste de provision suivante :rer la liste de provision suivante :

lait;lait;pain;pain;oeufs;oeufs;beurre;beurre;confiture;confiture;croissants;croissants;pommes;pommes;bananes.bananes.

Les Les ééllééments de la liste sont dans un ordre sments de la liste sont dans un ordre sééquentiel quentiel mais ne sont pas nmais ne sont pas néécessairement ordonncessairement ordonnéés par nom.s par nom.



Que peutQue peut--on faire avec une telle liste ?on faire avec une telle liste ?(Quels sont les services qui peuvent être d(Quels sont les services qui peuvent être dééfinit?)finit?)

crcrééer la liste;er la liste;ajouter un article dans la liste;ajouter un article dans la liste;retirer un article de la liste;retirer un article de la liste;calculer la longueur de la liste (le nombre dcalculer la longueur de la liste (le nombre d’’articles dans la liste);articles dans la liste);retrouver lretrouver l’’article de la position i.article de la position i.

Quelle donnQuelle donnéées sont nes sont néécessaires aux diffcessaires aux difféérents rents enregistrements de la liste?enregistrements de la liste?

un nom dun nom d’’article.article.Ainsi, on vient de dAinsi, on vient de dééfinir un type de donnfinir un type de donnéées abstrait es abstrait nommnomméé «« liste de provisions liste de provisions »» comme une collection comme une collection dd’é’éllééments de provisions jointes ments de provisions jointes àà ll’’ensemble ensemble dd’’opopéérations prrations prééddééfinis.finis.



DDééfinition des opfinition des opéérations :rations :CreateCreate : Cr: Créée et fait le et fait l’’initialisation de la liste initialisation de la liste ((àà vide)vide)Insert : InsInsert : Insèère un nouvel enregistrement dans la listere un nouvel enregistrement dans la listeDeleteDelete : Supprime un enregistrement sp: Supprime un enregistrement spéécifique de la listecifique de la listeRetrieveRetrieve : Retrouve un enregistrement sp: Retrouve un enregistrement spéécifique de la liste et retourne cifique de la liste et retourne son contenuson contenuLengthLength : Retourne le nombre d: Retourne le nombre d’’enregistrements prenregistrements préésents dans la listesents dans la liste

Les spLes spéécifications de ces 5 opcifications de ces 5 opéérations sont les termes de contrat rations sont les termes de contrat pour cette liste.pour cette liste.QuQu’’estest--ce que la dce que la dééfinition finition cici--hauthaut peut nous dire sur son peut nous dire sur son comportement :comportement :

les fonctions : les fonctions : CreateCreate, Insert et , Insert et DeleteDelete modifient le contenu de la liste.modifient le contenu de la liste.les fonctions : les fonctions : RetrieveRetrieve et et LengthLength questionnent la liste et retourne des questionnent la liste et retourne des informations sur elle.informations sur elle.



Un TDA ne doit pas inclure les problUn TDA ne doit pas inclure les probléématiques de matiques de ll’’implimpléémentation. Par exemple, on veut crmentation. Par exemple, on veut crééer la liste er la liste suivante :suivante :

On utilise alors le On utilise alors le pseudopseudo--codecode suivant :suivant :

Create(List)

Insert(List, Lait)Insert(List, Pain)Insert(List, Oeufs)Insert(List, Beurre)Insert(List, Confiture)Insert(List, Fruits)

Lait Pain BeurreOeufs Confiture FruitsList


Exemples d’implémentation de liste Exemples d’implémentation de liste (1/3)(1/3)

Liste avec allocation statique et organisation contiguListe avec allocation statique et organisation contiguëë

Liste avec allocation statique et organisation chaListe avec allocation statique et organisation chaîînnéée simplee simple

Liste avec allocation dynamique par bloc et organisation chaListe avec allocation dynamique par bloc et organisation chaîînnéée doublee double

0 1 2 3 4 5 6 7 8 9AlfredAlexia Katy Karen PatrickKevinKen -Mike -

List

-7

Zach-1

-0

Katy4

Karen8

Christ3

Alexia5

--1

Nicolas9

Patrick1

0 1 2 3 4 5 6 7 8 9Data6First

List

2

Empty

0 1 2 3 4

5

MemAllocSList

3-1

Alexia-13

Sassia-1-

-10

Nicolas2-

-

1

Last3

n4

Empty0

First Data



Liste avec allocation dynamique par enregistrement et organisatiListe avec allocation dynamique par enregistrement et organisation on chachaîînnéée simple e simple (ou liste cha(ou liste chaîînnéée)e)

Listes doublement chaListes doublement chaîînnéées es (standard et circulaire)(standard et circulaire)

Alexia Ben Christ Katy Karen Nicolas PatrickHead

List


Tail

List

Alexia Ben Christ Katy Karen Nicolas

HeadList

© ÉTS - GPA - GPA665 10


Liste gListe géénnééralisralisééee

© ÉTS - GPA - GPA665 11

Implémentations de listes Implémentations de listes (1/2)(1/2)

On fera lOn fera l’’implimpléémentation de 3 listes diffmentation de 3 listes difféérentes :rentes :liste avec allocation statique et organisation contiguliste avec allocation statique et organisation contiguëë;;liste avec allocation dynamique par enregistrement et organisatiliste avec allocation dynamique par enregistrement et organisation on chachaîînnéée simple e simple (liste cha(liste chaîînnéée simple)e simple);;liste avec allocation dynamique par bloc et organisation par douliste avec allocation dynamique par bloc et organisation par double ble chachaîînage nage (liste cha(liste chaîînnéée double dans un tableau dynamique)e double dans un tableau dynamique)..

Toutes les listes nToutes les listes n’’auront quauront qu’’une seule donnune seule donnéée e (une cha(une chaîîne de ne de caractcaractèères)res) et devront être triet devront être triéée en ordre croissant.e en ordre croissant.Seulement quelques services seront implantSeulement quelques services seront implantéés, par exemple :s, par exemple :

Compter le nombre dCompter le nombre d’’ enregistrementsenregistrements LengthLength((……))InsInséérer un nouvel enregistrementrer un nouvel enregistrement Insert(Insert(……))Supprimer un enregistrement existantSupprimer un enregistrement existant DeleteDelete((……))Rechercher un enregistrement Rechercher un enregistrement SearchSearch((……))Consulter un enregistrementConsulter un enregistrement RetrieveRetrieve((……))CrCrééer et/ou initialiser la liste de donner et/ou initialiser la liste de donnééeses CreateCreate((……))DDéétruire la liste de donntruire la liste de donnééeses Destroy(Destroy(……))Afficher le contenu de la liste de donnAfficher le contenu de la liste de donnééeses PrintListPrintList((……))Parcourir la liste de donnParcourir la liste de donnééeses GoThroughGoThrough((……))

© ÉTS - GPA - GPA665 12

Implémentations de listes Implémentations de listes (2/2)(2/2)

Quelques commentaires avant de commencerQuelques commentaires avant de commencerLes mLes mééthodes rthodes rééalisaliséées sont bases sont baséées sur quelques approches es sur quelques approches particuliparticulièères. En fait, il existe une multitude dres. En fait, il existe une multitude d’’approches approches possibles et elles sont tous aussi valables les unes que les possibles et elles sont tous aussi valables les unes que les autres, avec leurs avantages et leurs inconvautres, avec leurs avantages et leurs inconvéénients.nients.

Il est recommandIl est recommandéé dans la plupart des cas ddans la plupart des cas d’’utiliser une utiliser une structure globale ou une structure dstructure globale ou une structure d’’enen--tête permettant le tête permettant le stockage des informations gstockage des informations géénnéérales de la liste telles que le rales de la liste telles que le nombre dnombre d’é’éllééments ments (même si cette m(même si cette mééthode requiert lthode requiert lééggèèrement plus de rement plus de mméémoire)moire)..

© ÉTS - GPA - GPA665 13

ImplImpléémentation dmentation d’’une liste avec allocation une liste avec allocation statique et organisation contigustatique et organisation contiguëë

Alexia Alfred Katy Karen Ken Kevin Mike Patrick - -0 1 2 3 4 5 6 7 8 9Data

7

LasPosSList

© ÉTS - GPA - GPA665 14

Implémentation d’une liste avec allocation statique et Implémentation d’une liste avec allocation statique et organisation contiguë organisation contiguë (1/14)(1/14)

DDééfinition dfinition d’’un exemple de ce type de TDAun exemple de ce type de TDALe TDA contient :Le TDA contient :

un tableau de taille fixe contenant les donnun tableau de taille fixe contenant les donnéées es (qui peut contenir un (qui peut contenir un nombre maximum dnombre maximum dééfini dfini d’’enregistrements)enregistrements);;une variable entiune variable entièère contenant lre contenant l’’indexe du dernier enregistrement indexe du dernier enregistrement prpréésent dans le tableau sent dans le tableau (nommons cette variable (nommons cette variable LastPosLastPos));;

La variable La variable LastPosLastPos indique lindique l’’indexe du dernier enregistrement, indexe du dernier enregistrement, cc’’estest--àà--dire que dire que LastPosLastPos = n = n -- 11 (o(oùù n est le nombre n est le nombre dd’’enregistrements)enregistrements). Ainsi, lorsqu. Ainsi, lorsqu’’il nil n’’y a aucun enregistrement y a aucun enregistrement prpréésent : sent : LastPosLastPos = = --11..Les fonctions de crLes fonctions de crééation et de destruction de la structure de ation et de destruction de la structure de donndonnéées sont inutiles puisque ces dernies sont inutiles puisque ces dernièères sont prises en res sont prises en charge par le compilateur au moment de la dcharge par le compilateur au moment de la dééclaration de la claration de la variable.variable.Par contre, le TDA doit être initialisPar contre, le TDA doit être initialiséé correctement. Ccorrectement. C’’estest--àà--dire dire que la variable que la variable LastPosLastPos doit être initialisdoit être initialiséée e àà --1.1.

© ÉTS - GPA - GPA665 15

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (2/14)(2/14)

1.1. DDééclaration des types nclaration des types néécessaires au cessaires au TDATDA..

2.2. Fonction dFonction d’’initialisation initialisation (mettre la variable (mettre la variable LastPosLastPos àà --1)1)..void InitList(SList *pList){pList->LastPos = -1;

}

#define MAXDATA 1000#define STRLENGTH 25

typedef struct {int LastPos;char Data[MAXDATA][STRLENGTH];

} SList;

SList List;


7

LasPosSList

© ÉTS - GPA - GPA665 16

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (3/14)(3/14)3.3. Fonction dFonction d’’insertion insertion (exemple : ajouter l(exemple : ajouter l’’enregistrement John)enregistrement John)

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 5 opeffectue en 5 opéérations :rations :1.1. ss’’assurer quassurer qu’’il reste un enregistrement de libre dans le tableau il reste un enregistrement de libre dans le tableau (facultatif)(facultatif);;2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans le tableau rer dans le tableau

(l(l’’enregistrement recherchenregistrement recherchéé doit possdoit possééder une valeur plus grand que celui der une valeur plus grand que celui àà insinséérer)rer);;

3.3. effectuer un deffectuer un déécalage calage àà droite droite àà partir de lpartir de l’’endroit dendroit d’’insertion;insertion;

John


7

LasPosSList

John

Alexia Alfred Katy -0 1 2 3 4 5 6 7 8 9Data

7

LasPosSList

Karen Ken Kevin Mike PatrickKaty

© ÉTS - GPA - GPA665 17

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (4/14)(4/14)3.3. Fonction dFonction d’’insertion insertion (suite)(suite)

1.1. Description logique Description logique (suite)(suite). . 4.4. insinséérer la nouvelle donnrer la nouvelle donnéée e àà la position trouvla position trouvéée;e;

5.5. ajuster les variables de contrôle.ajuster les variables de contrôle.

Alexia Alfred Karen Ken Kevin Mike PatrickKaty -0 1 2 3 4 5 6 7 8 9Data

7

LasPosSList

John

Alexia Alfred Karen Ken Kevin Mike PatrickKaty -0 1 2 3 4 5 6 7 8 9Data

8

LasPosSList

John

© ÉTS - GPA - GPA665 18


2.2. DDééfinition du prototype de la fonction finition du prototype de la fonction (d(dééfinition des entrfinition des entréées/sorties)es/sorties)

3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes : : 1.1. ss’’assurer quassurer qu’’il reste un enregistrement de libre dans le tableau;il reste un enregistrement de libre dans le tableau;

2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans le tableau;rer dans le tableau;

3.3. effectuer un deffectuer un déécalage calage àà droite droite àà partir de lpartir de l’’endroit dendroit d’’insertion;insertion;

4.4. insinséérer la nouvelle donnrer la nouvelle donnéée e àà la position trouvla position trouvéée;e;


Position = Recherche plus grand que : NewValue dans : pList

void Insert(SList *pList, char NewValue[], int *Success);

i = LastPosTant que i >= PositionValeur à i = Valeur à i + 1i = i - 1

Valeur à Position = NewValue

Si LastPos < MAXDATA (on peut insérer)

LastPos = LastPos + 1Success = vrai;

© ÉTS - GPA - GPA665 19


4.4. ÉÉcriture finale du code en langage Ccriture finale du code en langage Cvoid Insert(SList *pList, char NewValue[], int *Success){int i, Pos;/*** 1ière étape : Vérifie que la liste existe et qu'elle n'est pas remplie ***/if ((pList != NULL) && (pList->LastPos < MAXDATA)) {/*** 2ière étape : Recherche du point d'insertion ***/Pos = SearchGreater(pList, NewValue);/* Si le point d'insertion est valide on insère */if (Pos != -1) {/*** 3ième étape : Décalage à droite à partir du point d'insertion ***/for (i = pList->LastPos; i >= Pos; i--) {strcpy(pList->Data[i+1], pList->Data[i]);

}/*** 4ième étape : Copie les données ***/strcpy(pList->Data[Pos], NewValue);/*** 5ième étape : Ajuste les variables de contrôle ***/pList->LastPos++;*Success = 1;

} else {*Success = 0;

}} else*Success = 0;

}

© ÉTS - GPA - GPA665 20

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (7/14)(7/14)4.4. Fonction de suppression Fonction de suppression (exemple : supprimer l(exemple : supprimer l’’enregistrement Katy)enregistrement Katy)

Attention Attention àà la mla mééthode de suppression direct qui est inapproprithode de suppression direct qui est inappropriééee

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 4 opeffectue en 4 opéérations :rations :1.1. ss’’assurer quassurer qu’’il existe au moins un enregistrement de libre dans le tableau; il existe au moins un enregistrement de libre dans le tableau;

(facultatif car l(facultatif car l’é’étape suivante peut faire cette tâche)tape suivante peut faire cette tâche)

2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà supprimer dans le tableau;supprimer dans le tableau;

Alexia Alfred Karen Ken Kevin Mike Patrick -0 1 2 3 4 5 6 7 8 9Data

8

LasPosSList

John Katy

© ÉTS - GPA - GPA665 21

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (8/14)(8/14)4.4. Fonction de suppression Fonction de suppression (suite)(suite)

1.1. Description logique Description logique (suite)(suite)..3.3. effectuer un deffectuer un déécalage calage àà gauche gauche àà partir de lpartir de l’’endroit de suppression;endroit de suppression;


Alexia Alfred -0 1 2 3 4 5 6 7 8 9Data

8

LasPosSList

John PatrickKaren Ken Kevin Mike Patrick

Alexia Alfred Karen Ken Kevin Mike Patrick -0 1 2 3 4 5 6 7 8 9Data

7

LasPosSList

John Patrick

© ÉTS - GPA - GPA665 22



3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes : : 1.1. ss’’assurer quassurer qu’’il existe au moins un enregistrement de libre dans le tableau;il existe au moins un enregistrement de libre dans le tableau;

2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà supprimer dans le tableau;supprimer dans le tableau;

3.3. effectuer un deffectuer un déécalage calage àà gauche gauche àà partir de lpartir de l’’endroit de suppression;endroit de suppression;


Position = Recherche exactement : OldValue) dans : pList

void Delete(SList *pList, char OldValue[], int *Success);

i = PositionTant que i < LastPosValeur à i = Valeur à i + 1i = i + 1

LastPos = LastPos - 1Success = vrai

Si LastPos >= 0 (on peut continuer)

© ÉTS - GPA - GPA665 23


4.4. ÉÉcriture finale du code en langage Ccriture finale du code en langage Cvoid Delete(SList *pList, char OldValue[], int *Success){int i, Pos;

/*** 1ière étape : Vérifie que la liste existe et qu'elle n'est pas vide ***/if ((pList != NULL) && (pList->LastPos >= 0)) {/*** 2ième étape : Recherche l'enregistrement à supprimer ***/Pos = SearchEqual(pList, OldValue);/* Si le point de suppression est valide on supprime */if (Pos != -1) {/*** 3ième étape : Décalage à gauche à partir du point de suppression ***/for (i = Pos; i < pList->LastPos; i++)strcpy(pList->Data[i], pList->Data[i+1]);

/*** 4ième étape : Ajuste les variables de contrôle ***/pList->LastPos--;*Success = 1;


}} else {*Success = 0;

}}

© ÉTS - GPA - GPA665 24

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (11/14)(11/14)5.5. Fonction de recherche Fonction de recherche (exemple : rechercher l(exemple : rechercher l’’enregistrement Patrick)enregistrement Patrick)

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue par :effectue par :parcourir le tableau tant que les conditions de recherche ne soiparcourir le tableau tant que les conditions de recherche ne soient pas ent pas atteintes. Ces conditions peuvent varier en fonction des besoinatteintes. Ces conditions peuvent varier en fonction des besoins et peuvent s et peuvent être, par exemple :être, par exemple :

1.1. ll’’enregistrement uniquement enregistrement uniquement éégal gal àà celui recherchcelui recherchéé;;2.2. ll’’enregistrement plus petit que celui recherchenregistrement plus petit que celui recherchéé;;3.3. ll’’enregistrement plus grand que celui recherchenregistrement plus grand que celui recherchéé;;4.4. ... .... .

de plus, cette rde plus, cette rééfféérence peut prendre deux formes drence peut prendre deux formes déépendamment des pendamment des besoins et de la mbesoins et de la mééthode dthode d’’implimpléémentation du TDA :mentation du TDA :

1.1. ll’’indexe du tableau correspondant indexe du tableau correspondant àà ll’’enregistrement enregistrement (ou (ou --1 si aucun r1 si aucun réésultat)sultat);;2.2. le pointeur correspondant le pointeur correspondant àà ll’’enregistrement enregistrement (ou NULL si aucun r(ou NULL si aucun réésultat)sultat). .


3.3. DDééfinition de la recherche par un finition de la recherche par un pseudopseudo--codecode ::

int Search(SList *List, char Value[]);

i = 0;Tant que i

© ÉTS - GPA - GPA665 25

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (12/14)(12/14)5.5. Fonction de recherche Fonction de recherche (suite)(suite)

4.4. ÉÉcriture finale du code en langage C :criture finale du code en langage C :int SearchEqual(SList *pList, char Value[]){int i = 0, iRes = -1, n = Length(pList);/* Vérifie que la liste ne soit pas vide */if (n != 0){while ((i LastPos) && (strcmp(pList->Data[i], Value) < 0)) i++;/* S'assure que l'élément recherché est celui trouvé */if ((i LastPos) && (strcmp(pList->Data[i], Value) == 0)) {iRes = i;

}}return iRes;

}

int SearchGreater(SList *pList, char Value[]){int i = 0, iRes = -1, n = Length(pList);/* Vérifie que la liste ne soit pas pleine */if (n < MAXDATA) {while ((i LastPos) && (strcmp(pList->Data[i], Value)

© ÉTS - GPA - GPA665 26

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (13/14)(13/14)6.6. Fonction de comptageFonction de comptage

7.7. Fonction questionnant le TDA Fonction questionnant le TDA àà savoir ssavoir s’’il est videil est vide

8.8. Fonction retournant un Fonction retournant un éélléément en fonction de sa positionment en fonction de sa position

int Length(SList *pList){return pList->LastPos + 1;

}

int IsEmpty(SList *pList){return (Length(pList) == 0) ? 1 : 0;

}

char* Retrieve(SList *pList, int i){if ((i > 0) && (i Data[i-1];

} else {return NULL;

}}

© ÉTS - GPA - GPA665 27

Implémentation d’une liste avec allocation Implémentation d’une liste avec allocation statique et organisation contiguë statique et organisation contiguë (14/14)(14/14)

Quelques commentairesQuelques commentaires

On remarque que le dOn remarque que le déécalage des calage des ééllééments devient un problments devient un problèème me de performance important associde performance important associéé àà la maintenance des la maintenance des donndonnéées si la taille des ces dernies si la taille des ces dernièères devient considres devient considéérable ou si rable ou si il y a un grand nombre de manipulations.il y a un grand nombre de manipulations.

Les TDA basLes TDA baséés sur les structures par chas sur les structures par chaîînage sont une solution nage sont une solution trtrèès efficace au probls efficace au problèème de dme de déécalage pour les insertions et calage pour les insertions et suppressions entre les suppressions entre les éélléémentsments

© ÉTS - GPA - GPA665 28

ImplImpléémentation dmentation d’’une liste avec allocation une liste avec allocation dynamique par enregistrement et dynamique par enregistrement et organisation en chaorganisation en chaîîne ne (liste cha(liste chaîînnéée)e)


© ÉTS - GPA - GPA665 29

Implémentation d’une liste avec allocation dynamique par enregisImplémentation d’une liste avec allocation dynamique par enregistrement et trement et organisation chaînée simple (liste chaînée simple) organisation chaînée simple (liste chaînée simple) (1/15)(1/15)

DDééfinition dfinition d’’un exemple de ce type de TDAun exemple de ce type de TDALe TDA est dLe TDA est dééfini comme suit :fini comme suit :

chaque enregistrement est dchaque enregistrement est dééfini par une structure contenant les fini par une structure contenant les donndonnéées et un pointeur vers la structure suivante;es et un pointeur vers la structure suivante;la liste est rla liste est rééfféérencrencéée par un pointeur global qui pointe vers le e par un pointeur global qui pointe vers le premier premier éélléément de la liste. On nomme ce pointeur, le pointeur de ment de la liste. On nomme ce pointeur, le pointeur de tête. tête.

La fin de la liste est indiquLa fin de la liste est indiquéée par un pointeur nul.e par un pointeur nul.La fonction de crLa fonction de crééation a le rôle dation a le rôle d’’initialiser correctement le initialiser correctement le pointeur de tête pointeur de tête àà une valeur nulle (pour ainsi assurer la une valeur nulle (pour ainsi assurer la cohcohéérence de la liste drence de la liste dèès le ds le déépart). part). DD’’un autre côtun autre côtéé, la fonction de destruction du TDA doit plutôt , la fonction de destruction du TDA doit plutôt ss’’assurer quassurer qu’’il ne reste aucun enregistrements allouil ne reste aucun enregistrements allouéés pour la s pour la liste.liste.

© ÉTS - GPA - GPA665 30

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (2/15)(2/15)

1.1. DDééclaration des types nclaration des types néécessaires au cessaires au TDATDA..

2.2. Fonction de crFonction de crééation de la liste ation de la liste (qui consiste (qui consiste àà initialiser le pointeur de tête initialiser le pointeur de tête ààune valeur nulle)une valeur nulle)..

void CreateList(SNode **pHead){*pHead = NULL;

}

#define STRLENGTH 25

typedef struct _node {char Data[STRLENGTH];struct _node *Next;

} SNode;


© ÉTS - GPA - GPA665 31

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (3/15)(3/15)3.3. Fonction de destruction de la liste Fonction de destruction de la liste (qui consiste (qui consiste àà liblibéérer toute mrer toute méémoire moire

rréésiduelle associsiduelle associéée e àà la liste, soit tous les enregistrements restants)la liste, soit tous les enregistrements restants)..

4.4. Fonction qui vide tout le contenu de la liste.Fonction qui vide tout le contenu de la liste.void DeleteAll(SNode **pHead){SNode *TempNode;

/* Libère tous les premiers noeuds de la liste tant qu'il en reste */while (*pHead != NULL) {TempNode = *pHead;*pHead = (*pHead)->Next;free(TempNode);

}*pHead = NULL;

}

void DestroyList(SNode **pHead){DeleteAll(pHead);

}

© ÉTS - GPA - GPA665 32

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (4/15)(4/15)5.5. Fonction dFonction d’’affichage de la liste affichage de la liste (avec parcours en ordre croissant)(avec parcours en ordre croissant)

6.6. Fonction de comptageFonction de comptage

void PrintList(SNode *Head){SNode *Cur = Head;while (Cur != NULL) { /* Parcours la liste et affiche son contenue */printf("%s\n", Cur->Data);Cur = Cur->Next;

}}

void Length(SNode *Head){SNode *Cur = Head;int n = 0;while (Cur != NULL) { /* Parcours la liste et compte le nombre d’item */Cur = Cur->Next;n++;

}return n;

}

© ÉTS - GPA - GPA665 33

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (5/15)(5/15)7.7. Fonction questionnant le TDA Fonction questionnant le TDA àà savoir ssavoir s’’il est videil est vide

8.8. Fonction retournant un Fonction retournant un éélléément en fonction de sa positionment en fonction de sa positionchar* Retrieve(SNode *Head, int i){SNode *Cur = Head;

if ((i > 0) && (i 1; Cur = Cur->Next, i--);return Cur->Data;


}}

void IsEmpty(SNode *Head){return (Head == NULL) ? 1 : 0;

}

© ÉTS - GPA - GPA665 34

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (6/15)(6/15)9.9. Fonction dFonction d’’insertion insertion (exemple : ajouter l(exemple : ajouter l’’enregistrement John)enregistrement John)

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 3 opeffectue en 3 opéérations :rations :1.1. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans la liste rer dans la liste

(l(l’’enregistrement recherchenregistrement recherchéé doit possdoit possééder une valeur plus grand que celui der une valeur plus grand que celui àà insinséérer)rer);;

2.2. allouer la mallouer la méémoire nmoire néécessaire au nouvel enregistrement et copier les cessaire au nouvel enregistrement et copier les donndonnéées;es;


John

Prev Cur

New


John

Prev Cur

© ÉTS - GPA - GPA665 35

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (7/15)(7/15)9.9. Fonction dFonction d’’insertion insertion (suite)(suite)

1.1. Description logique Description logique (suite)(suite)..3.3. ajuster les rajuster les rééfféérences de liens et variables de contrôle.rences de liens et variables de contrôle.


John

Prev Cur

New

© ÉTS - GPA - GPA665 36



3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes ::1.1. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans la liste;rer dans la liste;

2.2. allouer la mallouer la méémoire nmoire néécessaire au nouvel enregistrement et copier les cessaire au nouvel enregistrement et copier les donndonnéées;es;New = nouvel enregistrement

La valeur de New = NewValue

void Insert(SNode **pHead, char NewValue[], int *Success);

Initialise Prev = nul et Cur = pHeadTant que Cur != nul et que la valeur de Cur < NewValuePrev = CurCur = prochain

© ÉTS - GPA - GPA665 37


3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes (suite)(suite) : : 3.3. ajuster les rajuster les rééfféérences de liens et variables de contrôle.rences de liens et variables de contrôle.

*** Insertion au début de la listeSi Prev = nulLe prochain de New = pHeadpHead = New

*** Insertion entre 2 noeuds ou à la finSinonLe prochain de New = CurLe prochain de Prev = New

© ÉTS - GPA - GPA665 38


4.4. ÉÉcriture finale du code en langage C :criture finale du code en langage C :void Insert(SNode **pHead, char NewValue[], int *Success){SNode *Prev, *Cur, *New;

/*** 1ière étape : Recherche du point d'insertion ***/Prev = NULL; Cur = *pHead;while ((Cur != NULL) && (strcmp(Cur->Data, NewValue) < 0)) {Prev = Cur; Cur = Cur->Next;

}/*** 2ième étape : Allocation dynamique et copie des données ***/if ((New = (SNode*) malloc(sizeof(SNode))) == NULL) {*Success = 0; return;

}strcpy(New->Data, NewValue);/*** 3ième étape : Ajuste les variables de contrôle (les liens) ***/if (Prev == NULL) { /* Insertion au début de la liste */New->Next = *pHead;*pHead = New;

} else { /* Insertion entre 2 noeuds ou à la fin */New->Next = Cur;Prev->Next = New;

}*Success = 1;

}

© ÉTS - GPA - GPA665 39

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (11/15)(11/15)10.10. Fonction de suppression Fonction de suppression (exemple : supprimer l(exemple : supprimer l’’enregistrement Ben)enregistrement Ben)

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 3 opeffectue en 3 opéérations :rations :1.1. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà supprimer de la liste;supprimer de la liste;

2.2. ajuster les rajuster les rééfféérences de liens;rences de liens;


Prev Cur


Prev Cur

© ÉTS - GPA - GPA665 40

Implémentation d’une liste avec allocation dynamique par Implémentation d’une liste avec allocation dynamique par enregistrement et organisation chaînée simple (liste chaînée enregistrement et organisation chaînée simple (liste chaînée simple) simple) (12/15)(12/15)10.10. Fonction de suppression Fonction de suppression (suite)(suite)

1.1. Description logique Description logique (suite)(suite)..3.3. liblibéérer la mrer la méémoire associmoire associéée e àà ll’’enregistrement enregistrement àà supprimer et ajuster les supprimer et ajuster les

variables de contrôle.variables de contrôle.

Alexia Christ Katy Karen Nicolas PatrickHead

Prev Cur

Ben

© ÉTS - GPA - GPA665 41



3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes ::1.1. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà supprimer de la liste;supprimer de la liste;

2.2. ajuster les rajuster les rééfféérences de liens;rences de liens;*** Si la valeur recherchée a été trouvéeSi Cur != nul et que la valeur de Cur correspond à OldValue*** Suppression au début de la listeSi Prev = nulpHead = le prochain de Cur

*** Suppression entre 2 noeuds ou à la fin de la listeSinonle prochain de Prev = le prochain de Cur

void Delete(SNode **pHead, char OldValue[], int *Success);

Initialise Prev = nul et Cur = pHeadTant que Cur != nul et que la valeur de Cur < NewValuePrev = CurCur = le prochain de Cur

© ÉTS - GPA - GPA665 42


3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes (suite)(suite) : : 3.3. liblibéérer la mrer la méémoire associmoire associéée e àà ll’’enregistrement enregistrement àà supprimer et ajuster les supprimer et ajuster les

variables de contrôle.variables de contrôle.Libérer Cur

Success = vrai

© ÉTS - GPA - GPA665 43


4.4. ÉÉcriture finale du code en langage C :criture finale du code en langage C :void Delete(SNode **pHead, char OldValue[], int *Success){SNode *Prev = NULL, *Cur = *pHead;

/*** 1ière étape : Recherche de l'enregistrement à supprimer ***/while ((Cur != NULL) && (strcmp(Cur->Data, OldValue) < 0)) {Prev = Cur; Cur = Cur->Next;

}/* Effectue la suppression si l'enregistrement recherché existe */if ((Cur != NULL) && (strcmp(Cur->Data, OldValue) == 0)) {/*** 2ième étape : Ajuste les variables de contrôle (les liens) ***/if (Prev == NULL) { /* Suppression au début de la liste */*pHead = Cur->Next;

} else { /* Suppression entre 2 noeuds ou à la fin de la liste */Prev->Next = Cur->Next;

}/*** 3ième étape : Libération de l'enregistrement ***/free(Cur);*Success = 1;


}}

© ÉTS - GPA - GPA665 44

ImplImpléémentation dmentation d’’une liste avec allocation une liste avec allocation dynamique par bloc et organisation par dynamique par bloc et organisation par double chadouble chaîînage nage (liste cha(liste chaîînnéée double dans un tableau dynamique)e double dans un tableau dynamique)

0 1 2 3 4

5

MemAllocSList

3-1

Alexia-13

Sassia-1-

-10

Nicolas2-

-

1

Last3

n4

Empty0

First Data

Str

Next

Prev

© ÉTS - GPA - GPA665 45

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc et organisation organisation par double chaînage (liste chaînée double dans un tableau dynamipar double chaînage (liste chaînée double dans un tableau dynamique) que) (1/16)(1/16)

DDééfinition dfinition d’’un exemple de ce type de TDAun exemple de ce type de TDALe TDA est dLe TDA est dééfini comme suit :fini comme suit :

le tableau est de taille dynamique le tableau est de taille dynamique (la taille du tableau est ajust(la taille du tableau est ajustéée selon les besoins)e selon les besoins);;lorsque le tableau est rempli (lorsque le tableau est rempli (n = tn = t) et qu) et qu’’une insertion est en cours, on une insertion est en cours, on augmente la taille du tableau par augmente la taille du tableau par t t ×× 22;;(o(oùù t est la taille du tableau et n est le nombre dt est la taille du tableau et n est le nombre d’’enregistrement dans le tableau)enregistrement dans le tableau);;lorsque le tableau nlorsque le tableau n’’est rempli quest rempli qu’à’à n = t n = t ÷÷ 44 et quet qu’’une suppression est une suppression est en cours, ou ren cours, ou rééduit la taille du tableau duit la taille du tableau àà t t ÷÷ 22chaque enregistrement est dchaque enregistrement est dééfini par une structure contenant les donnfini par une structure contenant les donnéées et es et deux entiers servants de rdeux entiers servants de rééfféérence de lien rence de lien (l(l’’un pointant vers lun pointant vers l’’enregistrement prenregistrement prééccéédent dent et let l’’autre vers le suivant)autre vers le suivant);;quelques variables de rquelques variables de rééfféérence globale rence globale àà la liste sont nla liste sont néécessaires : lcessaires : l’’indexe indexe du premier du premier ((FirstFirst)) et dernier et dernier ((LastLast)) éélléément, lment, l’’indexe du premier vide indexe du premier vide ((EmptyEmpty)), , le nombre dle nombre d’’enregistrements disponibles dans le tableau enregistrements disponibles dans le tableau ((MemAllocMemAlloc)) et le et le nombre dnombre d’’enregistrements en cours dans le tableau enregistrements en cours dans le tableau ((nn));;une liste des une liste des ééllééments vides doit être maintenue;ments vides doit être maintenue;les donnles donnéées sont tries sont triéées en ordre croissant.es en ordre croissant.

Pour cet exemple, question de complexifier un peu le problPour cet exemple, question de complexifier un peu le problèème, la me, la chachaîîne de caractne de caractèères est dres est dééfinie par un tableau dynamique.finie par un tableau dynamique.

© ÉTS - GPA - GPA665 46

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (2/16)(2/16)

1.1. DDééclaration des types nclaration des types néécessaires au cessaires au TDATDA../* EXEMPLE – Une façon de déclarer le

type booléen en C */

typedef enum {FALSE = 0,TRUE = 1

} BOOL;

#define MINSIZE 5#define STRLENGTH 25

0 1 2 3 4

5

MemAllocSList

3-1

Alexia-13

Sassia-1-

-10

Nicolas2-

-

1

Last3

n4

Empty0

First Data

Str

Next

Prev

typedef struct {char *Str;int Next, Prev;

} SData;

typedef struct {int First, Last, Empty, n;int MemAlloc;SData *Data;

} SList;

© ÉTS - GPA - GPA665 47

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (3/16)(3/16)

BOOL CreateList(SList *List)

BOOL CreateList(SList *List){BOOL Success;/* Ajustement des variables de contrôle */List->First = -1;List->Last = -1;List->n = 0;List->MemAlloc = 0;List->Data = NULL;

/* Réalise l'allocation dynamique du tableau d'enregistrements */Success = IncreaseMemory(List, MINSIZE);

return Success;}

2.2. Fonction de crFonction de crééationation1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 2 opeffectue en 2 opéérations :rations :

1.1. initialiser toutes les donninitialiser toutes les donnéées du tableau es du tableau (sans oublier la liste des vides)(sans oublier la liste des vides);;2.2. allouer lallouer l’’espace mespace méémoire nmoire néécessaire au tableau .cessaire au tableau .


2.2. ÉÉcriture finale du code en langage C :criture finale du code en langage C :

© ÉTS - GPA - GPA665 48

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (4/16)(4/16)3.3. Fonction de destruction de la liste Fonction de destruction de la liste (qui consiste (qui consiste àà liblibéérer toute mrer toute méémoire moire

rréésiduelle associsiduelle associéée e àà la liste, cla liste, c’’estest--àà--dire le tableau de donndire le tableau de donnéées)es)..void DestroyList(SList *List){int i;

List->First = -1;List->Last = -1;List->n = 0;List->MemAlloc = 0;

for (i = 0; i < List->MemAlloc; i++)free(List->Data[i].Str);

free(List->Data);}

© ÉTS - GPA - GPA665 49

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (5/16)(5/16)4.4. Augmentation de la taille du tableau de donnAugmentation de la taille du tableau de donnééeses

BOOL IncreaseMemory(SList *List, int nData){BOOL Success = TRUE;int OldMemAlloc = List->MemAlloc, i;

/* Réalise la nouvelle allocation dynamique du tableau d'enregistrements */List->MemAlloc = nData;if (List->Data = (SData*) realloc(List->Data, sizeof(SData) * List->MemAlloc)) {/* Réalise l'alloc. dyn. seulement pour les nouvelles chaînes de caractères */for (i = OldMemAlloc; (i < List->MemAlloc) && (Success); i++)if (!(List->Data[i].Str = (char*) malloc(sizeof(char) * STRLENGTH)))Success = FALSE;

/* Si il y a erreur d’allocation, on libère TOUTE la mémoire déjà allouée */if (!Success) {for (i -= 2; i >= 0; i--)free(List->Data[i].Str);

free(List->Data);List->MemAlloc = 0;

/* Sinon on initialise la nouvelle liste de vides */} elseDefineEmpty(List, OldMemAlloc);

/* Échec de la nouvelle allocation dynamique du tableau */} elseSuccess = FALSE;

return Success;}

© ÉTS - GPA - GPA665 50

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (6/16)(6/16)5.5. DDééfinition de la liste des videsfinition de la liste des vides

6.6. Fonction de comptageFonction de comptage

void DefineEmpty(SList* List, int iEmpty){int i, Order;

/* Défini le premier vide */List->Empty = iEmpty;/* Détermine la liste complète */for (i = iEmpty, Order = i+1; i < List->MemAlloc; i++) {List->Data[i].Next = Order;List->Data[i].Prev = -1;Order++;

}List->Data[List->MemAlloc - 1].Next = -1;

}

int Length(SList *List){return List->n;

}

© ÉTS - GPA - GPA665 51

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (6/16)(6/16)7.7. Fonction questionnant le TDA Fonction questionnant le TDA àà savoir ssavoir s’’il est videil est vide

8.8. Fonction retournant un Fonction retournant un éélléément en fonction de sa positionment en fonction de sa position

BOOL IsEmpty(SList *List){return (List->n == 0) ? TRUE : FALSE;

}

BOOL IsEmpty(SList *List)char* Retrieve(SList *List, int i){int Cur = List->First;

if ((i > 0) && (i First; i > 1; Cur = List->Data[Cur].Next, i--);return List->Data[Cur].Str;


}}

© ÉTS - GPA - GPA665 52

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (7/16)(7/16)9.9. Fonction dFonction d’’affichage de la liste affichage de la liste (avec choix d(avec choix d’’ordre de parcours)ordre de parcours)

void PrintList(SList *List, BOOL Forward){int Cur;

/* Affichage en ordre croissant */if (Forward) {Cur = List->First;while (Cur != -1) {printf("%s\n", List->Data[Cur].Str);Cur = List->Data[Cur].Next;

} /* Affichage en ordre décroissant */} else {Cur = List->Last;while (Cur != -1) {printf("%s\n", List->Data[Cur].Str);Cur = List->Data[Cur].Prev;

}}

}

© ÉTS - GPA - GPA665 53

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (8/16)(8/16)10.10. Fonction dFonction d’’insertion insertion (exemple : ajouter l(exemple : ajouter l’’enregistrement John)enregistrement John)

1.1. Description logique. Cette fonction sDescription logique. Cette fonction s’’effectue en 4 opeffectue en 4 opéérations :rations :1.1. augmenter la taille du tableau si elle est insuffisante;augmenter la taille du tableau si elle est insuffisante;

0 1 2 3 4

10

MemAllocSList

4-1

Alexia-12

Sassia13

Patrick24

Nicolas30

Karen

1

Last5

n5

Empty0

First Data

Str

Next

Prev

5 6 7 8 9

6-1

-7-1

-8-1

-9-1

--1-1

-

0 1 2 3 4

5

MemAllocSList

4-1

Alexia-12

Sassia13

Patrick24

Nicolas30

Karen

1

Last5

n-1

Empty0

First Data

Str

Next

Prev

© ÉTS - GPA - GPA665 54

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (9/16)(9/16)10.10. Fonction dFonction d’’insertion insertion (suite)(suite)

1.1. Description logique Description logique (suite)(suite)..2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans la liste rer dans la liste

(l(l’’enregistrement recherchenregistrement recherchéé doit possdoit possééder une valeur plus grand que celle der une valeur plus grand que celle àà insinséérer)rer);;

0 1 2 3 4

10

MemAllocSList

4-1

Alexia-12

Sassia13

Patrick24

Nicolas30

Karen

1

Last5

n5

Empty0

First Data

Str

Next

Prev

John3Cur

5 6 7 8 9

6-1

-7-1

-8-1

-9-1

--1-1

-

© ÉTS - GPA - GPA665 55


1.1. Description logique Description logique (suite)(suite)..3.3. copier les donncopier les donnéées;es;

0 1 2 3 4

10

MemAllocSList

4-1

Alexia-12

Sassia13

Patrick24

Nicolas30

Karen

1

Last5

n5

Empty0

First Data

Str

Next

Prev

3Cur

5 6 7 8 9

6-1

John7-1

-8-1

-9-1

--1-1

-

© ÉTS - GPA - GPA665 56


1.1. Description logique Description logique (suite)(suite)..4.4. ajuster les variables de rajuster les variables de rééfféérences.rences.

John0 1 2 3 4

10

MemAllocSList

5-1

Alexia-12

Sassia13

Patrick24

Nicolas35

Karen

1

Last6

n6

Empty0

First Data

Str

Next

Prev

5 6 7 8 9

40

7-1

-8-1

-9-1

--1-1

-

© ÉTS - GPA - GPA665 57



3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes ::1.1. augmenter la taille du tableau si elle est insuffisante;augmenter la taille du tableau si elle est insuffisante;

2.2. trouver la position de ltrouver la position de l’’enregistrement enregistrement àà insinséérer dans la liste;rer dans la liste;

3.3. copier les donncopier les donnéées;es;

BOOL Insert(SList *List, char NewValue[])

Si n = MemAllocIncreaseMemory de la liste jusqu’à MemAlloc*2

Cur = FirstTant que Cur != -1 et que la valeur de Cur < NewValueCur = le suivant de Cur

New = EmptyLa valeur à New = NewValue

© ÉTS - GPA - GPA665 58


3.3. DDééfinition des parties logiques par des finition des parties logiques par des pseudopseudo--codescodes (suite)(suite) : : 4.4. ajuster les variables de rajuster les variables de rééfféérences.rences.

Empty = l suivant de Emptyn = n + 1Si Cur = First /* Insertion au début de la liste */le suivant du New = Firstle précédent du New = -1Si n = 1 /* Ajuste le Last si c’est la 1ière insertion */Last = New

else /* Sinon, ajuste le Prev de l’ancien premier */le précédent du First = New;

First = NewSinonSi Cur = -1 /* Insertion à la fin */le suivant du New = Curle précédent du New = Lastle suivant du Last = NewLast = New

sinon /* Insertion entre 2 noeuds existants */le suivant du New = Curle précédent du New = le précédent du Curle suivant du précédent du New = Newle précédent du suivant du New = New

© ÉTS - GPA - GPA665 59


4.4. ÉÉcriture finale du code en langage Ccriture finale du code en langage CBOOL Insert(SList *List, char NewValue[]){BOOL Success;int Cur, New;

/* 1ière étape : Augmente la taille du tableau si il est plein */if (List->n == List->MemAlloc) {Success = IncreaseMemory(List, List->MemAlloc * 2);

}

/* Insertion dans la liste */if (Success) {/*** 2ième étape : Recherche le point d'insertion ***/Cur = List->First;while ((Cur != -1) && (strcmp(List->Data[Cur].Str, NewValue) < 0)) {Cur = List->Data[Cur].Next;

}/*** 3ième étape : Copie les données ***/New = List->Empty;List->Empty = List->Data[List->Empty].Next;strcpy(List->Data[New].Str, NewValue);List->n++;

...

© ÉTS - GPA - GPA665 60


4.4. ÉÉcriture finale du code criture finale du code (suite)(suite)...

/*** 4ième étape : Ajuste les variables de liens ***/if (Cur == List->First) { /* Insertion au début de la liste */List->Data[New].Next = List->First;List->Data[New].Prev = -1;List->First = New;if (List->n == 1) /* Ajuste le Last si c’est la 1ière insertion */List->Last = List->First;

else /* Sinon, ajuste le Prev de l’ancien premier */List->Data[List->Data[New].Next].Prev = New;

} else {if (Cur == -1) { /* Insertion à la fin */List->Data[New].Next = Cur;List->Data[New].Prev = List->Last;List->Data[List->Data[New].Prev].Next = New;List->Last = New;

} else { /* Insertion entre 2 noeuds existants */List->Data[New].Next = Cur;List->Data[New].Prev = List->Data[Cur].Prev;List->Data[List->Data[New].Prev].Next = New;List->Data[List->Data[New].Next].Prev = New;

} } }return Success;

}

© ÉTS - GPA - GPA665 61

Implémentation d’une liste avec allocation dynamique par bloc etImplémentation d’une liste avec allocation dynamique par bloc etorganisation par double chaînage (liste chaînée double dans un organisation par double chaînage (liste chaînée double dans un tableau dynamique) tableau dynamique) (16/16)(16/16)11.11. Fonction de suppressionFonction de suppression

ÀÀ faire comme travail libre faire comme travail libre (facultatif)(facultatif)

2 niveaux de difficult2 niveaux de difficultéés :s :1.1. sans gestion dynamique de la msans gestion dynamique de la méémoire moire (assez facile)(assez facile);;2.2. avec gestion dynamique de la mavec gestion dynamique de la méémoire moire (plus difficile)(plus difficile)

(attention, le ph(attention, le phéénomnomèène de dne de déécalage est encore prcalage est encore préésent ici)sent ici)..

© ÉTS - GPA - GPA665 62

Retour sur l’abstraction de la conception Retour sur l’abstraction de la conception (1/3)(1/3)

Tous les exemples prTous les exemples prééccéédents montrent bien que la dents montrent bien que la ddééfinition dfinition d’’un TDA spun TDA spéécifie lcifie l’’effet des opeffet des opéérations sans rations sans indiquer comment stocker les donnindiquer comment stocker les donnéées, ni comment es, ni comment implimpléémenter les opmenter les opéérations. rations.

CC’’est lest l’’abstraction du concept qui doit primer et non les abstraction du concept qui doit primer et non les techniques dtechniques d’’implimpléémentation.mentation.

Ainsi, lAinsi, l’’utilisateur du TDA nutilisateur du TDA n’’a pas a pas àà connaconnaîître les dtre les déétails tails dd’’implimpléémentation. Il utilise le TDA avec un niveau mentation. Il utilise le TDA avec un niveau dd’’abstraction tel quabstraction tel qu’’il a pratiquement lil a pratiquement l’’impression de impression de coder avec du coder avec du pseudopseudo--codecode..

© ÉTS - GPA - GPA665 63


Concepts et définition d’un TDA Implémentation de TDAListe chaînée

Interface

1 5 110x3C8 0010 0101 1011

0xE48 0x4FF 0x000

0x3C8 0xE48 0x4FF0x100

int Retrieve(SNode *Head, int i){SNode *Cur = Head;

if ((i > 0) && (i 1; i--); Cur = Cur->Next return Cur->Data; } else { return NULL; }}

Snode *Head;int Success;

CreateList(&Head);Insert(&Head, 1, &Success);Insert(&Head, 5, &Success);Insert(&Head, 11, &Success);

int ThirdRec;

ThirdRec = Retrieve(&Head,3);Troisième = Retrouve(3ième)

© ÉTS - GPA - GPA665 64


Voici un exemple de cet indVoici un exemple de cet indéépendance :pendance :ÉÉcriture dcriture d’’un un pseudopseudo--codecode dd’’une fonction une fonction PrintListPrintList qui affiche qui affiche les les ééllééments contenus dans un TDA de type liste ordonnments contenus dans un TDA de type liste ordonnééee

PrintList(L)for (i = 1; i

© ÉTS - GPA - GPA665 65

Quelques commentaires sur les implémentations Quelques commentaires sur les implémentations réaliséesréalisées

Les exemples vus prLes exemples vus prééccéédemment illustrent quelques demment illustrent quelques listes rlistes rééalisaliséées selon diffes selon difféérentes techniques. Il en existe rentes techniques. Il en existe beaucoup dbeaucoup d’’autre autre (comme par exemple une liste utilisant un (comme par exemple une liste utilisant un «« dummydummyheadhead nodenode »»).).

Les techniques choisies sont un exemple Les techniques choisies sont un exemple dd’’implimpléémentation parmi dmentation parmi d’’autre. autre.

CrCrééez vos propres TDA ou quelques services de TDA ez vos propres TDA ou quelques services de TDA ddééjjàà proposproposééss…… soyez imaginatifsoyez imaginatif…… vos efforts vos efforts àà cet cet effet augmenterons vos connaissances et vos habiliteffet augmenterons vos connaissances et vos habilitéés s plus que tout autre choseplus que tout autre chose…… tentez ltentez l’’expexpéérience!rience!

Documents

Définition des listes généralisées · Définition des listes généralisées (2/2) Les listes sont ... Les spécifications de ces 5 opérations sont les termes de contrat pour