CM2 Pile File
Télécharger le CM2 Pile File 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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
Page 1 : INFORMATIQUE 3I I . L E S F I L E S E T L E S P I L E SEva ANSERMIN & Romuald GRIGNONv1.1
Page 2 : Rappel et objectifs•Nous avons vu au cours dernier les listes chaînées. •Les listes chaînées permettent d’ajouter/ de supprimer des éléments n’importe où dans la liste.•Les piles et les files sont des objets informatiques qui permettent d’ajouter/ supprimer des éléments dans une liste en répondant à des règles plus spécifiques que les listes chaînées.pliste10225103NULLEva ANSERMIN Romuald GRIGNON2
Page 3 : I. PilesEva ANSERMIN Romuald GRIGNON3
Page 4 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés » :•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile •On l’appelle aussi LIFO : « last in, first out »•Pensez à une pile d’assiettes !Eva ANSERMIN Romuald GRIGNON4
Page 5 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Exemple d’une pile d’entiers : 2158120Eva ANSERMIN Romuald GRIGNON5
Page 6 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Ajout d’un nouvel élément : empilage215812033Eva ANSERMIN Romuald GRIGNON6
Page 7 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Empilage : le nouvel élément va au sommet de la pile 215812033Eva ANSERMIN Romuald GRIGNON7
Page 8 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Suppression de deux éléments : dépilage 215812033Eva ANSERMIN Romuald GRIGNON8
Page 9 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Dépilage de deux éléments :215812033Eva ANSERMIN Romuald GRIGNON9
Page 10 : Piles : principe•Une pile est une liste d’éléments qui sont « empilés »:•Un élément est toujours ajouté en haut de la pile •Un élément est toujours retiré en haut de la pile•Dépilage de deux éléments :2158120Eva ANSERMIN Romuald GRIGNON10
Page 11 : Piles : utilisation• Les piles sont très utilisées en informatique. On en trouve notamment:Pour permettre des retours en arrière à l’utilisateur : oL’action « undo » ctrl+z oRetour arrière dans un navigateur web Pour la gestion des appels de fonctions récursives non-terminaleDans les processeurs pour gérer, entre autre, l’appel à des fonctions quelconques. Et également pour simuler des problèmes mathématiques ou de la vie réelle! Eva ANSERMIN Romuald GRIGNON11
Page 12 : Piles : Implémentation d’une pile •Une pile peut être implémentée de deux manières:•A l’aide d’un tableau pile statique•A l’aide d’une liste chaînée pile dynamique•Pourquoi utiliser l’un ou l’autre ? 1022510310225103NULLEva ANSERMIN Romuald GRIGNON12
Page 13 : Piles : Implémentation statique•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. Structure PileStat :tabPile : tableau d’Element de taille ‘taille’ constantetaille : entier // taille du tableautete :entier // indice indiquant le haut de la pile Structure PileStat :tabPile : pointeur sur Element // si allocation dynamiquetaille : entier // taille du tableautete :entier // indice indiquant le haut de la pile OUEva ANSERMIN Romuald GRIGNON13
Page 14 : Piles : Implémentation statique•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •ExempleIci tabPile est de taille tete = 10225103/Eva ANSERMIN Romuald GRIGNON14
Page 15 : Piles : Implémentation statique•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •ExempleIci tabPile est de taille 7tete = 310225103???teteEva ANSERMIN Romuald GRIGNON15
Page 16 : Piles : Implémentation statique•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •ExempleIci tabPile est de taille 7tete = 3102251035516147teteRemarque : les cases situées après tête ne sont pas vides, mais on ne s’y intéresse pasEva ANSERMIN Romuald GRIGNON16
Page 17 : Piles : Implémentation statique•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •Dépiler: 102251035516147teteEva ANSERMIN Romuald GRIGNON17
Page 18 : Piles : Implémentation statique102251035516147teteval ← tabPiletetetete - tete-1retourner val•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •Dépiler: Eva ANSERMIN Romuald GRIGNON18
Page 19 : Piles : Implémentation statique102251035516147tete•Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •Empiler : Ajouter 40 Eva ANSERMIN Romuald GRIGNON19
Page 20 : •Une pile implémentée en statique tableau est une structure possédant trois variables :•Le tableau tabPile permettant de stocker les éléments de la pile. •La taille maximale N du tableau•Un entier tete indiquant l’indice du haut de la pile remplissage. •Empiler : Ajouter 40 Piles : Implémentation statiquetete ←tete+1tabPiletete ← 40tete10225405516147Eva ANSERMIN Romuald GRIGNON20
Page 21 : Piles : Implémentation statique•Initialisation de la pile statique : FONCTION creationPileStat: PileStatVARIABLE pile: PileStatDEBUTtetepile ← ???RETOURNER pileFIN Eva ANSERMIN Romuald GRIGNON21
Page 22 : Piles : Implémentation statique•Initialisation de la pile statique : 10225405516147tabPileteteFONCTION creationPileStat: PileStatVARIABLE pile: PileStatDEBUTtetepile ← -1 // la pile est videRETOURNER pileFIN Eva ANSERMIN Romuald GRIGNON22
Page 23 : Piles : Implémentation statique•Vérification de l’intégrité de la structure PileStat : •A chaque fois que nous allons utiliser une structure de type PileStat dans une fonction, il faudra s’assurer qu’elle n’a pas été corrompue : FONCTION verificationPileStatpile : pointeur sur PileStat : entierVARIABLEresult ← 0 : entier// resultat 0 signifie OKDEBUTSI ??? ALORSresult ← -1// données d’entrées invalidesSINON SI ??? ALORS result ← -2// la structure est corrompueFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON23
Page 24 : Piles : Implémentation statique•Vérification de l’intégrité de la structure PileStat : •A chaque fois que nous allons utiliser une structure de type PileStat dans une fonction, il faudra s’assurer qu’elle n’a pas été corrompue : FONCTION verificationPileStatpile : pointeur sur PileStat : entierVARIABLEresult ← 0 : entier// resultat 0 signifie OKDEBUTSI pile EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesSINON SI ??? ALORS result ← -2// la structure est corrompueFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON24
Page 25 : Piles : Implémentation statique•Vérification de l’intégrité de la structure PileStat : •A chaque fois que nous allons utiliser une structure de type PileStat dans une fonction, il faudra s’assurer qu’elle n’a pas été corrompue : FONCTION verificationPileStatpile : pointeur sur PileStat : entierVARIABLEresult ← 0 : entier// resultat 0 signifie OKDEBUTSI pile EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesSINON SI taillepile EST INF. OU EGAL A 0OU ??? ALORS result ← -2// la structure est corrompueFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON25
Page 26 : Piles : Implémentation statique•Vérification de l’intégrité de la structure PileStat : •A chaque fois que nous allons utiliser une structure de type PileStat dans une fonction, il faudra s’assurer qu’elle n’a pas été corrompue : FONCTION verificationPileStatpile : pointeur sur PileStat : entierVARIABLEresult ← 0 : entier// resultat 0 signifie OKDEBUTSI pile EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesSINON SI taillepile EST INF. OU EGAL A 0OU tetepile EST INF. STRICT. A -1OU ??? ALORS result ← -2// la structure est corrompueFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON26
Page 27 : Piles : Implémentation statique•Vérification de l’intégrité de la structure PileStat : •A chaque fois que nous allons utiliser une structure de type PileStat dans une fonction, il faudra s’assurer qu’elle n’a pas été corrompue : FONCTION verificationPileStatpile : pointeur sur PileStat : entierVARIABLEresult ← 0 : entier// resultat 0 signifie OKDEBUTSI pile EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesSINON SI taillepile EST INF. OU EGAL A 0OU tetepile EST INF. STRICT. A -1OU tetepile EST SUP. STRICT. A taillepile-1 ALORS result ← -2// la structure est corrompueFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON27
Page 28 : Piles : Implémentation statique•Empilage : tete10225405516147Eva ANSERMIN Romuald GRIGNON28
Page 29 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← ???SI ??? ALORS SI ??? ALORSresult ← 1SINON tetepile ←???tabPilepiletete ←???FIN SIFIN SIRETOURNER resultFIN tete10225405516147Eva ANSERMIN Romuald GRIGNON29
Page 30 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI ??? ALORS SI ??? ALORSresult ← 1SINON tetepile ←???tabPilepiletete ←???FIN SIFIN SIRETOURNER resultFIN tete10225405516147Eva ANSERMIN Romuald GRIGNON30
Page 31 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI result EST EGAL A 0 ALORS SI ??? ALORSresult ← 1SINON tetepile ←???tabPilepiletete ←???FIN SIFIN SIRETOURNER resultFIN tete10225405516147Eva ANSERMIN Romuald GRIGNON31
Page 32 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI result EST EGAL A 0 ALORS SI tetepile EST EGAL A taillepile-1 ALORSresult ← 1// la liste est déjà pleineSINON tetepile ←???tabPilepiletete ←???FIN SIFIN SIRETOURNER resultFIN tete10225405516147Eva ANSERMIN Romuald GRIGNON32
Page 33 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI result EST EGAL A 0 ALORS SI tetepile EST EGAL A taillepile-1 ALORSresult ← 1// la liste est déjà pleineSINON tetepile ←tetepile + 1 // décalage de la tête tabPilepiletete ←???FIN SIFIN SIRETOURNER resultFIN tete10225405516147Eva ANSERMIN Romuald GRIGNON33
Page 34 : Piles : Implémentation statique•Empilage : FONCTION empilagePileStatpile : pointeur sur PileStat, elmt : Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI result EST EGAL A 0 ALORS SI tetepile EST EGAL A taillepile-1 ALORSresult ← 1// la liste est déjà pleineSINON tetepile ←tetepile + 1 // décalage de la tête tabPilepiletete ←elmt// stockage de l’élementFIN SIFIN SIRETOURNER resultFIN 1022540’elmt’16147teteEva ANSERMIN Romuald GRIGNON34
Page 35 : Piles : Implémentation statique•Dépilage : 10225405516147teteEva ANSERMIN Romuald GRIGNON35
Page 36 : Piles : Implémentation statique•Dépilage : FONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI ??? ALORSresult ← -1// données d’entrées invalidesFIN SISI ??? ALORS SI ??? ALORSresult ← 1SINON pelmt ← ??? tetepile ←???FIN SIFIN SIRETOURNER resultFIN 10225405516147teteEva ANSERMIN Romuald GRIGNON36
Page 37 : Piles : Implémentation statique•Dépilage : 10225405516147teteFONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI pelmt EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesFIN SISI ??? ALORS SI ??? ALORSresult ← 1SINON pelmt ← ??? tetepile ←???FIN SIFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON37
Page 38 : Piles : Implémentation statique•Dépilage : 10225405516147teteFONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI pelmt EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesFIN SISI result EST EGAL A 0 ALORS SI ??? ALORSresult ← 1SINON pelmt ← ??? tetepile ←???FIN SIFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON38
Page 39 : Piles : Implémentation statique•Dépilage : 10225405516147teteFONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI pelmt EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesFIN SISI result EST EGAL A 0 ALORS SI tetepile EST EGAL A -1 ALORSresult ← 1// la liste est déjà videSINON pelmt ← ??? tetepile ←???FIN SIFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON39
Page 40 : Piles : Implémentation statique•Dépilage : 10225405516147teteFONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI pelmt EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesFIN SISI result EST EGAL A 0 ALORS SI tetepile EST EGAL A -1 ALORSresult ← 1// la liste est déjà videSINON pelmt ← tabPilepiletete // récupération élementtetepile ←???FIN SIFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON40
Page 41 : Piles : Implémentation statique•Dépilage : 10225405516147teteFONCTION depilagePileStatpile : pointeur sur PileStat, pelmt : pointeur sur Element : entierVARIABLEresult ← 0 : entier// résultat de l’empilage 0 signifie OK DEBUTresult ← verificationPileStatpileSI pelmt EST EGAL A NULL ALORSresult ← -1// données d’entrées invalidesFIN SISI result EST EGAL A 0 ALORS SI tetepile EST EGAL A -1 ALORSresult ← 1// la liste est déjà videSINON pelmt ← tabPilepiletete // récupération élementtetepile ← tetepile - 1// décalage de la tête FIN SIFIN SIRETOURNER resultFIN Eva ANSERMIN Romuald GRIGNON41
Page 42 : Piles : Implémentation dynamique •La pile dynamique est une liste chaînée : 10225103NULLQuel maillon est la tête de la pile? Eva ANSERMIN Romuald GRIGNON42
Page 43 : Piles : Implémentation dynamique •La pile dynamique est une liste chaînée :•La tête de la pile est un pointeur indiquant le premier chaînon de la liste chaînée. 10225103NULLteteEva ANSERMIN Romuald GRIGNON43
Page 44 : Piles : Implémentation dynamique •La pile dynamique est une liste chaînée :10225103NULLteteStructure Chainon :elmt : Elementsuivant : pointeur sur structure ChainonFonction creationPileDyn: pointeur sur ChainonVARIABLEtete : pointeur sur ChainonDEBUTtete - NULL // pas encore d’elementRETOURNER teteFINEva ANSERMIN Romuald GRIGNON44
Page 45 : Piles : Implémentation dynamique •A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Empilage : tete10512NULLNULL7Eva ANSERMIN Romuald GRIGNON45
Page 46 : Piles : Implémentation dynamique •A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Empilage : ajout d’un Chainon en début de liste insertDebuttete10512NULLNULL7Eva ANSERMIN Romuald GRIGNON46
Page 47 : Piles : Implémentation dynamique •A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Empilage : ajout d’un Chainon en début de liste insertDebut.2.Dépilage : 10225103NULLplisteEva ANSERMIN Romuald GRIGNON47
Page 48 : Piles : Implémentation dynamique •A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Empilage : ajout d’un Chainon en début de liste insertDebut.2.Dépilage : suppression d’un Chainon en début de liste suppDebut et on récupère de la valeur de ce chaînon.10225103NULLtetep110Eva ANSERMIN Romuald GRIGNON48
Page 49 : Piles : Implémentation dynamique •A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Empilage : ajout d’un Chainon en début de liste insertDebut.2.Dépilage : suppression d’un Chainon en début de liste suppDebut et on récupère de la valeur de ce chaînon.Une pile dynamique est une liste chaînée dont les éléments ne peuvent être ajoutés/retirés qu’en début de chaîne.Eva ANSERMIN Romuald GRIGNON49
Page 50 : II. FilesEva ANSERMIN Romuald GRIGNON50
Page 51 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •On l’appelle aussi FIFO : « first in, first out »•Pensez à une file d’attente !QueueEntrée de la fileFin de la file TêteSortie de la fileDébut de la file Eva ANSERMIN Romuald GRIGNON51
Page 52 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •ExempleQueue de la file 2158120Tête de la file Eva ANSERMIN Romuald GRIGNON52
Page 53 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •Exemple : ajouter un élément : enfiler Queue de la file 2158120Tête de la file 33Eva ANSERMIN Romuald GRIGNON53
Page 54 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •Exemple : enfiler : on place l’élément en bas de la fileQueue de la file 2158120Tête de la file 33Eva ANSERMIN Romuald GRIGNON54
Page 55 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •Exemple : supprimer un élément : défilerQueue de la file 2158120Tête de la file 33Eva ANSERMIN Romuald GRIGNON55
Page 56 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •Exemple : défiler: l’élément est supprimé en haut de la fileQueue de la file 2158Tête de la file 33Eva ANSERMIN Romuald GRIGNON56
Page 57 : Files : principe•Une file est une liste d’éléments :•Un élément est toujours ajouté en bas de la file •Un élément est toujours retiré en haut de la file •Exemple : défiler : l’élément est supprimé en haut de la fileQueue de la file 215Tête de la file 33Eva ANSERMIN Romuald GRIGNON57
Page 58 : Files : utilisation• Dans l’ordinateur, les files sont principalement utilisées pour stocker des données qui doivent être traitées dans l’ordre d’arrivée. • Exemple : les tâches d’impression !• En algorithmie la File permet de simuler de nombreux problèmes comme la gestion de file d’attente.Eva ANSERMIN Romuald GRIGNON58
Page 59 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées. 10225103NULLplisteTête de la fileQueue de la fileEva ANSERMIN Romuald GRIGNON59
Page 60 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Enfilage :10225103NULLplisteTête de la fileQueue de la fileEva ANSERMIN Romuald GRIGNON60
Page 61 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Enfilage : ajout d’un élément en fin de liste fin de la file / en queue10225103NULLpliste58Tête de la fileQueue de la fileEva ANSERMIN Romuald GRIGNON61
Page 62 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Enfilage : ajout d’un élément en fin de liste fin de la file / en queue2.Défilage : 10225103NULLplisteTête de la fileQueue de la fileEva ANSERMIN Romuald GRIGNON62
Page 63 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•A quelles opérations sur une liste chaînée sont équivalentes les opérations suivantes :1.Enfilage : ajout d’un élément en fin de liste fin de la file / en queue2.Défilage : suppression d’un élément en début de liste début de file / en tête+ récupération de l’Element10225103plisteTête de la fileNULLNULLQueue de la fileEva ANSERMIN Romuald GRIGNON63
Page 64 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•Pour ne pas avoir besoin de parcourir la liste chaînée, la pile va exploiter deux pointeurs: NULLtêtequeueStructure FileDyn :tete : pointeur sur ChainonQueue : pointeur sur ChainonEva ANSERMIN Romuald GRIGNON64
Page 65 : Files dynamiques •Les files dynamiques sont gérées à partir de listes chaînées.•Pour ne pas avoir besoin de parcourir la liste chaînée, la pile va exploiter deux pointeurs: NULLqueuetêteL’inverse est moins optimal !Eva ANSERMIN Romuald GRIGNON65
Page 66 : Files dynamiques •Vérification de l’intégrité de la structure FileDynNULLtêtequeueFONCTION verificationFileDynfile: pointeur sur FileDyn : entierVARIABLE result ← 0 : entier// retour 0 signifie OKDEBUTSI??? ALORSresult ← -1// pointeur structure NULLSINON SI??? ALORSresult ← -2// structure corrompue 1SINON SI??? ALORSresult ← -3 // structure corrompue 2FIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON66
Page 67 : Files dynamiques •Vérification de l’intégrité de la structure FileDynNULLtêtequeueFONCTION verificationFileDynfile: pointeur sur FileDyn : entierVARIABLE result ← 0 : entier// retour 0 signifie OKDEBUTSIfile EST EGAL A NULL ALORSresult ← -1// pointeur structure NULLSINON SI??? ALORSresult ← -2// structure corrompue 1SINON SI??? ALORSresult ← -3 // structure corrompue 2FIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON67
Page 68 : Files dynamiques •Vérification de l’intégrité de la structure FileDynNULLtêtequeueFONCTION verificationFileDynfile: pointeur sur FileDyn : entierVARIABLE result ← 0 : entier// retour 0 signifie OKDEBUTSIfile EST EGAL A NULL ALORSresult ← -1// pointeur structure NULLSINON SItetefile EGAL A NULL DIFFERENT DE queuefile EGAL A NULL ALORSresult ← -2// structure corrompue 1SINON SI??? ALORSresult ← -3 // structure corrompue 2FIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON68
Page 69 : Files dynamiques •Vérification de l’intégrité de la structure FileDynNULLtêtequeueFONCTION verificationFileDynfile: pointeur sur FileDyn : entierVARIABLE result ← 0 : entier// retour 0 signifie OKDEBUTSIfile EST EGAL A NULL ALORSresult ← -1// pointeur structure NULLSINON SItetefile EGAL A NULL DIFFERENT DE queuefile EGAL A NULL ALORSresult ← -2// structure corrompue 1SINON SIsuivantqueuefile DIFFERENT DE NULL ALORSresult ← -3 // structure corrompue 2FIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON69
Page 70 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON70NULLqueuetête
Page 71 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON71NULLqueuetêteFONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - ???SI ??? ALORSnouveau ← ??? elmtnouveau ← ???SI ???// si la file est vide…??????SINON??? FIN SIFIN SIRETOURNER resultFIN
Page 72 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON72NULLqueuetêteFONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI ??? ALORSnouveau ← ??? elmtnouveau ← ???SI ???// si la file est vide…??????SINON??? FIN SIFIN SIRETOURNER resultFIN
Page 73 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON73NULLqueuetêteFONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← ??? elmtnouveau ← ???SI ???// si la file est vide…??????SINON??? FIN SIFIN SIRETOURNER resultFIN
Page 74 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON74NULLqueuetêteelmtnouveauNULLFONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← ???SI ???// si la file est vide…??????SINON??? FIN SIFIN SIRETOURNER resultFIN
Page 75 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON75FONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← elmtSI queuefile EST EGAL A NULL// si la file est vide…??????SINON??? FIN SIFIN SIRETOURNER resultFINelmtnouveauNULLtêtequeue
Page 76 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON76FONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← elmtSI queuefile EST EGAL A NULL// si la file est vide…tetefile ← nouveau???SINON??? FIN SIFIN SIRETOURNER resultFINelmtnouveauNULLqueuetête
Page 77 : Files dynamiques •Enfilage FONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← elmtSI queuefile EST EGAL A NULL// si la file est vide…tetefile ← nouveauqueuefile ← nouveauSINON??? FIN SIFIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON77elmtnouveauNULLtêtequeue
Page 78 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON78FONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← elmtSI queuefile EST EGAL A NULL // si la file est vide…tetefile ← nouveauqueuefile ← nouveauSINON??? FIN SIFIN SIRETOURNER resultFINNULLqueuetêteelmtnouveauNULL
Page 79 : Files dynamiques •Enfilage Eva ANSERMIN Romuald GRIGNON79FONCTION enfilerDynfile: pointeur sur FileDyn, elmt : Element : entierVARIABLE nouveau : pointeur sur Chainonresult ← 0 : entierDEBUTresult - verificationFileDynfileSI result EST SUP. STRICT. A -2 ALORSnouveau ← creationChainonelmtnouveau ← elmtSI queuefile EST EGAL A NULL // si la file est vide…tetefile ← nouveauqueuefile ← nouveauSINONsuivantqueuefile ← nouveauFIN SIFIN SIRETOURNER resultFINqueuetêteelmtnouveauNULL
Page 80 : Files statiques•La file statique est une file réalisée avec un tableau.•Le tête et la queue de la file vont être représentées par des indices de ces tableaux indiquant leur positions.•Exemple :101587686513875587Structure FileStat :tabPile : tableau d’Element de taille N tete :entierqueue : entier tete ←2queue ←8Eva ANSERMIN Romuald GRIGNON80
Page 81 : Files statiques•Les opérations de la file statique : •Enfiler Eva ANSERMIN Romuald GRIGNON81
Page 82 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION enfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUT???SI??? ALORSSI??? ALORSresult ← 1SINON??? ???FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON82
Page 83 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION enfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSI??? ALORS// données intègresSI??? ALORSresult ← 1SINON??????FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON83
Page 84 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION enfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSIresult EST EGAL A 0 ALORS// données intègresSI??? ALORSresult ← 1SINON??????FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON84
Page 85 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION enfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSIresult EST EGAL A 0 ALORS// données intègresSIqueuefile EST EGAL A taillefile-1 ALORSresult ← 1// file déjà pleineSINON??????FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON85
Page 86 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION enfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSIresult EST EGAL A 0 ALORS// données intègresSIqueuefile EST EGAL A taillefile-1 ALORSresult ← 1// file déjà pleineSINON??????FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON86
Page 87 : Files statiques•Les opérations de la file statique : •Enfiler 101587686513725587FONCTION EnfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSIresult EST EGAL A 0 ALORS// données intègresSIqueuefile EST EGAL A taillefile-1 ALORSresult ← 1// file déjà pleineSINONqueuefile ← queuefile + 1// décalage queue???FIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON87
Page 88 : Files statiques•Les opérations de la file statique : •Enfiler 10158768651372elmt87FONCTION EnfilerStat file : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ←vérification du pointeur pile et du contenu de la structureSIresult EST EGAL A 0 ALORS// données intègresSIqueuefile EST EGAL A taillefile-1 ALORSresult ← 1// file déjà pleine SINONqueuefile ← queuefile + 1// décalage queuetabFilefilequeue ←elmt// stockage élémentFIN SIFIN SIRETOURNER resultFINtetequeueEva ANSERMIN Romuald GRIGNON88
Page 89 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler Eva ANSERMIN Romuald GRIGNON89
Page 90 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUT???SI??? ALORSSI??? ALORSresult ← 1SINON?????? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON90
Page 91 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSI??? ALORSSI??? ALORSresult ← 1SINON?????? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON91
Page 92 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSIresult EST EGAL A 0 ALORS// données intègresSI??? ALORSresult ← 1SINON?????? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON92
Page 93 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSIresult EST EGAL A 0 ALORS// données intègresSItetefile EST EGAL A queuefile + 1 ALORSresult ← 1// file déjà videSINON?????? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON93
Page 94 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSIresult EST EGAL A 0 ALORS// données intègresSItetefile EST EGAL A queuefile + 1 ALORSresult ← 1// file déjà videSINON?????? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON94
Page 95 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSIresult EST EGAL A 0 ALORS// données intègresSItetefile EST EGAL A queuefile + 1 ALORSresult ← 1// file déjà videSINONpElmt ←tetefile// récupération élément ??? FIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON95
Page 96 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler FONCTION defilerStat file : pointeur sur FileStat, pElmt : pointeur sur element : entierDEBUTresult ←vérification des pointeurs et contenu de structureSIresult EST EGAL A 0 ALORS// données intègresSItetefile EST EGAL A queuefile + 1 ALORSresult ← 1// file déjà videSINONpElmt ←tetefile// récupération élément tetefile ← tetefile + 1// décalage teteFIN SIRETOURNER resultFIN101587686513725587tetequeueEva ANSERMIN Romuald GRIGNON96
Page 97 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la fileEva ANSERMIN Romuald GRIGNON97
Page 98 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la file101587686513875587FONCTION initFileStat file : pointeur sur FileStat : entierVARIABLEresult ← 0 : entierDEBUTSI ??? ALORS result ← ???FIN SItetefile ← ???queuefile ← ???retourner resultFINEva ANSERMIN Romuald GRIGNON98
Page 99 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la file101587686513875587FONCTION initFileStat file : pointeur sur FileStat : entierVARIABLEresult ← 0 : entierDEBUTSI file EST EGAL A NULL ALORS result ← ???FIN SItetefile ← ???queuefile ← ???retourner resultFINEva ANSERMIN Romuald GRIGNON99
Page 100 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la file101587686513875587FONCTION initFileStat file : pointeur sur FileStat : entierVARIABLEresult ← 0 : entierDEBUTSI file EST EGAL A NULL ALORS result ← -1FIN SItetefile ← ???queuefile ← ???retourner resultFINEva ANSERMIN Romuald GRIGNON100
Page 101 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la file101587686513875587queueteteFONCTION initFileStat file : pointeur sur FileStat : entierVARIABLEresult ← 0 : entierDEBUTSI file EST EGAL A NULL ALORS result ← -1FIN SItetefile ← 0queuefile ← -1retourner resultFINEva ANSERMIN Romuald GRIGNON101
Page 102 : Files statique : limites •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Exemple : 101587686513875587queueteteEva ANSERMIN Romuald GRIGNON102
Page 103 : Files statiques : limites •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Exemple : 101587686513875515queueteteOn ne peut pas rajouter de nouvel élément!Eva ANSERMIN Romuald GRIGNON103
Page 104 : Files statiques : limites •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Exemple : •Les indices de tête et de queue se décale en fin de tableau avec les utilisations de la pile : on arrive toujours à ce résultat au bout d’un certain nombres d’opérations!101587686513875515queueteteOn ne peut pas rajouter de nouvel élément!Eva ANSERMIN Romuald GRIGNON104
Page 105 : Files statiques cycliques •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Solution : utilisation d’une file cyclique.•Principe : les éléments de la file vont « reboucler » dans le tableau.101587686513875515queueteteEva ANSERMIN Romuald GRIGNON105
Page 106 : Files statiques cycliques •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Solution : utilisation d’une file cyclique.•Principe : les éléments de la file vont « reboucler » dans le tableau.L’élément supplémentaire est rajouté au début du tableau ! 301587686513875515queueteteEva ANSERMIN Romuald GRIGNON106
Page 107 : Files statiques cycliques •Les opérations telles que celles définies précédemment peuvent mener à une impossibilité d’utiliser la file même lorsque celle-ci n’est pas pleine.•Solution : utilisation d’une file cyclique.•Principe : les éléments de la file vont « reboucler » dans le tableau.L’élément supplémentaire est rajouté au début du tableau ! 307287686513875515queueteteEva ANSERMIN Romuald GRIGNON107
Page 108 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =7queue = 9101587686513875515queueteteEva ANSERMIN Romuald GRIGNON108
Page 109 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =7queue = 10151587686513875515queueteteEva ANSERMIN Romuald GRIGNON109
Page 110 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =7queue = 11152087686513875515queueteteEva ANSERMIN Romuald GRIGNON110
Page 111 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =8queue = 11152087686513875515queueteteEva ANSERMIN Romuald GRIGNON111
Page 112 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =9queue = 11152087686513875515queueteteEva ANSERMIN Romuald GRIGNON112
Page 113 : Files statiques cycliques •Dans la file cyclique, les entiers tete et queue ne vont pas indiquer directement les indices des tableaux.•tete et queue indiquent les positions du haut et du bas de la file s’il n’y avait pas de rebouclage comme si le tableau avait une taille infinie •Exemple : tete =10queue = 11152087686513875515queueteteEva ANSERMIN Romuald GRIGNON113
Page 114 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage 152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON114
Page 115 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDDEBUTresult ← ???SI??? ALORS// file pleineresult ← ???SINON??? // décalage queue???// stockage élémentFIN SIRETOURNER resultFIN152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON115
Page 116 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDDEBUTresult ← vérification du pointeur de file et contenu de la structureSI??? ALORS// file pleineresult ← ???SINON??? // décalage queue???// stockage élémentFIN SIRETOURNER resultFIN152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON116
Page 117 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDDEBUTresult ← vérification du pointeur de file et contenu de la structureSIqueuefile-tetefile EGAL A taillefile-1 ALORS // file pleineresult ← ???SINON??? // décalage queue???// stockage élémentFIN SIRETOURNER resultFIN152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON117
Page 118 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDDEBUTresult ← vérification du pointeur de file et contenu de la structureSIqueuefile-tetefile EGAL A taillefile-1 ALORS // file pleineresult ← 1SINON??? // décalage queue???// stockage élémentFIN SIRETOURNER resultFIN152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON118
Page 119 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDDEBUTresult ← vérification du pointeur de file et contenu de la structureSIqueuefile-tetefile EGAL A taillefile-1 ALORS // file pleineresult ← 1SINONqueuefile ←queuefile + 1// décalage queue???// stockage élémentFIN SIRETOURNER resultFIN152087686513875515tetequeueEva ANSERMIN Romuald GRIGNON119
Page 120 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage FONCTION enfilerStatCycliquefile : pointeur sur FileStat, elmt : Element : entierVARIABLEresult ← 0 : entierDEBUTresult ← vérification du pointeur de file et contenu de la structureSIqueuefile-tetefile EGAL A taillefile-1 ALORS // file pleineresult ← 1SINONqueuefile ←queuefile + 1// décalage queuetabFilefilequeuefile MOD taillefile ← elmt // stockage élémentFIN SIRETOURNER resultFIN1520elmt686513875515tetequeueEva ANSERMIN Romuald GRIGNON120
Page 121 : Files statiques cycliques •Opérations dans une file cyclique :•Défilagetetequeue152087686513875515Eva ANSERMIN Romuald GRIGNON121
Page 122 : Files statiques cycliques •Opérations dans une file cyclique :•Défilage152087686513875515queueFONCTION defilerStatCycliquefile : ptr sur FileStat, pelmt : ptr sur Element : entierVARIABLEresult ← 0 : entierDEBUT???SI???SI??? ALORS // file videresult ← 1SINON??? // récupération??? // décalageFIN SIFIN SIRETOURNER resultFINteteEva ANSERMIN Romuald GRIGNON122
Page 123 : Files statiques cycliques •Opérations dans une file cyclique :•Défilage152087686513875515queueFONCTION defilerStatCycliquefile : ptr sur FileStat, pelmt : ptr sur Element : entierVARIABLEresult ← 0 : entierDEBUTresult ← vérification des pointeurs et contenus des structuresSIresult EGAL A 0SI??? ALORS // file videresult ← 1SINON??? // récupération??? // décalageFIN SIFIN SIRETOURNER resultFINteteEva ANSERMIN Romuald GRIGNON123
Page 124 : Files statiques cycliques •Opérations dans une file cyclique :•Défilage152087686513875515queueFONCTION defilerStatCycliquefile : ptr sur FileStat, pelmt : ptr sur Element : entierVARIABLEresult ← 0 : entierDEBUTresult ← vérification des pointeurs et contenus des structuresSIresult EGAL A 0SIqueuefile-tetefile EGAL A -1 ALORS // file videresult ← 1SINON??? // récupération??? // décalageFIN SIFIN SIRETOURNER resultFINteteEva ANSERMIN Romuald GRIGNON124
Page 125 : Files statiques cycliques •Opérations dans une file cyclique :•Défilage152087686513875515queueFONCTION defilerStatCycliquefile : ptr sur FileStat, pelmt : ptr sur Element : entierVARIABLEresult ← 0 : entierDEBUTresult ← vérification des pointeurs et contenus des structuresSIresult EGAL A 0SIqueuefile-tetefile EGAL A -1 ALORS // file videresult ← 1SINONpelmt ← tabFilefiletetefile MOD taillefile// récupération??? // décalageFIN SIFIN SIRETOURNER resultFINteteEva ANSERMIN Romuald GRIGNON125
Page 126 : Files statiques cycliques •Opérations dans une file cyclique :•Défilage152087686513875515tetequeueFONCTION defilerStatCycliquefile : ptr sur FileStat, pelmt : ptr sur Element : entierVARIABLEresult ← 0 : entierDEBUTresult ← vérification des pointeurs et contenus des structuresSIresult EGAL A 0SIqueuefile-tetefile EGAL A -1 ALORS // file videresult ← 1SINONpelmt ← tabFilefiletetefile MOD taillefile// récupérationtetefile ←tetefile + 1// décalageFIN SIFIN SIRETOURNER resultFINEva ANSERMIN Romuald GRIGNON126
Page 127 : Résumé•Les piles et les files sont des objets algorithmiques permettant de stocker des données en répondant à des critères d’insertion et de suppression précis. •Pile : dernier entré, premier sorti last IN, first OUT LIFO. •File : premier entré, premier sorti First In, First Out FIFO.•Il existe plusieurs manières d’implémenter les piles et les files selon les résultats souhaités statique, dynamique, cyclique.•Les piles et les files sont très utilisées par l’ordinateur pour son fonctionnement, mais elles sont également régulièrement présentes dans certains algorithmes classiques voir cours suivant !. Eva ANSERMIN Romuald GRIGNON127
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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127