/* Programme de gestion de listes chaînées d'entiers */ /* Auteur : Maude Manouvrier - Univ. Paris-Dauphine */ */ Derniere MAJ : 13/10/2004 */ #include #include /* Déclaration d'un type élément de liste chaînée */ typedef struct lis { /* Valeur de l'élément */ int iValeur; /* Pointeur sur l'élément suivant */ struct lis* suivant; } *element; /* Déclaration d'un type liste chaînée */ typedef struct t { /* pointeurs sur le premier élément de la liste, sur le dernier */ /* et sur l'élément courant */ element prem,der,cour; } *liste; /* Fonction de création d'une liste */ /* Paramètres d'entrée : Aucun */ /* Paramètre de sortie : une liste */ liste creer_liste() { /* Déclaration d'une liste locale */ liste Liste_Entier; /* Allocation mémoire de la liste */ Liste_Entier = (liste)malloc(sizeof(struct t)); /* Allocation mémoire des pointeurs prem, der, et cour de la liste */ /* au départ, la liste est vide, les pointeurs ne pointent sur rien. */ /* Ceci est une allocation multiple */ Liste_Entier->prem=Liste_Entier->der=Liste_Entier->cour = NULL; /* La liste est retournée */ return Liste_Entier; } /* Fonction d'insertion après la position courante d'un élément */ /* dans une liste */ /* Paramètres d'entrée : */ /* liste Liste_Entier : liste où a lieu l'insertion */ /* int iVal : valeur de l'élément */ /* Paramètre de sortie : rien */ void inserer_apres(liste Liste_Entier,int iVal) { /* Element à insérer */ element Element_Liste = NULL; /* Allocation mémoire de l'élément */ Element_Liste = (element)malloc(sizeof(struct lis)); /* Initialisation de la valeur de e */ Element_Liste->iValeur = iVal; /* S'il n'y a pas d'élément dans la liste */ if (Liste_Entier->prem == NULL) { /* prem, der et cour pointent sur e */ Liste_Entier->prem=Liste_Entier->der=Liste_Entier->cour = Element_Liste; /* Il n'y a pas d'élément suivant */ Element_Liste->suivant = NULL; } /* Fin de S'il n'y a pas d'élément dans la liste */ /* Si la liste est non vide */ else /* Si l'élément courant n'est pas le dernier */ if(Liste_Entier->cour!=Liste_Entier->der) { /* Element_Liste pointe sur l'élément suivant de l'élément courant */ Element_Liste->suivant = Liste_Entier->cour->suivant; /* Le suivant de l'élément courant est e */ Liste_Entier->cour->suivant = Element_Liste; /* L'élément courant est Element_Liste */ Liste_Entier->cour = Element_Liste; } /* Fin de Si l'élément courant n'est pas le dernier */ /* Si l'élément courant est le dernier élément */ else { /* Element_Liste n'a pas de suivant */ Element_Liste->suivant = NULL; /* L'élément suivant de l'élément courant est Element_Liste */ Liste_Entier->cour->suivant = Element_Liste; /* Element_Liste est l'élément courant et le dernier élément */ Liste_Entier->cour = Liste_Entier->der = Element_Liste; } /* Fin de Si l'élément courant est le dernier élément */ } /* Fonction qui déplace l'élément courant à la position iPosition */ /* A la sortie de la fonction le pointeur cour pointera sur l'élément */ /* de position iPosition */ /* Paramètres d'entrée : */ /* liste Liste_Entier : liste où a lieu le déplacement */ /* du pointeur cour */ /* int iPosition : Position où déplacer cour */ /* Paramètre de sortie : rien */ void deplacer(liste Liste_Entier,int iPosition) { /* Compteur */ int i; /* il fuadrait tester idéalement si iPosition n'est pas supérieur */ /* au nombre d'élements dans la liste, je vous laisse le faire */ /* On place le pointeur cour au début de la liste */ Liste_Entier->cour=Liste_Entier->prem; /* On deplace le pointeur cour du début à la position iPosition */ /* à l'aide des pointeurs suivant */ for(i=0;icour=Liste_Entier->cour->suivant; printf("élément de position %d : %d\n",iPosition,Liste_Entier->cour->iValeur); } /* Fonction supprime l'élément de la position iPosition */ /* Paramètres d'entrée : */ /* liste Liste_Entier : liste où a lieu la suppression */ /* int iPosition : Position de l'élément à supprimer */ /* Paramètre de sortie : rien */ void supprimer(liste Liste_Entier,int iPosition) { /* Variable locale pour désallouer l'élément à supprimer */ element Element_Liste = NULL; /* Compteur */ int i; /* Si la liste est non vide */ if(Liste_Entier!=NULL) { /* Si la liste contient un seul élément, elle devient vide */ if(Liste_Entier->prem=Liste_Entier->der) { /* On recopie l'élément à supprimer */ Element_Liste=Liste_Entier->cour; Liste_Entier->prem=Liste_Entier->der=Liste_Entier->cour=NULL; /* Desallocation mémoire de l'element a supprimer */ free(Element_Liste); } /* Sinon Si l'élément à supprimer est le premier */ else if(iPosition==1) { /* On place le pointeur cour sur l'élément à supprimer */ /* et on copie l'élément à supprimer dans Element_Liste */ Element_Liste=Liste_Entier->cour=Liste_Entier->prem; /* On met à jour cour et prem qui maintenant doivent */ /* correspondre au deuxième élément, le premier devant */ /* être supprimé */ Liste_Entier->cour=Liste_Entier->cour->suivant; Liste_Entier->prem=Liste_Entier->prem->suivant; /* Desallocation mémoire de l'element a supprimer */ free(Element_Liste); } /* Si l'élément à supprimer n'est pas le premier */ else { /* On place le pointeur cour sur l'élément à supprimer */ deplacer(Liste_Entier,iPosition); printf("élément à supprimer : %d\n",Liste_Entier->cour->iValeur); /* Si l'élément à supprimer est le dernier élément de la liste */ if(Liste_Entier->cour==Liste_Entier->der) { /* On recopie l'élément à supprimer */ Element_Liste=Liste_Entier->cour; /* On place le pointeur cour juste avant l'élément à supprimer */ deplacer(Liste_Entier,iPosition-1); /* On met à jour en conséquence : l'avant dernier élément devient */ /* le dernier de la liste */ Liste_Entier->der=Liste_Entier->cour; Liste_Entier->cour->suivant=NULL; /* Desallocation mémoire de l'element a supprimer */ free(Element_Liste); } /* Si l'élément à supprimer est au milieur de la liste */ else { /* On recopie l'élément à supprimer */ Element_Liste=Liste_Entier->cour; /* On place le pointeur cour juste avant l'élément à supprimer */ deplacer(Liste_Entier,iPosition-1); /* On met à jour en conséquence : l'élément précédent a pour suivant */ /* le suivant de l'élément à supprimer */ Liste_Entier->cour->suivant=Element_Liste->suivant; /* Desallocation mémoire de l'element a supprimer */ free(Element_Liste); } } } /* Si la liste est vide on ne fait rien */ else printf("Liste vide\n"); } /**************************************************************************/ /* Programme principal */ /**************************************************************************/ void main() { /* Déclaration d'une liste */ liste l; /* Déclaration d'un compteur */ int iCompteur; int iPosition; /* Création de la liste */ l = creer_liste(); /* Pour les entiers de 1 à 5 */ for(iCompteur=1;iCompteur<=5;iCompteur++) { /* Ajout de l'entier dans la liste */ inserer_apres(l,iCompteur); /* Affichage de l'élément courant */ printf("Courant = %d\n",l->cour->iValeur); } /* Affichage de la liste */ /* On positionne le pointeur courant sur le premier élément */ l->cour = l->prem; printf("Liste dans sa totalité :"); /* Tant qu'on est pas au dernier élément */ while(l->cour!=l->der) { /* Affichage de la valeur de l'élément courant */ printf("%d ",l->cour->iValeur); /* On passe au suivant */ l->cour = l->cour->suivant; } /* Affichage du dernier élément */ printf("%d\n",l->der->iValeur); iPosition=1; supprimer(l,iPosition); l->cour=l->prem; printf("Liste apres la suppression de l'élement de position %d : ",iPosition); /* Tant qu'on est pas au dernier élément */ while(l->cour!=l->der) { /* Affichage de la valeur de l'élément courant */ printf("%d ",l->cour->iValeur); /* On passe au suivant */ l->cour = l->cour->suivant; } /* Affichage du dernier élément */ printf("%d\n ",l->der->iValeur); }