CM1 Listes Chainee
Télécharger le CM1 Listes Chainee en pdf
Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
Page 1 : INFORMATIQUE 3I . L E S L I S T E S C H A I N É E SEva Ansermin & Romuald Grignon v1.3
Page 2 : Un point sur l’informatique 32Eva ANSERMIN & Romuald GRIGNON• Sujets abordés dans la matière:• Algorithmie : listes chaînées, piles, files, arbres, …• UNIX et Script Shell• Organisation:• 6 CM algo + 2 CM Unix/Shell• TD sur 13 semaines Algo : 7 / Unix-Shell : 3 / Projet : 3• Evaluation : • 3 DS 2 x 90min + 1 x 120min• Moyenne des quiz qui compte pour 1 DS.• 1 Projet en fin de semestre• Moyenne = 0.7 max moyDS1, DS2, DS3, QUIZ, DS3 + 0.3 PROJET
Page 3 : Page de cours + Quiz Eva ANSERMIN & Romuald GRIGNON3• Des quiz auront lieu régulièrement à partir d’octobre en début de séance de TD, en ligne sur la page du cours : https://cours.cyu.fr/course/view.php?id=338• Vous trouverez aussi des support de cours, TD, quiz d’entrainement, archives de DS, liste des intervenants par groupe, et les modalités d’évaluation.• Inscrivez-vous sur ce site avec votre groupe pour accéder aux évaluations !
Page 4 : I. Rappels 4Eva ANSERMIN & Romuald GRIGNON
Page 5 : Pointeur et pseudo-code • Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !Adresse Valeur 11541158…5340……10 032……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;5Eva ANSERMIN & Romuald GRIGNON
Page 6 : Pointeur et pseudo-code Adresse Valeur 11541158…5340……10 032……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;6Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 7 : Pointeur et pseudo-code Adresse Valeur 1154???1158…5340……10 032……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;a7Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 8 : Pointeur et pseudo-code Adresse Valeur 1154???1158…5340……10 0320 NULL……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap18Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 9 : Pointeur et pseudo-code Adresse Valeur 115451158…5340……10 0320 NULL……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap19Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 10 : Pointeur et pseudo-code Adresse Valeur 115451158…5340……10 0321154……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap110Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 11 : Pointeur et pseudo-code Adresse Valeur 115451158…5340……10 0321154……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap1a=511Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 12 : Pointeur et pseudo-code Adresse Valeur 115451158…5340……10 0321154……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap1a=5p1=512Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 13 : Pointeur et pseudo-code Adresse Valeur 1154101158…5340……10 0321154……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap1a=5p1=513Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 14 : Pointeur et pseudo-code Adresse Valeur 1154101158…5340……10 0321154……22 222inta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;ap1a=5p1=5a=1014Eva ANSERMIN & Romuald GRIGNONEva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 15 : Pointeur et pseudo-code int maininta;int p1 = NULL;a= 5;p1 = &a;printf" a =d \n",a;printf"p1=d \n",p1;p1 = 10;printf" a =d \n",a;return 0;VARIABLE a : entierp1 : pointeur sur entier DEBUTa ← 5p1 ←adresse de aECRIRE«a=»+aECRIRE«p1 =»+p1p1 ← 10ECRIRE« a =»+aFIN15Eva ANSERMIN & Romuald GRIGNON• Un pointeur est :• Une variable dont la valeur est une adresse mémoire…• L’adresse mémoire d’une autre variable !
Page 16 : Les tableaux• Les valeurs d’un tableau sont à la suite dans la mémoire.• Lorsqu’un tableau est déclaré :• Un espace mémoire de la bonne taille est réservé.• Un pointeur constant portant le nom du tableau est créé. Il pointe sur la première case du tableau. VARIABLE tab5 : tableau d’entiersDEBUTtab - 1,3FINAdresse Valeur 115413000…………22 2201154tab0tab1tab2tab3tab4tab16Eva ANSERMIN & Romuald GRIGNON
Page 17 : Les tableaux : contraintes• Il est obligatoire de connaître la taille d’un tableau lors de sa déclaration.• Même lors d’une allocation dynamique, la taille de l’espace mémoire à allouer doit être donnée. • Solutions possibles :• Déclarer une taille de tableau suffisamment grande :Il faut être certain qu’on ne dépassera pas.Risque de mémoire « gâchée ».• Imposer une limite de taille à l’utilisateur Application limitée.• Utiliser une liste chaînée.17Eva ANSERMIN & Romuald GRIGNON
Page 18 : II. Listes chaînées : principe18Eva ANSERMIN & Romuald GRIGNON
Page 19 : Les listes chaînées• Une liste chaînée est un objet informatique permettant de stocker des éléments dans un ordre précis comme un tableau.• Contrairement à un tableau, les éléments d’une liste chaînée ne sont pas à la suite dans la mémoire. • Même lors d’une allocation dynamique, la taille de l’espace mémoire à allouer doit être donnée. • Un élément stocké dans une liste chaînée est toujours accompagné d’un pointeur indiquant où se trouve l’élément suivant de la liste dans la mémoire.Les éléments de la liste ne sont pas à la suite dans la mémoire mais on sait toujours où se trouve l’élément suivant grâce à un pointeur !19Eva ANSERMIN & Romuald GRIGNON
Page 20 : Constitution d’une liste chaînée20Eva ANSERMIN & Romuald GRIGNON• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante.
Page 21 : Constitution d’une liste chaînéeStructure Chainon :elmt : Elementsuivant : pointeur sur structure Chainon21Eva ANSERMIN & Romuald GRIGNON• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante.
Page 22 : Constitution d’une liste chaînéeStructure Chainon :elmt : Elementsuivant : pointeur sur structure ChainonStructure Chainon :elmt : entier suivant : pointeur sur structure Chainon22Eva ANSERMIN & Romuald GRIGNON• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante. • Elément de type entier
Page 23 : Constitution d’une liste chaînéeStructure Chainon :elmt : Elementsuivant : pointeur sur structure ChainonStructure Chainon :elmt : réel suivant : pointeur sur structure Chainon23Eva ANSERMIN & Romuald GRIGNON• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante. • Elément de type réel
Page 24 : Constitution d’une liste chaînéeStructure Chainon :elmt : Elementsuivant : pointeur sur structure ChainonStructure Chainon :elmt : Etudiant suivant : pointeur sur structure Chainon24Eva ANSERMIN & Romuald GRIGNON• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante. • Elément de type structure
Page 25 : Constitution d’une liste chaînée• Une liste chaînée est constituée de chaînons, une structure qui contient :• L’ élément à stocker entier, flottant, tableau de caractères etc...• Un pointeur vers l’occurrence suivante. • Exemple en C : Structure Chainon :elmt : Elementsuivant : pointeur sur structure Chainontypedef struct chainonint nombre;struct chainon suivant; Chainon;struct chainonint nombre;struct chainon suivant;;typedef struct chainon Chainon;OU25Eva ANSERMIN & Romuald GRIGNON
Page 26 : Listes chaînées : schéma elmChainonElément stocké entier, réel, structure, ...Pointeur sur Chainon suivant26Eva ANSERMIN & Romuald GRIGNON
Page 27 : Listes chaînées : schéma Chainonelmelmelmelm….27Eva ANSERMIN & Romuald GRIGNON
Page 28 : Listes chaînées : schéma Chainonelmelmelmelm….Pointeur sur le premier Chainon de la liste Tête28Eva ANSERMIN & Romuald GRIGNON
Page 29 : Listes chaînées : schéma Chainonelmelmelmelm….Pointeur sur le premier Chainon de la liste TêteNULLLe dernier Chainon pointe sur NULL29Eva ANSERMIN & Romuald GRIGNON
Page 30 : Listes chaînées en mémoire : exempleAdresse décimaleValeur décimale1 0001152……1152101156…11605344……534425348…535210 016……10 0162510020…10 02422 222……22 21610322 220…22 2240 NULLpliste10225103NULLpliste30Eva ANSERMIN & Romuald GRIGNON
Page 31 : II. Listes chaînées : opérations31Eva ANSERMIN & Romuald GRIGNON
Page 32 : Listes chaînées : construction1. Initialisation de la chaîne : initialisation pointeur sur Chainon NULL plisteNULL32Eva ANSERMIN & Romuald GRIGNON
Page 33 : Listes chaînées : construction1. Initialisation de la chaîne : initialisation pointeur sur Chainon NULL2. Création d’un Chainon plisteNULLNULL1033Eva ANSERMIN & Romuald GRIGNON
Page 34 : Listes chaînées : construction1. Initialisation de la chaîne : initialisation pointeur sur Chainon NULL2. Création d’un Chainon3. Faire pointer le pointeur sur le Chainon créé plisteNULL1034Eva ANSERMIN & Romuald GRIGNON
Page 35 : Liste chaînée : construction1. Initialisation de la chaîne : initialisation pointeur sur Chainon NULL2. Création d’un Chainon Chainon creationChainon//déclaration du ChainonChainon c = mallocsizeofChainon;ifc==NULLexit1;printf"Entrer la valeur : ";if scanf"d", &c-elmt != 1 exit2;c-suivant=NULL;return c;Remarque : nous verrons plus tard l’intérêt d’utiliser le malloc35Eva ANSERMIN & Romuald GRIGNON
Page 36 : Listes chaînées : construction1. Initialisation de la chaîne : initialisation pointeur sur Chainon NULL2. Création d’un Chainon3. Pointer le pointeur sur le Chainon créé Chainon creationChainon//déclaration du ChainonChainon c = mallocsizeofChainon;ifc==NULLexit1;printf"Entrer la valeur : ";if scanf"d", &c-elmt != 1 exit2;c-suivant=NULL;return c;int mainChainon pliste = NULL; //initialisationpListe = creationChainon;…return 0;36Eva ANSERMIN & Romuald GRIGNON
Page 37 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.pliste10225103NULLp1 ←plistep1 = pliste;37Eva ANSERMIN & Romuald GRIGNON
Page 38 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.10225103NULLplistep1 ←plistep1 = pliste;38Eva ANSERMIN & Romuald GRIGNON
Page 39 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.• On passe au Chainon suivant et on traite son élément10225103NULLplistep1 ←suivantp1p1 = p1 - suivant; 39Eva ANSERMIN & Romuald GRIGNON
Page 40 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.• On passe au Chainon suivant et on traite son élément.10225103NULLplistep1 ←suivantp1p1 = p1 - suivant; 40Eva ANSERMIN & Romuald GRIGNON
Page 41 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.• On passe au Chainon suivant et on traite son élément.• …10225103NULLplistep1 ←suivantp1p1 = p1 - suivant; 41Eva ANSERMIN & Romuald GRIGNON
Page 42 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.• On passe au Chainon suivant et on traite son élément.• …• Jusqu’à arriver au pointeur NULL10225103NULLplistep1 ←suivantp1p1 = p1 - suivant; 42Eva ANSERMIN & Romuald GRIGNON
Page 43 : Listes chaînées : parcours• Pour parcourir une liste chaînée :• On déclare un pointeur = pliste. Il pointe donc sur le premier élément.• On traite le premier élément.• On passe au Chainon suivant et on traite son élément.• …• Jusqu’à arriver au pointeur NULL10225103NULLplisteOn ne peut pas utiliser d’indice comme pour les tableaux !!p1 ←suivantp1p1 = p1 - suivant; 43Eva ANSERMIN & Romuald GRIGNON
Page 44 : Listes chaînées : parcours10225103NULLplisteprocédure traiterListepliste : pointeur sur ChainonVARIABLE p1 : pointeur sur ChainonDEBUTp1 ←pliste;TANT QUE p1 NULL FAIREtraiter elementp1p1 ← suivantp1FIN TANT QUEp1 ←suivantp144Eva ANSERMIN & Romuald GRIGNON
Page 45 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînepliste10512NULL45Eva ANSERMIN & Romuald GRIGNON
Page 46 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînea.Création du Chainonb. Parcours de la liste jusqu’au dernier Chainonpliste10512NULL7NULLp1 ←suivantp146Eva ANSERMIN & Romuald GRIGNON
Page 47 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînea.Création du Chainonb. Parcours de la liste jusqu’au dernier Chainonpliste10512NULL7NULLp1 ←suivantp147Eva ANSERMIN & Romuald GRIGNON
Page 48 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînea.Création du Chainonb. Parcours de la liste jusqu’au dernier Chainonpliste10512NULL7NULLp1 ←suivantp148Eva ANSERMIN & Romuald GRIGNON
Page 49 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînea.Création du Chainonb. Parcours de la liste jusqu’au dernier Chainonc.Faire pointer le suivant du dernier Chainon sur le nouveau. pliste105127NULLp149Eva ANSERMIN & Romuald GRIGNON
Page 50 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaînea.Création du Chainonb. Parcours de la liste jusqu’au dernier Chainonc.Faire pointer le suivant du dernier Chainon sur le nouveau. fonction insertFinpliste : pointeur sur Chainon : pointeur sur ChainonVARIABLE nouveau, p1 : pointeur sur ChainonDEBUTnouveau ←creationChainon // etape ap1 ←plisteTANT QUEsuivantp1 NULL FAIRE// étape bp1 ← suivantp1FIN TANT QUEsuivantp1 ← nouveau// étape c // par convention on retourne le début de liste// même si il n’a pas été modifiéRETOURNER plisteFINComplexitétemporelleON50Eva ANSERMIN & Romuald GRIGNON
Page 51 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaînea.Création Chainonpliste10512NULLNULL751Eva ANSERMIN & Romuald GRIGNON
Page 52 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaînea.Création Chainonb. Faire pointer le suivant du nouveau sur la chaîne pliste10512NULL752Eva ANSERMIN & Romuald GRIGNON
Page 53 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaînea.Création Chainonb. Faire pointer le suivant du nouveau sur la chaînec.Faire pointer pliste sur le nouveau Chainon 10512NULL7pliste53Eva ANSERMIN & Romuald GRIGNON
Page 54 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîneAttention à l’ordre !pliste10512NULLNULL754Eva ANSERMIN & Romuald GRIGNON
Page 55 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîneAttention à l’ordre !10512NULLNULL7Le reste de la liste est perdu !plisteChaîne infinie55Eva ANSERMIN & Romuald GRIGNON
Page 56 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaînea.Création Chainonb. Faire pointer le suivant du nouveau sur la chaînec.Faire pointer pliste sur le nouveau Chainon Fonction insertDebut pliste : pointeur sur Chainon : pointeur sur ChainonVARIABLEnouveau : pointeur sur ChainonDEBUTnouveau ←creationChainon // étape asuivantnouveau ← pliste// étape bpliste ← nouveau // étape c RETOURNER plisteFINLe pointeur sur le début de la liste ayant été modifié, il faut le retourner !!ComplexitétemporelleO156Eva ANSERMIN & Romuald GRIGNON
Page 57 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaînea.Création du nouveau Chainon10512NULLplisteNULLNULL757Eva ANSERMIN & Romuald GRIGNON
Page 58 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaînea.Création du nouveau Chainonb. Parcourir la liste jusqu’à Chainon devant précéder le nouveau10512NULLpliste7p1NULL58Eva ANSERMIN & Romuald GRIGNON
Page 59 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaînea.Création du nouveau Chainonb. Parcourir la liste jusqu’à Chainon devant précéder le nouveauc.Faire pointer le suivant du nouveau sur le suivant de p110512NULLpliste7p159Eva ANSERMIN & Romuald GRIGNON
Page 60 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaînea.Création du nouveau Chainonb. Parcourir la liste jusqu’à Chainon devant précéder le nouveauc.Faire pointer le suivant du nouveau sur le suivant de p1d. Faire pointer le suivant de p1 sur le nouveau 10512NULLpliste7p160Eva ANSERMIN & Romuald GRIGNON
Page 61 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaîneAttention à l’ordre !10512NULLpliste7p1NULL61Eva ANSERMIN & Romuald GRIGNON
Page 62 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaîneAttention à l’ordre !10512NULLpliste7p1NULLReste de la liste perdueChaîne infinie62Eva ANSERMIN & Romuald GRIGNON
Page 63 : Listes chaînées : ajout de Chainon 1. Ajout d’un Chainon en fin de chaîne2. Ajout d’un Chainon en début de chaîne3. Ajout d’un Chainon en milieu de chaînea.Parcourir la liste jusqu’à Chainon devant précéder le nouveaub. Création du nouveau Chainonc.Faire pointer le suivant du nouveau sur le suivant de p1d. Faire pointer le suivant de p1 sur le nouveau 63Eva ANSERMIN & Romuald GRIGNON
Page 64 : Listes chaînées : ajout de Chainon a.Parcourir la liste jusqu’à Chainon devant précéder le nouveaub.Création du nouveau Chainonc.Faire pointer le suivant du nouveau sur le suivant de p1d.Faire pointer le suivant de p1 sur le nouveau fonction insertPos pliste : pointeur sur Chainon, pos : entier : pointeur sur ChainonVARIABLEnouveau, p1 : pointeurs sur Chainoni : entier DEBUTSI pos EST EGAL A 0 OU pliste EST EGAL A NULL ALORS // insertion à l’indice 0pliste ←insertDebutplisteSINONp1 ← plistePOUR i DE 0 à pos FAIRE// étape aSI p1 EST EGAL A NULL ALORSERREUR// pos nombre de chainonsSINONp1 ←suivantp1FIN SI FIN POURnouveau ← creationChainon // étape bsuivantnouveau ← suivantp1// étape csuivantp1 ← nouveau // étape dFIN SIRETOURNER plisteFIN64Eva ANSERMIN & Romuald GRIGNON
Page 65 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaîne10225103NULLpliste65Eva ANSERMIN & Romuald GRIGNON
Page 66 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaînea.Initialiser un pointeur sur le premier chaînon10225103NULLplistep166Eva ANSERMIN & Romuald GRIGNON
Page 67 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaînea.Initialiser un pointeur sur le premier chaînonb. Faire pointer pliste sur le suivant10225103NULLpliste ← suivantplistep167Eva ANSERMIN & Romuald GRIGNON
Page 68 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaînea.Initialiser un pointeur sur le premier chaînonb. Faire pointer pliste sur le suivantc.Libérer le Chainon à supprimer 10225103NULLplistep110p168Eva ANSERMIN & Romuald GRIGNON
Page 69 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaînea.Initialiser un pointeur sur le premier chaînonb. Faire pointer pliste sur le suivantc.Libérer le Chainon à supprimer 10225103NULLplistep110p1•Libérer la mémoire allouée au Chainon à supprimer permet d’éviter les fuites mémoires RAM. 69Eva ANSERMIN & Romuald GRIGNON
Page 70 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaînea.Initialiser un pointeur sur le premier chaînonb. Faire pointer pliste sur le suivantc.Libérer le Chainon à supprimer Chainon suppDebutChainon plisteChainon p1;// on vérifie si la liste contient au moins un Chainonifpliste==NULLexit1;p1=pliste; // étape apliste=p1-suivant; // étape bfreep1; // étape c : ‘libérerp1’ en pseudo-codereturn pliste;70Eva ANSERMIN & Romuald GRIGNON
Page 71 : Listes chaînées : suppression de Chainon1. Suppression d’un Chainon en début de chaîne2. Exercice : suppression d’un Chainon en milieu de chaîne10225103NULLpliste71Eva ANSERMIN & Romuald GRIGNON
Page 72 : III. Listes doublement chaînées72Eva ANSERMIN & Romuald GRIGNON
Page 73 : Listes doublement chaînées• Les listes que nous venons d’étudier sont dites simplement chaînées.• On peut également construire des listes doublement chaînées.10225103NULL10225103NULLNULL73Eva ANSERMIN & Romuald GRIGNON
Page 74 : Listes doublement chaînées• Les Chainons des listes doublement chaînées possèdent deux pointeurs : l’un indiquant le Chainon suivant, l’autre indiquant le précédent.• Ces chaînes sont plus compliquées à implémenter mais permettent de parcourir la liste dans les deux sens. 10225103NULLNULLStructure Chainon :elmt : Elementsuivant : pointeur sur structure Chainonprecedent : pointeur sur structure Chainon74Eva ANSERMIN & Romuald GRIGNON
Page 75 : Listes doublement chaînées• Insertion dans une liste doublement chaînée : NULLNULL1010138NULLNULLnouveau75Eva ANSERMIN & Romuald GRIGNON
Page 76 : Listes doublement chaînées• Insertion dans une liste doublement chaînée : NULLNULL1010138p1precedentnouveau ←p1suivantnouveau ←suivantp1nouveau76Eva ANSERMIN & Romuald GRIGNON
Page 77 : Listes doublement chaînées• Insertion dans une liste doublement chaînée : NULLNULL1010138p1nouveauprecedentsuivantp1 ← nouveau77Eva ANSERMIN & Romuald GRIGNON
Page 78 : Listes doublement chaînées• Insertion dans une liste doublement chaînée : NULLNULL1010138p1nouveausuivantp1 ← nouveau;78Eva ANSERMIN & Romuald GRIGNON
Page 79 : IV. Listes chaînées ou tableaux ? 79Eva ANSERMIN & Romuald GRIGNON
Page 80 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’éléments Fixe Illimité et non fixé80Eva ANSERMIN & Romuald GRIGNON
Page 81 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’éléments Fixe Illimité et non fixéDonnées contiguësOuiNon81Eva ANSERMIN & Romuald GRIGNON
Page 82 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élémentsFixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :82Eva ANSERMIN & Romuald GRIGNON
Page 83 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élément Fixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :Nécessite l’espace pour les éléments + un pointeurChaque élément de la liste a un pointeur ou plus associé.83Eva ANSERMIN & Romuald GRIGNON
Page 84 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élément Fixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :Nécessite l’espace pour les éléments + un pointeurChaque élément de la liste a un pointeur ou plus associé.Complexité temporelle : Ajout/suppression d’un élément84Eva ANSERMIN & Romuald GRIGNON
Page 85 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élément Fixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :Nécessite l’espace pour les éléments + un pointeurChaque élément de la liste a un pointeur ou plus associé.Complexité temporelle : Ajout/suppression d’un élémentDécalage de tous les éléments OnO1 en bout de chaîneOn sinonAccès à un élément85Eva ANSERMIN & Romuald GRIGNON
Page 86 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élément Fixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :Nécessite l’espace pour les éléments + un pointeurChaque élément de la liste a un pointeur ou plus associé.Complexité temporelle : Ajout/suppression d’un élémentDécalage de tous les éléments OnO1 en bout de chaîneOn sinonAccès à un élémentAccès direct O1O1 en bout de chaîneOn sinon86Eva ANSERMIN & Romuald GRIGNON
Page 87 : Comparaison liste chaînée/tableauTableauListe chaînéeNombre d’élément Fixe Illimité et non fixéDonnées contiguësOuiNonComplexité spatiale :Nécessite l’espace pour les éléments + un pointeurChaque élément de la liste a un pointeur ou plus associé.Complexité temporelle : Ajout/suppression d’un élémentDécalage de tous les éléments OnO1 en bouts de chaîneOn sinonAccès à un élémentAccès direct O1O1 en bouts de chaîneOn sinonLes listes chaînées ne sont pas toujours la meilleure solution !87Eva ANSERMIN & Romuald GRIGNON
Page 88 : Pour résumer• Une liste chaînée est constituée d’éléments et de pointeurs associés indiquant l’emplacement mémoire de l’élément suivant et/ou précédent.• Il faut donc bien gérer les structures et les pointeurs !!• Ce principe permet à la liste chaînée de ne pas avoir un nombre fixé d’éléments, contrairement au tableau.• La liste chaînée simplifie également certaines opérations par rapport au tableau. Elle n’est cependant pas toujours la meilleure solution.• Le principe des listes chaînées est à la base de nombreux autres objets informatiques … et à la base de votre programme d’algorithmie de deuxième année !88Eva ANSERMIN & Romuald GRIGNON
Pages : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88