Manipulation des listes linéaires simplement chaînées
Manipulation des listes simplement chainées
Définition d'une liste chaînée
struct pointeur{
int entier;/* on s'est mis d'accord pour que notre chaîne traite des entiers*/
struct pointeur *suivant;/* pour pointer sur l'élément suivant de la chaîne*/
};
Le langage C nous permet de créer nos propres types; à ce titre, on va définir un type "cellule" qui nous servira de moule pour toute cellule de la chaîne qui sera implémentée:
typedef struct pointeur cellule;
Création d'une liste linéaire chaînée simple
La fonction suivante va servir à créer une liste chaînée simple. Elle va retourner la tête de la liste ainsi créée:
cellule *creation_liste_chainee_1(){
char reponse;/* confirmation ou non d'ajout d'un élément à la liste */
do{
clrscr(); /* pour effacer l'écran, il faut inclure <conio.h> */
puts("Souhaitez-vous ajouter un élément à votre liste ? (o/n) : ");
scanf("%c",&reponse);
}while((rep!='o')&&(reponse!='n')&&(reponse!='O')&&(reponse!='N');
/*retaper si autre chose que N,O,o,n est saisi*/
if((reponse=='o')||(reponse=='O')) {
/*si le user souhaite effectivement saisir un élement*/
cellule*ptr_tampon=NULL; /*il faut initialiser votre pointeur intermédiaire à NULL pour qu'il ne pointe pas aléatoirement sur un élément mémoire*/
ptr_tampon=(cell*)malloc(sizeof(cell)); /*allocation d'un espace mémoire pour la nouvelle cellule de la chaîne*/
puts("Veuillez saisir votre entier : ");
scanf("%3d",&ptr_tampon->entier);
ptr_tampon->suivant=tete_de_liste;
tete_de_liste=ptr_tampon;
}
return tete_de_liste;/*notre fonction va retourner la tête de la liste car on en aura besoin*/
}
Remarque:
En effet, l'exécution de la fonction précédente a pour effet l'insertion de chaque élément au début de la liste ce qui aura pour effet d'inverser la liste d'entiers ainsi saisie.
Pour remédier à ce problème, on va implémenter une fonction qui crée la liste d'entier et insère chaque élément arrivant à la fin de la liste, comme suit:
cellule* creation_liste_chainee_2()
{
cellule*precedent=NULL; // Pour le pointeur qui sauvegarde l'adresse du pointeur précédent déjà crée
cell*actual=NULL; // Pour le pointeur courant
int datum;
int err;
do
{
puts(" Veuiellez saisir un entier (une lettre pour arreter) : ");
err=scanf("%d",&datum);
if(err<=0) break; // Pour rendre le nombre de variables lues sans erreur
actual=(cellule*)malloc(sizeof(cellule));
actual->entier=datum;
if(precedent==NULL)
{
tete_de_liste=actual;
}else
{
precedent->suivant=actual;
}
precedent=actual;
}while(1); // fin de la boucle do
actual->suivant=NULL;
return tete_de_liste;
}
Ce document intitulé « Manipulation des listes linéaires simplement chaînées » issu de CodeS SourceS (codes-sources.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.