Manipulation and Use of Linked Lists in C
Listes chaînées en C Les listes chaînées en C sont une structure de données qui permet de stocker des éléments de manière dynamique. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de taille fixe et permettent une manipulation plus flexible des éléments.
D'après le document Manipulation and Use of Linked Lists in C
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Computer Science · 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 qui permet de stocker des éléments de manière dynamique. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de taille fixe et permettent une manipulation plus flexible des éléments. Cet article couvre la déclaration des listes chaînées, ainsi que les opérations courantes telles que l'ajout, la suppression et la recherche d'éléments.
Généralités sur les listes chaînées
Les listes chaînées sont composées d'éléments appelés nœuds, où chaque nœud contient une valeur et un pointeur vers le nœud suivant. Cela permet d'ajouter et de supprimer des éléments sans avoir à déplacer les autres éléments, contrairement aux tableaux où les éléments sont stockés de manière contiguë en mémoire.
Chaque nœud d'une liste chaînée est constitué de deux parties :
- La valeur que vous souhaitez stocker.
- L'adresse de l'élément suivant, qui sera NULL si c'est le dernier élément de la liste.
Déclaration en C d'une liste chaînée
Pour déclarer une liste chaînée en C, vous devez définir une structure pour représenter un nœud. 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 important d'initialiser la liste chaînée à NULL.
Manipulation des listes chaînées
Une fois la liste chaînée déclarée, vous pouvez manipuler ses éléments. Voici quelques opérations courantes :
Ajouter un élément
Il existe deux manières d'ajouter un élément à une liste chaînée : en tête ou en fin de liste.
Ajouter en tête
Pour ajouter un élément en tête, vous créez un nouvel élément, lui assignez une valeur, puis le reliez à la liste existante :
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, vous devez parcourir la liste jusqu'au dernier élément et le relier au nouvel élément :
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 également se faire en tête ou en fin de liste.
Supprimer un élément en tête
Pour supprimer le premier élément, vous devez stocker l'adresse du deuxième élément avant de libérer le premier :
llist supprimerElementEnTete(llist liste) {
if (liste != NULL) {
element* aRenvoyer = liste->nxt;
free(liste);
return aRenvoyer;
}
return NULL;
}
Supprimer un élément en fin de liste
Pour supprimer le dernier élément, vous devez parcourir la liste jusqu'à l'avant-dernier élément :
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, parcourez la liste jusqu'à trouver l'élément avec la valeur recherchée :
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 :
- Les listes chaînées permettent une gestion dynamique de la mémoire.
- Chaque nœud contient une valeur et un pointeur vers le nœud suivant.
- Les opérations d'ajout et de suppression sont flexibles et ne nécessitent pas de déplacement d'éléments.
- Les listes chaînées peuvent être parcourues pour rechercher des éléments ou compter le nombre d'éléments.
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 nœuds et un type de pointeur pour la liste. Par exemple :
typedef struct element element;
struct element {
int val;
struct element *nxt;
};
typedef element* llist;
Comment ajouter un élément à 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 à la liste existante. 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 en tête, stockez l'adresse du deuxième élément avant de libérer le premier. Pour supprimer en fin, parcourez la liste jusqu'à l'avant-dernier élément et libérez le dernier.
Comment rechercher un élément dans une liste chaînée ?
Pour rechercher un élément, parcourez la liste et comparez chaque valeur jusqu'à trouver celle recherchée. Si trouvée, renvoyez l'adresse de l'élément.
Commentaires
Aucun commentaire pour le moment. Posez la première question.