Ce programme a été réalisé en grosse partie grâce à l'IUT où j'ai étudié. Les listes chaînées forment une structure dynamique qui permet de stocker les informations de manière non indéxée ce qui a pour avantage d'insérer plus facilement une valeur et surtout de créer une structure plus complexe, comme par exemple un arbre, voir une forêt. La source de chaque programme se trouve en bas de page.





0x01. PRINCIPES


Une liste chainée commence avec une tête, et se finit par une queue. Entre la tête et la queue il y a des éléments, qui se suivent par une propriété spéciale de la structure qui pointe vers elle même. La fin d'une liste chainée se termine par un objet dont l'élément suivant est nul, indéterminé.


Tete > élément_1 > élément_2 > Queue

Tete->suivant = élément_1
Tete->suivant->suivant = élément_2
Tete->suivant->suivant->suivant = Queue

Queue->suivant = RIEN 


RIEN dans bien des langages se traduit par NULL 



0x02. RAPPELS SUR LES POINTEURS


- Les adresses sont contigües: 0x00000001, 0x00000002
- 2 variables ne peuvent avoir la même adresse sans être =
- A la fin d'un "for" la condition est remplie:


for( p=m ; p!=NULL ; p=p->s );
// En sortant p vaut NULL 


- Un pointeur est une variable dynamique qu'on peut déplacer sur l'adrese d'une autre


int *p, *q;
p=1;    // On définit l'adresse de 'p' à 1, on ne peut pas écrire l'adresse mémoire la variable va être.
q=p;    // La variable 'q' connait l'adresse de 'p', elle connait donc aussi son contenu.
*p=1;   // Si 'p' est initialisé à 1 alors 'q' aura pour valeur 1. 


- On peut allouer un emplacement mémoire à un pointeur sans forcément lui mettre un contenu.


int *p;
 
// On alloue 'sizeof(int)' octets à la variable 'p' en convertissant cette allocation au type de 'p'.
p=(int*)malloc(sizeof(int));
 
// On alloue 10 * 'sizeof(int)' c'est à dire ici 10 * 4 octets.
p=(int*)malloc(10*sizeof(int));   


Voici un programme récapitulatif :


#include <conio.h>    // getch  , clrscr
#include <stdio.h>    // printf , scanf
#include <malloc.h>   // malloc
 
 
// EXPLICATIONS SUR LES POINTEURS //////////////////////////////////////////////
void main()
{
unsigned int N;   // Pour l'allocation...
unsigned int i;   // Variable d'index du 'for'
int *aa,*bb,cc;
aa=(int*)malloc(sizeof(int));   // Initialisation d'un pointeur par la taille 
                                // minimale de son type
bb=(int*)malloc(sizeof(int));
cc=999;                 // Affectation de 'cc' (variable)
*aa=4;                  // Le contenu de 'aa' vaut 4
*bb=*aa;                // Dans 'bb' on met 'aa'
cc=*bb;                 // cc = *bb = 4 , cc n'est plus égale à 999
 
printf("/n/n** TEST D ADRESSE - 1 **");
printf("/na la declaration:");
printf("/naa= %d",aa);
printf("/nbb= %d",bb);
printf("/ncc= %d",&cc);   // Il faut remarque le symbole '&'
                          // marquant le passage par adresse
 
printf("/n/n** TEST DE CONTENU **");
printf("/nTaille de aa= %d",sizeof(aa));
printf("/naa= %d",*aa);
printf("/nbb= %d",*bb);
printf("/ncc= %d",cc);
 
// &cc=bb;   -> On ne peut pas écrire l'adresse mémoire d'une variable
// bb=1;     -> ni d'un pointeur, du moins par cette méthode.
 
aa=&cc;   // Par contre un pointeur peut pointer sur l'adresse d'une variable
bb=aa;    // 'bb' connait l'adresse de 'aa'
          // Ici tout le monde se connait...
 
printf("/n/n** TEST D ADRESSE - 2 **");
printf("/naa= %d",aa);
printf("/nbb= %d",bb);
printf("/ncc= %d",&cc);
 
getch();
 
printf("/n/nUn pointeur est un tableau dynamique de taille N/n");
printf("Entrer le nombre d'octets à allouer : ");
 
// A remarquer que la fonction 'scanf' passe justement par l'adresse pour
// écrire le contenu d'une variable, pour écrire le contenu on est obligé 
// de connaitre son adresse ou son nom. L'homme connait son nom, la machine
// connait son adresse.
scanf("%d",&N);
 
// Initialisation d'un pointeur par une taille voulue
// aa [0]  aa [1]  ... aa [N-1]  aa [N]  aa [?] 
// Il faut faire attention à ne pas dépasser la limite sinon on va
// dans une zone mémoire inconnue.
aa=(int*)malloc(N*sizeof(int));   
 
 
printf("/n/n** TEST D ALLOCATION **");
printf("/n/nValeurs initialisees par iteration - var: "int i":");
 
// aa [0] =0; aa [1] =1; ... aa [9] =9;
// On peut parcourir selon le type de donnée un pointeur comme un tableau
// C'est pourquoi un pointeur est aussi un tableau dynamique
for(i=0;i<N;i++)
  aa [i] =i;      
 
for(i=0;i<N;i++)
  printf("/n%d",aa [i] );
 
getch();
} 




0x03. CREATION


Décomponsons l'allocation mémoire dans le cas d'un objet de type 'liste'. A noter que cette décomposition est valable pour tout types de varibales déclarer en tant que pointeurs, il suffit de remplacer 'liste' par le type de la variable comme montré ci-dessus.


liste *p = (liste*)malloc(sizeof(liste)); 
liste                        la structure de la liste, un type est défini par typedef : liste 
*                            le symbole du type de donnée dynamique (pointeur) 
p                            la variable p est donc un pointeur de type liste 
(liste*)                     ceci est un caste on associe à un type une taille : uniquement avec les pointeurs 
sizeof(liste)                sizeof : taille de liste, pour associer l'espace mémoire 
malloc(sizeof(liste));       malloc associe un espace mémoire de la taille de liste pour p  

// STRUCTURE D UNE LISTE CHAINEE ///////////////////////////////////////////////
typedef struct list
{
  int n;                // Sa valeur peut contenir autant 
  //  [...]               // de types de donnée que voulu
                        // quelque soit le type de données. 
  struct list *suivant; // Le maillon de la chaine
} liste;                // Permet d'écrire "liste" au lieu de "struct list"
                        // On a défini on nouveau type de donnée 'liste'
 
 
 
 
 
void main()
{
liste *ma_l=(liste*)malloc(sizeof(liste));         // Initialisation de 
liste *p=(liste*)malloc(sizeof(liste));            // chaque pointeurs
liste *i=(liste*)malloc(sizeof(liste));            //
liste *q=(liste*)malloc(sizeof(liste));            //
liste *m=(liste*)malloc(sizeof(liste));            //
 
 
clrscr();                 // Vide l'écran, incompatible
                          // (par défaut) Linux et VC++
 
ma_l->suivant=NULL;       // La tete EST la queue quand ma_l->suivant=NULL
p->suivant=NULL;
 
printf("/n** TEST DE LISTE CHAINEE **/n/n");
printf("Entrer 1er element de ma liste n: ");
scanf("%d",&ma_l->n);
 
printf("n de ma tete de liste: %d",ma_l->n);
 
// On attribue de l'espace de la taille de la structure
ma_l->suivant=(liste*)malloc(sizeof(liste));
 
// On peut donc insérer une valeur
printf("/n/nentrer n de l'element suivant: ");
scanf("%d",&ma_l->suivant->n);              
 
printf("n de ma tete de liste: %d",ma_l->n);      // ma_l->n
printf("/nn de mon element suivant: %d",ma_l->suivant->n);
 
 
 
 
// Le suivant du suivant du suivant est NULL c'est à dire
ma_l->suivant->suivant=(liste*)malloc(sizeof(liste));
ma_l->suivant->suivant->suivant=NULL;
 
printf("/n/nentrer n de la queue: ");
scanf("%d",&ma_l->suivant->suivant->n); 




0x04. PARCOURS


// PARCOURS D'UNE LISTE ////////////////////////////////////////////////////////
printf("/nParcours de la liste:");
for(p=ma_l;p!=NULL;p=p->suivant)
{
   printf("/nn: %d",p->n);
}
 
 
/*
 
1
|   2
|        3
|
|
p -> n = 1
p = ma_l
ma_l -> n = 1
Départ de p = ma_l
 
 
1
    2
    |    3
    |
    |
    p -> n = 2
    p = ma_l -> suivant
    ma_l -> suivant -> n = 1
    Départ de p = p -> suivant
    Départ de p = ma_l -> suivant
 
 
1
    2
         3
         |
         |
         p -> n = 3
         p = ma_l -> suivant -> suivant
         ma_l -> suivant -> suivant -> n = 3
         Départ de p = p -> suivant
         Départ de p = ma_l -> suivant -> suivant
 
 
*/ [/div] 
 
 
 [title=5] INSERTION EN TETE [/title] 
 
 
 
 [code=c] // INSERTION EN TETE ///////////////////////////////////////////////////////////
 
// On se rappelle de : i=(liste*)malloc(sizeof(liste));
// au début du main... on peut donc initialiser la donnée
printf("/n/nEntrer n de l'element a inserer en tete: ");
scanf("%d",&i->n);   
 
// Voir dessin ci-dessous : en bref, l'ancienne t&ecirc;te est l'élément suivant
// de la nouvelle t&ecirc;te.
i->suivant=ma_l;
ma_l=i;         
 
 
 
/*
 
1
|   2
|        3
|
|
0->suivant = 1
 
 
 
 
0->suivant = 1
            /  
           /
          / 1->suivant = 2
         2
              3
 
 
 
0
    1
         2
              3
*/ 




0x06. INSERTION EN QUEUE


// INSERTION EN QUEUE //////////////////////////////////////////////////////////
printf("/n/nentrer n de l'element a inserer en queue: ");
scanf("%d",&q->n);
q->suivant=NULL;
 
// On parcours la liste                                             
for(p=ma_l;p->suivant!=NULL;p=p->suivant);  
 
// En fin de liste on alloue la mémoire
p->suivant=(liste*)malloc(sizeof(liste));   
 
// On sauvegarde le nouvel élément comme étant le suivant du dernier.
// c'est à dire, la nouvelle queue, le dernier élément précédent étant donc 
// devenu l'avant dernier
p->suivant=q;                               
 
 
 
/*
0
    1
         2
              3
                   NULL
 
0
    1
         2
              3
                   *        
                Allocation mémoire
 
 
 
0
    1
         2
              3
                    4
                On sauvegarde le maillon
                de la liste en mémoire
 
*/ 




0x07. INSERTION AU MILIEU


// INSERTION EN MILIEU /////////////////////////////////////////////////////////
int nbr_ex;
printf("/n/nentrer n de l'element a inserer en milieu: ");
scanf("%d",&m->n);
printf("/napres quelle valeur de la liste ? (entre 1 & 2 par ex.): ");
scanf("%d",&nbr_ex);
 
 
for(p=ma_l;p->n!=nbr_ex;p=p->suivant); // On cherche en utilisant les données
m->suivant=p->suivant;                 // le 'for' va s'arr&ecirc;ter dès que la condition
p->suivant=m;                          // est vraie. On peut alors insérer les deux éléments
 
 
/*
 
0
    1
         2
        /     3
       /           4
      9
     m->suivant = p->suivant  // '9' se met à gauche de '2'
 
 
 
0
    1
     /   2
      /       3
       /           4
        9
         p->suivant = m      // '9' se met à droite de '1'
 
 
0
    1                        // '9' est bien à gauche de '2'  
    ---->9                   // et à droite de '1', il est donc
         ---->2              // bien inséré
                  3
                        4
 
 
 
La logique veut qu'on ne peut s'insérer qu'entre deux éléments
 
 
*/ 



   =>   Écrit par : Nicolas, le 26 juin 2015


 
Mots clés :  
  c 
  
  system 
    >   Articles connexes :

Comment gagner du temps sur Internet



/tmp et /var/log en noexec sur macOS



1228155