Les listes chainées
Structures de Données
- Les structures de données sont essentiellement des formes d'organisation de la mémoire.
- Il existe de nombreuses façons d'organiser les données dans la mémoire.
- Les structures de données abstraites sont celles que nous pouvons conceptuellement imaginer.
Lors de l'apprentissage de l'informatique, il est souvent utile de commencer par ces structures
de données conceptuelles. En les apprenant, il sera plus facile par la suite de comprendre
comment mettre en œuvre des structures de données plus concrètes.
Piles et Files
- Les sont une forme de .
- Les ont des propriétés spécifiques. En particulier, elles
sont ou (premier entré, premier sorti). Vous pouvez vous imaginer dans une pour un stand dans
un parc d'attractions. La première personne de la file d'attente est la première à entrer dans
le véhicule, tandis que la dernière personne est la dernière à entrer dans le véhicule. La
dernière personne monte dans le véhicule en dernier.
- Les sont associées à des actions spécifiques. Par
exemple, un article peut être mis en
, c'est-à-dire qu'il peut rejoindre la ligne ou la file
d'attente. En outre, un élément peut
être retiré de la file d'attente ou la quitter une fois qu'il a atteint le début de la file
d'attente.
- Les s'opposent à une . Fondamentalement, les propriétés d'une sont différentes de
celles d'une . Plus précisément, il s'agit d'une pile , c'est-à-dire . Tout comme l'empilage des plateaux dans une cafétéria, un
plateau placé
en dernier dans une est le premier à pouvoir être pris.
- Les sont associées à des actions spécifiques. Par
exemple, place un objet sur le
dessus d'une .
consiste à retirer un objet du sommet de la .
- En code, vous pouvez imaginer une comme suit :
typedef struct
{
personne personnes[TAILLE];
int taille;
}
pile;
Remarquez qu'un tableau appelé personnes est de type . La est la
hauteur que la pourrait atteindre. L'entier indique à quel point la est pleine,
indépendamment de ce qu'elle pourrait contenir.
Vous pouvez imaginer que le code ci-dessus a une limite. En effet, la capacité du tableau est
toujours prédéterminée dans ce code. Par conséquent, la
peut toujours être surdimensionnée.
Vous pourriez imaginer n'utiliser qu'une seule place dans la sur .
Nous aimerions que notre soit dynamique, c'est-à-dire
qu'elle puisse s'agrandir au fur et à
mesure que de nouveaux éléments y sont ajoutés.
Redimensionnement des tableaux
- Imaginons un tableau de 3 entiers:
- Dans la mémoire, ce tableau est stocké avec d'autres tableaux, programmes, fonctions et
variables. Certains d'entre eux pourraient également être des octets vides non utilisés par un
autre programme.
- Supposons maintenant que nous voulions ajouter un quatrième nombre au tableau. Mais cela est
impossible car les tableaux ont une taille statique que nous ne pouvons pas modifier.
- Au lieu de cela, nous pouvons créer un nouveau tableau de type int de taille 4, le remplir avec
des éléments du premier tableau.
- Puis ajouter notre nouveau nombre au tableau.
- Voici à quoi ressemble notre bloc de mémoire.
- Comme vous pouvez le constater, nous avons créé 2 tableaux de 3 éléments similaires. Ce qui
n'est pas vraiment efficace car maintenant le premier tableau est inutile mais utilise
de la mémoire.
- Nous perdons également du temps en réinsérant les anciens éléments dans un nouveau tableau.
- Imaginons que nous ayons 1000 nombres et que nous voulions ajouter un 1001ème nombre. Cela nous
prendra encore 1001x4 octets et du temps juste pour un nouveau nombre.
- Voici un exemple de code dans lequel nous créons un tableau de 3 entiers, puis afficher les
elements de tableau:
#include <stdio.h>
int main(){
int T[3];
T[0] = 1;
T[1] = 2;
T[2] = 3;
for(int i = 0; i < 3; i++) {
printf("%i\n",T[i]);
}
}
Remarquez que ce qui précède ressemble beaucoup à ce que nous avons appris plus tôt dans le
semestre 1 et 2 de programmation C. La mémoire est préallouée pour trois éléments.
Nous savons que les tableaux sont des blocs de mémoire
préalloués. Pour gérer dynamiquement la taille, nous pouvons allouer manuellement la mémoire
pour les éléments nécessaires, puis réallouer de la mémoire lors de l'ajout ou la suppression
d'éléments, en libérant l'ancienne mémoire ensuite.
En nous basant sur nos connaissances, nous pouvons tirer parti de notre compréhension des
pointeurs pour créer une meilleure conception dans ce code.
#include <stdio.h>
#include <stdlib.h>
int main(){
int *T = (int *)malloc(sizeof(int) * 3);
T[0] = 1;
T[1] = 2;
T[2] = 3;
for(int i = 0; i < 3; i++) {
printf("%d\n", T[i]);
}
printf("-----------\n");
int *Temp = (int *)malloc(sizeof(int) * 4);
for(int i = 0; i < 3; i++) {
Temp[i] = T[i];
}
Temp[3] = 4;
free(T);
T = Temp;
for(int i = 0; i < 4; i++) {
printf("%d\n", T[i]);
}
free(T);
}
Types des listes chaînées
- Il existe 4 types de listes chaînées :
Liste chaînée simple
Liste double chaînée
Circulaire chaînée simple
Circulaire double chaînée
Liste chaînée simple
- Une est un type de données que vous pouvez définir
vous-même. Un en notation point
permet d'accéder à des variables à l'intérieur de cette structure. L'opérateur permet de
déclarer un pointeur ou de déréférencer une variable.
- Aujourd'hui, nous vous présentons l'opérateur . Il s'agit
d'une flèche. Cet opérateur va à une
adresse et regarde à l'intérieur d'une structure.
- Une liste chaînée est l'une des structures de données les plus puissantes du langage . Une
liste chaînée vous permet d'inclure des valeurs situées à différents endroits de la mémoire. En
outre, elle vous permet d'augmenter ou de réduire dynamiquement la liste à votre guise.
- Vous pouvez imaginer trois valeurs stockées dans trois zones différentes de la mémoire, comme
suit :
- Comment peut-on rassembler ces valeurs dans une liste ?
- Nous pourrions imaginer ces données comme suit :
- Nous pourrions utiliser plus de mémoire pour savoir où se trouve l'élément suivant.
- Remarquez que NULL est utilisé pour indiquer que rien d'autre ne suit dans la liste.
- Par convention, nous conservons un élément supplémentaire en mémoire, un pointeur, qui indique
le premier élément de la liste.
- Si l'on fait abstraction des adresses de mémoire, la liste se présente comme suit :
- Ces boîtes sont appelées (ou maillon). Un contient à la fois un élément et un
pointeur appelé suivant. En code, vous pouvez imaginer un
comme suit :
typedef struct noeud
{
int nombre;
struct noeud *suivant;
} noeud;
Notez que l'élément contenu dans ce est un
entier appelé . Ensuite, un pointeur vers un appelé est inclus,
qui pointera vers un autre quelque part dans la mémoire.
Insertion en tête
- Conceptuellement, nous pouvons imaginer le processus de création d'une liste chaînée. Tout
d'abord, le est déclaré, mais il a une .
- Ensuite, un appelé est
alloué en mémoire.
- Ensuite, la valeur 1 est attribuée au du nœud.
- Ensuite, le champ suivant du se voit attribuer .
- Ensuite, la liste est pointée sur l'emplacement de mémoire où
pointe. et pointent
maintenant au même endroit.
- Un nouveau nœud est alors créé. Le champ numéro et le champ suivant sont tous deux remplis avec
des valeurs poubelles.
- La valeur du nœud (le nouveau nœud) est mise à jour à .
- Plus important encore, nous ne voulons pas perdre notre connexion à l'un de ces nœuds, de peur
qu'ils ne soient perdus à jamais. En conséquence, le champ de est pointé vers le
même
emplacement mémoire que
- Enfin, est mise à jour pour pointer sur . Nous avons maintenant une liste chaînée de deux éléments.
- Masquer n pour mieux visualiser la structure de nos liste chaînée
- Pour mettre cela en pratique, modifiez votre code comme suit :
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *next;
} noeud;
int main(){
noeud *list;
noeud *n;
n = (noeud *) malloc(sizeof(noeud));
n->numero = 1;
n->next = NULL;
list = n;
n = (noeud *) malloc(sizeof(noeud));
n->numero = 2;
n->next = list;
list = n;
for(noeud *p = list; p != NULL; p = p->next){
printf("%i\n", p->numero);
}
noeud *point = n;
while(point != NULL){
noeud *suivant = point->next;
free(point);
point = suivant;
}
}
Utilisons maintenant une fonction pour insérer n nombres entrés par l'utilisateur et les
afficher.
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *next;
} noeud;
noeud *inserer(noeud* list, int nmbr);
int main(){
noeud *list = NULL;
int n;
printf("Veuillez entrer le nombre n d'éléments: ");
scanf("%d", &n);
printf("Veuillez entrer n nombres:\n");
for(int i = 0; i < n; i++){
int nmbr;
scanf("%d", &nmbr);
list = inserer(list, nmbr);
}
printf("Les elements sont: \n");
for(noeud *p = list; p != NULL; p = p->next){
printf("%i\n", p->numero);
}
}
noeud *inserer(noeud* list, int nmbr){
noeud *n = (noeud *) malloc(sizeof(noeud));
n->numero = nmbr;
if(list == NULL){
n->next = NULL;
} else {
n->next = list;
}
list = n;
return list;
}
Comme vous pouvez le remarquer, nous avons initialisé la avec , car si
nous ne le faisons pas, la condition vérifiant si la liste est vide ou non dans la fonction
ne sera jamais vraie, car comme nous l'avons dit
précédemment, lorsque nous
initialisons une variable, nous récupérons toujours un morceau de mémoire qui contient une
valeur .
Si nous initialisons la avec
Tester le code sans initialiser la avec
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *next;
} noeud;
noeud *inserer(noeud* list, int nmbr);
int main(){
noeud *list;
int n;
printf("Veuillez entrer le nombre n d'éléments: ");
scanf("%d", &n);
printf("Veuillez entrer n nombres:\n");
for(int i = 0; i < n; i++){
int nmbr;
scanf("%d", &nmbr);
list = inserer(list, nmbr);
}
printf("Les elements sont: \n");
for(noeud *p = list; p != NULL; p = p->next){
printf("%i\n", p->numero);
}
}
noeud *inserer(noeud* list, int nmbr){
noeud *n = (noeud *) malloc(sizeof(noeud));
n->numero = nmbr;
if(list == NULL){
n->next = NULL;
} else {
n->next = list;
}
list = n;
return list;
}
Sortie :
Comme vous pouvez le constater, le programme a produit plus de nombres. C'est parce que le
premier nombre que nous avons ajouté à la liste n'a jamais eu
son pointeur changé en
, donc il pointait déjà vers un autre déchet de mémoire qui
contenait une valeur jusqu'à ce
qu'il pointe vers .
Nous pourrions visualiser cette liste comme suit :
Nous pouvons également utiliser les pointeurs pour ajouter de nouveaux éléments à la liste sans
avoir à renvoyer toute la liste.
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *next;
} noeud;
void inserer(noeud** list, int nmbr);
int main(){
noeud *list = NULL;
int n;
printf("Veuillez entrer le nombre n d'éléments: ");
scanf("%d", &n);
printf("Veuillez entrer n nombres:\n");
for(int i = 0; i < n; i++){
int nmbr;
scanf("%d", &nmbr);
inserer(&list, nmbr);
}
printf("Les elements sont: \n");
for(noeud *p = list; p != NULL; p = p->next){
printf("%i\n", p->numero);
}
}
void inserer(noeud** list, int nmbr){
noeud *n = (noeud *) malloc(sizeof(noeud));
n->numero = nmbr;
if(*list == NULL){
n->next = NULL;
} else {
n->next = *list;
}
*list = n;
}
Insertion en queue
- Essayons de mettre les nouveaux éléments dans la queue. Cela signifie que les nouveaux éléments
seront à la fin de la liste.
- Nous commençons par déclarer la liste.
- Ensuite, un nœud appelé n est alloué en mémoire.
- Ensuite, la valeur 1 est attribuée au du nœud.
- Ensuite, le champ suivant du se voit attribuer .
- Ensuite, la liste est pointée sur l'emplacement de mémoire où
pointe. et pointent
maintenant au même endroit.
- Un nouveau nœud est alors créé. Le champ numéro et le champ suivant sont tous deux remplis avec
des valeurs poubelles.
- La valeur du nœud (le nouveau nœud) est mise à jour à .
- Ensuite, le champ suivant du se voit attribuer .
- Enfin, est mise à jour pour pointer sur . Nous avons maintenant une liste chaînée de deux éléments.
- Un nouveau nœud est alors créé. Le champ numéro et le champ suivant sont tous deux remplis avec
des valeurs poubelles.
- La valeur du nœud (le nouveau nœud) est mise à jour à .
- Ensuite, le champ suivant du se voit attribuer .
- Remarquez ici que la ne peut pas
pointer vers , car nous perdrions
alors la nœud avec le chiffre
- Pour résoudre ce problème, nous pouvons utiliser un pointeur
qui parcourra jusqu'à ce
qu'il trouve le dernier élément.
- pointera d'abord vers
- Ensuite pointera vers
- Nous trouvons maintenant que est donc c'est le dernier élément de la liste.
- Et maintenant peut pointer vers sans perdre aucun des éléments précédents.
- Nous disposons à présent d'une liste chaînée en insérant des éléments en queue.
- Pour mettre cela en pratique, modifiez votre code comme suit :
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *suivant;
} noeud;
noeud *inserer(noeud *list, int nmbr);
int main(){
noeud *list = NULL;
list = inserer(list, 1);
list = inserer(list, 2);
list = inserer(list, 3);
for(noeud *p = list; p != NULL; p = p->suivant){
printf("%i\n", p->numero);
}
noeud *p = list;
while(p != NULL){
noeud *tmp = p->suivant;
free(p);
p = tmp;
}
return 0;
}
noeud *inserer(noeud *list, int nmbr){
noeud *n = (noeud *) malloc(sizeof(noeud));
n->numero = nmbr;
n->suivant = NULL;
noeud *c = list;
if(c == NULL){
list = n;
} else {
while(c->suivant != NULL){
c = c->suivant;
}
c->suivant = n;
}
return list;
}
Remarquez que ce code parcourt la liste pour en trouver la fin. Lors de l'ajout d'un
élément (à la fin de la liste), notre code s'exécutera en \(O(n)\) (Cela signifie qu'il faudra
au programme n étapes pour atteindre la fin de la liste), car nous devons parcourir toute la
liste avant d'ajouter le dernier élément.
Nous pouvons améliorer ce programme en utilisant une qui a 3 données ; , et .
En code, vous pouvez imaginer le structure de contrôle comme suit :
typedef struct controle{
noeud *debut;
noeud *fin;
int taille;
} controle;
Ensuite, un liste appelé et un structure de contrôle sont alloué en mémoire.
Ces deux pointeurs pointent vers une valeur poubelle.
Ensuite, un nœud appelé est alloué en mémoire.
Nous mettons d'abord à jour les pointeurs et pour qu'ils pointent vers
et nous fixons à
Ensuite, la valeur est attribuée au du nœud.
Ensuite, le champ du nœud se voit attribuer .
Ensuite, est pointée sur l'emplacement de mémoire où pointe. et pointent maintenant au même endroit.
Un nouveau nœud est alors créé. Le champ et le champ
sont tous deux remplis avec des valeurs poubelles.
Nous augmenterons également le champ par , ce qui signifie que nous avons ajouté un nouvel élément à la
liste.
La valeur du nœud n(le nouveau nœud) est mise à jour à et le
champ du nœud se voit attribuer .
Et maintenant, puisque le nouveau nœud doit être lié au
dernier élément de la liste, nous pouvons récupérer ce nœud avec
Puis mettre à jour à pour qu'il pointe sur le nouvelle
noeud ajouté
Nous pouvons maintenant voir qu'en utilisant des structures de contrôle, nous pouvons ajouter
des éléments à la fin d'une liste sans dépendre d'un pointeur pour parcourir une liste.
Cela signifie que nous sommes passés de \(O(n)\) à \(O(1)\) pour insérer un nouvel élément à la fin
d'une liste. Cela peut être important, car imaginez que nous ayons éléments et que nous
décidions d'ajouter le élément à la liste. L'utilisation d'un pointeur pour parcourir
la liste prendra au moins d'étapes avant d'atteindre la fin, alors qu'avec un contrôle
de structure, il ne faudra qu'une étape.
Pour mettre cela en pratique, modifiez votre code comme suit :
#include <stdio.h>
#include <stdlib.h>
typedef struct noeud{
int numero;
struct noeud *suivant;
} noeud;
typedef struct controle{
noeud *debut;
noeud *fin;
int taille;
} controle;
void inserer(noeud **list, controle *c, int nmbr);
int main(){
noeud *list = NULL;
controle *c = malloc(sizeof(controle));
inserer(&list, c, 1);
inserer(&list, c, 2);
inserer(&list, c, 3);
for(noeud *p = list; p != NULL; p = p->suivant){
printf("%i\n", p->numero);
}
noeud *p = list;
while(p != NULL){
noeud *tmp = p->suivant;
free(p);
p = tmp;
}
free(c);
return 0;
}
void inserer(noeud **list, controle *c, int nmbr){
noeud *n = (noeud *) malloc(sizeof(noeud));
n->numero = nmbr;
n->suivant = NULL;
if(*list == NULL){
c->debut = n;
c->fin = n;
c->taille = 1;
*list = n;
} else {
c->fin->suivant = n;
c->fin = n;
c->taille++;
}
}
