Date création : 05-01-2009 12:43:34
Date de la dernière modification : 05-01-2009 18:48:45
 Vous êtes dans : Langage C Astuces / ExercicesRecquis La connaissances de mécanisme des listes simplement chaînées et recquis pour la compréhension de cet exercice.
EnnoncéCréer une liste chaînée de nombres entiers, dans l'ordre d'insertion des éléments.
SolutionAvec votre editeur de texte préféré créez un fichier liste_dans_ordre.c et ecrivez dédans le code ci-dessous :
#include <stdio.h>
#include "liste.h"
int main()
{
Liste *L;
L=CreerListeDansOrdre(L);
AfficheListe(L);
ViderListe(&L);
return 0;
}
|
Compilation Les fichiers liste.h, liste_funct.c et liste_dans_ordre.c se trouvent dans le même répertoire
$ gcc -c liste_funct.c liste_dans_ordre.c
$ gcc liste_funct.o liste_dans_ordre.o -o liste_dans_ordre |
ExplicationToute les fonctions pour l'implémentation de la liste se trouvent dans le fichier liste_funct.c.
Pour pouvoir construire une liste avec les éléments dans l'ordre d'insertion, il faut toujours faire l'insertion à la fin de la liste.
C'est le rôle de la fonction InsertionFinListe qui prends comme argument un pointeur de type liste et un entier.
Au début, après l'initialisation, le pointeur liste *L vaut NULL (pointe vers le pointeur NULL).
Le 1ère élément inséré sera le début et la fin de la liste.
L'insertion des éléments suivant se fera selon l'algorithme suivant :
- déplacement à l'aide d'un pointeur de type liste vers la fin de la liste (la boucle for) et ensuite l'insertion de nouveau élément à la position trouvée et ainsi de suite pour chaque nouveau élément.
Pour afficher la liste se fera en affichant un par un les éléments en partant de début de la liste (fonction AfficherListe)
Après l'affichage de la liste, nous utiliserons la fonction ViderListe pour libérer la mémoire utilisé.
Exemples exécution
lami20j@debian:~/c_exercices$ ./liste_dans_ordre
Entrez numéro : 1
Continuer ? o/n : o
Entrez numéro : 2
Continuer ? o/n : o
Entrez numéro : 3
Continuer ? o/n : n
1 2 3 |
liste.h
#ifndef __LISTE__
#define __LISTE__
typedef struct Element{
int donnee;
struct Element *suivant;
}Liste;
Liste *InitialiserListe(Liste *L);
Liste *InsertionDebutListe(Liste *L,int donnee);
Liste *InsertionFinListe(Liste *L,int donnee);
Liste *CreerListeDansOrdre();
Liste *CreerListeInverse();
void ViderListe(Liste **L);
void AfficheListe(Liste *L);
#endif
|
liste_funct.c
#include "liste.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
Liste *InitialiserListe(Liste *L){
return NULL;
}
Liste *alloc(){
return (Liste *)malloc(sizeof(Liste));
}
Liste *InsertionDebutListe(Liste *L,int donnee){
Liste *nouveau;
/* création de nouveau élément */
nouveau = alloc();
nouveau->donnee = donnee;
nouveau->suivant = NULL;
/* le pointeur suivant du nouveau élément
pointe sur le 1er élément de la liste */
nouveau->suivant=L;
/* retourne du 1er élément de la liste */
return nouveau;
}
Liste *CreerListeInverse(){
Liste *L;
char c = 'o';
int N;
L=InitialiserListe(L);
while(c=='o'){
printf("Entrez numéro : ");
scanf("%d",&N);
getchar();
L = InsertionDebutListe(L,N);
printf("Continuer ? o/n : ");
c=getchar();
}
return L;
}
Liste *InsertionFinListe(Liste *L,int donnee){
Liste *nouveau,*pL;
/* création de nouveau élément */
nouveau = alloc();
nouveau->donnee = donnee;
nouveau->suivant = NULL;
/* si la liste est vide, nouveau c'est le 1er élément */
if(L==NULL)
L=nouveau;
else{ /* parcours de la liste jusqu'au dernier élément */
for(pL=L;pL->suivant!=NULL;pL=pL->suivant)
;
pL->suivant=nouveau; /* le pointeur suivant du dernier élément pointe vers le nouveau élément */
}
return L;
}
Liste *CreerListeDansOrdre(){
Liste *L;
char c = 'o';
int N;
L=InitialiserListe(L);
while(c=='o'){
printf("Entrez numéro : ");
scanf("%d",&N);
getchar();
L = InsertionFinListe(L,N);
printf("Continuer ? o/n : ");
c=getchar();
}
return L;
}
void AfficheListe(Liste *L){
Liste *pL;
for(pL=L;pL!=NULL;pL=pL->suivant)
printf("%d ",pL->donnee);
printf("\n");
}
void ViderListe(Liste **L){
Liste *courant;
while(*L!=NULL){
courant=*L;
*L=(*L)->suivant;
free(courant);
}
*L=NULL;
}
|
|
