Cours Structures de Donnees2

Département de Génie Informatique

Module : Algorithmes et Structures de données Module : Algorithmes et Structures de données Module : Algorithmes et Structures de données Module : Algorithmes et Structures de données

en Cen Cen Cen C

UNIVERSITE ABDELMALEK ESSAADI

FACULTE DES SCIENCES ET TECHNIQUESTANGER

1 21/11/2012

en Cen Cen Cen C

Filière : MPIC Groupe : II-4

� Encadré parEncadré par ::

Professeur Chakkor Saad

[email protected]

Année Universitaire : 2011-2012

Programme Programme Programme Programme

• Rappel général et mise à niveau

• Tableaux

• Les fonctions

• Directives au pré processeur

• Type composé et structures

2 21/11/2012

• Type composé et structures

• Fichiers

• Pointeurs

• Récursivité

• Listes chaînées

• Arbres

• Tables de hachage

• Graphes

EvaluationEvaluationEvaluationEvaluation

• Remarque !! :

• la présence et la réalisation des Exos de TD & de TP & mini-projet seront pris en considération dans la note finale de module.

• CC1

• CC2

• CC3

• Examen de TP

Les tableauxLes tableauxLes tableauxLes tableaux

• Un tableau représente selon ses dimensions, un vecteur ou une matrice d'éléments d'un même type.

4 21/11/2012

• Un tableau est un ensemble fini d'éléments de même type, stockés en mémoire à des adresses contiguës.


• Déclaration de tableaux en C :

<TypeSimple> <NomTableau>[<Dimension>];

5 21/11/2012

<TypeSimple> <NomTableau>[<Dimension>];

Les noms des tableaux sont des identificateurs

Les tableaux à une dimension

Déclaration: type nom[dim]; Exemples: int compteur[10];float nombre[20];

Utilisation:


Un élément du tableau est repéré par son indice. En langage C les tableaux commencent à l'indice 0. L'indice maximum est donc dim-1.

Appel: nom[indice]

Exemples: compteur[2] = 5;nombre[i] = 6.789;printf("%d",compteur[i]);scanf("%f",&nombre[i]);

Les tableaux à plusieurs dimensions:

Tableaux à deux dimensions:

Déclaration: type nom[dim1][dim2]; Exemples: int compteur[4][5];

float nombre[2][10];

Utilisation:


Un élément du tableau est repéré par ses indices. En langage C les tableaux

commencent aux indices 0. Les indices maximum sont donc dim1-1, dim2-1.

Appel: nom[indice1][indice2]

Exemples: compteur[2][4] = 5;

nombre[i][j] = 6.789;

printf("%d",compteur[i][j]);

scanf("%f",&nombre[i][j]);

Initialisation des tableaux

On peut initialiser les tableaux au moment de leur

déclaration:


Exemples:

int liste[10] = {1,2,4,8,16,32,64,128,256,528};float nombre[4] = {2.67,5.98,-8,0.09};int x[2][3] = {{1,5,7},{8,4,3}}; /* 2 lignes et 3 colonnes * /


• Si la dimension n'est pas indiquée explicitement lors de l'initialisation, alors le compilateur réserve automatiquement le nombre d'octets nécessaires.

• Exemples :

9 21/11/2012

• Exemples :

• int A[] = {10, 20, 30, 40, 50};

• ==> réservation de 5*sizeof(int) octets (dans notre cas: 10 octets)

• float B[] = {-1.05, 3.33, 0.87, -12.3};

• ==> réservation de 4*sizeof(float) octets (dans notre cas: 16 octets)


• Affichage et affectation :

Ecrire un programme qui permet de saisir N valeurs entières

10 21/11/2012

dans un tableau puis de les afficher horizontalement.

Calculer et afficher la somme des éléments de ce tableau.


• Exercices sur les tableaux :

Exercice 1 :

• Ecrire un programme qui lit la dimension N d'un tableau T du type int (dimension maximale: 50 composantes), remplit le tableau par des valeurs entrées au clavier et

11 21/11/2012

remplit le tableau par des valeurs entrées au clavier et affiche le tableau.

• Effacer ensuite toutes les occurrences de la valeur 0 dans le tableau T et tasser les éléments restants. Afficher le tableau résultant.


Exercice 2 :

Ecrire un programme qui lit la dimension N d'un tableau T du

type int (dimension maximale: 50), remplit le tableau par des

valeurs entrées au clavier et affiche le tableau.

12 21/11/2012

valeurs entrées au clavier et affiche le tableau.

Ranger ensuite les éléments du tableau T dans l'ordre

inverse sans utiliser de tableau d'aide. Afficher le tableau

résultant.


Exercice 3 :

Ecrire un programme qui lit la dimension N d'un tableau T

du type int (dimension maximale: 50), remplit le tableau par

des valeurs entrées au clavier et affiche le tableau.

13 21/11/2012

des valeurs entrées au clavier et affiche le tableau.

Copiez ensuite toutes les composantes strictement

positives dans un deuxième tableau TPOS et toutes les

valeurs strictement négatives dans un troisième tableau

TNEG. Afficher les tableaux TPOS et TNEG.


Exercice 4:

Ecrire un programme qui permet d’insérer une valeur

entrée au clavier dans un tableau d’entiers.

Exercice 5:

14 21/11/2012

Exercice 5:

Rechercher dans un tableau d'entiers une valeur VAL

entrée au clavier. Afficher la position de VAL si elle se

trouve dans le tableau, sinon afficher un message

correspondant. La valeur POS qui est utilisée pour

mémoriser la position de la valeur dans le tableau, aura la

valeur -1 aussi longtemps que VAL n'a pas été trouvée.


Exercice 6 :

Ecrire un programme qui permet de supprimer une valeur

d’un tableau d’entiers en indiquant sa position dans ce

tableau.

15 21/11/2012

tableau.

Exercice 7 :

Ecrire un programme qui permet de modifier une valeur

d’un tableau d’entiers en indiquant sa position dans ce

tableau.


Sujet de Travaux Pratiques N°1 :

On se propose de réaliser « un répertoire d’adresses » :

un répertoire est un ensemble d’information dont chaque

16 21/11/2012

un répertoire est un ensemble d’information dont chaque

élément possède les informations suivantes :

Contact : Nom*, Prénom*, Lien de parenté, adresse,

Tél.dom, Tél.entreprise, GSM*, email*

Avec Adresse : Numéro, Nom Rue, Code Postal, Ville, Pays.

Le lien de parenté est un indice de la liste suivante :

0 : Mère 3 : Frère 6 : Ami 1 : Père 4 : cousin 7 : Relation personnelle 2 : Sœur 5 : Parent 8 : Relation professionnelle


Les informations indiquées par * sont obligatoires

1) Fonctions à programmer :

2) Ajouter un contact

3) Afficher la liste des contacts

4) Consulter un contact

17 21/11/2012

4) Consulter un contact

5) Modifier un contact

6) Supprimer un contact

7) Recherche par Nom

8) Recherche multicritère : Nom, Prénom, Ville,

9) Amélioration : l’ajout doit vérifier si le contact existe déjà.

Les fichiersLes fichiersLes fichiersLes fichiers

• Un fichier (file) est un ensemble structuré de

données stocké en général sur un support

externe (disque dur, disque optique, ...).

18 21/11/2012

externe (disque dur, disque optique, ...).

• Un fichier structuré contient une suite

d'enregistrements homogènes, qui regroupent

le plus souvent plusieurs composantes.


• Opérations possibles avec les fichiers:

Créer - Ouvrir - Fermer - Lire - Ecrire - Détruire -Renommer.

• La plupart des fonctions permettant la manipulation des fichiers sont rangées dans la bibliothèque des fichiers sont rangées dans la bibliothèque <STDIO.H>, certaines dans <IO.H>.

• Déclaration:

FILE *fichier;

/* majuscules obligatoires pour FILE */

• La déclaration des fichiers doit figurer AVANT la déclaration des autres variables.

19 21/11/2012


• Ouverture:

• FILE *fopen(char *nom, char *mode);

• FILE *fopen(filename, mode) • FILE *fopen(filename, mode)

• /* déclaration dans stdio.h */

• char filename[], mode[];

• On passe donc 2 chaînes de caractères

• nom: celui figurant sur le disque, exemple: « C :\test.dat »

20 21/11/2012


• fopen a pour argument deux chaînes de caractères, le nom du fichier et le mode d'ouverture.

• donne comme résultat un pointeur NULL si l'ouverture a échoué

• sinon le pointeur renvoyé est utilisé dans les écritures, les lectures et les déplacements ultérieurs.


• Mode (pour les fichiers TEXTES) :

• « r » : lecture seule

• « w » : écriture seule (destruction de l'ancienne version si elle existe)si elle existe)

• « w+ » : lecture/écriture (destruction ancienne version si elle existe)

• « r+ » : lecture/écriture d'un fichier existant (mise à jour), pas de création d'une nouvelle version.

• « a+ » : lecture/écriture d'un fichier existant (mise à jour), pas de création d'une nouvelle version, le pointeur est positionné à la fin du fichier.

22 21/11/2012


• Mode (pour les fichiers BINAIRES) :

• On ajoute b devant les modes qu’on a vu :

• « rb » « wb » …• « rb » « wb » …

• Exemple : FILE *fichier ;

• fichier = fopen(« C:\test.dat», « rb ») ;

23 21/11/2012


• #include <stdio.h> /* Inclusion de la biblio standard */

• int main()

• { /* Déclaration d'un fichier */

• FILE* fichier;

• /* Ouverture du fichier test en lecture */

• fichier = fopen("/home/users/manouvrier/test","r");

• /* Test de l'ouverture pour vérifier les éventuels problèmes */

• if (fichier== NULL) /* Il y a eu un problème */

• { /* Affichage d'un message d'erreur */

• printf("Erreur ouverture fichier ");

• } /* Si l'ouverture a pu se faire */

• else ... }

24 21/11/2012


• Fermeture:

• Int fclose(FILE *fichier);

• Retourne 0 si la fermeture s’est bien passée, EOF en cas d’erreur.

• Il faut toujours fermer un fichier à la fin d'une • Il faut toujours fermer un fichier à la fin d'une session. mode (pour les fichiers TEXTE) :

• Exemple : FILE *fichier ;

• fichier = fopen(« C:\test.dat », « rb ») ;

• /* Ici instructions de traitement */

• fclose(fichier) ;

•25 21/11/2012


• Destruction:

• int remove(char *nom);

• Retourne 0 si la fermeture s’est bien passée.

• Exemple : remove(« C:\test.dat ») ;

• Renommer:

• int rename(char *oldname, char *newname);

• Retourne 0 si la fermeture s’est bien passée.26 21/11/2012


• Positionnement du pointeur au début du fichier :

• void rewind(FILE *fichier);

int feof(FILE *id) dit si on est en fin de fichier ou non (0).

• Récupération de la position du curseur dans le fichier : fichier :

• int ftell (FILE * fichier) ;

• Exemple :• #include <stdio.h>

• FILE* fichier;

• int pos;

• ...

• pos=ftell(fichier);

27 21/11/2012


• Ecriture dans le fichier texte:

• int putc(char c, FILE *fichier);

• Ecrit la valeur de c à la position courante du pointeur , le pointeur avance d'une case mémoire.pointeur , le pointeur avance d'une case mémoire.

• Retourne EOF qui marque la fin de fichier, en cas d’erreur.

• Exemple : putc(‘A’, fichier) ;

28 21/11/2012


• int putw(int n, FILE *fichier);

• le pointeur avance du nombre de cases correspondant à la taille d'un entier (4 cases).

• Retourne n si l’écriture s’est bien passée.• Retourne n si l’écriture s’est bien passée.

• int fputs(char *chaîne, FILE *fichier);

• le pointeur avance de la longueur de la chaine ('\0' n'est pas rangé dans le fichier). signifie "met une chaîne dans un fichier"

• Retourne EOF en cas d’erreur.

• Exemple : fputs(« BONJOUR ! », fichier) ;

29 21/11/2012


• fputc : ce qui signifie "met un caractère dans un fichier". Comme son nom l'indique, cette fonction écrit un octet dans un fichier.

Exemple :

char erreur;char erreur;

erreur = fputc('x', Pointeur_sur_fichier);

• putc

• putc(caractère, pointeur_sur_fichier)

• écrit le caractère dans un fichier à la position pointeur_sur_fichier (et renvoie le caractère).


• Ecriture dans le fichier binaire:

• int fwrite(void *p,int taille_bloc,int nb_bloc,FILE *fichier);

• p écrit à partir de la position courante du pointeur fichier nb_bloc X taille_bloc octets lus à partir de l'adresse p.

• Retourne le nombre de blocs écrits.

• Exemple :

• taille_bloc=4 (taille d'un entier en C), nb_bloc=3, écriture de 3 octets.

• int tab[10] ;

• fwrite(tab,4,3,fichier) ;31 21/11/2012


• fwrite : écrit dans un fichier des objets d'un type quelconque. Il faut préciser la taille d'un objet (par exemple avec sizeof(objet)), le nombre d'objets à écrire et le pointeur du fichier destination.

• la fonction renvoie le nombre d'éléments • la fonction renvoie le nombre d'éléments effectivement écrits.


• int fprintf(FILE *fichier, char *format, liste d'expressions);

• réservée plutôt aux fichiers ASCII.

• Retourne EOF en cas d’erreur.

••

• Exemples: fprintf(fichier,"%s","il fait beau");

• fprintf(fichier,%d,n);

• fprintf(fichier,"%s%d","il fait beau",n);

33 21/11/2012


• getc

• getc(pointeur_sur_fichier)

• renvoie le caractère lu dans un fichier à l'endroit pointé par le pointeur_sur_fichier et incrémente ce pointé par le pointeur_sur_fichier et incrémente ce pointeur, ou renvoie EOF si on est à la fin du fichier.


Exemple : copier un fichier dans un autre

void main(int argc, char *argv[] )

/* copier le fichier en premier argument dans le fichier en 2ème argument */

{

FILE *fopen(), *pf1, *pf2 ;

int c ;

if (argc <= 2)

printf(" deux arguments SVP...") ;

else

{ pf1 = fopen(argv[1] , "r") ; /* uverture du premier fichier en lecture */

pf2 = fopen(argv[2] , "w") ; /* ouverture du deuxième fichier en écriture */

while ( (c = getc(pf1)) != EOF ) putc(c, pf2) ;

fclose(pf1) ;

fclose(pf2) ;

}

}


• Lecture dans un fichier :

fscanf : lecture analogue à scanf.

Syntaxe :

Nb_lu = fscanf(Pointeur_sur_fichier, format, liste de pointeurs);Nb_lu = fscanf(Pointeur_sur_fichier, format, liste de pointeurs);

Nb_lu est le nombre d'arguments lus et acceptés.

Exemple :

Nb_lu = fscanf(Pointeur_sur_fichier, "%s", Chaîne);


• Dans un fichier texte

• fgetc : ce qui signifie "prend un caractère dans un fichier".fichier".

Exemple :

int caractere;

caractere = fgetc(Pointeur_sur_fichier);


• fgets : ce qui signifie "prend une chaîne dans un fichier".

• Lit un certain nombre de caractères dans un fichier et les met dans une chaîne en ajoutant le caractère nul à la fin.

Exemple :

• fgets(Chaine, 10, Pointeur_sur_fichier);• fgets(Chaine, 10, Pointeur_sur_fichier);

• Lit 10 caractères dans le fichier et les écrits dans Chaine. Un dernier caractère nul est ajouté.

• Si une fin de ligne (EOL) est rencontrée avant le dixième caractère lu, seuls les caractères avant la fin de ligne seront lus et ils seront suivis dans la chaîne par EOL et NULL


• Dans un fichier binaire

• Syntaxe :

• Nb_lu = fread(pointeur_sur_tableau, taille_element, nb_elements, fichier);nb_elements, fichier);

• Nb_lu est égal à nb_elements si l'écriture s'est passée correctement.


• Exemple:

• #include <stdio.h>

• FILE *Pointeur_sur_fichier;

• fopen("C:\FSTT\essai.dat", "wb");• fopen("C:\FSTT\essai.dat", "wb");

• int tableau[5];

• nb = fread(tableau, sizeof(int), 3, Pointeur_sur_fichier);

• Lit des nombres entiers et les range dans les trois premières cellules du tableau ; nb a pour valeur le nombre d'éléments écrits, 3 si tout s'est bien passé.


• Exercice 1:

• Ecrire un programme qui permet de créer un fichier d’étudiants.

• Exercice 2 :• Exercice 2 :

• Ecrire une procédure qui permet de modifier les informations d’un étudiant.

Les pilesLes pilesLes pilesLes piles

• Une pile est un type de données abstrait basé sur lemodèle de données liste, dans lequel les opérationssont réalisées à une extrémité de la liste, appelésommet de la pile.

• Le terme LIFO (Last-In-First-out) est synonyme depile.


• Les opérations sur une pile :

• Empiler(p) : ajout d’un élément au sommet de la pile.

• Dépiler() : enlève un élément de la pile, retourne le sommet de la pile. sommet de la pile.

• EstVide(P) retourne vrai si P est vide.

Empiler Dépiler


• Une pile peut être représentée sous forme d'un tableau :

• 3 ← sommet de la pile

• 4 • 4

• 5

• 6

• 7

• 8


• Empiler :

• Dépiler :


• Implantation d’une pile par un tableau :

• Déclaration :

• #define maxpile 100• #define maxpile 100

• Typedef struct {

• Int tableau[maxpile] ;

• Int sommet ;

• } pile ;


• Initialisation :

• Pile initialiser() {

• Pile p ;• Pile p ;

• p.sommet=0 ;

• return p ;

• }


• Empiler :

• Void empiler(pile *p,int x)

• {• {

• p.tableau[p.sommet]=x ;

• p.sommet+ +;

• }


• Dépiler :

• Int Dépiler(pile p)

• {

• int x=p.tableau[p.sommet] ;• int x=p.tableau[p.sommet] ;

• p.sommet-- ;

• return x ;

• }

• Remarque : les piles peuvent être implémentées par des listes.


• Exercice :

• Améliorer la fonction empiler pour qu’elle affiche un message d’erreur si le sommet dépasse la taille maximum de la pile.

• Ecrire une fonction menu() dont la structure est la suivante :

• Printf_______menu principal__________\n• Printf_______menu principal__________\n

• Printf( ‘ empiler _____________ e\n’) ;

• Printf( ‘ dépiler _____________ d\n’) ;

• Printf( ‘ afficher _____________ a\n’) ;

• Printf( ‘ Quitter _____________ Q\n’) ;

• Ecrire la fonction qui fait appel à ces fonctions.

• Réécrire les fonctions en utilisant le formalisme pointeur.

Les listesLes listesLes listesLes listes

Définitions :

• Une liste est une séquence finie de zéro, un, ou plusieurs éléments d'un type donné. Si les éléments sont de type E, on dit que le type de la liste est "liste sont de type E, on dit que le type de la liste est "liste de E'‘ : listes d'entiers, des listes de nombres réels, des listes de structures, etc.

• Une liste est souvent écrite comme une séquence d'éléments séparés par des virgules et entourée par des parenthèses : (a1,a2, ...an) où les ai sont les éléments de la liste.


Longueur d'une liste :

• La longueur d'une liste est le nombre d'éléments (même les doublons) dans la liste. Si le nombre d'occurrences est zéro, on dit que la liste est vide. d'occurrences est zéro, on dit que la liste est vide.

• EXEMPLES :

• L = (a,b,t,y,a,u) de longueur 6.

• L = (1,2,3,6) de longueur 4


Parties d'une liste :

• Si la liste n'est pas vide, alors elle comprend un premier élément, appelé la tête.

• Le reste de la liste est appelé la queue.

• Si L=(a1,a2, ...an) est une liste, alors pour tous i et j tels que 1≤ i ≤ j ≤ n, (ai,ai+1, ...aj) est une sous-liste de L.


Position d'un élément :

• A chaque élément de la liste est associé une position. Si (a1,a2, ...an) est une liste et n ≥ 1, alors on dit que a1 est le premier élément de la liste, a2 le second, et ainsi de suite, an

étant le dernier. On dit que a est de position i. De plus, on dit étant le dernier. On dit que ai est de position i. De plus, on dit que ai suit ai-1 et précède ai+1.

• Une position contenant l'élément a est une occurrence de a.

• Le nombre de positions dans une liste est égal à sa longueur. Il est possible qu'un même élément apparaisse à plusieurs positions. Il ne faut donc pas confondre position et élément de la liste.


Opérations sur les listes :

• a) Insertion :

• On peut insérer un élément x à la position i d'uneliste L. Cette action consiste à placer x dans la listeL à la ième place, et de décaler les éléments de laliste à partir de la position i d'une position dans laliste (le ième élément devient le ième+1, etc.).


• EXEMPLE :

• L=(2,3,4,2,6,7)

• 1 - Insertion de l'élément 7 à la position 3.

⇒


• ⇒ L=(2,3,7,4,2,6,7)


• ⇒ L=(1,2,3,7,4,2,6,7)

• 3 - Insertion de l'élément 7 à la fin de la liste.

• ⇒ L=(1,2,3,7,4,2,6,7,7)


• b) Suppression :

• supprimer l'occurrence de position i d'une liste,signifie que l'élément de position i dans la liste vaêtre enlevé de la liste.être enlevé de la liste.

• Il est également possible de supprimer un élément xde la liste : Cette opération consiste à supprimertoutes les occurrences x apparaissant dans la liste.Si x n'est pas dans la liste, la suppression est sanseffet.


• EXEMPLE :

• L=(1,2,3,7,4,2,6,7,7)

• 1 - Suppression de l'occurrence de position 2.

⇒

• 1 - Suppression de l'occurrence de position 2.

• ⇒ L=(1,3,7,4,2,6,7,7)

• 2 - Suppression de l'élément 7.

• ⇒ L=(1,3,4,2,6)

• 3 - Suppression de l'élément 5.

• ⇒ L=(1,3,4,2,6)


• c) Recherche :

• La recherche d'un élément x dans une liste est uneopération qui retourne VRAI ou FAUX en fonctionopération qui retourne VRAI ou FAUX en fonctionde la présence ou non de l'élément x dans la liste.Cette opération peut également retourner la positiondu premier élément d'occurrence x rencontré dansla liste, et 0 si l'élément n'existe pas dans la liste.


• d) Concaténation :

• On concatène deux liste L et M en formant une listecommençant par les éléments de L et se poursuivant avec leséléments de M.

• EXEMPLE :

• L=(5,6,7,89) M=(3,5,6,7,8,9,0,23,4)

• La liste résultat de la concaténation de L et M est :

• (5,6,7,89,3,5,6,7,8,9,0,23,4)

• On peut concaténer plus de deux listes.


• e) Autres opérations:

• L'opération first retourne le premier élément de la liste. Le type retour de first est un élément de la liste.

• EXEMPLE : L=(5,6,7,89) first(L)=5 • EXEMPLE : L=(5,6,7,89) first(L)=5

• L'opération last retourne la queue de la liste. Le type retour de last est une liste.

• EXEMPLE : L=(5,6,7,89) last(L)=(6,7,89)

• Ces deux opérations provoquent une erreur si la liste est vide.

• Il est possible de les combiner.

• EXEMPLE : L=(5,6,7,89) first(last(L))=6


• Une manière d'implanter une liste en C est d'utiliser untableau pour stocker les éléments.

• Il est possible de maintenir un compteur du nombred'éléments de la liste dans une variable séparée, et destocker les éléments dans des emplacements contigus dustocker les éléments dans des emplacements contigus dutableau.

• Ce type d’implantation n’est pas pratique à utiliser pourinsérer ou supprimer des éléments dans la liste.

• Il faut à chaque fois décaler tous les éléments du tableau.

Les listes chaLes listes chaLes listes chaLes listes chaînnnnéeseseses

• Une liste chaînée est une structure qui permet de gérer un ensemble d'objet en les chaînant les uns aux autres.

• L'adresse du premier élément appelé tête de la liste permet d'accéder au premier élément. liste permet d'accéder au premier élément.

• Chaque élément est ensuite chaîné au suivant par un pointeur. Le dernier élément est associé à un pointeur contenant la valeur NULL, il est appelé queue de la liste.


• Chaque élément de la liste chaînée est composé de deux informations.

• La valeur de l’élément.

• Un pointeur vers l'élément suivant • Un pointeur vers l'élément suivant

• Il n'existe pas de structure prédéfinie dans C pour gérer une liste. Il est donc nécessaire de la construire à partir d'autres éléments: les types structurés et les pointeurs.


• Pointeurs d’une liste chaînée :


• Déclaration d’une structure liste :

• Typedef struct element *PElement;

• Typedef struct element {

• PElement suivant;• PElement suivant;

• /* informations spécifiques à l’application*/

• } Element;

• Le type Element est une structure contenant au moins un pointeur sur un autre élément.


• Typedef struct {

• PElement premier;

• PElement dernier;

• PElement courant;• PElement courant;

• } liste;


• Opérations usuelles sur les listes :

• Initialisation :

• Void initialiser(liste *L) {• Void initialiser(liste *L) {

• L->premier=NULL;

• L->dernier=NULL;

• L->courant=NULL;

• }


• Test si vide :

• Booleen listevide(liste *L) {

• Return L->premier==NULL;• Return L->premier==NULL;

• }


• Insertion d’un élément :

• L'insertion d'un élément dans une liste chaînée, peut se faire après l'élément courant de la liste.

• Trois cas se présentent alors :

• La liste est vide : dans ce cas, les pointeurs • La liste est vide : dans ce cas, les pointeurs premier, courant et dernier pointent, après insertion de l'élément X, sur X.


• La liste est non vide, et l'élément courant est un élément interne à la liste (courant ne pointe pas sur le dernier élément de la liste).

• Après insertion de l'élément X, l'élément suivant de X sera le suivant de l'élément courant (pointé par courant), l'élément suivant de l'élément courant courant), l'élément suivant de l'élément courant sera X, et l'élément courant sera X.


• 3 opérations à effectuer :

• Remarque :

• L’ordre des opérations est important !!!


• La liste est non vide, et l'élément courant est le dernier élément.

• Après insertion de l'élément X, le suivant du dernier élément sera X, l'élément suivant de X sera nul, et le dernier élément, ainsi que l'élément courant seront X. seront X.


• 3 opérations à effectuer :

• Remarque :

• L’ordre des opérations est important !!!


• Ajout en tête de liste :

• Void insererentete(liste *L, PElement Nouveau) {

• Nouveau->suivant=L->premier;• Nouveau->suivant=L->premier;

• L->premier=Nouveau;

• If(L->dernier==NULL) L->dernier=Nouveau;

• }


• Ajout après l’élément précédent :

• Void insererapres(liste *L, PElement Nouveau, PElement precedent) {

• If(precedent ==NULL) {

• insererentete(L,Nouveau);• insererentete(L,Nouveau);

• }

• Else {

• Nouveau->suivant=precedent->suivant;

• precedent->suivant=Nouveau;

• If(precedent==L->dernier) L->dernier=Nouveau;

• }

• }


• Ajout en fin de liste :

• Void insererenfin(liste *L, PElement Nouveau) {• Void insererenfin(liste *L, PElement Nouveau) {

• Insererapres(L,L->dernier,Nouveau);

• }


• Retrait d’un élément de la liste :

• Retrait en tête d’un élément :

• Retirer l’élément en tête de la liste pointée par L.

• PElement extraireentete(liste *L) {• PElement extraireentete(liste *L) {

• PElement extrait;

• extrait =L->premier;

• If(!listevide(L)) {

• L->premier= L->premier->suivant;

• If(L->premier==NULL) L->dernier=NULL; }

• Return extrait;

• }


• Retrait suivant précédent :

• PElement extraireapres(Liste *L, PElement precedent) {

• PElement extrait;

• If(precedent == NULL) {

• extrait =extraireentete(L);• extrait =extraireentete(L);

• } else { extrait= precedent->suivant;

• If(extrait!=NULL) {

• precedent->suivant=extrait->suivant;

• If(extrait==L->dernier) L->dernier=precedent;

• }

• }

• Return extrait;

• }


• Retrait en fin :

• PElement extraireenfin(Liste *L) {

• PElement extrait,ptc; /* pointeur courant */

• If(listevide(L)) {

• Extrait=NULL;

• } else if(L->premier==L->dernier) { /* un seul élément */

• Extrait=L->premier;

• L->premier=NULL;

• L->dernier=NULL;

• } else { Ptc=L->premier;

• While(ptc->suivant !=L->dernier) ptc->ptc->suivant;

• /* extrait = extraireapres(L,ptc) */

• Extrait= ptc->suivant;

• ptc->suivant=NULL;

• L->dernier=ptc; } return extrait; }


• Parcours de liste :

• Fonction ouvrirliste() permet de se positionner sur le premier élément de la liste :

• Void ouvrirliste(liste *L) {

• L->courant=L->premier; }• L->courant=L->premier; }

• Fonction booléenne finliste() permet de savoir si on a atteint la fin de la liste ouverte :

• Booleen finliste(liste *L) {

• Return L->courant==NULL; }


• Fonction elementcourant() fournit un pointeur sur l’élément courant de la liste et se positionne sur l’élément suivant qui devient l’élément courant :

• PElement elementcourant() {• PElement elementcourant() {

• PElement ptc;

• Ptc=L->courant;

• If(L->courant !=NULL) {

• L->courant=L->courant->suivant; }

• Return ptc; }


• Destruction de liste :

• Il faut faire un parcours de liste avec destruction de chaque élément.

• La tête de liste est réinitialiser.• La tête de liste est réinitialiser.

• Il faut se positionner en début de liste tant qu’on n’a pas atteint la fin de la liste, il prendre l’élément courant et le détruire.

• Le pointeur sur le prochain élément est conservé dans le champs courant de la tête de liste.


• Void detruireliste(liste *L) {

• PElement ptc;

• Ouvrirliste(L);

• While(!finliste(L)) {• While(!finliste(L)) {

• Ptc=elementcourant(L);

• Free(ptc); }

• Initialiser(L); }


• Recopie de liste :

• Transfert la liste L2 dans la liste L1 en réinitialisant L2.

• Void recopieliste(liste *L1,liste *L2) {• Void recopieliste(liste *L1,liste *L2) {

• Detruireliste(L1);

• *L1=*L2;

• Initialiser(L2);

• }


• Exercice d’application 1 :

• On se propose de gérer une liste de personnes avec un programme interactif utilisant un menu et le formalisme liste :

• 1- Insertion en tête de liste.

• 2- Insertion en fin de liste.

• 3- Retrait en tête de liste.

• 4- Retrait en fin de liste.

• 5- Parcours de liste.

• 6- Recherche dans la liste.

• 0- Quitter.



• On se propose de mémoriser des polynômes d’une variable réelle et de réaliser des opérations sur ces polynômes avec un programme interactif utilisant un menu et le formalisme liste :

• 1- Insertion en tête de liste. 7- Insertion ordre croissant• 1- Insertion en tête de liste. 7- Insertion ordre croissant

• 2- Insertion en fin de liste. 8- Insertion ordre décroissant

• 3- Retrait en tête de liste. 9- Valeur P(X) = ?

• 4- Retrait en fin de liste.

• 5- Parcours.

• 6- Recherche dans la liste.

• 0- Quitter.



• La représentation d’un monôme est vue comme suit :

• Exemple :

Coefficient Exposant Pointeur vers le monôme

suivant

• Exemple :

• P(X) = 3X5+2X3+1

P(X) 3 5 2 3 1 0



• Implémenter en C une pile en se basant sur une liste chaînée ?liste chaînée ?

• Opérations sur une pile :

• Empiler : ajouter un élément en tête de la liste.

• Dépiler : enlever un élément en tête de la liste.

Les files

• Définition :

• Une file d’attente est une structure de données telle que :

• L’ajout d’un élément se fait en fin de file d’attente.• L’ajout d’un élément se fait en fin de file d’attente.

• La suppression d’un élément se fait en début de file d’attente.

• Cette structure de données est appelée aussi FIFO :

• First in First out.

Les files

• Opérations sur une file :

• Enfiler : ajouter un élément en fin de la liste.

• Défiler : enlever un élément en tête de la liste.• Défiler : enlever un élément en tête de la liste.

• Implémenter en C une file en se basant sur une liste chaînée ?

Liste doublement chaListe doublement chaListe doublement chaListe doublement chaînnnnéeeee

• Une liste doublement chaînée(appelée aussi symétrique) est une liste telle que chaque élément pointe sur l’élément suivant et sur l’élément précédent.

92 21/11/2012


• L’intérêt majeur des listes symétriques réside dans le fait qu’il est facile d’extraire un élément à partir d’un pointeur sur l’élément à extraire.

• Il n’y a pas besoin de parcourir la liste pour retrouver le précédent. retrouver le précédent.

• La liste symétrique peut se trouver en mémoire centrale ou en mémoire secondaire (fichier en accès direct).

ListeListeListeListe doublement chadoublement chadoublement chadoublement chaînnnnéeeee

• Chaque élément de la liste contient un pointeur sur l’objet de la liste, un pointeur sur l’élément suivant comme pour les listes simples, et un pointeur sur l’élément precedent.

• Un pointeur sur le premier et un pointeur sur le

94 21/11/2012

• Un pointeur sur le premier et un pointeur sur le dernier élément de la liste symétrique.

• On peut parcourir la liste dans les deux sens.


• La fonction void extraireListeSym (ListeS* ls, Element* extrait) ; extrait l’élément pointé par extrait de la liste symétrique ls.

• Dans le cas général où l’élément à extraire se trouve entre deux autres éléments (donc pas en trouve entre deux autres éléments (donc pas en début ou fin de liste),

• on peut facilement définir un pointeur sur le précédent et un pointeur sur le suivant comme l’indique la Figure, et en conséquence, modifier le pointeur precedent du suivant et le pointeur suivant du précédent.

95 21/11/2012


96 21/11/2012


• void insererEnFinDeListeSym (ListeS* ls, PElement nouveau) {

• nouveau->suivant = NULL;

• if (listeVide(ls)) { // liste symétrique vide

• nouveau->precedent = NULL;• nouveau->precedent = NULL;

• ls->premier = nouveau;

• } else {

• nouveau->precedent = ls->dernier;

• ls->dernier->suivant = nouveau;

• }

• ls->dernier = nouveau; }97 21/11/2012


• void extraireListeSym (ListeS* ls, PElement* extrait) {

• if ( (ls->premier==extrait) && (ls->dernier==extrait) ) {

• // suppression de l'unique élément de ls• // suppression de l'unique élément de ls

• ls->premier = NULL;

• ls->dernier = NULL;

• }

98 21/11/2012


• else if (ls->premier == extrait) {

• // suppression du premier de la liste ls

• ls->premier->suivant->precedent = NULL;

• ls->premier = ls->premier->suivant;• ls->premier = ls->premier->suivant;

• }

99 21/11/2012


• else if (ls->dernier == extrait) {

• // suppression du dernier de la liste ls

• ls->dernier->precedent->suivant = NULL;

• ls->dernier = ls->dernier->precedent;• ls->dernier = ls->dernier->precedent;

• }

100 21/11/2012


• else {

• // suppression de extrait entre 2 éléments non nuls

• extrait->suivant->precedent = extrait->precedent;

• extrait->precedent->suivant = extrait->suivant;• extrait->precedent->suivant = extrait->suivant;

• }

• }

101 21/11/2012


• void extraireElement (ListeS* ls, float objet)

• {

• PElement* element = chercherElement (ls, objet);

• if (element != NULL) • if (element != NULL)

• extraireListeSym (ls, element);

• }

102 21/11/2012


• Exercice d’application :

• Réaliser un programme de gestion d’une liste symétrique de réelles ?symétrique de réelles ?

103 21/11/2012

Documents

Cours Structures de Donnees2