Donnez votre avis

Manipulation des listes linéaires simplement chaînées

Posez votre question

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;
}

A voir également

Ajouter un commentaire

Commentaires

Commenter la réponse de begueradj
Les tops du mois