[C] Parcours d'une liste chainee
Résolu
Bonjour,
dans le cadre de l'amélioration d'un programme de pendu pour l'école, je dois manipuler une liste chainée (en langage C).
Avant de bousiller le programme, sachant que je ne maitrisais pas trop les liste chainées, j'ai créé un petit programme tout simple pour voir le fonctionnement de ce genre de structure, voici ce que j'ai :
Fichier contenant la structure et les prototypes:
typedef struct pile
{
int valeur;
struct pile *prec;
}pile;
void push(pile **p, int val);
int pop(pile **p);
int Length(pile *p);
void clear(pile **p);
void view(pile *p);
Fichier contenant les implémentations de mes fonctions:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include "struct.h"
void push(pile **p, int val)
{
pile *element=(pile*)malloc(sizeof(pile));
if(!element)
{
printf("erreur allocation, relancer le programme");
exit(-1);
}
element->valeur=val;
element->prec=*p;
*p=element;
};
int pop(pile **p)
{
int val;
pile *tmp;
if(!*p) return -1;
tmp=(*p)->prec;
val=(*p)->valeur;
free(*p);
*p=tmp;
return val;
};
int Length(pile *p)
{
int n=0;
while(p)
{
n++;
p=p->prec;
}
return n;
};
void clear(pile **p)
{
pile *tmp;
while(*p)
{
tmp=(*p)->prec;
free(*p);
*p=tmp;
}
};
void view(pile *p)
{
while(p)
{
printf("%d\n",p->valeur);
p=p->prec;
}
}
Fichier main pour les tests :
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include "struct.h"
int main(void)
{
pile *MaPile=NULL;
int menu,nb;
do
{
system("CLS");
printf("1. ajouter un element a la pile\n");
printf("2. enlever un element de la pile\n");
printf("3. afficher la pile\n");
printf("4. nombre d'elements dans la pile\n");
printf("5. quitter\n");
scanf("%d",&menu);
system("CLS");
switch(menu)
{
case 1 : printf("Nombre (entier) a ajouter: ");
scanf("%d",&nb);
push(&MaPile,nb);
break;
case 2 : nb=pop(&MaPile);
break;
case 3 : view(MaPile);
getch();
break;
case 4 : printf("Nb elements: %d\n",Length(MaPile));
getch();
break;
case 5 : clear(&MaPile);
break;
default: printf("entrer un chiffre entre 1 et 5");
getch();
break;
}
}while(menu!=5);
return 0;
}
j'ai trouvé les implémentations sur le net et je les comprends assez bien.
Ce dont j'ai besoin maintenant, c'est une fonction permettant d'aller à un maillon bien précis pour en retirer le contenu et ensuite le supprimer.
dans le cadre de l'amélioration d'un programme de pendu pour l'école, je dois manipuler une liste chainée (en langage C).
Avant de bousiller le programme, sachant que je ne maitrisais pas trop les liste chainées, j'ai créé un petit programme tout simple pour voir le fonctionnement de ce genre de structure, voici ce que j'ai :
Fichier contenant la structure et les prototypes:
typedef struct pile
{
int valeur;
struct pile *prec;
}pile;
void push(pile **p, int val);
int pop(pile **p);
int Length(pile *p);
void clear(pile **p);
void view(pile *p);
Fichier contenant les implémentations de mes fonctions:
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include "struct.h"
void push(pile **p, int val)
{
pile *element=(pile*)malloc(sizeof(pile));
if(!element)
{
printf("erreur allocation, relancer le programme");
exit(-1);
}
element->valeur=val;
element->prec=*p;
*p=element;
};
int pop(pile **p)
{
int val;
pile *tmp;
if(!*p) return -1;
tmp=(*p)->prec;
val=(*p)->valeur;
free(*p);
*p=tmp;
return val;
};
int Length(pile *p)
{
int n=0;
while(p)
{
n++;
p=p->prec;
}
return n;
};
void clear(pile **p)
{
pile *tmp;
while(*p)
{
tmp=(*p)->prec;
free(*p);
*p=tmp;
}
};
void view(pile *p)
{
while(p)
{
printf("%d\n",p->valeur);
p=p->prec;
}
}
Fichier main pour les tests :
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include "struct.h"
int main(void)
{
pile *MaPile=NULL;
int menu,nb;
do
{
system("CLS");
printf("1. ajouter un element a la pile\n");
printf("2. enlever un element de la pile\n");
printf("3. afficher la pile\n");
printf("4. nombre d'elements dans la pile\n");
printf("5. quitter\n");
scanf("%d",&menu);
system("CLS");
switch(menu)
{
case 1 : printf("Nombre (entier) a ajouter: ");
scanf("%d",&nb);
push(&MaPile,nb);
break;
case 2 : nb=pop(&MaPile);
break;
case 3 : view(MaPile);
getch();
break;
case 4 : printf("Nb elements: %d\n",Length(MaPile));
getch();
break;
case 5 : clear(&MaPile);
break;
default: printf("entrer un chiffre entre 1 et 5");
getch();
break;
}
}while(menu!=5);
return 0;
}
j'ai trouvé les implémentations sur le net et je les comprends assez bien.
Ce dont j'ai besoin maintenant, c'est une fonction permettant d'aller à un maillon bien précis pour en retirer le contenu et ensuite le supprimer.
A voir également:
- Parcourir une liste chainée en c
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
- Site dangereux liste - Guide
- Voir liste d'amis facebook - Guide
7 réponses
je sais mais c'est ce que j'ai trouvé de plus approchant (mais surtout de plus clair) en cherchant sur la toile.
Ceci dit, entre
typedef struct pile
{
int valeur;
struct pile *prec;
}pile;
et
typedef struct _maillon{
struct _maillon *next;
int data; // si on prends un cas particulier plutot qu'on générique
} maillon;
je ne vois pas de grande différence, si je renome prec en next, il n'y a plus que les noms de variables qui changent.
Je comprends bien l'idée de la structure supplémentaire contenant deux pointeurs (l'un vers le premier maillon et l'autre vers le dernier) bien que dans le cas d'un liste simplement chainée je n'en vois pas l'utilité (si ce n'est que en général c'est utilisé par tout le monde).
il me reste à poser deux questions pour orienter un peu la discussion et éviter de lancer un "simple" débat sur les listes
Entre la pile et la liste, qu'est-ce qui changerait dans mon code?
Comme je l'ai déjà demandé avant :
si j'ai 10 maillons, que je veux extraire la donnée du 3e (par exemple) pour la transférer à une autre variable (donc il ne me fait pas un void element_x(); mais plutot un int element_x();
comment puis-je procéder ? (en oubliant pas que une fois la donnée extraite, je dois supprimer le maillon)
Ceci dit, entre
typedef struct pile
{
int valeur;
struct pile *prec;
}pile;
et
typedef struct _maillon{
struct _maillon *next;
int data; // si on prends un cas particulier plutot qu'on générique
} maillon;
je ne vois pas de grande différence, si je renome prec en next, il n'y a plus que les noms de variables qui changent.
Je comprends bien l'idée de la structure supplémentaire contenant deux pointeurs (l'un vers le premier maillon et l'autre vers le dernier) bien que dans le cas d'un liste simplement chainée je n'en vois pas l'utilité (si ce n'est que en général c'est utilisé par tout le monde).
il me reste à poser deux questions pour orienter un peu la discussion et éviter de lancer un "simple" débat sur les listes
Entre la pile et la liste, qu'est-ce qui changerait dans mon code?
Comme je l'ai déjà demandé avant :
si j'ai 10 maillons, que je veux extraire la donnée du 3e (par exemple) pour la transférer à une autre variable (donc il ne me fait pas un void element_x(); mais plutot un int element_x();
comment puis-je procéder ? (en oubliant pas que une fois la donnée extraite, je dois supprimer le maillon)
Dans le cas de ta structure de pile c'est comme si tu maillais ta liste en partant de la fin. Dans le cas de la liste tu mailles ta structure du début de la liste vers la fin. On pourrait même imaginer que tu mailles ta liste dans les deux sens (liste doublement chaînée). Après tout dépend de ce que tu veux faire.
Pour l'histoire du void * et du int,
- soit tu stockes directement un objet dans le maillon (par exemple un int, un float, une structure etc...) et ta liste ne peut être utilisé que pour un type de data
- soit tu stockes une adresse mémoire (void *) et cette adresse indique où se trouve l'objet en question. Comme une adresse fait toujours la même taille, tu peux donc adresser n'importe quel objet dans ta liste. C'est en ça que cette structure de liste est plus générique, mais "plus compliquée" à utliser puisqu'elle utilise des pointeurs.
Pour extraire le nième maillon. Suppose que tu utilises la structure que je t'ai donné. La structure liste contient deux pointeur (un sur le premier maillon, l'autre sur le dernier). On pourrait même imaginer que tu stockes la taille de la liste en plus. Imagine aussi que tes maillons soient simplement chaînés (du début de la liste vers la fin de la liste). Ta structure liste te permet de retrouver le début de la liste. Tu avances d'autant de maillon qu'il le faut pour arriver au nième (grâce au champ next des maillon) en vérifiant que tu n'es pas au dernier maillon (end).
Bonne chance
Pour l'histoire du void * et du int,
- soit tu stockes directement un objet dans le maillon (par exemple un int, un float, une structure etc...) et ta liste ne peut être utilisé que pour un type de data
- soit tu stockes une adresse mémoire (void *) et cette adresse indique où se trouve l'objet en question. Comme une adresse fait toujours la même taille, tu peux donc adresser n'importe quel objet dans ta liste. C'est en ça que cette structure de liste est plus générique, mais "plus compliquée" à utliser puisqu'elle utilise des pointeurs.
Pour extraire le nième maillon. Suppose que tu utilises la structure que je t'ai donné. La structure liste contient deux pointeur (un sur le premier maillon, l'autre sur le dernier). On pourrait même imaginer que tu stockes la taille de la liste en plus. Imagine aussi que tes maillons soient simplement chaînés (du début de la liste vers la fin de la liste). Ta structure liste te permet de retrouver le début de la liste. Tu avances d'autant de maillon qu'il le faut pour arriver au nième (grâce au champ next des maillon) en vérifiant que tu n'es pas au dernier maillon (end).
Bonne chance
Ce que je ne comprends pas très bien c'est que là tu fourni un code pour des piles mais pas pour des listes. Donc normalement tu es sensé reprogrammer un nouveau code et pas "bousiller l'ancien" pour reprendre tes termes ;)
Pour une liste chaîne générique la structure est :
Bonne chance
Pour une liste chaîne générique la structure est :
typedef struct _maillon{
struct _maillon *next;
// tu peux mettre int data si par exemple c'est une liste d'entier, l'idée c'est que là
// tu stockes l'adresse d'un objet quelconque
void *data;
} maillon;
typedef struct _liste{
maillon *begin;
maillon *end;
} liste;
Bonne chance
pour ce qui est du void en int, je vais m'en tenir à une version avec le moins de pointeurs possibles (déjà qu'ici c'est juste pour que j'arrive à manier la liste, sinon je dois jouer avec d'es chaines de caractères)
De plus, si j'arrive a régler pour un cas particulier, je pourrai ensuite dans mon temps libre, me pencher sur le cas général dans un but d'utilisation ultérieure.
Ensuite, pour ce qui est du nieme maillon, ce maillon end, est intéressant puisqu'il réduit le nombre de paramètres à passer à la fonction (pas besoin de passer la taille puisqu'on peut simplement vérifier qu'on est pas au dernier maillon).
Je ne demande pas que tu réécrive toute ma fonction (vais pas être ch... à ce point là), mais pourrais tu me montrer d'une part mes erreurs - différence entre les deux types de structure mentionnés - dans les fonctions et d'autre part m'expliquer en code l'atteinte, estraction, suppression d'un maillon.
Je vois bien un truc du genre (pseudo code, donc inutile de me dire que ca marchera jamais comme ça, c'est une idée générale)
struct recherche(int nb, struct **p)
/*donc je retourne un objet du type struct (le maillon que je veux atteindre) par une fonction qui reçoit un entier toujours inférieur (car vérifié avant) à la taille de la liste et un pointeur vers ma liste*/
{
int i=0;
struct tmp;
TANT QUE (i<nb)
p=p->next;
i++;
FIN_TANT
tmp=p;
free(p);
RETURN tmp->val;
};
mon gros défaut est le manque de manipulation des pointeurs, la bien que les profs insistent sur le fait que c'est important, j'ai du mal. Je sais don qu'il manque des étoiles, mais ou, bonne question !
De plus, si j'arrive a régler pour un cas particulier, je pourrai ensuite dans mon temps libre, me pencher sur le cas général dans un but d'utilisation ultérieure.
Ensuite, pour ce qui est du nieme maillon, ce maillon end, est intéressant puisqu'il réduit le nombre de paramètres à passer à la fonction (pas besoin de passer la taille puisqu'on peut simplement vérifier qu'on est pas au dernier maillon).
Je ne demande pas que tu réécrive toute ma fonction (vais pas être ch... à ce point là), mais pourrais tu me montrer d'une part mes erreurs - différence entre les deux types de structure mentionnés - dans les fonctions et d'autre part m'expliquer en code l'atteinte, estraction, suppression d'un maillon.
Je vois bien un truc du genre (pseudo code, donc inutile de me dire que ca marchera jamais comme ça, c'est une idée générale)
struct recherche(int nb, struct **p)
/*donc je retourne un objet du type struct (le maillon que je veux atteindre) par une fonction qui reçoit un entier toujours inférieur (car vérifié avant) à la taille de la liste et un pointeur vers ma liste*/
{
int i=0;
struct tmp;
TANT QUE (i<nb)
p=p->next;
i++;
FIN_TANT
tmp=p;
free(p);
RETURN tmp->val;
};
mon gros défaut est le manque de manipulation des pointeurs, la bien que les profs insistent sur le fait que c'est important, j'ai du mal. Je sais don qu'il manque des étoiles, mais ou, bonne question !
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
De plus, si j'arrive a régler pour un cas particulier, je pourrai ensuite dans mon temps libre, me pencher sur le cas général dans un but d'utilisation ultérieure.
Ok
Ensuite, pour ce qui est du nieme maillon, ce maillon end, est intéressant puisqu'il réduit le nombre de paramètres à passer à la fonction (pas besoin de passer la taille puisqu'on peut simplement vérifier qu'on est pas au dernier maillon).
Tu y accèdes surtout en O(1) et non en O(n). Par ailleurs si tu décide de passer en liste doublement chainer et que tu veux pouvoir parcourir ta liste en sens inverse (comme avec les reverse iterator du C++) ce champ est bien pratique. Mais tu pourrais éventuellement te contenter de dire que le dernier maillon à son champ *next qui vaut NULL. Pour moi c'est un détail d'implémentation, il faut que tu codes ta structure de sorte à être le plus à l'aise possible.
Je ne demande pas que tu réécrive toute ma fonction (vais pas être ch... à ce point là), mais pourrais tu me montrer d'une part mes erreurs - différence entre les deux types de structure mentionnés - dans les fonctions et d'autre part m'expliquer en code l'atteinte, estraction, suppression d'un maillon.
Ben j'ai pas le temps de tout recoder de toute façon. Mais c'est à peu près le même raisonnement que pour les piles, il faut juste garantir que ton maillage de liste est toujours cohérent :
- d'une part au niveau des champs begin et end (en particulier si tu supprimes ou ajoute un maillon en début/fin de liste)
- d'autre part au niveau des champs next de chaque maillon (en particulier au niveau des maillons entourant le maillon ajouté ou supprimé).
Si tu écris les opérations à apporter au maillage tu vas voir ça coule de source. Je n'ai pas trop envie de détailler trop comment tu dois faire car pour moi c'est l'exercice idéal pour apprendre les pointeurs, donc je préférerais que tu trouves par toi-même. En cas de blocage bien entendu je t'aiderai, mais j'aimerais au moins que tu me fournisses une souche de code sur laquelle repartir.
Je vois bien un truc du genre (pseudo code, donc inutile de me dire que ca marchera jamais comme ça, c'est une idée générale)
Merci de la précision mais je pense que je m'en serai doutée :)
Le problème c'est que si nb est supérieur à la taille de la liste ça va planter (segmentation fault au moment de faire p = p->next). Par ailleurs tu n'as pas à faire de free(p) (chaque free est associé à un malloc et là tu n'as pas fait de malloc, et une fonction de recherche ).
Ici je suppose que tu stockes dans ta structure de liste le premier maillon (begin), le dernier (end), et le nombre de maillon (size). On cherche le maillon i avec i dans {0...l.size}. On retourne NULL s'il n'existe pas. On garantit que i est positif en utilisant un unsigned plutôt qu'un int.
Sinon tu peux jeter un oeil à cette implémentation : liste simplement chainee
Bonne chance
Ok
Ensuite, pour ce qui est du nieme maillon, ce maillon end, est intéressant puisqu'il réduit le nombre de paramètres à passer à la fonction (pas besoin de passer la taille puisqu'on peut simplement vérifier qu'on est pas au dernier maillon).
Tu y accèdes surtout en O(1) et non en O(n). Par ailleurs si tu décide de passer en liste doublement chainer et que tu veux pouvoir parcourir ta liste en sens inverse (comme avec les reverse iterator du C++) ce champ est bien pratique. Mais tu pourrais éventuellement te contenter de dire que le dernier maillon à son champ *next qui vaut NULL. Pour moi c'est un détail d'implémentation, il faut que tu codes ta structure de sorte à être le plus à l'aise possible.
Je ne demande pas que tu réécrive toute ma fonction (vais pas être ch... à ce point là), mais pourrais tu me montrer d'une part mes erreurs - différence entre les deux types de structure mentionnés - dans les fonctions et d'autre part m'expliquer en code l'atteinte, estraction, suppression d'un maillon.
Ben j'ai pas le temps de tout recoder de toute façon. Mais c'est à peu près le même raisonnement que pour les piles, il faut juste garantir que ton maillage de liste est toujours cohérent :
- d'une part au niveau des champs begin et end (en particulier si tu supprimes ou ajoute un maillon en début/fin de liste)
- d'autre part au niveau des champs next de chaque maillon (en particulier au niveau des maillons entourant le maillon ajouté ou supprimé).
Si tu écris les opérations à apporter au maillage tu vas voir ça coule de source. Je n'ai pas trop envie de détailler trop comment tu dois faire car pour moi c'est l'exercice idéal pour apprendre les pointeurs, donc je préférerais que tu trouves par toi-même. En cas de blocage bien entendu je t'aiderai, mais j'aimerais au moins que tu me fournisses une souche de code sur laquelle repartir.
Je vois bien un truc du genre (pseudo code, donc inutile de me dire que ca marchera jamais comme ça, c'est une idée générale)
Merci de la précision mais je pense que je m'en serai doutée :)
Le problème c'est que si nb est supérieur à la taille de la liste ça va planter (segmentation fault au moment de faire p = p->next). Par ailleurs tu n'as pas à faire de free(p) (chaque free est associé à un malloc et là tu n'as pas fait de malloc, et une fonction de recherche ).
Ici je suppose que tu stockes dans ta structure de liste le premier maillon (begin), le dernier (end), et le nombre de maillon (size). On cherche le maillon i avec i dans {0...l.size}. On retourne NULL s'il n'existe pas. On garantit que i est positif en utilisant un unsigned plutôt qu'un int.
maillon *recherche(liste l,unsigned n){
unsigned i=0;
maillon *p;
if(n == l.size - 1) return l.end; // dernier élément de la liste, accès en O(1)
if(n >= l.size) return NULL; // en dehors de la liste, réponse en O(1)
for(p = l.begin; p != l.end ; p = p->next, ++i){
if(i == n) return p; // nieme élément de la liste, accès en O(n)
}
return NULL; // n'arrive jamais
}
Sinon tu peux jeter un oeil à cette implémentation : liste simplement chainee
Bonne chance
merci de cette aide, avec ça et ce que j'ai trouvé hier sur le site (exactement ce que tu me donne en lien) je devrait pouvoir m'en sortir avec les liste chainée.
Une simple remarque sur ta dernière réponse:
j'espère que c'est le fait d'avoir dit que je dois faire un programme pour l'école (et donc que je dois être en informatique) qui t'as fat parler de complexité temporelle. Si ce n'est pas le cas, pense que tout le monde ne comprend pas ce genre de chose, moi ça va pas de prob à ce sujet, j'ai étudié ca presque 1 an.
Une simple remarque sur ta dernière réponse:
j'espère que c'est le fait d'avoir dit que je dois faire un programme pour l'école (et donc que je dois être en informatique) qui t'as fat parler de complexité temporelle. Si ce n'est pas le cas, pense que tout le monde ne comprend pas ce genre de chose, moi ça va pas de prob à ce sujet, j'ai étudié ca presque 1 an.
Ne t'inquiète pas beaucoup d'informaticiens savent ce qu'est la complexité ;) Par exemple si tu vas sur la doc de boost par exemple (qui est plutôt une librairie s'adressant à des informaticiens vue qu'elle est assez technique à utiliser), la complexité est souvent donnée. Exemple :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/push_relabel_max_flow.html
Et au pire si tu n'avais pas compris, tu m'aurais demandé et je t'aurais répondu, non ? :)
Bonne continuation avec les listes !
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/push_relabel_max_flow.html
Et au pire si tu n'avais pas compris, tu m'aurais demandé et je t'aurais répondu, non ? :)
Bonne continuation avec les listes !
