1-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;
2-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éja 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;
}