[C]Aide pour écrire un algo
Fermé
Grizzly
-
19 mai 2006 à 18:52
mamiemando Messages postés 33407 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 29 novembre 2024 - 20 mai 2006 à 00:11
mamiemando Messages postés 33407 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 29 novembre 2024 - 20 mai 2006 à 00:11
A voir également:
- [C]Aide pour écrire un algo
- Ecrire en gras sur whatsapp - Guide
- Application pour écrire les chiffre en lettre - Télécharger - Outils professionnels
- Ecrire en miroir - Guide
- Écrire en majuscule - Guide
- Application pour ecrire une lettre - Télécharger - Dictionnaires & Langues
4 réponses
mamiemando
Messages postés
33407
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
29 novembre 2024
7 806
19 mai 2006 à 21:07
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
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
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
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; }
Salut,
est-ce que quelqu'un pourrait m'indiquer des pseudos-code s'il vous plait car je n'y arrive pas ?
Merci
est-ce que quelqu'un pourrait m'indiquer des pseudos-code s'il vous plait car je n'y arrive pas ?
Merci
mamiemando
Messages postés
33407
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
29 novembre 2024
7 806
20 mai 2006 à 00:11
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
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