[C]Aide pour écrire un algo

Fermé
Grizzly - 19 mai 2006 à 18:52
mamiemando Messages postés 33304 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 octobre 2024 - 20 mai 2006 à 00:11
Bonjour,

j'aurais besoin d'aide pour écrire en pseudo ou en C, des fonctions pour la création d'un réseau d'IP . Je décris la manière de procéder.

A - B - C - X
     |    |
     |    H - Z
    E - G - Y 


struct s_IP
{
       char IP[4];// adresse IP
       struct s_IP **tabIP; // tableau des adresse des noeuds associés (tableau dynamique)
}



Le noeud "A" contiendra l'adresse du noeud "B"
Le noeud "B" contiendra les adresses des noeuds "C" et "E"
Le noeud "C" contiendra les adresses des noeuds "X" et "H"
etc

Dès qu'on récupères une IP, il faut
- savoir si elle est présente dans l'arbre => une fonction qui renverra l'adresse du noeud contenant cette IP si elle est présente
- si elle n'est pas présente, comme on as gardé l'adresse du noeud qui était juste avant, on crées un nouveau noeud pour cette IP et on l'insères comme fille du noeud juste avant.

Ex: On cherche A-B-C-Y

Il faut chercher "B" juste sous "A" mais pas en profondeur. Puis "C" sous "B" puis "Y" sous "C". Et là, la fonction renverra "NULL" donc on insère "Y" sous "C"

Ensuite, une fois qu'on a inséré un noeud, tous les noeuds suivants seront mis à partir de ce noeud.
Donc avec "A-B-C-Y-H-Z" et l'algo ci-dessus, le "Y" ira sous le "C", le "H" ira sous le "Y" précédent et le "Z" ira sous le "H" précédent et tu obtiendras
A - B - C - X
     |    |   |
     |    |   Y - H - Z
     |    H - Z-Y
    E - G - Y 


Comme la recherche ne se fait pas en profondeur mais juste sur un niveau, la fonction n'a pas besoin d'être récursive

4 réponses

mamiemando Messages postés 33304 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 octobre 2024 7 794
19 mai 2006 à 21:07
Pose une question plus précise, genre sur quel point tu bloques... En effet pour que l'exercice soit enrichissant il faut que ce soit toi qui le fasse, car sinon on va te donner la réponse et tu n'en auras rien retiré.

La première étape est de réflechir qui vont stocker l'information. Ici ca consiste a représenter les éléments d'un graphe (ie des arcs et des sommets), et les données encapsulées par ces élements (adresse ip, nom du routeur...).

Une fois la structure de donnée définie, il faut écrire quelques fonctions pour les manipuler aisément (ajout d'un arc entre deux sommets, récupérer les arcs sortants d'un sommet, récupérer un sommet à partir de som nom, etc...)

Après avoir écrit cette partie assez générique écrite (qui existe déjà dans certaines libs opensource comme boost pour le C++.. cf la BGL), tu peux réfléchir a l'algorithme proprement dit...

Bonne chance
0
Salut,

j'ai codé tout ça pour des sommets "normaux" du style : 1,2,3.... mais mon problème est que je ne n'arrive pas à l'adapter au sommet IP

Je met les codes que j'ai écrit en espérant que vous puissiez m'aider pour les modifications :

Merci d'avance

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




typedef struct cellule{
  int val;
  struct cellule *next;
}Cellule;
typedef Cellule *Liste;



typedef struct graphe{
  int size;
  Liste *adj;
}Graphe;



Cellule *CreerCellule(int val){
  Cellule *c = (Cellule*)malloc(sizeof(Cellule));
  if(c == NULL)
    return NULL;
  
  c->val = val;
  c->next = NULL;
  
  return c;
}


Liste consListe(int val, Liste liste)
{
  Liste parcours ;
  Cellule* c = CreerCellule(val);
  
  if (!c) return NULL ;
  
  if ( liste == NULL )
    {
      c->next = NULL ; 
      return c ;
    }
  
  for(parcours=liste; parcours->next; parcours=parcours->next ) ;
  
  parcours->next = c ;
  return liste;
}


Graphe *consGraph(int size){
  int i;
  
  Graphe *g = (Graphe*)malloc(sizeof(Graphe));
  if(g == NULL)
    return NULL;
  
  g->size = size;
  
  if(size > 0)
    g->adj = (Liste*)malloc(size*sizeof(Liste));
  else
    g->adj = NULL;
  
  for(i=0; i<size; i++)
    g->adj[i] = NULL;
  
  return g;
}

void addEdge(Graphe *g, int source, int dest){
  g->adj[source] = consListe(dest, g->adj[source]);
}

int main(void)
{
  int i ; Liste parcours ;
  Graphe *g = NULL;
  g = consGraph(3);
  
  addEdge(g,0,1);
  addEdge(g,0,2);
  addEdge(g,1,2);
  
  for( i=0; i<g->size; i++ )
    {
      printf( "Sommet %d :", i );
      for( parcours=g->adj[i]; parcours; parcours=parcours->next )
	printf( " %d", parcours->val ) ;
      printf ("\n" ) ;
    }
  return 0;
}
0
Salut,

est-ce que quelqu'un pourrait m'indiquer des pseudos-code s'il vous plait car je n'y arrive pas ?

Merci
0
mamiemando Messages postés 33304 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 octobre 2024 7 794
20 mai 2006 à 00:11
Ah oui c'est ta structure qui n'est pas adaptées c'est pour ca. Il faut que tu definisses une structure aussi proche que ce que tu veux décrire pour que ce soit facile à manipuler.

Dans le acs d'un graphe, une matrice d'adjacence M, avec Mij le poids de l'arc i->j (avec Mij = inifini si i et j ne sont pas adjacents) est plus adapté qu'une liste. Il est aisé ensuite de déterminer les arcs sortants ou entrants d'un sommet.

Tu peux aussi partir sur une structure avec un sommet contenant une liste de pointeurs sur ses arcs sortants et/ou entrants, mais c'est plus compliqué (structures croisées etc...).

Ensuite il suffit pour ton algo de ce dire je cherche le sommet source du chemin cherché dans le graphe. Si je le trouve, je regarde ces arcs sortants, et je vérifie que le 2e sommet du chemin est adjacent au premire (en parcourant les arcs sortants du premier sommet). Et ainsi de suite jusqu'à avoir déterminé si le chemin existait ou non.

Bonne chance
0