LES LISTES CHAÎNÉES EN LANGAGE C

Lorsque vous créez un  algorithme  utilisant des conteneurs, il existe différentes manières de les implémenter, la façon la plus courante é...

Lorsque vous créez un algorithme utilisant des conteneurs, il existe différentes manières de les implémenter, la façon la plus courante étant les tableaux, que vous connaissez tous. Lorsque vous créez un tableau, les éléments de celui-ci sont placés de façon contiguë en mémoire. Pour pouvoir le créer, il vous faut connaître sa taille. Si vous voulez supprimer un élément au milieu du tableau, il vous faut recopier les éléments temporairement, ré-allouer de la mémoire pour le tableau, puis le remplir à partir de l'élément supprimé. En bref, ce sont beaucoup de manipulations coûteuses en ressources.


Une liste chaînée est différente dans le sens où les éléments de votre liste sont répartis dans lamémoire et reliés entre eux par des pointeurs. Vous pouvez ajouter et enlever des éléments d'une liste chaînée à n'importe quel endroit, à n'importe quel instant, sans devoir recréer la liste entière.
Nous allons essayer de voir ceci plus en détail sur ces schémas :

Vous avez sur ce schéma la représentation que l'on pourrait faire d'un tableau et d'une liste chaînée. Chacune de ces représentations possède ses avantages et inconvénients. C'est lors de l'écriture de votreprogramme que vous devez vous poser la question de savoir laquelle des deux méthodes est la plus intéressante.

• Dans un tableau, la taille est connue, l'adresse du premier élément aussi. Lorsque vous déclarez un tableau, la variable contiendra l'adresse du premier élément de votretableau.
  Comme le stockage est contigu, et la taille de chacun des éléments connue, il est possible d'atteindre directement la case i d'un tableau.
• Pour déclarer un tableau, il faut connaître sa taille.
• Pour supprimer ou ajouter un élément à un tableau, il faut créer un nouveau tableau et supprimer l'ancien. Ce n'est en général pas visible par l'utilisateur, mais c'est ce querealloc va souvent faire. L'adresse du premier élément d'un tableau peut changer après un realloc, ce qui est tout à fait logique puisque realloc n'aura pas forcement la possibilité de trouver en mémoire la place nécessaire et contiguë pour allouer votre nouveau tableau. realloc va donc chercher une place suffisante, recopier votre tableau, et supprimer l'ancien.

• Dans une liste chaînée, la taille est inconnue au départ, la liste peut avoir autant d'éléments que votre mémoire le permet.
  Il est en revanche impossible d'accéder directement à l'élément i de la liste chaînée.
  Pour ce faire, il vous faudra traverser les i-1 éléments précédents de la liste.
• Pour déclarer une liste chaînée, il suffit de créer le pointeur qui va pointer sur le premier élément de votre liste chaînée, aucune taille n'est donc à spécifier.
• Il est possible d'ajouter, de supprimer, d'intervertir des éléments d'un liste chaînée sans avoir à recréer la liste en entier, mais en manipulant simplement leurs pointeurs.

Chaque élément d'une liste chaînée est composé de deux parties :

• la valeur que vous voulez stocker,
• l'adresse de l'élément suivant, s'il existe.
  S'il n'y a plus d'élément suivant, alors l'adresse sera NULL, et désignera le bout de la chaîne.
  Voilà deux schémas pour expliquer comment se passent l'ajout et la suppression d'un élément d'une liste chaînée. Remarquez le symbole en bout de chaîne qui signifie que l'adresse de l'élément suivant ne pointe sur rien, c'est-à-dire sur NULL.

Déclaration en C d'une liste chaînée :

typedef struct n{

int info ;

struct n* suivant ;

} NOEUD ;

On crée le type NOEUD qui est une structure contenant un entier (info) et un pointeur sur élément (suivant), qui contiendra l'adresse de noeud suivant. 

Manipuler les listes chaînées:

Initialiser une liste chaînée

Initialiser une liste chaînée:

NOEUD* initialiser(){

return NULL ;

}

void main(){

NOEUD* ptrNoeud ;

ptrNoeud = initialiser() ;

}

Initialiser une liste chaînée avec un noeud factice au début:

NOEUD* initialiser(){

NOEUD* ptrNoeud ;

ptrNoeud = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( ptrNoeud != NULL ){

ptrNoeud->suivant = NULL ;

}

return ptrNoeud ;

}

void main(){

NOEUD* debut ;

debut = initialiser() ;

}

Initialiser une liste chaînée avec un noeud factice au début et à la fin:

NOEUD* initialiser(){

NOEUD* z, *debut ;

z = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( z != NULL ){

z->suivant = z ;

debut = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( debut != NULL ){

debut->suivant = z ;

}

}

return debut ;

}

void main(){

NOEUD* debut ;

debut = initialiser() ;

}

Insérer dans une liste chaînée

Insérer dans une liste chaînée avec un argument de type pointeur:

  

NOEUD* insererEnTete( NOEUD* debut, int i ){

NOEUD* nouveau ;

nouveau = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( nouveau != NULL ){

nouveau->suivant = debut ;

nouveau->info = i ;

}

return nouveau ;

}

void main(){

NOEUD* debut ;

debut = initialiser() ;

debut = insererEnTete( debut, 20 ) ;

}

Insérer dans une liste chaînée avec un argument de type pointeur de pointeur :

void main(){

NOEUD* debut ;

int res ;

debut = initialiser() ;

res = insererEnTete(&debut, 20 ) ;

}

int insererEnTete(NOEUD**,debut, int i ){

NOEUD* nouveau ;

nouveau = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( nouveau != NULL ){

nouveau->suivant =*debut;

nouveau->info = i ;

*debut= nouveau ;

return 1 ;

} else {

return 0 ;}

}

Insérer dans une liste chaînée avec un nœud factice au début :

int insererEnTete( NOEUD* debut, int i ){

NOEUD* nouveau ;

nouveau = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( nouveau != NULL ){

nouveau->suivant = debut->suivant ;

nouveau->info = i ;

debut->suivant = nouveau ;

return 1 ;

} else {

return 0 ;

}

}

void main(){

NOEUD* debut ;

int res ;

debut = initialiser() ;

res = insererEnTete( debut, 20 ) ;

}

Insérer dans une liste chaînée avec un nœud factice au début et à la fin :

int insererEnTete( NOEUD* debut, int i ){

NOEUD* nouveau ;

nouveau = (NOEUD*)malloc( sizeof( NOEUD ) ) ;

if( nouveau != NULL ){

nouveau->suivant = debut->suivant ;

nouveau->info = i ;

debut->suivant = nouveau ;

return 1 ;

} else {

return 0 ;

}

}

Rechercher dans une liste chaînée

Rechercher un élément :

Noeud* recherchePrecedent( Noeud* debut, int i ){

while( debut!=NULL && debut->info!=i ){ /*tant que info du suivant ¹ i*/

debut = debut ->suivant ; /*continuer la recherche*/

}

return debut ;

}

Rechercher un élément dans un liste ayant un noeud factice à la fin :

Noeud* recherchePrecedent( Noeud* debut, int i ){

while( debut->info != i ){ /*tant que info du suivant ¹ i*/

debut = debut ->suivant ; /*continuer la recherche*/

}

return debut ;

}

Ads