besoin d'aide pour structure arbre - Page 1

J'ai un fichier de donnee contenant des noeuds n1 a n6
afin d'etablir un arbre

chaque noeud peut etre entouré de 4 noeud chacun
tout ça en liste chainee


je ne sais pas comment m'y prendre

- la balise [pre] permet d'éviter de niquer les espaces et d'éviter que texte[i] bousille le reste du post à cause de [i]
- traite le fichier ligne par ligne sans revenir sur tes pas, ça te donnera de meilleures performances et ça permettra à ton programme de lire indifféremment un vrai fichier ou un flux genre stdin
- pour pouvoir faire référence aux noeuds pas encore définis, tu vas être obligé de créer des noeuds "incomplets", i.e. dont on ne connaît pas encore la liste des voisins ; en gros il suffit que tu aies une fonction chercher_noeud_ou_creer_si_inexistant(nom_du_noeud) que tu appelles à chaque fois que tu as besoin de transformer la chaîne "n6" en un NODE * ^^

(et par rapport au titre, ta structure est un graphe, pas un arbre )

ouah merci a toi je commence a comprendre un peu plus

j'avais justement en tete de creer la fonction recherche, (faire la fonction creer_si_inexistant a part mais j'y reflechirais mieux apres), et je pensais faire en sorte que cette fonction prend en argument le nom du noeud a rechercher, et renvoi son adresse

j'aimerais que tu me dises ce que t'en penses, parce que je debute dans ce genre de principe

faux

En fait "tete" est l'adresse du tout 1er noeud, que je garde dans mon programme a tout moment, pour connaitre l'origine de la pile
"id" est le nom du noeud (exemple n1)
j'aimerais que la fonction recherche retourne donc l'adresse du noeud qui possede le nom "id", ou renvoi NULL s'il n'existe pas
mais a force d'appeler lui même la fonction recherche, je n'arrive pas a savoir si l'argument retourné est bien le bon

et je ne peux pas tester etant donné que je n'ai pas encore reussis a faire la fonction qui gere la pile

qu'en penses tu ?

Pour la ligne en vert dans le code, puisqu'il y a un element qui est l'adresse du precedent, il est peut etre pas necessaire d'en traiter 4, mais alors comment traiter les bons ?


en fait comme les noeuds se recoupent, j'ai peur que ma fonction tourne en rond comment eviter ça ? compter le niveau de recherche, et ne pas aller sur un element deja comptabilisé ? en determinant le numero d'un noeud a partir de son identifiant ?

Au passage, je n'ai pas créé d'element precedent dans la structure, puisque je ne sais pas vraiment lequel est le precedent etant donne le nombre de connexion pour chaque noeud. Un noeud peut etre relié a 4 autres noeuds maximum


C'est un vrai casse tete ce truc !

merci !!

Plusieurs remarques :
- tu vois bien qu'avoir 4 membres différents suivant1..4 ça t'oblige à dupliquer plein de code : ce serait plus pratique de déclarer un tableau à 4 éléments, et en plus ça te permettra par la suite d'augmenter le nb maximum de voisins si nécessaire (et même si tu n'en as pas besoin c'est quand même une bonne idée de faire #define MAX_VOISINS 4)
- l'idée de parcourir les voisins d'un noeud donné, c'est pas idiot mais outre le fait que tu risques de faire une boucle infinie (mais ça ça peut se corriger), ça t'empêche d'avoir plusieurs composantes connexes -- au sens où si deux réseaux ne sont pas (ou pas encore) reliés, tu t'interdis d'aller chercher le noeud parmi le 2è réseau, du coup tu vas devoir en créer un nouveau dans le 1er réseau et ça c'est un gros problème... en fait ce que tu voudrais c'est plutôt parcourir *tous* les noeuds, donc il faut que tu aies un moyen d'accéder à tous les noeuds : peut-être que tes noeuds sont des éléments d'un tableau et dans ce cas-là il te suffit de parcourir le tableau, ou peut-être que tu dois prévoir une liste chaînée pour pouvoir parcourir les noeuds dans leur ordre d'allocation ^^
- c'est quoi struct reseau ?

la 1ere colonne c'est le noeud identifié, les autres colonnes sont les noeuds ratachés
donc a prioris les noeuds sont declarés à peu près dans l'ordre

C'est un programme qui ne sera pas ultra complexe, limité a 4 voisins par noeud, dont le noeud precedent, et avec un seul réseau a gerer
En effet utiliser un tableau pour les voisins ça peut simplifier


"struct reseau" -> erreur de frappe


Il est en effet prevu aussi une liste chainee qui peut permettre aussi de repertorier tous les noeuds, dans leur ordre d'allocation, mais cette liste ne me servira pas a obtenir leur adresse ! juste a savoir s'ils ont deja ete alloué


Comment d'apres toi je peux faire une fonction de recherche
- en ayant une liste chainee qui contient les noeuds enregistré dans leur ordre d'allocation
- et a partir d'un noeud d'origine, relié a 4 voisins chacun ?

cette fonction recherche doit renvoyer l'adresse du noeud dont le nom est precisé
Avec l'autre liste chainee je peux savoir a l'avance si le noeud existe ou non, mais je ne peux pas savoir ou il est


exemple ligne4 Comment retrouver l'adresse de n4 ?

en fait, voila comment je pense m'y prendre
le fichier texte est organisé en 5 colonnes (4 voisins + le nom du noeud en question)(sur l'exemple presenté ici il n'y a que 3 voisins maxi, donc 4 colonnes)


=> comment savoir si 2 noeuds possede le même nom ?
=> quelles sont les autres solution pour retrouver l'adresse d'un noeud autrement qu'en parcourant le graph depuis le 1er noeud, et autrement qu'en stockant les adresses dans un tableau ?