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 �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 la m�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 votre programmeque 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 votre tableau.
  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 que realloc 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 pointeursur �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 ;

}