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 :
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 ;
}
