Liste doublement chaînée
[Dal]
Messages postés
6198
Date d'inscription
mercredi 15 septembre 2004
Statut
Contributeur
Dernière intervention
13 décembre 2024
-
Modifié le 30 mai 2022 à 02:11
Note : lami20j est l'auteur d'origine de l'astuce.
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînéess (facultatif)
L'implémentation en fonction des besoins et des performances vous appartient.
Les listes doublement chaînées peuvent être utilisées quand plusieurs opérations d'insertion/suppression d'éléments sont nécessaires.
L'allocation de la mémoire est faite au moment de l'exécution.
En revanche, par rapport aux listes simplement chaînées la liaison entre les éléments se fait grâce à deux pointeurs (un qui pointe vers l'élément précédent et un qui pointe vers l'élément suivant).
Le pointeur precedent du premier élément doit pointer vers NULL (le début de la liste).
Le pointeur suivant du dernier élément doit pointer vers NULL (la fin de la liste).
Pour accéder à un élément la liste peut être parcourue dans les deux sens :
En bref, le déplacement se fait dans les deux directions, du premier vers le dernier élément et/ou du dernier vers le premier élément.
L'élément de la liste contiendra un champ donnee, un pointeur precedent et un pointeur suivant.
Les pointeurs precedent et suivant doivent être du même type que l'élément, sinon ils ne pourront pas pointer vers un élément de la liste.
Le pointeur "precedent" permettra l'accès vers l'élément précédent tandis que le pointeur suivant permettra l'accès vers le prochain élément.
Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.
Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition :
Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.
Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.
Toutefois je vous rappelle que cet article est purement didactique.
C'est la raison pour laquelle j'ai écrit une fonction pour chaque opération d'insertion et de suppression.
Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.
La fonction
Pour ajouter un élément dans la liste il y a plusieurs situations :
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes :
La fonction
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes:
La fonction
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes:
La fonction
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
L'insertion s'effectuera avant une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être ni le 1er ni le dernier élément. Dans ce cas il faut utiliser les fonctions d'insertion au début et/ou à la fin de la liste.
Étapes:
La fonction
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
L'insertion s'effectuera après une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste.
Étapes:
La fonction
Par rapport aux listes simplement chaînées où la suppression ne peux pas être faite qu'après un élément désigné, les listes doublement chaînées sont plus maniables grâce aux 2 pointeurs qui permettent de garder une trace en arrière comme en avant.
Pour supprimer un élément dans la liste il y a plusieurs situations :
Toutefois, la suppression au début et à la fin de la liste doublement chaînées ainsi qu'avant ou après un élément revient à la suppression à la position 0 (zéro) ou à la position N (N = nombre d'éléments de la liste) ou ailleurs dans la liste.
Dans le cas des listes doublement chaînées la suppression à n'importe quelle position ne pose pas des problèmes grâce au pointeurs precedent et suivant, qui permettent de garder la liaison entre les éléments de la liste.
C'est la raison pour la quelle nous allons créer une seule fonction.
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Nous distinguons plusieurs situations :
La suppression dans une liste vide n'a pas de sens.
Étapes:
La fonction
Ensuite en utilisant le pointeur suivant ou precedent de chaque élément la liste est parcourue du 1er vers le dernier élément ou du dernier vers le 1er élément.
La condition d'arrêt est donnée par le pointeur suivant du dernier élément qui vaut NULL dans le cas de la lecture du début vers la fin de liste, ou par le pointeur precedent du 1er élément qui vaut NULL, dans le cas d'une lecture de la fin vers le début de la liste.
Les fonctions
La fonction
LISTES DOUBLEMENT CHAINÉES
- Requis
- I. INTRODUCTION
- II. Définition
- III. La construction du prototype d'un élément de la liste
- IV. Opérations sur les listes doublement chaînées
- V. Exemple complet
- VI. Voir aussi
Requis
Les types de donnéesLes structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur
Les listes simplement chaînéess (facultatif)
I. INTRODUCTION
Cet article a pour but la compréhension des listes doublement chaînées.L'implémentation en fonction des besoins et des performances vous appartient.
Les listes doublement chaînées peuvent être utilisées quand plusieurs opérations d'insertion/suppression d'éléments sont nécessaires.
II. Définition
Les listes doublement chaînées sont des structures de données semblables aux listes simplement chaînées .L'allocation de la mémoire est faite au moment de l'exécution.
En revanche, par rapport aux listes simplement chaînées la liaison entre les éléments se fait grâce à deux pointeurs (un qui pointe vers l'élément précédent et un qui pointe vers l'élément suivant).
Le pointeur precedent du premier élément doit pointer vers NULL (le début de la liste).
Le pointeur suivant du dernier élément doit pointer vers NULL (la fin de la liste).
Pour accéder à un élément la liste peut être parcourue dans les deux sens :
- en commençant avec la tête, le pointeur suivant permettant le déplacement vers le prochain élément.
- en commençant avec la queue, le pointeur precedent permettant le déplacement vers l'élément précédent.
En bref, le déplacement se fait dans les deux directions, du premier vers le dernier élément et/ou du dernier vers le premier élément.
III. La construction du prototype d'un élément de la liste
Pour définir un élément de la liste le type struct sera utilisé.L'élément de la liste contiendra un champ donnee, un pointeur precedent et un pointeur suivant.
Les pointeurs precedent et suivant doivent être du même type que l'élément, sinon ils ne pourront pas pointer vers un élément de la liste.
Le pointeur "precedent" permettra l'accès vers l'élément précédent tandis que le pointeur suivant permettra l'accès vers le prochain élément.
typedef struct dl_ElementListe { char *donnee; struct dl_ElementListe *precedent; struct dl_ElementListe *suivant; }dl_Element;
Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.
Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition :
typedef struct dl_ListeRepere { dl_Element *debut; dl_Element *fin; int taille; }dl_Liste;
Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.
Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.
IV. Opérations sur les listes doublement chaînées
Pour l'insertion ainsi que pour la suppression, une seule fonction est largement suffisante si elle est bien conçue en fonction des besoins.Toutefois je vous rappelle que cet article est purement didactique.
C'est la raison pour laquelle j'ai écrit une fonction pour chaque opération d'insertion et de suppression.
A. Initialisation
Prototype de la fonction :void initialisation (Liste *liste);
Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.
La fonction
void initialisation (Liste *liste){ liste->debut = NULL; liste->fin = NULL; taille = 0; }
B. Insertion d'un élément dans la liste
Voici l'algorithme d'insertion et de sauvegarde des éléments :- déclaration d'élément(s) à insérer
- allocation de la mémoire pour le nouvel élément
- remplir le contenu du champ de données
- mettre à jour les pointeurs vers l'élément précédent et l'élément suivant
- mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
- Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
- mettre à jour la taille de la liste
Pour ajouter un élément dans la liste il y a plusieurs situations :
- 1. Insertion dans une liste vide
- 2. Insertion au début de la liste
- 3. Insertion à la fin de la liste
- 4. Insertion avant un élément
- 5. Insertion après un élément
1. Insertion dans une liste vide
Prototype de la fonction :int ins_dans_liste_vide (dl_Liste * liste, char *donnee);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes :
- allocation de la mémoire pour le nouvel élément
- remplir le champ de données du nouvel élément
- le pointeur precedent du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur debut qui vaut NULL)
- le pointeur suivant du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur fin qui vaut NULL)
- les pointeurs debut et fin pointeront vers le nouvel élément
- la taille est mise à jour
La fonction
int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = liste->debut; nouveau_element->suivant = liste->fin; liste->debut = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; }
2. Insertion au début de la liste
Prototype de la fonction :int ins_debut_liste (dl_Liste * liste, char *donnee);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes:
- allocation de la mémoire pour le nouvel élément
- remplir le champ de données du nouvel élément
- le pointeur precedent du nouvel élément pointe vers NULL
- le pointeur suivant du nouvel élément pointe vers le 1er élément
- le pointeur precedent du 1er élément pointe vers le nouvel élément
- le pointeur debut pointe vers le nouvel élément
- le pointeur fin ne change pas
- la taille est incrémentée
La fonction
int ins_debut_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = liste->debut; liste->debut->precedent = nouveau_element; liste->debut = nouveau_element; liste->taille++; return 0; }
3. Insertion à la fin de la liste
Prototype de la fonction :int ins_fin_liste (dl_Liste * liste, char *donnee);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Étapes:
- allocation de la mémoire pour le nouvel élément
- remplir le champ de données du nouvel élément
- le pointeur suivant du nouvel élément pointe vers NULL
- le pointeur precedent du nouvel élément pointe vers le dernier élément (c'est le pointeur fin qui contient pour l'instant son adresse
- le pointeur suivant du dernier élément va pointer vers le nouvel élément
- le pointeur fin pointe vers le nouvel élément
- le pointeur debut ne change pas
- la taille est incrémentée
La fonction
int ins_fin_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = NULL; nouveau_element->precedent = liste->fin; liste->fin->suivant = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; }
4. Insertion avant un élément de la liste
Prototype de la fonction :int ins_avant (dl_Liste * liste, char *donnee, int pos);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
L'insertion s'effectuera avant une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être ni le 1er ni le dernier élément. Dans ce cas il faut utiliser les fonctions d'insertion au début et/ou à la fin de la liste.
Étapes:
- allocation de la mémoire pour le nouvel élément
- remplir le champ de données du nouvel élément
- choisir une position dans la liste (l'insertion se fera après la position choisie)
- le pointeur suivant du nouvel élément pointe vers l'élément courant.
- le pointeur precedent du nouvel élément pointe vers l'adresse sur la quelle pointe le pointeur precedent d'élément courant. (une explication un peu tordue avec l'espoir que l'image vous éclaira ;-)
- le pointeur suivant de l'élément qui précède l'élément courant pointera vers le nouveau élément
- le pointeur precedent d'élément courant pointe vers le nouvel élément
- le pointeurs fin ne change pas
- le pointeur debut change si et seulement la position choisie est la position1
- la taille est incrémentée d'une unité
La fonction
int ins_avant (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant; nouveau_element-> precedent = courant->precedent; if(courant->precedent == NULL) liste->debut = nouveau_element; else courant->precedent->suivant = nouveau_element; courant->precedent = nouveau_element; liste->taille++; return 0; }
5. Insertion après un élément de la liste
Prototype de la fonction :int ins_apres (dl_Liste * liste, char *donnee, int pos);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
L'insertion s'effectuera après une certaine position passée en argument à la fonction.
La position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste.
Étapes:
- allocation de la mémoire pour le nouvel élément
- remplir le champ de données du nouvel élément
- choisir une position dans la liste (l'insertion se fera après la position choisie)
- le pointeur suivant du nouvel élément pointe vers l'adresse sur la quelle pointe le pointeur suivant d'élément courant (voir l'image)
- le pointeur precedent du nouvel élément pointe vers l'élément courant.
- le pointeur precedent de l'élément qui succède l'élément courant pointera vers le nouveau élément
- le pointeur suivant d'élément courant pointe vers le nouvel élément
- le pointeurs debut ne change pas
- le pointeur fin change si et seulement la position choisie est la position du dernier élément (la taille de liste)
- la taille est incrémentée d'une unité
La fonction
int ins_apres (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant->suivant; nouveau_element->precedent = courant; if(courant->suivant == NULL) liste->fin = nouveau_element; else courant->suivant->precedent = nouveau_element; courant->suivant = nouveau_element; liste->taille++; return 0; }
C. Suppression d'un élément dans la liste
Voici l'algorithme de suppression d'un élément de la liste :- utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
- l'élément à supprimer peut se trouver dans n'importe quelle position dans la liste.
Par rapport aux listes simplement chaînées où la suppression ne peux pas être faite qu'après un élément désigné, les listes doublement chaînées sont plus maniables grâce aux 2 pointeurs qui permettent de garder une trace en arrière comme en avant.
- libérer la mémoire occupée par l'élément supprimé
- mettre à jour la taille de la liste
Pour supprimer un élément dans la liste il y a plusieurs situations :
- 1. Suppression au début de la liste
- 2. Suppression à la fin de la liste
- 3. Suppression avant un élément
- 4. Suppression après un élément
- 3. Suppression d'un élément
Toutefois, la suppression au début et à la fin de la liste doublement chaînées ainsi qu'avant ou après un élément revient à la suppression à la position 0 (zéro) ou à la position N (N = nombre d'éléments de la liste) ou ailleurs dans la liste.
Dans le cas des listes doublement chaînées la suppression à n'importe quelle position ne pose pas des problèmes grâce au pointeurs precedent et suivant, qui permettent de garder la liaison entre les éléments de la liste.
C'est la raison pour la quelle nous allons créer une seule fonction.
- si nous voulons supprimer l'élément au début de la liste nous choisirons la position zéro
- si nous voulons supprimer l'élément à la fin de la liste nous choisirons la position N (le nombre d'éléments)
- si nous désirons supprimer un élément quelconque alors on choisit sa position dans la liste
Suppression dans la liste
Prototype de la fonction :int supp(dl_Liste *liste, int pos);
La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.
Nous distinguons plusieurs situations :
- suppression à la position 1 dans une liste avec un seul élément
- suppression à la position 1 dans une liste avec plusieurs éléments
- suppression à la dernière position (le dernier élément)
- suppression ailleurs dans la liste à une certaine position
La suppression dans une liste vide n'a pas de sens.
Étapes:
- la position choisie est 1 (le cas de suppression du 1er élément de la liste)
- le pointeur supp_element contiendra l'adresse du 1er élément
- le pointeur debut contiendra l'adresse contenue par le pointeur suivant du 1er élément que nous voulons supprimer (si ce pointeur vaut NULL alors nous mettons à jour le pointeur fin puisqu'on est dans le cas d'une liste avec un seul élément, sinon nous faisons pointer le pointeur precedent du 2ème élément vers NULL)
- la position choisie est égale avec le nombre d'éléments de la liste
- le pointeur supp_element contiendra l'adresse du dernier élément
- nous faisons pointer le pointeur suivant de l'avant dernier élément (c'est l'élément vers le quel pointe le pointeur <precedent> de dernier élément), vers NULL
- nous mettons à jour le pointeur fin
- la position choisie est aléatoire dans la liste
- le pointeur supp_element contiendra l'adresse de l'élément à supprimer
- le pointeur suivant d'élément qui précède l'élément à supprimer pointe vers l'adresse contenu par le pointeur suivant d'élément à supprimer
- le pointeur precedent d'élément qui succède l'élément à supprimer pointe vers l'adresse contenu par le pointeur precedent d'élément à supprimer.
- la taille de la liste sera décrémentée d'un élément
La fonction
int supp(dl_Liste *liste, int pos){ int i; dl_Element *supp_element,*courant; if(liste->taille == 0) return -1; if(pos == 1){ /* suppresion de 1er élément */ supp_element = liste->debut; liste->debut = liste->debut->suivant; if(liste->debut == NULL) liste->fin = NULL; else liste->debut->precedent == NULL; }else if(pos == liste->taille){ /* suppression du dernier élément */ supp_element = liste->fin; liste->fin->precedent->suivant = NULL; liste->fin = liste->fin->precedent; }else { /* suppression ailleurs */ courant = liste->debut; for(i=1;i<pos;++i) courant = courant->suivant; supp_element = courant; courant->precedent->suivant = courant->suivant; courant->suivant->precedent = courant->precedent; } free(supp_element->donnee); free(supp_element); liste->taille--; return 0; }
D. Affichage de la liste
Pour afficher la liste entière nous pouvons nous positionner au début de la liste ou à la fin de la liste (le pointeur debut ou fin le permettra).Ensuite en utilisant le pointeur suivant ou precedent de chaque élément la liste est parcourue du 1er vers le dernier élément ou du dernier vers le 1er élément.
La condition d'arrêt est donnée par le pointeur suivant du dernier élément qui vaut NULL dans le cas de la lecture du début vers la fin de liste, ou par le pointeur precedent du 1er élément qui vaut NULL, dans le cas d'une lecture de la fin vers le début de la liste.
Les fonctions
void affiche(dl_Liste *liste){ /* affichage en avançant */ dl_Element *courant; courant = liste->debut; /* point du départ le 1er élément */ printf("[ "); while(courant != NULL){ printf("%s ",courant->donnee); courant = courant->suivant; } printf("]\n"); } void affiche_inv(dl_Liste *liste){ /* affichage en reculant */ dl_Element *courant; courant = liste->fin; /* point du départ le dernier élément */ printf("[ "); while(courant != NULL){ printf("%s : ",courant->donnee); courant = courant->precedent; } printf("]\n"); }
E.Destruction de la liste
Pour détruire la liste entière, j'ai utilisé la suppression à la position 1 tant que la taille est plus grande que zéro.La fonction
void detruire(dl_Liste *liste){ while(liste->taille > 0) supp(liste,1); }
V. Exemple complet
dliste.h
/* ---------- dliste.h ----------- */ typedef struct dl_ElementListe{ char *donnee; struct dl_ElementListe *precedent; struct dl_ElementListe *suivant; } dl_Element; typedef struct dl_ListeRepere{ dl_Element *debut; dl_Element *fin; int taille; } dl_Liste; /* initialisation de la liste */ void initialisation (dl_Liste * liste); dl_Element *alloc (dl_Element * nouveau_element); /* INSERTION */ int ins_dans_liste_vide (dl_Liste * liste, char *donnee); int ins_debut_liste (dl_Liste * liste, char *donnee); int ins_fin_liste (dl_Liste * liste, char *donnee); int ins_apres (dl_Liste * liste, char *donnee, int pos); int ins_avant (dl_Liste * liste, char *donnee, int pos); /* SUPPRESSION */ int supp(dl_Liste *liste, int pos); void affiche (dl_Liste * liste); /**************************/ void affiche_inv (dl_Liste * liste); void detruire (dl_Liste * liste); /* -------- FIN liste.h --------- */
dliste_function.h
/***************************\ * dliste_function.h * \***************************/ void initialisation (dl_Liste * liste){ liste->debut = NULL; liste->fin = NULL; liste->taille = 0; } int insertion_dans_liste_vide (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = NULL; liste->debut = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; } int ins_debut_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->precedent = NULL; nouveau_element->suivant = liste->debut; liste->debut->precedent = nouveau_element; liste->debut = nouveau_element; liste->taille++; return 0; } int ins_fin_liste (dl_Liste * liste, char *donnee){ dl_Element *nouveau_element; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); nouveau_element->suivant = NULL; nouveau_element->precedent = liste->fin; liste->fin->suivant = nouveau_element; liste->fin = nouveau_element; liste->taille++; return 0; } int ins_apres (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant->suivant; nouveau_element->precedent = courant; if(courant->suivant == NULL) liste->fin = nouveau_element; else courant->suivant->precedent = nouveau_element; courant->suivant = nouveau_element; liste->taille++; return 0; } int ins_avant (dl_Liste * liste, char *donnee, int pos){ int i; dl_Element *nouveau_element, *courant; if ((nouveau_element = alloc (nouveau_element)) == NULL) return -1; strcpy (nouveau_element->donnee, donnee); courant = liste->debut; for (i = 1; i < pos; ++i) courant = courant->suivant; nouveau_element->suivant = courant; nouveau_element-> precedent = courant->precedent; if(courant->precedent == NULL) liste->debut = nouveau_element; else courant->precedent->suivant = nouveau_element; courant->precedent = nouveau_element; liste->taille++; return 0; } int supp(dl_Liste *liste, int pos){ int i; dl_Element *supp_element,*courant; if(liste->taille == 0) return -1; if(pos == 1){ /* suppresion de 1er élément */ supp_element = liste->debut; liste->debut = liste->debut->suivant; if(liste->debut == NULL) liste->fin = NULL; else liste->debut->precedent == NULL; }else if(pos == liste->taille){ /* suppression du dernier élément */ supp_element = liste->fin; liste->fin->precedent->suivant = NULL; liste->fin = liste->fin->precedent; }else { /* suppression ailleurs */ courant = liste->debut; for(i=1;i<pos;++i) courant = courant->suivant; supp_element = courant; courant->precedent->suivant = courant->suivant; courant->suivant->precedent = courant->precedent; } free(supp_element->donnee); free(supp_element); liste->taille--; return 0; } void detruire(dl_Liste *liste){ while(liste->taille > 0) supp(liste,1); } dl_Element *alloc (dl_Element * nouveau_element){ if ((nouveau_element = (dl_Element *) malloc (sizeof (dl_Element))) == NULL) return NULL; if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char))) == NULL) return NULL; return nouveau_element; } int menu (dl_Liste *liste){ int choix; if (liste->taille == 0){ printf ("1. Ajout du 1er element\n"); printf ("2. Quitter\n"); } else{ printf ("1. Ajout au debut de la liste\n"); printf ("2. Ajout a la fin de la liste\n"); printf ("3. Ajout avant la position specifie\n"); printf ("4. Ajout apres la position specifie\n"); printf ("5. Suppression à la position specifie\n"); printf ("6. Detruire la liste\n"); printf ("7. Quitter\n"); } printf ("\n\nFaites votre choix : "); scanf ("%d", &choix); getchar(); if(liste->taille == 0 && choix == 2) choix = 7; return choix; } int supp(dl_Liste *liste, int pos); void affiche(dl_Liste *liste){ dl_Element *courant; courant = liste->debut; printf("[ "); while(courant != NULL){ printf("%s ",courant->donnee); courant = courant->suivant; } printf("]\n"); } void affiche_inv(dl_Liste *liste){ dl_Element *courant; courant = liste->fin; while(courant != NULL){ printf("%s : ",courant->donnee); courant = courant->precedent; } printf("\n"); } /* -------- FIN dliste_function.h --------- */
dliste.c
/**********************\ * dliste.c * \**********************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "dliste.h" #include "dliste_function.h" int main (void) { int choix = 0,pos; char *donnee; donnee = malloc(50); dl_Liste *liste; dl_Element *pilote = NULL; liste = (dl_Liste *) malloc (sizeof(dl_Liste)); initialisation(liste); while(choix != 7){ choix = menu(liste); switch(choix){ case 1: printf("Entrez un element : "); scanf("%s",donnee); getchar(); if(liste->taille == 0) insertion_dans_liste_vide(liste,donnee); else ins_debut_liste (liste, donnee); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 2: printf("Entrez un element : "); scanf("%s",donnee); getchar(); ins_fin_liste (liste, donnee); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 3: if(liste->taille == 1){ printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n"); break; } printf("Entrez un element : "); scanf("%s",donnee); getchar(); do{ printf("Entrez la position : "); scanf("%d",&pos); }while (pos < 1 || pos > liste->taille); getchar(); ins_avant(liste,donnee,pos); printf("%d elements: deb=%s fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 4: if(liste->taille == 1){ printf("Utiliser l'insertion au debut ou a la fin (Entree Menu : 1 ou 2)\n"); break; } printf("Entrez un element : "); scanf("%s",donnee); getchar(); do{ printf("Entrez la position : "); scanf("%d",&pos); }while (pos < 1 || pos > liste->taille); getchar(); ins_apres(liste,donnee,pos); printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); affiche(liste); break; case 5: do{ printf("Entrez la position : "); scanf("%d",&pos); }while (pos < 1 || pos > liste->taille); getchar(); supp(liste,pos); if(liste->taille != 0) printf("%d elements: deb=%s,fin=%s ", liste->taille,liste->debut->donnee,liste->fin->donnee); else printf("liste vide : %d elements",liste->taille); affiche(liste); break; case 6: detruire(liste); printf("la liste a ete detruite : %d elements\n",liste->taille); break; } } return 0; } /* -------- FIN dliste.c --------- */