Listes chainées questions

Version imprimable

07/04/2008, 22h46
Klaine

Listes chainées questions

voilà j'ai une question, regardez l'image pleaze :

http://img353.imageshack.us/img353/4602/41765378hc1.jpg

voilà ma question : puis-je créer une liste chainées qui me permette de passer par exemple de B1 à F1 ?

comme vous le constatez la chaine A1 est reliée à F1 , B2 reliée à F2, et C3 reliée à F3 et que l'avant dernière reçoit la chaine A1 et B2 ...

Si oui comment puis-je l'implémenter ??

Merci :king:
08/04/2008, 09h51
ToTo13

Bonjour,

c'est une simple liste chainée : chaque maillon pointe vers un seul successeur.
Donc une liste chainée classique avec un champ *suiv afin de pointer vers le maillon suivant.
Ensuite, à toi de faire les bonnes relations.
08/04/2008, 09h55
Médinoc

Le problème, c'est qu'il y a au moins deux maillons qui pointent vers deux successeurs différents...
08/04/2008, 10h11
becoupama
Citation:

Envoyé par Médinoc

Le problème, c'est qu'il y a au moins deux maillons qui pointent vers deux successeurs différents...

si c'est que ca, une liste chainée n'est pas nécessairement cantonnée à un predecesseur et un suivant...
Code:

1 2 3 4 5 6 7 typedef struct link_list { int data; // ca ou n importe quoi d autre link_list *post1; link_list *post2; } link_list;
ok, c est pas de la grande proprete

bon, apres, j ai pas bien percute la raison du pourquoi de la question mais ca c un autre probleme :bug:
08/04/2008, 10h35
Médinoc
Déjà, pour les successeurs, il ne faut pas faire N variables.
En supposant que le nombre de successeurs maximum soit fixe, on a ceci:
Code:

1 2 3 4 5 6 7 8 #define MAX_SUCCESSORS 10 struct link_list { int data; // ca ou n importe quoi d autre struct link_list *posts[MAX_SUCCESSORS]; } typedef struct link_list link_list;
Si le nombre max n'est pas fixe, il faudra utiliser un truc encore plus élaboré qu'un tableau.
08/04/2008, 10h55
becoupama

ah, tout de suite c plus classe ;)
un chouille verbeux a mon gout, mais classe

Citation:

Si le nombre max n'est pas fixe, il faudra utiliser un truc encore plus élaboré qu'un tableau.

:yaisse2::yaisse2:
une liste chainee de successeurs, ouarf
08/04/2008, 17h01
ToTo13

Citation:

Envoyé par Médinoc

Le problème, c'est qu'il y a au moins deux maillons qui pointent vers deux successeurs différents...

:oops:: avais pas vu :aie:
Ben dans le cas il faut augmenter le nombre de successeurs ;)
08/04/2008, 20h00
Klaine

oui mais le problème c'est qu'on ne connai pas le nombre exacte de successeurs, je vais essayer de trouver une autre méthode , je vais essayer struct list_link *ptr[MAX_SUCCESSEUR] (je ne savais pas qu'on pouvait cela)

comme on ne connais pas le nombre de successeurs j'aurai juste qu'à allouer le tableau ;)

merci
09/04/2008, 00h04
Klaine

ok encore une question :
j'espère ne pas me faire uher de honte voilà :

Citation:

#define MAX_SUCCESSORS 3
struct compartiment
{
char *type;
int place;
};

struct link_list
{
struct compartiment;
struct link_list *posts[MAX_SUCCESSORS];
}
typedef struct link_list link_list;

si par exemple j'ai cette implémentation

cela veut dire que la liste de la structure compartiment pourra pointer sur 3 listes chainées différentes ?

est-ce que j'aurai ceci en mémoire :
http://img365.imageshack.us/img365/1639/pmfz7.png
09/04/2008, 09h27
Médinoc

Oui, ça a l'air bon.
09/04/2008, 18h34
Klaine

vous n'auriez pas un exemple qui l'implémente ?
09/04/2008, 22h41
Klaine

arggg je svais que ça me disait quelque chose c'est ce que l'on appel un arbre :yaisse2:
10/04/2008, 11h40
Médinoc

Sauf que ça n'en est pas un.
Ça a beau être un graphe sans cycle, ce n'est pas un arbre car ça a plusieurs racines.
10/04/2008, 15h14
Klaine

pourtant quand j'ai lu ce cours http://rperrot.developpez.com/articl.../arbres/#LII-E
c'est un peu ce que je veux faire
10/04/2008, 15h17
Médinoc

Sauf que dans le graphe que tu nous as montré, il y a trois racines.
Ou bien, on peut considérer ça plus ou moins comme trois arbres...
10/04/2008, 16h44
Klaine

ha ok je vois le truc

et ça donnerai quoi si je l'implémente voici le code à implémenter :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 3
 
struct chainon  {
                        char val;
                        struct chainon * suivant;
                };
typedef struct chainon * chaine;
 
chaine stringTchaine(char *s)
{
  chaine L=NULL,Laux=NULL;
  while(*s)
    {
      Laux=(chaine)malloc(sizeof(struct chainon));
      Laux->val=*s;
      Laux->suivant=L;
      L=Laux;
      s++;
    }
  return L;
}
 
void chaine_afficher(chaine y)
{
  if (y!=NULL){
  chaine_afficher( y->suivant);
  putchar(y->val);
  }
}
 
int main (void)
{
  chaine x,y;
  int i=0;
  char tmp[200];
  printf("\nEntrez une chaine de caracteres : ");
  scanf("%s",tmp);
  x=stringTchaine(tmp);
  chaine_afficher(x);
  printf("\n");
 
  return 0;
}