Les listes linéaires PDF 2023/2024

Chapitre : Les listes linéaires Hager KAMMOUN BOUZAIENE 2023/2024  2 LSI 1 Définitions Opérations élémentaires Opérations élaborées Re...

Chapitre : Les listes linéaires Hager KAMMOUN BOUZAIENE 2023/2024  2 LSI 1 Définitions Opérations élémentaires Opérations élaborées Représentations physiques Contigüe Chaînée Les différentes variantes de la SD ll Représentation chaînée Matérialisation de la SD ll Représentation chaînée Représentation chaînée vs représentation contigüe pour la résolution de problème  3 LSI 1 Les LL : Définitions Une liste linéaire (LL) est la représentation informatique d’un ensemble fini, de taille variable et éventuellement nul, d’éléments de type T ▫ Cet ensemble est ordonné Mathématiquement, on peut présenter une LL en énumérant ses éléments dans l’ordre Pour la SD pile, les adjonctions (empiler), les suppressions (depiler), les recherches (dernier) sont faites par rapport au sommet On dit que la SD pile est une structure à un seul point d’accès Pour la SD file, les adjonctions (enfiler) sont faites par rapport à queue, les suppressions (défiler) et les recherches (premier) sont faites par rapport à tête On dit que la SD file est une structure à deux points d’accès Pour la SD LL, les adjonctions, les suppressions et les recherches ne sont pas faites systématiquement ni par rapport à tête, ni par rapport à queue  4 LSI 1 Les LL : Opérations élémentaires ou atomiques creerliste ▫ permet de créer une liste linéaire vide listevide ▫ permet de voir si la liste linéaire est vide ou non recherche Opération de création ▫ permet de voir si un élément appartient à une liste linéaire  le point de départ peut être fourni comme paramètre Opérations de consultation ajouter ou opération d’adjonction ▫ en tête : avant le premier ▫ en queue : après le dernier Opérations de modification ▫ quelque part au milieu au milieu supprimer un élément de la liste ▫ le premier élément ▫ le dernier élément ▫ quelque part au milieu visiter ▫ permet de visiter tous les éléments de la liste linéaire en effectuant pour chaque élément visité une action donnée (paramètre)  cette action est connue sous le nom de traversée  5 LSI 1 Les LL : Opérations élaborées inversersion ▫ permet d’inverser une liste linéaire  ll=(a, b, c, d)  llinv=(d, c, b, a) supprimer_tous ▫ permet de supprimer tous les éléments d’une liste donnée concaténation ▫ permet de concaténer deux listes données  ll1=(a, b, c, d)  ll2=(x, y, z, w, k) ▫ La concaténation de ll1 et ll2 dans l’ordre (ordre significatif) donne  ll=(a, b, c, d, x, y, z, w, k)  6 LSI 1 Représentation physique On distingue deux types de représentations physique ▫ Représentation contigüe ▫ Représentation chaînée  7 LSI 1 Les LL : représentation physique contigüe ll=(a, b, c, d) représentation abstraite ou mathématique 1 2 3 4 5 n ll a b c d représentation contigüe n est estimé a priori leff : longueur/taille effective 4 suppression ▫ supprimer le premier élément ou un élément quelque part au milieu ▫ elle exige des décalages à gauche pour récupérer la position devenue disponible  exemple : supprimer b 1 2 3 4 5 n a c d recherche leff : longueur/taille effective 3 ▫ recherche dans un tableau  on fait appel aux algorithmes connus  Soit recherche séquentielle soit recherche dichotomique  8 LSI 1 Les LL : représentation physique contiguë adjonction ▫ ajout avant le premier élément ou quelque part au milieu ▫ elle exige des décalages à droite  exemple : ajouter x après b 1 2 3 4 5 n a b x c d leff : longueur/taille effective 5 visiter ▫ balayer tous les éléments d’un tableau dans la partie garnie  La partie concernée : 1..leff  La partie non concernée : leff+1..n  9 LSI 1 Les LL : représentation physique chainée cle suivant a b c d premier dernier ll=(a, b, c, d) L’adjonction dans une liste linéaire (LL) matérialisée à l’aide d’une représentation chaînée n’exige pas de décalages contrairement à la représentation contiguë On peut dire que la représentation contiguë de la SD LL n’est pas recommandée à cause des décalages impliqués par les deux opérations fondamentales ajouter et supprimer  notamment pour les listes linéaires de taille plus au moins importante  10 LSI 1 Les différentes variantes de la SD LL Liste Linéaire unidirectionnelle avec un seul point d’entrée (premier) cle suivant premier Liste Linéaire unidirectionnelle avec deux points d’entrée (premier et dernier) cle suivant premier dernier Pour les deux variantes (1) et (2), la liste linéaire est unidirectionnelle À partir d’un élément donné on peut passer à son successeur Ceci est possible grâce au champ de chaînage suivant dans la variante (1), le premier élément est privilégié (accès direct) dans la variante (2), le premier et le dernier élément sont privilégiés (accès direct)  11 LSI 1 Les différentes variantes de la SD LL Liste Linéaire bidirectionnelle avec deux points d’entrée (premier et dernier) precedent cle suivant precedent cle suivant \ \ dernier À partir d’un élément donné, on peut passer soit à premier son successeur soit à son prédécesseur Liste Linéaire circulaire ou anneau Les notions de premier et dernier disparaissent cle suivant ces notions n’ont pas de sens dans un anneau Un anneau est doté uniquement d’un point d’entrée quelconque entrée Un anneau peut être unidirectionnel ou bidirectionnel  12 LSI 1  13 LSI 1 Matérialisation de la SD LL : variante  Partie interface : liste.h Partie implémentation : liste.c struct noeud { int cle ; cle suivant struct nœud * suivant ; }; premier dernier struct liste { struct nœud * premier ; struct nœud * dernier ; nœud };...  14 LSI 1 Matérialisation de la SD LL : variante  Solution1 : sous forme d’une procédure Solution 2 : sous forme d’une fonction void creer_liste(struct liste * ll) struct liste * creer_liste(void) { llpremier=NULL ; { lldernier=NULL ; struct liste *ll ; } ll=(struct liste*) malloc (size of(struct liste)) ; Environnement utilisateur llpremier=NULL; struct liste ll; lldernier=NULL; creer_liste(&ll); return ll; } struct liste *ll; Environnement utilisateur ll=(…) malloc(…); struct liste * ll; creer_liste(ll); ll=creer_liste(); La solution 2 est meilleure (plus facile) que la solution 1  15 LSI 1 Matérialisation de la SD LL tester la vacuité d’une liste linéaire tester la vacuité d’une liste linéaire Variante 1 Variante 2 unsigned liste_vide(struct liste *ll) unsigned liste_vide(struct liste*ll) { { return(llpremier==NULL) ; return((llpremier==NULL) && } (lldernier==NULL)); } ll premier dernier  16 LSI 1 Matérialisation de la SD LL opérations d’adjonction ou d’insertion insertion après un élément référencé par p void inserer_apres(int info, struct nœud *p) insérer après un élément référencé { struct nœud *q ; q=(struct nœud*) malloc(size of(struct nœud)) ; insérer avant un élément référencé qcle=info;  q suivant=psuivant ; insérer avant premier TD  psuivant=q ; insérer après dernier } p  q   info  17 LSI 1 Matérialisation de la SD LL insertion avant un élément référencé par p le problème : la liste est unidirectionnelle à void inserer_avant(int info, struct nœud*p) partir de p, on ne peut pas passer à son { prédécesseur struct nœud * q ; q=(struct nœud*) malloc(size of(struct nœud)) ; p info *q=*p;     3 p->cle=info ; p->suivant=q ; } Solution  18 LSI 1 Matérialisation de la SD LL opération de recherche dans une liste linéaire opération de recherche dans une liste linéaire Un problème de recherche à deux issues struct nœud * chercher(int info, struct nœud*p) ▫ succès référence non nulle { ▫ échec référence nulle while(p&&(p->cle!=info)) struct nœud *cherche(int info, struct nœud *p ) p=p->suivant ; elle rend une référence non nulle si info appartient à la liste à partir de l’élément référencé par p sinon elle rend une référence séquentielle dans un tableau ▫ Il s’agit d’adapter l’algorithme de return(p) ; recherche séquentielle au contexte d’une liste linéaire }  19 LSI 1 Pointeur sur une fonction : Rappel en C Il est parfois utile de passer une fonction comme paramètre d’une autre fonction ▫ Cette procédure permet en particulier d’utiliser une même fonction pour différents usages  Un mécanisme de pointeur est utilisé  Un pointeur sur une fonction correspond à l’adresse du début du code de cette fonction Un pointeur sur une fonction de prototype type fonction(type1, type2, …, typen) Est de type type (*) (type1, type2, …, typen)  20 LSI 1 Matérialisation de la SD LL opération de parcours ou visite Paramètres formels Cette opération permet de visiter tous les éléments d’une liste Paramètres non fonctionnels linéaire (ou les éléments à partir d’un point de départ) il s’agit d’un paramètre qui mémorise ▫ Pour chaque élément visité on lui applique un traitement une valeur (ordinaire, adresse) donné Paramètres fonctionnels ils mémorisent un comportement (ou Quels sont les paramètres formels nécessaires à l’opération de parcours ? un traitement) traduit par un sous- programme paramètre non fonctionnel indique le point de départ pour traverser la liste Les sous programmes qui admettent struct nœud *p des paramètres fonctionnels sont dits des sous-programmes d’ordre paramètre fonctionnel supérieur indique le traitement à effectuer sur les nœuds visités void(*oper)(struct nœud*) Oper est un pointeur sur une procédure exigeant un paramètre de type struct nœud *  21 LSI 1 Matérialisation de la SD LL Définition de la procédure parcours Utilisation de la procédure parcours À ne pas confondre ! Traitement afficher chaque élément Traitement incrémenter chaque void* oper(struct nœud *); visité élément visité Il s’agit d’une fonction appelée oper qui rend un pointeur sur n’importe quoi et qui exige un paramètre de type struct nœud* struct nœud * point_de_depart ; struct nœud * point_de_depart ; et void (* oper)(struct nœud *); oper est un pointeur sur une procédure. void afficher(struct nœud * q) void incrementer (struct nœud *q) { { void parcours(struct nœud*p,void(*oper)(struct nœud*)) printf (’’%u d\n ‘’, q->cle) ; q->cle++ ; { } } while(p) { parcours(point_de_depart, parcours(point_de_depart, (*oper)(p) ; p=p->suivant ; } } Pointeur sur un programme En c, le nom d’un sous-programme est considéré comme et non une activation un pointeur. Toute référence à (*oper) au sein de la P.E du (* oper) correspond au contenu pointé c’est-à- sous-programme parcours est une référence au paramètre dire le sous programme en question effectif correspond : c’est le principe d’indirection  22 LSI 1 Représentation contigüe/Représentation chaînée : matrice creuse Problème : proposer une structure de données permettant de matérialiser d’une façon efficace les matrices creuses en évitant de stocker les éléments nuls ▫ Trouver une représentation informatique des matrices creuses  une matrice creuse est une matrice comportant un nombre important d’éléments nuls (tend vers n2) ▫ La représentation souhaitée doit stocker uniquement les éléments non nuls 9 0 0 0 0 0 0 0 1 0 0 0 0 0 2 #define n 100 float m[n][n]; 3 0 4 0 0 0 0 0 0 0  23 LSI 1 Représentation contigüe/Représentation chaînée : matrice creuse 1 2 3 4 5 Solution Représentation contigüe pour les lignes Accès rapide ou directe à la ligne col info suivant Accès séquentiel à la colonne  Le tableau ligne comporte des Représentation chaînée éléments qui sont des listes pour les colonnes linéaires  listes linéaires  Chaque nœud de la liste linéaire comporte les champs suivants : col : colonne info : valeur m[i][col] suivant : successeur non nul relative à la ligne i  24 LSI 1 Représentation contigüe/Représentation chaînée : matrice creuse 1 2 3 4 5 La colonne appartenant à une ligne i est obtenue par recherche séquentielle au sein de la liste ligne[i] \ On a intérêt à trier les listes sur le champ colonne Traduction en c 1 9 \ #define n 100 struct element 4 1 \ { unsigned col ; float info ; struct element * suivant ; 5 2 \ }; struct element* ligne[n] ; 1 3 Une matrice creuse représentée ci- dessus peut être assimilée à une SD dotée des opérations suivantes Création d’une matrice creuse vide 3 4 \ ▫ tous les éléments sont à zéro Accès à un élément identifié par le couple (ligne :i, colonne : j) Modification d’un élément donné  25 LSI 1 Représentation contigüe/Représentation chaînée : matrice creuse Créer une matrice vide Accès à un élément de coordonnés (i,j) void creer(struct element * ligne[]) i désigne la ligne et j désigne la colonne { La réalisation de l’opération accès nécessite une unsigned i; recherche dans une liste linéaire triée : ligne[i] for(i=0, i