cours - partie 2

cours - partie 2

-

Documents
12 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Plan Listes > Définition Une liste est un ensemble d’objets de même type Algorithmeconstituant les éléments de la liste. Les éléments Types abstraits de donnéessont chaînés entre eux et on peut facilement ajouter ou extraire un ou plusieurs éléments. Pointeurs Une liste simple est une structure de données telle Listesque chaque élément contient : Piles Des informations caractéristiques de l’application développée. Files Un pointeur vers un autre élément de la liste ou une marqueur indiquant la fin de la liste. Tris Complexité20/09/2006 1 20/09/2006 2Listes > Exemple Listes > Opérations Créer_liste : ⇒ Liste Accès : Liste ⊗ Entier ⇒ PlaceDupond DurandPremier Contenu : Place ⇒ Element Longueur : Liste ⇒ Entier Supprimer : Liste ⊗ Entier ⇒ Liste Insérer : Liste ⊗ Entier ⊗ Element⇒Paul / ParkerListe Succ : Place ⇒ Place20/09/2006 3 20/09/2006 41Listes > Représentation en Listes > Représentation en mémoire mémoire > Allocation contiguë> Allocation dynamiqueAdressesPosition Element Suivantp500 DupondP0 Dupond 21 Paul /Toto1002 Toto 31000Titi3 Titi 1Paul /3504520/09/2006 5 20/09/2006 6Listes > Algorithme avec allocation Listes > Comparaisondynamique > Structure de donnéesEnregistrement Place{ Allocation dynamiqueElt : Pointeur[Element]; Plus de souplesse, virtuellement pas de Suivant : Pointeur[Place];limite de taille} Gestion du dépassement de capacité àprévoirEnregistrement Liste { ...

Sujets

Informations

Publié par
Nombre de visites sur la page 20
Langue Latin
Signaler un problème
Plan
Algorithme Types abstraits de données Pointeurs Listes Piles Files Tris Complexité
20/09/2006
Listes > Exemple
Premier
20/09/2006
Dupond
Paul
/
Durand
Parker
1
3
Listes > Définition
Une liste est un ensemble d’objets de même type constituant les éléments de la liste. Les éléments sont chaînés entre eux et on peut facilement ajouter ou extraire un ou plusieurs éléments.
Une liste simple est une structure de données telle que chaque élément contient : Des informations caractéristiques de l’application développée. Un pointeur vers un autre élément de la liste ou une marqueur indiquant la fin de la liste.
20/09/2006
Listes > Opérations
Créer_liste :Liste Accès : ListeEntierPlace Contenu : PlaceElement Longueur : ListeEntier Supprimer : ListeEntierListe Insérer : ListeEntierElementListe Succ : PlacePlace
20/09/2006
2
4
1
Listes > Représentation en mémoire > Allocation dynamique
Adresses
500
100
1000
350
20/09/2006
p
Dupond
Toto
Titi
Paul
/
Listes > Comparaison
Allocation dynamique Plus de souplesse, virtuellement pas de limite de taille Gestion du dépassement de capacité à prévoir Allocation contiguë Taille maximale doit être connue d’avance Structure semblable à un fichier sur un disque
20/09/2006
5
7
P
Listes > Représentation en mémoire > Allocation contiguë
Position 0 1 2 3 4 5
20/09/2006
Element Dupond Paul Toto Titi
Suivant 2 / 3 1
Listes > Algorithme avec allocation dynamique > Structure de données
Enregistrement Place{ Elt : Pointeur[Element]; Suivant : Pointeur[Place]; }
Enregistrement Liste { Premier : Pointeur[Place]; }
20/09/2006
6
8
2
Listes > Algorithme avec allocation dynamique > Représentation en mémoire
Premier
20/09/2006
Place
Element
Listes > Algorithme avec allocation dynamique > Créer_liste
Créer_liste :Liste
Fonction créer_liste() : Liste{ Resultat : Liste; ResultatPremier = null; Retourne Resulat; }
20/09/2006
/
9
11
Listes > Algorithme avec allocation dynamique > Créer_liste
Premier
20/09/2006
/
Listes > Algorithme avec allocation dynamique > Accès
Premier
20/09/2006
0
1
2
Longueur  1
/
10
12
3
Listes > Algorithme avec allocation dynamique > Accès
Accès : ListeEntierPlace
Fonction Accès(L : Liste; I : Entier) : Pointeur[Place]{ Résultat : Pointeur[Place]; Courant : Pointeur[Place]; Compteur : Entier; Si (I >= 0) { Courant = LPremier; } Sinon { Courant = null; } FinSi Compteur = 0; TantQue (Courant != null ET Compteur < I){ Courant = Valeur[Courant]Suivant; Compteur = Compteur + 1; } FinTantQue Résultat = Courant; Retourne Résultat; } 20/09/2006
Listes > Algorithme avec allocation dynamique > Contenu & Longueur
Premier
20/09/2006
0
1
2
Longueur  1
/
13
15
Listes > Algorithme avec allocation dynamique > Accès > Trace
Accès(Liste_1, 6)?
Accès(Liste_1, -1)?
20/09/2006
Listes > Algorithme avec allocation dynamique > Contenu & Longueur
Contenu : PlaceElement
Fonction Contenu (P : Place) : Pointeur[Element] { Retourne PElt; }
Longueur : ListeEntier
Fonction Longueur(L : Liste) : Entier { Taille : Entier; Courant : Pointeur[Place]; Taille = 0; Courant = LPremier; TantQue (Courant != null) Faire { Taille = Taille + 1; Courant = Valeur[Courant]Suivant; } FinTantQue; Retourne Taille; }
20/09/2006
14
16
4
Listes > Algorithme avec allocation dynamique > Supprimer
Premier
X
20/09/2006
0
1
X
2
Longueur  1
Listes > Algorithme avec allocation dynamique > Supprimer
}
Si (LPremier != null) Alors { Si (Pos == 0) Alors { LPremier = Valeur[LPremier]Suivant; } Sinon { Courant = Valeur[LPremier]Suivant; Prec = LPremier; TantQue (Courant != null) ET (Compteur < Pos) Faire { Prec = Courant; Courant = Valeur[Courant]Suivant; Compteur = Compteur + 1; } FinTantQue Si (Courant != null) Et (Compteur == Pos) Alors { Valeur[Prec]Suivant = Valeur[Courant]Suivant; } FinSi } FinSi } FinSI Retourne L;
20/09/2006
/
17
19
Listes > Algorithme avec allocation dynamique > Supprimer
Supprimer : ListeEntierListe
Fonction Supprimer (L : Liste; Pos : Entier) : Liste;{ Compteur : Entier; Prec : Pointeur[Place]; Courant : Pointeur[Place];
Compteur = 1;
20/09/2006
18
Listes > Algorithme avec allocation dynamique > Insérer
PremierX
20/09/2006
X
/
20
5
Listes > Algorithme avec allocation dynamique > Insérer
Insérer : ListeEntierElementListe
Fonction Inserer (L : Liste; Pos : Element) : Liste;{…?}
20/09/2006
: Entier; Elt
Listes > Algorithme avec allocation dynamique > Succ
Succ : PlacePlace
Fonction Succ(P : Pointeur[Place]) : pointeur[place];{ Resultat : Pointeur[place]; Si P != null Alors Resultat = Valeur[P]Suivant; Sinon Resultat = null; FinSi Retourne Resultat; }
20/09/2006
21
23
Listes > Algorithme avec allocation dynamique > Succ
Liste
20/09/2006
/
22
Listes > Algorithme avec allocation dynamique > Succ > Trace
Succ(&P_1)? Succ(&P_4)?
20/09/2006
24
6
Listes > Algorithme avec allocation contiguë > Structure de données
Constante vide : entier = -1; Constante longueur : entier = N;
Enregistrement Place{ Elt : Element; Suivant : Entier; Libre : Booleen; }
Enregistrement Liste { Premier : Entier; Places : Tableau [0..longueur-1] de Place; } 20/09/2006
Listes > Algorithme avec allocation contiguë > Créer_liste
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
Vide 6 Elt Indéfini Indéfini Indéfini Indéfini Indéfini Indéfini
Libre Vrai Vrai Vrai Vrai Vrai Vrai
Suivant Vide Vide Vide Vide Vide Vide
25
27
Listes > Algorithme avec allocation contiguë > Exemple
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
0 6 Elt Dupond Paul Toto Titi Indéfini Indéfini
Libre Faux Faux Faux Faux Vrai Vrai
Suivant 2 Vide 3 1 Indéfini Indéfini
Listes > Algorithme avec allocation contiguë > Créer_liste
Créer_liste :Liste Fonction Créer_liste : Liste {…?}
20/09/2006
26
28
7
Listes > Algorithme avec allocation contiguë > Accès
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
0 6 Elt Dupond Paul Toto Titi Indéfini Indéfini
Libre Faux Faux Faux Faux Vrai Vrai
Suivant 2 Vide 3 1 Indéfini Indéfini
Listes > Algorithme avec allocation contiguë > Accès
}
TantQue (Courant != Vide) Et (Compteur < Pos) Faire { Courant = LPlaces[Courant]Suivant; Compteur = Compteur + 1; } FinTantQue;
Si (courant != Vide) Alors { Resultat = LPlaces[Courant]; } Sinon { ResultatLibre = Vrai; } FinSi Retourne Resultat;
20/09/2006
29
31
Listes > Algorithme avec allocation contiguë > Accès
Accès : ListeEntierPlace
Fonction accès(L : Liste; Pos : Entier) : Place;{ Resultat : Place; Courant : Entier; Compteur : entier;
Compteur = 0; Courant = LPremier;
20/09/2006
30
Listes > Algorithme avec allocation contiguë > Accès > Trace
Acces(Liste_2, 1)? Acces(Liste_2, 5)?
20/09/2006
32
8
Listes > Algorithme avec allocation contiguë > Contenu
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
0 6 Elt Dupond Paul Toto Titi Indéfini Indéfini
Libre Faux Faux Faux Faux Vrai Vrai
Suivant 2 Vide 3 1 Indéfini Indéfini
33
Listes > Algorithme avec allocation contiguë > Longueur
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
0 6 Elt Dupond Paul Toto Titi Indéfini Indéfini
Libre Faux Faux Faux Faux Vrai Vrai
Suivant 2 Vide 3 1 Indéfini Indéfini
35
Listes > Algorithme avec allocation contiguë > Contenu
Contenu : PlaceElement
Fonction Contenu(P : Place) : Element;{
}
Retourne PElt;
20/09/2006
34
Listes > Algorithme avec allocation contiguë > Longueur
Longueur : ListeEntier
Fonction Longueur(L : Liste) : entier; { Courant : Entier; Compteur : entier;
}
Compteur = 0; Courant = LPremier;
TantQue (Courant != Vide) Faire { Courant = LPlaces[Courant]Suivant; Compteur = Compteur + 1; } FinTantQue;
Retourne Compteur;
20/09/2006
36
9
Listes > Algorithme avec allocation contiguë > Supprimer
Premier Longueur Position 0 1 2 3 4 5
20/09/2006
0 6 Elt Dupond Paul Toto Titi Indéfini Indéfini
Libre Suivant Faux 2 3 Faux Vide Faux Vrai 3 Indéfini Faux 1 Vrai Indéfini Vrai Indéfini
Listes > Algorithme avec allocation contiguë > Insérer
Premier Position 0 1 2 3 4
5
20/09/2006
0 Longueur Elt Libre Dupond Faux Paul Faux Toto Faux Titi Faux Nouveau Vrai Q Faux Indéfini Vrai
6 Suivant 2 Vide 3 4 1 Indéfini 3 Indéfini
37
39
Listes > Algorithme avec allocation contiguë > Supprimer
Supprimer : ListeEntierListe
Fonction supprimer(L : Liste; Pos Liste;{…?}
20/09/2006
: Entier) :
Listes > Algorithme avec allocation contiguë > Insérer
Insérer : ListeEntierElementListe
Fonction Inserer(L :Liste; Pos : Entier; EltIns : Element) : Liste;{ Compteur : Entier; Courant : Entier; PlaceIns : Entier Compteur2 : Entier; Compteur = 1; Ins : Place; Compteur2 = 0; PlaceIns = vide;
20/09/2006
38
40
10
Listes > Algorithme avec allocation contiguë > Insérer
TantQue (Compteur2 < Longueur) Et (PlaceIns = Vide) Faire { Si (LPlaces[Compteur2]Libre) Alors { PlaceIns = Compteur2; } FinSi Compteur2 = Compteur2 +1; } FinTantQue
20/09/2006
Listes > Algorithme avec allocation contiguë > Insérer
}
41
Si (Courant != Vide) Et (Compteur == Pos) Alors { LPlaces[PlaceIns]Element = EltIns; LPlaces[PlaceIns]Suivant = LPlaces[Courant]Suivant; LPlaces[PlaceIns]Libre = Faux; LPlaces[Courant]Suivant = PlaceIns; } FinSi } FinSi } FinSi Retourne L
20/09/2006
43
Listes > Algorithme avec allocation contiguë > Insérer
Si (PlaceIns != vide){
Si (Pos == 0) Alors { InsElement = EltIns; InsSuivant = LPremier; InsLibre = Faux; LPremier = PlaceIns; } Sinon{ Courant = LPremier; TantQue (Courant != Vide) Et (Compteur < Pos) Faire { Compteur = compteur + 1 ; Courant = Valeur[Courant]Suivant; } FinTantQue;
20/09/2006
42
Listes > Algorithme avec allocation contiguë > Insérer > Trace
Inserer(Liste_2, 2, {192.168.1.50,…})? Inserer(Liste_2, 5, {192.168.1.50,…})?
20/09/2006
44
11