[C] Arbre n-aire [Résolu]

Une manière de faire :

#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdio.h>

#define NB_CARACTERE 26

typedef struct noeud{
	char lettre;
	struct noeud **fils;
} noeud_t;

typedef noeud_t arbre_t;

// Cette fonction retourne
// 0 à 25 si c == 'a' à 'z'
// 26 si c == '\0' (ou autre chose)
unsigned char2index(const char c){
	char c_lower;
	if(isalpha(c)){
		c_lower = tolower(c); // convention : on met tout en minuscule
		return (c - 'a');
	}
	return NB_CARACTERE;
}

// Crée un noeud et remplit la lettre qu'il stocke
noeud_t *creer_noeud(const char c){
	noeud_t *n = (noeud_t *)malloc(sizeof(noeud_t));
	n->lettre = c;
	// calloc permet d'initialiser directement chaque n->fils[i] à NULL
	n->fils = (noeud_t **)calloc((NB_CARACTERE+1),sizeof(noeud_t *));
	return n;
}

arbre_t *creer_arbre(){
	return creer_noeud('\0');
}

// Créé un noeud fils (si besoin) correspondant à une lettre
noeud_t *creer_fils(noeud_t *n,const char c){
	unsigned idx = char2index(c);
	if (!n->fils[idx]){
		n->fils[idx] = creer_noeud(c); // nouveau fils
	}
	return n->fils[idx];
}

// Ajoute un mot dans l'arbre étant donné sa racine
void ajouter_mot(arbre_t *a,const char *s){
	unsigned i,idx_cur,n = strlen(s);
	noeud_t *noeud_cur = a;
	for(i=0;i<n;++i){
		idx_cur = char2index(s[i]);
		noeud_cur = creer_fils(noeud_cur,s[i]);
	}
	creer_fils(noeud_cur,'\0');
}

// Supprime tout le sous arbre à partir d'un noeud n
void supprimer_sous_arbre(noeud_t *n){
	unsigned i;
	for(i=0;i<=NB_CARACTERE;++i){
		if (n->fils[i]) supprimer_sous_arbre(n->fils[i]);
		free(n->fils[i]);
	}
	free(n->fils);
}

// Supprime un arbre étant donné sa racine
void supprimer_arbre(arbre_t *a){
	supprimer_sous_arbre(a);
}

// Recherche si un mot figure dans un dictionnaire
int trouver_mot(const arbre_t *a,const char *s){
	unsigned i,idx_cur,n = strlen(s);
	const noeud_t *noeud_cur = a;
	for(i=0;i<n;++i){
		idx_cur = char2index(s[i]);
		if(!noeud_cur->fils[idx_cur]) return 0;
		else noeud_cur = noeud_cur->fils[idx_cur];
	}
	return 1;
}

void ajoute_medor(arbre_t *a,const char *s){
	printf("ajoute le mot %s",s);
	ajouter_mot(a,"tapir");
}


void cherche_medor(const arbre_t *a,const char *s){
	int trouve = trouver_mot(a,s);
	printf("est ce que le dictionnaire contient %s ? %i\n",s,trouve);
}

int main(){
	arbre_t *a = creer_arbre();
	printf("1) ajoute les mots\n");
	ajoute_medor(a,"tapir");
	ajoute_medor(a,"tapis");
	ajoute_medor(a,"tapisser");
	printf("2) cherche les mots\n");
	cherche_medor(a,"tapir");
	cherche_medor(a,"tapis");
	cherche_medor(a,"plop");
	printf("3) supprime l'arbre\n");
	supprimer_arbre(a);
	return 0;
}

Bonne chance

Pour résoudre le problème proprement il faut distinguer à mon avis deux choses :
- d'une part la structure de l'arbre, indépendante du contenu des noeuds
- d'autre part la structure encapsulée dans le noeud de l'arbre contenant les données (ici les adresses ip)

Typiquement, si on faisait une liste chainées générique ça donnerait :

struct maillon{
  void * data; //adresse de la capsule
  struct maillon * next;  
};

typedef struct maillon * liste;

Ici chaque noeud ne contient pas un pointeur vers un noeud suivant, mais n pointeurs vers chacun des n successeurs potentiels puique nous sommes dans un arbre n-aire.

Dans ton cas, il faudrait voir l'intérêt de faire un arbre, car s'il est de profondeur 1 ce n'est pas rentable aussi bien en terme d'accès que de taille de stockage. Peux-tu préciser ce que tu veux faire ?

Bonne chance

Salut,
c'est bien avec un arbre qu'il faut faire cette représentation.

J'ai oublié de préciser qu'il faut pour un noeud donné pouvoir accéder à ses fils mais également à son père

je donne un exemple si un traceroute donne ceci pour résultat (les lettres représentent des IP. La partie pour la récupération des IP d'un traceroute donné a été écrite)
traceroute D
A
B
C
D

l'arbre sera le suivant
A-B-C-D

on insère les sommets ainsi que ces fils. Chaque sommet doit pouvoir accéder à son père

si un autre traceroute donne
traceroute D
A
C
B
D

on insère rien dans l'arbre car tous ces sommets sont déjà présents(la notion de chemin différent n'est pas importante dans mon cas)

Ce qui compte est les premiers résultats obtenus puis on ajoute les autres s'ils ne sont pas présents dans l'arbre

Je ne sais pas si je suis clair.

En tous les cas, il faut bien utiliser un arbre ayant n fils car un sommet donné peut en avoir plusieurs

Si c'est bon j'ai compris. Chaque noeud doit encapsuler l'ip. Ensuite le pseudo code est :

noeud courant = racine
Pour chaque ip du traceroute{
  chercher parmi les successeurs de noeud courant l'ip courante
  si pas trouve{
    ajouter cette ip comme successeur du noeud courant
    noeud courant = noeud ajouté
  }sinon{
    noeud courant = noeud trouvé
  }
}

Avec ces indications et celle de la dernière fois tu dois pouvoir y arriver.

Bonne chance

Salut,

merci pour le pseudo-code.

Pour ce qui est de savoir le père d'un noeud donné, comment dois-je faire ?

Salut,

en faite, ma structure est inadaptée car un sommet donné peut apparaitre dans plusieurs fils par exemple :

A-------
| \ |
E B D
| |
F C
/ | |
H D D

Par exemple on pourrait avoir ce type d'arbre.

Lorsqu'il faudra ajouter un fils à D, quel D sera choisit ?

Que proposeriez-vous pour pouvoir représenter les résultats des différents traceroute sans encombre?

En effet. En réalité, si tu fais un traceroute à partir d'une seule source, le graphe obtenu n'est pas dans le cas général un arbre, mais un graphe sans cycles orientés. Néanmoins ta structure sera inadaptée, comme tu l'as très bien fait remarquer.

Il faut donc partir sur une tructure de graphe orienté. A priori tu peux t'en sortir avec juste les arcs sortants des sommets (cf le pseudo code).

Méthode 1 :

A l'époque j'avais dit :
Ici chaque noeud ne contient pas un pointeur vers un noeud suivant, mais n pointeurs vers chacun des n successeurs potentiels ...

Ceci reste valable :-) Ce que tu veux faire se fait assez facilement en C++, par exemple en boost (BGL), ou même directement avec la STL. Tu peux t'orienter vers une structure équivalente si tu prends le temps de réimplémenter une liste triée par exemple, pour stocker dans un sommet la liste de ses arcs sortants.

C'est la meilleure solution pour un graphe de grande taille.

Méthode 2 :

Dans ton cas si le graphe n'est pas trop grand, l'implémentation du graphe la plus simple est d'utiliser une matrice d'adjacence W, telle que :
- Wij est le poids de l'arc partant du sommet i à destination du sommet j
- Wij = infini si i et j ne sont pas adjacents.

Dans notre cas les arcs du graphe ne sont pas pondéré si tu ne considère pas les délais, et on peut choisir le codage 1 = relié, 0 = non relié.

Tu peux aussi utiliser une structure de matrice creuse pour que la structure soit moins lourde en mémoire.

Bonne chance

Bonjour,

voici l'énoncé du programme qu'il me faut effectuer.
Je sollicte votre aide car je tourne au rond et n'y arrive pas.
La partie graphe me pose problème concernant le choix des structures adaptées au problèmes ainsi que les fonctions à créer pour cela.

En vous remerciant par avance.


Enoncé :


Le réseau Internet peut être grossièrement assimilé à un graphe, dont les noeuds sont les hôtes (machines, routeurs...) et les arêtes les liens entre ces hôtes. Depuis un noeud A donné, il est très difficile d'avoir une vue d'ensemble du réseau ; cependant, on peut effectuer un « traceroute » vers un autre noeud B, et dans la plupart des cas, obtenir une liste de noeuds formant un chemin entre A et B.


Sur Internet, une machine (ou un routeur, c'est pareil!) peut avoir 1 ou plusieurs adresses IP, et chaque adresse IP peut avoir 0, 1 ou plusieurs noms DNS rattachés. Inversement, un nom DNS peut être rattaché à 0, 1 ou plusieurs adresses IP. Comme les relations entre les adresses IP et les noms DNS sont complexes, on ignorera complètement les noms DNS. D'autre part, même si une machine peut avoir plusieurs adresses IP, on n'essaiera pas de « deviner » si plusieurs adresses appartiennent à la même machine ou pas. On raisonnera donc, finalement, en adresses IP plutôt qu'en machines ou routeurs ou noms DNS.

L'option -n de la commande traceroute permet de désactiver la résolution DNS (la conversion des adresses IP en noms)

~traceroute -n 192.48.96.9
traceroute to 192.48.96.9 (192.48.96.9), 30 hops max, 40 byte packets
 1  192.168.0.1  9.754 ms  9.461 ms  8.046 ms
 2  195.6.244.14  60.885 ms  48.924 ms  90.517 ms
 3  194.206.126.244  50.503 ms  48.97 ms  120.122 ms
 4  194.206.126.2  55.655 ms  52.213 ms  58.908 ms
 5  208.213.229.130  588.303 ms  589.843 ms  589.611 ms
 6  208.213.229.129  599.564 ms  599.763 ms  600.749 ms
 7  208.213.229.226  629.167 ms  599.284 ms  599.383 ms
 8  195.10.40.34  599.152 ms  599.289 ms  631.011 ms
 9  157.130.34.217  642.326 ms  715.072 ms  653.724 ms
10  146.188.160.62  595.143 ms  590.433 ms  659.247 ms
11  146.188.160.181  649.863 ms  700.901 ms  617.067 ms
12  137.39.253.86  600.835 ms  599.379 ms  590.867 ms
13  192.48.96.9  607.071 ms  589.221 ms  603.156 ms

Attention, le graphe d'Internet n'est pas forcément un graphe « idéal », et les chemins que vous verrez apparaître en faisant des « traceroute » ne seront pas forcément les meilleurs ou les plus courts. Ne vous étonnez pas si par exemple, sur un traceroute, vous voyez des chemins non-optimaux !

D'autre part, ce n'est pas non plus un graphe figé ni déterministe, donc d'un jour à l'autre (ou même d'une minute à l'autre) un même traceroute pourra donner des résultats différents.

But

Il s'agit d'écrire un programme (ou un ensemble de programmes) permettant d'effectuer des traceroute automatiquement, en tâche de fond ; et pendant que se font ces traceroute, de rassembler des informations sur le graphe d'Internet. En particulier, pour chaque noeud du graphe (on assimilera un noeud à son adresse IP), on souhaite pouvoir connaître ses voisins, ainsi que sa distance minimale à l' « origine » (la distance n'est pas forcément constante, par exemple entre le noeud A et le noeud B, le noeud X peut apparaître en 5è position ; et le même noeud X peut apparaître en 8è position entre le noeud A et le noeud C -- c'est surprenant, mais c'est possible!).

Il est indispensable de pouvoir :

* avoir plusieurs traceroute s'effectuant simultanément, afin de rassembler des informations le plus vite possible ;
* pouvoir choisir à la volée combien de traceroute on souhaite exécuter en parallèle) ;
* ajouter de nouvelles « cibles » pour traceroute pendant que l'ensemble fonctionne ;
* ajouter des cibles « aléatoires » (en tirant des adresses IP au hasard) ;
* visualiser des statistiques indiquant le nombre d'adresses IP « explorées » (nombre total, et classement par distance par rapport à l'origine) ;
* indiquer les « voisins » d'un noeud donné par son adresse IP ;
* exporter (et importer) l'état du graphe, sous forme de deux fichiers CSV : un contenant la liste des sommets (adresses IP) avec leur distance minimale à la source, et un autre contenant une liste de couples d'adresses IP ;


Informations techniques

Une adresse IP = 4 octets. Généralement on la représente sous la forme 134.157.0.129 (sous forme de 4 nombres entiers, en décimal, séparés par des points).
Les plages d'adresses suivantes sont « privées », c'est-à-dire internes :

* 10.0.0.0 à 10.255.255.255
* 172.16.0.0 à 172.31.255.255
* 192.168.0.0 à 192.168.255.255

La plage 224.0.0.0 à 239.255.255.255 est réservée au multicast.
Les adresses de 240.0.0.0 à 255.255.255.255 sont réservées.
Toutes ces plages (adresses privées, multicast, réservées) ne doivent pas être traitées

Le format CSV à utiliser, pour la liste des noeuds : adresse IP, distance
1.2.3.4,17
134.157.0.129,8
193.55.63.92,2
Le format CSV à utiliser, pour la liste des arêtes : adresse IP1, adresse IP2
1.2.3.4,1.2.3.5
134.157.0.129,134.157.254.1
193.55.63.1,193.55.63.29
On utilisera \n comme séparateur de lignes

Tu n'as meme pas dit si tu voulais coder un graphe avec la première ou la deuxième méthode !! Fais un effort pour lire ce que j'écris !!

list.h

#ifndef LIST
#define LIST
#include <stdlib.h>

struct maillon{
  void * data; //L'adresse de la donnée a stocker dans le maillon
  struct maillon * next;
};

struct list{
  struct maillon * begin;
  struct maillon * end;
  unsigned size;
}

//Crée une nouvelle liste
struct list new_list();

// Ajoute un elt en fin de liste en prenant son adresse
struct append(struct list l,void * add);

#endif

list.c

#include "list.h"

//Crée une nouvelle liste
struct list new_list(){
  struct list l;
  l.begin = NULL;
  l.end = NULL;
  l.size = 0
  return l;
}

// Ajoute un elt en fin de liste en prenant son adresse
void append(struct list l,void * addr){
  struct maillon * m = (struct maillon *) malloc(sizeof(struct maillon));
  m->data = addr;
  m->next = NULL;
  if (l.end){ //Liste non vide
    l.end->next = m;
    l.end = NULL;
  }else{ //Premier maillon inséré dans la liste
    l.begin = m;
    l.end = m;
  }
  ++(l.size);
}

graph.h

#ifndef GRAPH
#define GRAPH

struct vertex{
  void * data; //pointeur vers une structure contenant les infos d'un sommet (ici par exemple une structure stockant l'adresse ip)
  list out_edges; // la liste des arcs sortants
};

struct edge{
  struct vertex * source;
  struct vertex * target;
  void * data;//pointeur vers une structure contenant les infos d'un sommet (ici par exemple une structure stockant le delai)
};

struct graph{
  list vertices; // la liste des sommets
  list edges; // la liste des arcs
};

// Crée un graphe vide
struct graph new_graph();

//Ajoute un sommet
void add_vertex(
  struct graph g,
  struct vertex,
  void * addr_data_vertex
);

//Ajoute un arc
void add_edge(
  struct vertex source,
  struct vertex target,
  void *addr_data_edge
);

//...

#endif

graph.c

#include "graph.h"

struct graph new_graph(){
  struct graph g;
  g.vertices = new_list();
  g.edges = new_list();
  return g;
}

//...

Je te laisse finir.

Bonne chance

je veux bien que vous m'aidez :
je veux ecrire une fonction récursive de recherche d'un mot dans un dictionnaire, cette fonction possède en argument outre l'arbre r, le mot de recherche sous forme d'une chaine de caractères et un entier i qui correspond à la position de la lettre examinée dans le mot.

je vous remercie pour la réponse apporté à mon probleme à bientôt