[C] Arbre n-aire

#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;
}

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

typedef struct maillon * liste;

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é
  }
}

~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

#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

#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);
}

#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

#include "graph.h"

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

//...