rss
Rechercher : dans
Par : Pertinence Date Nom d'utilisateur
Statut : Résolu

[C] Parcours d'une liste chainee

vgortz, le vendredi 19 octobre 2007 à 17:58:11
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.
Configuration: Windows XP
Internet Explorer 6.0
Répondre à vgortz  Signaler ce message aux modérateurs Aller au dernier message

1


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
mamiemando, le vendredi 19 octobre 2007 à 21:00:57
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 :
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
Répondre à mamiemando

2


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
vgortz, le vendredi 19 octobre 2007 à 21:28:25
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)
Répondre à vgortz

3


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
mamiemando, le samedi 20 octobre 2007 à 12:53:12
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
Répondre à mamiemando

4


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
vgortz, le samedi 20 octobre 2007 à 14:11:27
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 !
Répondre à vgortz

5


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
mamiemando, le lundi 22 octobre 2007 à 00:11:34
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.
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
Répondre à mamiemando

6


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
vgortz, le lundi 22 octobre 2007 à 07:08:34
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.
Répondre à vgortz

7


  • Ce message vous semble utile, votez !
  • Signaler ce message aux modérateurs
 mamiemando, le lundi 22 octobre 2007 à 10:10:06
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 :
http://www.boost.org/libs/graph/doc/push_relabel_max_flow.ht­ml

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 !
Répondre à mamiemando
[VS C++ .Net] Liste chaînée (linked list) (Résolu)bonjour, dans un exercice je dois creer une liste chainée d'une classe (acteurs) les classes que j'ai créé sont les suivantes : liste - element - acteurs - listacteurs mon probleme est que je bloque au niveau de la classe listacteurs.... www.commentcamarche.net/forum/affich-1497421-vs-c-net-liste-chainee-linked-list
[C] Liste chainée dans liste chainée. (Résolu)Bonjour, j'ai une liste chainée de contacts (nom+prénom+tel+mail). Pour chaque contacts, je souhaiterait créer une liste chainée à l'intérieur de celle çi. Mon problème est que je n'arrive pas à mettre NULL dans les (et non la) liste... www.commentcamarche.net/forum/affich-6061142-c-liste-chainee-dans-liste-chainee
Sucuture simple dans une cellule en langage C (Résolu)Salut les gars, J’ai besoin de vote aide SVP J’ai une structure simple et je veux la récupérer dans une cellule pour que je puisse construire une liste chainée simple. Et merci... www.commentcamarche.net/forum/affich-4589499-sucuture-simple-dans-une-cellule-en-langage-c
Liste simplement chaînéeLISTES SIMPLEMENT CHAINÉES Requis I. INTRODUCTION II. Définition III. La construction du prototype d'un élément de la liste IV. Opérations sur les listes chaînées A. Initialisation B. Insertion d'un élément dans la liste 1. Insertion... www.commentcamarche.net/faq/sujet-7444-liste-simplement-chainee
Les guillemets, apostrophes et les chaînesComment jouer avec les guillemets et les apostrophes dans les chaînes 1. Préambule 2. Éviter une coupure dans la chaîne 3. Ajouter un guillemet dans la chaîne 3.1 Avec l'apostrophe 3.2 Avec l'ASCII 3.3 Directement 3.3.1 Méthode... www.commentcamarche.net/faq/sujet-13095-les-guillemets-apostrophes-et-les-chaines
Envoi de commandes CISCO publipostées via SSH/TelnetExpect en action Informations générales publipmachin point cheu ? Mais c'est quoi au juste ? Le contenu des fichiers annexes commandes.txt liste.txt THE Script Commentaires Remerciements Questions / Report de Bugs /... www.commentcamarche.net/faq/sujet-9988-envoi-de-commandes-cisco-publipostees-via-ssh-telnet
TPS / CANALSAT et les chaînes italiennes (Résolu)Bonjour, à cause de la migration tps/canalsat il ne restera plus qu'une seule chaîne italienne. Qui peut m'aider? Est-ce qu'il existe une astuce pour capter les autres chaînes italiennes? Merci www.commentcamarche.net/forum/affich-4175812-tps-canalsat-et-les-chaines-italiennes
Créer une liste d'adresses email pour envoyer ma n (Résolu)j'ai créé mon site. Et je dois créer des listes d'adresses email pour informer régulièrement mes visiteurs. J'ai Outlook Express et Imac.. rien n'est dit dans l'aide de outlook ni dnas celle d'explorer. Comment ça marche ? www.commentcamarche.net/forum/affich-47-creer-une-liste-d-adresses-email-pour-envoyer-ma-n
[php] convertion d'une chaine de caractere (Résolu)Bonjour, Je sui entrain de créer un petit site php/html utilisant une base acces. A l'interieur d'une requete je souhaiterais convertir un format chaine de caractere en numérique. La fonction TO_NUMBET(chaine) n' a pas l'aire de... www.commentcamarche.net/forum/affich-1597968-php-convertion-d-une-chaine-de-caractere
Télécharger Widget Ciné TVRegarder la télé sur votre écran d'ordinateur sans matériels supplémentaires! Il vous suffit uniquement de ce petit gadget ! Widget CineTV est un gadget qui vous permet d'afficher vos programmes TV ou Ciné. Vous avez le choix entre des chaînes pré... www.commentcamarche.net/telecharger/telecharger-34055706-widget-cine-tv
Toutes les réponses pour « [C] Parcours d&#039;une liste chainee »