Lists: Implementation and Manipulation in C
Listes chaînées en C Les listes chaînées en C sont une structure de données dynamique qui permet de stocker des éléments de manière non contiguë en mémoire. Contrairement aux tableaux, les listes chaînées n'ont pas besoin de connaître leur taille à l'avance et permettent d'ajouter ou de supprimer des éléments facilement.
D'après le document Lists: Implementation and Manipulation in C
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Computer Science, Data Structures · PDF · 9 pages · 2011
Afficher l'aperçu du document
Listes chaînées en C
Les listes chaînées en C sont une structure de données dynamique qui permet de stocker des éléments de manière non contiguë en mémoire. Contrairement aux tableaux, les listes chaînées n'ont pas besoin de connaître leur taille à l'avance et permettent d'ajouter ou de supprimer des éléments facilement. Cet article aborde la déclaration, l'ajout, la suppression et la recherche d'éléments dans une liste chaînée, avec des exemples de code en C.
Généralités sur les listes chaînées
Les listes chaînées se distinguent des tableaux par leur structure. Dans un tableau, les éléments sont stockés de manière contiguë, ce qui nécessite de connaître la taille du tableau lors de sa déclaration. En revanche, une liste chaînée est composée d'éléments reliés entre eux par des pointeurs, permettant ainsi une flexibilité dans la gestion des éléments.
Chaque élément d'une liste chaînée contient deux parties :
- La valeur stockée.
- L'adresse de l'élément suivant, qui est NULL si l'élément est le dernier de la liste.
Déclaration en C d'une liste chaînée
Pour déclarer une liste chaînée en C, il est nécessaire de définir une structure qui représente un élément de la liste. Voici un exemple de déclaration d'une liste simplement chaînée d'entiers :
#include <stdlib.h>
typedef struct element element;
struct element
{
int val;
struct element *nxt;
};
typedef element* llist;
int main()
{
llist ma_liste1 = NULL;
element *ma_liste2 = NULL;
struct element *ma_liste3 = NULL;
return 0;
}
Il est essentiel d'initialiser la liste chaînée à NULL lors de sa déclaration.
Manipulation des listes chaînées
Une fois la liste chaînée déclarée, il est important de savoir comment ajouter, supprimer et rechercher des éléments. Nous allons examiner ces opérations en détail.
Ajouter un élément
Il existe deux méthodes principales pour ajouter un élément à une liste chaînée : l'ajout en tête et l'ajout en fin de liste.
Ajouter en tête
Pour ajouter un élément en tête, il faut créer un nouvel élément, lui assigner une valeur et le relier à la liste existante. Voici le code correspondant :
llist ajouterEnTete(llist liste, int valeur)
{
element* nouvelElement = malloc(sizeof(element));
nouvelElement->val = valeur;
nouvelElement->nxt = liste;
return nouvelElement;
}
Ajouter en fin de liste
Pour ajouter un élément en fin de liste, il faut d'abord créer le nouvel élément, puis parcourir la liste jusqu'au dernier élément pour le relier au nouvel élément. Voici le code :
llist ajouterEnFin(llist liste, int valeur)
{
element* nouvelElement = malloc(sizeof(element));
nouvelElement->val = valeur;
nouvelElement->nxt = NULL;
if(liste == NULL)
{
return nouvelElement;
}
else
{
element* temp = liste;
while(temp->nxt != NULL)
{
temp = temp->nxt;
}
temp->nxt = nouvelElement;
return liste;
}
}
Supprimer un élément
La suppression d'un élément peut se faire en tête ou en fin de liste.
Supprimer un élément en tête
Pour supprimer le premier élément de la liste, il faut stocker l'adresse du second élément avant de libérer le premier. Voici le code :
llist supprimerElementEnTete(llist liste)
{
if(liste != NULL)
{
element* aRenvoyer = liste->nxt;
free(liste);
return aRenvoyer;
}
else
return NULL;
}
Supprimer un élément en fin de liste
Pour supprimer le dernier élément, il faut parcourir la liste jusqu'à l'avant-dernier élément, puis le relier à NULL. Voici le code :
llist supprimerElementEnFin(llist liste)
{
if(liste == NULL)
return NULL;
if(liste->nxt == NULL)
{
free(liste);
return NULL;
}
element* tmp = liste;
element* ptmp = liste;
while(tmp->nxt != NULL)
{
ptmp = tmp;
tmp = tmp->nxt;
}
ptmp->nxt = NULL;
free(tmp);
return liste;
}
Rechercher un élément
Pour rechercher un élément dans une liste chaînée, il suffit de parcourir la liste jusqu'à trouver l'élément correspondant. Voici le code :
llist rechercherElement(llist liste, int valeur)
{
element *tmp = liste;
while(tmp != NULL)
{
if(tmp->val == valeur)
{
return tmp;
}
tmp = tmp->nxt;
}
return NULL;
}
Points clés à retenir
Voici les points essentiels à retenir concernant les listes chaînées en C :
- Les listes chaînées permettent une gestion dynamique des éléments.
- La déclaration d'une liste chaînée nécessite la création d'une structure.
- Les éléments peuvent être ajoutés en tête ou en fin de liste.
- La suppression d'éléments peut également se faire en tête ou en fin de liste.
- La recherche d'éléments nécessite de parcourir la liste jusqu'à trouver la valeur recherchée.
Questions fréquentes
Comment déclarer une liste chaînée en C ?
Pour déclarer une liste chaînée en C, vous devez définir une structure pour les éléments de la liste, contenant la valeur et un pointeur vers l'élément suivant. Ensuite, vous déclarez un pointeur de type élément pour représenter la liste.
Comment ajouter un élément dans une liste chaînée ?
Vous pouvez ajouter un élément en tête ou en fin de liste. Pour ajouter en tête, créez un nouvel élément et reliez-le au début de la liste. Pour ajouter en fin, parcourez la liste jusqu'au dernier élément et reliez-le au nouvel élément.
Comment supprimer un élément d'une liste chaînée ?
Pour supprimer un élément, vous pouvez le faire en tête ou en fin de liste. En tête, il suffit de libérer le premier élément et de renvoyer le second. En fin, parcourez la liste jusqu'à l'avant-dernier élément, reliez-le à NULL et libérez le dernier élément.
Comment rechercher un élément dans une liste chaînée ?
Pour rechercher un élément, parcourez la liste en vérifiant chaque valeur. Si vous trouvez l'élément correspondant, renvoyez son adresse. Sinon, continuez jusqu'à la fin de la liste.
Commentaires
Aucun commentaire pour le moment. Posez la première question.