CM2 Files Piles
Télécharger le CM2 Files Piles 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 & Renaud VERIN & Romuald GRIGNONv1.00
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.pliste10225103NULLE.ANSERMIN R.VERIN R.GRIGNON2
Page 3 : I. PilesE.ANSERMIN R.VERIN R.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 !E.ANSERMIN R.VERIN R.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 : 2158120E.ANSERMIN R.VERIN R.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 : empilage215812033E.ANSERMIN R.VERIN R.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 215812033E.ANSERMIN R.VERIN R.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 215812033E.ANSERMIN R.VERIN R.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 :215812033E.ANSERMIN R.VERIN R.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 :2158120E.ANSERMIN R.VERIN R.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! E.ANSERMIN R.VERIN R.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 ? 1022510310225103NULLE.ANSERMIN R.VERIN R.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 OUE.ANSERMIN R.VERIN R.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/E.ANSERMIN R.VERIN R.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???teteE.ANSERMIN R.VERIN R.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 pasE.ANSERMIN R.VERIN R.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: 102251035516147teteE.ANSERMIN R.VERIN R.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: E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 ← 40tete10225405516147E.ANSERMIN R.VERIN R.GRIGNON20
Page 21 : Piles : Implémentation statique•Initialisation de la pile statique : FONCTION creationPileStat: PileStatVARIABLE pile: PileStatDEBUTtetepile ← ???RETOURNER pileFIN E.ANSERMIN R.VERIN R.GRIGNON21
Page 22 : Piles : Implémentation statique•Initialisation de la pile statique : 10225405516147tabPileteteFONCTION creationPileStat: PileStatVARIABLE pile: PileStatDEBUTtetepile ← -1 // la pile est videRETOURNER pileFIN E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.GRIGNON27
Page 28 : Piles : Implémentation statique•Empilage : tete10225405516147E.ANSERMIN R.VERIN R.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 tete10225405516147E.ANSERMIN R.VERIN R.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 tete10225405516147E.ANSERMIN R.VERIN R.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 tete10225405516147E.ANSERMIN R.VERIN R.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 tete10225405516147E.ANSERMIN R.VERIN R.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 tete10225405516147E.ANSERMIN R.VERIN R.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’16147teteE.ANSERMIN R.VERIN R.GRIGNON34
Page 35 : Piles : Implémentation statique•Dépilage : 10225405516147teteE.ANSERMIN R.VERIN R.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 10225405516147teteE.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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? E.ANSERMIN R.VERIN R.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. 10225103NULLteteE.ANSERMIN R.VERIN R.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 teteFINE.ANSERMIN R.VERIN R.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 : tete10512NULLNULL7E.ANSERMIN R.VERIN R.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 insertDebuttete10512NULLNULL7E.ANSERMIN R.VERIN R.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 : 10225103NULLplisteE.ANSERMIN R.VERIN R.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.10225103NULLtetep110E.ANSERMIN R.VERIN R.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.E.ANSERMIN R.VERIN R.GRIGNON49
Page 50 : II. FilesE.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 33E.ANSERMIN R.VERIN R.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 33E.ANSERMIN R.VERIN R.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 33E.ANSERMIN R.VERIN R.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 33E.ANSERMIN R.VERIN R.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 33E.ANSERMIN R.VERIN R.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.E.ANSERMIN R.VERIN R.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 fileE.ANSERMIN R.VERIN R.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 fileE.ANSERMIN R.VERIN R.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 fileE.ANSERMIN R.VERIN R.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 fileE.ANSERMIN R.VERIN R.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 fileE.ANSERMIN R.VERIN R.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 ChainonE.ANSERMIN R.VERIN R.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 !E.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.GRIGNON69
Page 70 : Files dynamiques •Enfilage E.ANSERMIN R.VERIN R.GRIGNON70NULLqueuetête
Page 71 : Files dynamiques •Enfilage E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.GRIGNON77elmtnouveauNULLtêtequeue
Page 78 : Files dynamiques •Enfilage E.ANSERMIN R.VERIN R.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 E.ANSERMIN R.VERIN R.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 ←8E.ANSERMIN R.VERIN R.GRIGNON80
Page 81 : Files statiques•Les opérations de la file statique : •Enfiler E.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.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 resultFINtetequeueE.ANSERMIN R.VERIN R.GRIGNON88
Page 89 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler E.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.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 resultFIN101587686513725587tetequeueE.ANSERMIN R.VERIN R.GRIGNON96
Page 97 : Files statiques•Les opérations de la file statique : •Enfiler •Défiler •Initialisation de la fileE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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 : 101587686513875587queueteteE.ANSERMIN R.VERIN R.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!E.ANSERMIN R.VERIN R.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!E.ANSERMIN R.VERIN R.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.101587686513875515queueteteE.ANSERMIN R.VERIN R.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 ! 301587686513875515queueteteE.ANSERMIN R.VERIN R.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 ! 307287686513875515queueteteE.ANSERMIN R.VERIN R.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 = 9101587686513875515queueteteE.ANSERMIN R.VERIN R.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 = 10151587686513875515queueteteE.ANSERMIN R.VERIN R.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 = 11152087686513875515queueteteE.ANSERMIN R.VERIN R.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 = 11152087686513875515queueteteE.ANSERMIN R.VERIN R.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 = 11152087686513875515queueteteE.ANSERMIN R.VERIN R.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 = 11152087686513875515queueteteE.ANSERMIN R.VERIN R.GRIGNON113
Page 114 : Files statiques cycliques •Opérations dans une file cyclique :•Enfilage 152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN152087686513875515tetequeueE.ANSERMIN R.VERIN R.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 resultFIN1520elmt686513875515tetequeueE.ANSERMIN R.VERIN R.GRIGNON120
Page 121 : Files statiques cycliques •Opérations dans une file cyclique :•Défilagetetequeue152087686513875515E.ANSERMIN R.VERIN R.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 resultFINteteE.ANSERMIN R.VERIN R.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 resultFINteteE.ANSERMIN R.VERIN R.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 resultFINteteE.ANSERMIN R.VERIN R.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 resultFINteteE.ANSERMIN R.VERIN R.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 resultFINE.ANSERMIN R.VERIN R.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. •File : premier entré, premier sorti.•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 !. E.ANSERMIN R.VERIN R.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