Algorithmes en C Fermé

Question

Salut,j'aurais besoin d'aide pour ce projet.Merci d'avanceSYNOPSIS graphes –dkpf [-o] [n] fichierDESCRIPTIONUne des options au moins doit obligatoirement etre presente.Elles ne sont pas toutes mutuellement exclusives et certaines pourront etre demandées en meme temps.Les graphes traités sont tous valués par des entiers,et peuvent contenir des aretes (i,i) ou i est un sommet.Options -o le resultat doit etre place dans un fichier de meme nom que le fichier d’entrée suffixe par .optionS’il y a plusieurs options,plusieurs fichiers devront etre crées.Ainsi la commende graphes –dp –o fic produira le fichier fic.d et fic.pEn cas d’absence de cette option les résultats seront affichés sur la sortie standart. -d n plus courts chemins,ayant pour origine le sommet n.Si le graphe comporte des arcs de cout négatif on appliquera l’algo de Bellman-Ford.Si tous les arcs ont un cout positif,on appliquera l’algo de Dijkstra avec une file de priorité.             entrée fichier de type GRAPHE            sortie fichier de type LISTE contenant sur la i ème ligne la plus courte distance entre le sommet n et le sommet i suivie de la suite des sommets intermediaires sur le plus court chemin.S’il n’existe pas de plus court chemin entre n et i,la ligne sera vide.exemple graphe oriente:0->1 (poids 4),1->0(2),1->2(2),2->0(5),2->1(3)graphe non oriente:0--1(3),1--2(1),2--0(5) -f plus courts chemins entre chaque couple de sommets,en appliquant l’algo de Warshall-Floyd.             entrée fichier de type GRAPHE             sortie fichier de type GRAPHE séparés par une ligne vide, le graphe des distances suivi du graphe des prédécesseurs sur un plus court chemin. -p arbre recouvrant minimal par la méthode de Prim             entrée fichier de type GRAPHE             sortie fichier de type ARBRE -k arbre recouvrant minimal par la méthode de KruskalMeme type de fichiers que pour l’option [-p]                         FORMAT DES FICHIERS Tous les entiers indiques sur une meme ligne sont separes par un unique caractère espace.Pas d’espace avant le premier ou après le dernier.Toutes les lignes se terminent par 
 Les fichiers de format GRAPHECes fichiers contiennent la description d’un graphe sous forme de matrice d’adjacence ou de listes d’adjacence.première ligne : nombre de sommets deuxième ligne : une lettre indiquant le type du graphe : o pour graphe orienté, n pour graphe non oriente troisième ligne : une lettre indiquant le type de représentation du graphe, m pour matrice d’adjacence , l pour listes d’adjacence lignes suivantes : les lignes de la matrice ou la suite des listes            Pour les graphes données en exemple            -Representation par matrice du graphe orienté            3            o            m            0  4  0            2  0  2            5  3  0             -representation par listes d’adjacence du graphe orienteles arcs sont donnés sous forme de suites de 2 valeurs : cout sommet atteint             3             o             l            4  1            2  0  2  2            5  0  3  1  Cas d’un graphe non orienté             -Representation par matrice du graphe non orinente On ne fournit que la matrice triangumaire supérieure             3             n             m             0  3  5             0  1             0              -Representation par listes d’ajacences du graphe non oriente :un arc n’apparaît qu’une fois,associé à son extrémité de plus petit indice :              3              n              l             3  1  5  2             1   2 Remarques :-si un sommet n’a pas d’arc sortant,la ligne correspondante dans les fichiers est réduite au caractère passage à la ligne.-la plupart des algos fonctionnent le plus rapidement avec un type particulier de représentation en mémoire.A vous de convertirA vous de convertir le sformats pour utiliser la representation en memoire la plus adaptée. Les fichiers de format ARBRE Première ligne :  nombres d’arcs  Deuxieme ligne : poids de l’arbre Lignes suivantes : sur chaque ligne ,un arc de l’arbre recouvrant (indique par un couple de sommets en ordre craoissant ),les differents couples etant tries dans l’ordre croissant. Les fichiers de format LISTE Sur chaque ligne,une liste de sommets Pour tous les algos de distances ,lorsque la distance entre 2 sommets est infinie ,on affichera IS’il existe un chemin non trivial(formé d’au moins un arc) d’un sommet à lui-meme ,le programme devra fournir la longueur du plus court ,et fournir la valeur 0 s’il n’y ap pas de chemin non trivialEn entrée ,l’absence d’arc est symbolisée par 0Lorsqu’il y a plusieurs réponses possibles ,seule la plus petite dans l’ordre lexicographiqueest demandée.Un graphe non oriente sera considere comme oriente dans les 2 sens.Si le fichier en entrée est incorrect ,la sortie sera vide avec message d’erreur sur stderr.

mamiemando · Answer

Oui alors l'idée c'est qu'on n'est pas là pour faire ton projet. Donc il faut cibler un peu le problème et nous dire sur quoi tu bloques, et là on se fera un plaisir de t'aider :-)

Cartoon · Answer

Je sais bien mais est ce que tu pourrais m'indiquer,les champs que tu mettrais pour la sructure matrice et liste.

mamiemando · Answer

Une matrice se caractérise par les données qu'elle contient. Sauf qu'un tableau en C, on ne connait a priori pas sa taille sauf si on la passe en paramètre, donc il faut stocker le nombre de ligne et de colonne. Les cases de données seront allouées avec une fonction pour créer la matrice (l'équivalent du constructeur en C++), et détruite par une autre (par exemple dès que ut n'auras plus besoin de la matrice) (on parle en C++ de destructeur).

Ainsi, en C ça donne :

#include <stdio.h>

struct matrix{
   unsigned int nb_rows;
   unsigned int nb_columns;
   double **data;
};

struct matrix new_matrix(unsigned int nrows,unsigned int ncolumns){
  unsigned int i;
  struct matrix m;
  m.nb_rows=nrows;
  m.nb_columns=ncolumns;
  m.data=(double **) malloc(sizeof(double *)*nrows);
  for(i=0;i<nrows;++i){
     m.data[i]=(double *) calloc(sizeof(double),ncolumns);
  }
  return m;
}

void del_matrix(struct matrix m){
  unsigned int i;
  for(i=0;i<m.nb_rows;++i){
     free(m.data[i]);
  }  
  free(m.data);
}

S'il y a des lignes que tu ne comprends pas n'hésite pas à demander.

Pour les listes c'est plus simple. On manipule des maillons qui stockent des données, et un maillon suivant (en supposant qu'ils stockent des doubles, mais ça peut être une adresse sur un type générique, ie un pointeur de type void *) :

struct maillon{
  double data;
  struct maillon * next;
};

typedef maillon * list;

Bonne chance

LMD_MIAS · Answer

bonsoir a tt j'arrive pas a programmer un graphe TAD
(" l'utilisateur doit entrez les ville et les distance+calcule largeur +pranfondeur +dijskraaaaaa")
tt ça en orienter objet

Algorithmes en C

4 réponses

Discussions similaires