PDA

Visualizza la versione completa : [c]aiuto esercizio grafo


razzoman
04-01-2014, 14:41
ciao a tutti sto avendo problemi col seguente programma (vi posto la consegna):
Č dato un file contenente un elenco di voli aerei, secondo il formato seguente:
la prima riga contiene il numero totale NC delle cittā (aeroporti di partenza o arrivo dei voli)
le righe successive contengono le cittā in ordine alfabetico
segue l’elenco dei voli, in ragione di uno per riga, secondo il formato:
<partenza> <arrivo> <costo> <durata>
essendo <partenza>, <arrivo>, <costo> e <durata> la cittā di partenza, la cittā di arrivo, il costo in euro (intero) e la durata in ore (reale) del volo, rispettivamente.
I voli sono ordinati secondo cittā di partenza (in ordine alfabetico crescente). Inoltre, prima di ogni gruppo di voli in partenza dalla stessa cittā, il file contiene una riga indicante il numero totale di questi voli. Si supponga, infine, che i nomi delle cittā siano delle stringhe di lunghezza massima pari a 20 caratteri e non contengano spazi.
Un possibile esempio di contenuto del file č il seguente:
7
Francoforte
Londra
Milano
NewYork
Parigi
Roma
Torino
2
Londra Francoforte 220 1.5
Londra Milano 280 2.5
2
Milano Londra 250 2.2
Milano NewYork 950 12.4
2
NewYork Londra 820 8.2
NewYork Parigi 900 9.0
1
Parigi Milano 230 2.1
3
Roma Francoforte 300 2.8
Roma Londra 400 3.5
Roma Parigi 350 2.6
2
Torino Milano 200 0.5
Torino Roma 150 1.5
Si scriva un programma in linguaggio C che legga il file in ingresso e memorizzi le informazioni in esso contenute come grafo (si rappresenti il grafo tramite matrice di adiacenza, oppure tramite liste di adiacenza).Una volta memorizzato il grafo, il programma acquisisca da input il nome di una cittā C e stampi a video l’elenco di tutte le cittā che č possibile raggiungere da C (direttamente e/o indirettamente). Si proponga una soluzione che effettui sia una visita in ampiezza che una visita in profonditā.Il programma, infine, verifichi se nel grafo acquisito sia presente, oppure no, almeno un ciclo.





ora io son riuscito a creare la matrice di adiacenza, ma non capisco come fare la seconda parte vi posto il codice

#include <stdio.h>#include <stdlib.h>
#include <string.h>
typedef struct
{
char departures[21];
char arrives[21];
int prize;
float time;
} bookings;
int main(int argc,char *argv[])
{
int i,j,k,temp,numbercity;
FILE *f;
char **cityname;
f=fopen(argv[1],"r");
bookings cities;
fscanf(f,"%d",&numbercity);
int M[numbercity][numbercity];
for(i=0; i<numbercity; i++)
{
for(j=0; j<numbercity; j++)
{
M[i][j]=0;
}
}
cityname=malloc(21*sizeof(char*));


for(i=0; i<numbercity; i++)
{
cityname[i]=malloc(numbercity*sizeof(char));


fscanf(f,"%s",cityname[i]);
}
while(!feof(f))
{
fscanf(f,"%d",&temp);
for(i=0; i<temp; i++)
{
fscanf(f,"%s %s %d %f",cities.departures,cities.arrives,&cities.prize,&cities.time);
{
for(j=0; j<numbercity; j++)
{
for(k=0; k<numbercity; k++)
{
if((strcmp(cityname[j],cities.departures)==0)&&(strcmp(cityname[k],cities.arrives)==0))
{
M[j][k]=1;
}
}


}
}
}
}
for(i=0; i<numbercity; i++)
{
for(j=0; j<numbercity; j++)
{
printf("%d",M[i][j]);
}
printf("\n");
}
return 0;
}
grazie

Loading