30/06/13 14:44
Massimo23
Ciao a tutti, ci tengo a precisare che sono nuova nel forum e quindi non so bene le regole però ho un problema serio e urgente.
Ho buttato giù il codice per un progetto ovvero devo a partire da un file.txt leggere un numero n di centrali e e calcolare il percorso migliore dal punto di vista dei collegamenti tra di esse.
Il problema è che quando io lo compilo mi da segmentation fault quando vado ad inserire la centrale nel terminale e non capisco dove stia l'errore ( che secondo me è nella funzione cerca_in_lista ma non riesco a capire bene quale errore è
.
Inoltre dovrei anche fare una funzione che mi calcoli i valori massimo minimo e medio dei percorsi minimi di comunicazione e volevo chiedervi una mano perché non penso di aver chiaro questo punto.
Il codice l'ho messo qui sotto ma non sapevo bene come scriververlo.
Spero di essere stata chiara, esaustiva e che possiate darmi una mano sia per l'errore sia per il codice della seconda richiesta ( visto che sono veramente settimane che ci lavoro e non riesco ).
Grazie.
/***************************************************************/
/* programma per calcolare la distanza tra le reti telefoniche */
/***************************************************************/
/******************************/
/* inclusione delle librerie */
/******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*****************************************/
/* definizione delle costanti simboliche */
/*****************************************/
#define INFINITO 5000
#define MAX_CENTRALI 100 /* massimo di centrali in input */
#define N_COLLEGAMENTI 100 /* lunghezza massima delle stringhe */
/*************************************/
/* definizione dei tipi di strutture */
/*************************************/
typedef struct vertice_grafo
{
char nome[N_COLLEGAMENTI];
int indice;
struct vertice_grafo *succ_p;
} vertice_t;
/*************************************/
/* dichiarazione delle funzioni */
/*************************************/
void inizializza(int matrice[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI]);
int acquisisci(vertice_t **testa_p,
int matrice[][MAX_CENTRALI]);
int aggiungi_vertice(vertice_t **testa_p,
char centrali[]);
void floyd_warshall(int grafo[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
int n_collegamenti);
void calcola_collegamenti(int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
vertice_t *testa_p);
int cerca_in_lista(vertice_t *testa_p,
char centrale[]);
/***************************************/
/* definizione delle funzioni */
/***************************************/
/* definizione della funzione main*/
int main()
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *testa_p = NULL; /* lavoro: puntatore alla testa della lista inizializzato a NULL */
int n_centrali, /* input: totale numero di centrali */
matrice[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che contiene i percorsi minimi per ogni collegamento possibile */
dist[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che consente di risalire al percorso da effettuare per minimizzare il percorso del collegamento */
padre[MAX_CENTRALI][MAX_CENTRALI];
/* inizializzazione delle matrici */
inizializza(matrice,
dist,
padre);
/* acquisizione dei dati di input */
n_centrali = acquisisci(&testa_p,
matrice);
/* applicazione dell'algoritmo per il calcolo del percorso più conveniente */
floyd_warshall(matrice,
dist,
padre,
n_centrali);
/* calcolo dei collegamenti */
calcola_collegamenti(dist,
padre,
testa_p);
return(0);
}
/* definizione della funzione che inizializza le matrici */
void inizializza(int matrice[][MAX_CENTRALI], /* input: matrice di adiacenza */
int dist[][MAX_CENTRALI], /* output: matrice del costo minimo per ogni collegamento possibile */
int padre[][MAX_CENTRALI]) /* oputput: matrice per minimizzare il costo dei collegamenti */
{
/* dichiarazione delle variabili locali della funzione */
int i, /* lavoro: variabile contatore i */
j; /* lavoro: variabile contatore j */
for(i=0;
(i < MAX_CENTRALI);
i++)
for(j=0;
(j < MAX_CENTRALI);
j++)
{
matrice[i][j] = ( i == j)?
0:
INFINITO;
dist[i][j] = padre[i][j] = 0;
}
}
/* dichiarazione della funzione che acquisisce i dati di input da file */
int acquisisci(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
int matrice[][MAX_CENTRALI]) /* output: matrice di adiacenza */
{
/* dichiarazione delle variabili locali della funzione */
int n_centrali, /* lavoro: numero di centrali */
esito, /* lavoro: esito della fscanf */
i, /* lavoro: variabile contatore i */
indice_p, /* lavoro: indice della centrale di partenza */
indice_a, /* lavoro: indice della centrale di arrivo */
charToInt=0; /* da char a int */
char charTmp, /* carattere corrente */
partenza[MAX_CENTRALI],/* input: centrale di partenza */
arrivo[MAX_CENTRALI]; /* input: centrale di arrivo */
FILE *f; /* lavoro: puntatore al file di input */
/* apro il file in modalità lettura */
f = fopen("file.txt",
"r";
/* acquisizione del numero di centrali */
esito=fscanf(f,
"%d",
&n_centrali);
if(esito)
while((charTmp = fgetc(f)) != EOF ){ /*leggo tt il file carattere x carattere fino la fine (eof)*/
if(charTmp=='\n'){ /* se il carattere temporaneo letto è 'a capo' */
charTmp = fgetc(f); /* allora leggo un altro carattere, il carattere successivo */
if(isdigit(charTmp)) /* se qst è una cifra la devo convertire in intero */
charToInt = charTmp-'0'; /* conversione da char a int */
for(i=0;
(i<charToInt);
i++){ /* lettura dei collegamenti di ogni centrale */
esito=fscanf(f,
"%s%s",
partenza,
arrivo);
printf("%d:%s %s\n",
charToInt,
partenza,
arrivo);
if(esito){
indice_p = aggiungi_vertice(testa_p,partenza);
indice_a = aggiungi_vertice(testa_p,arrivo);
matrice[indice_p][indice_a] = charToInt;
}
}
}
}
/* chiusura del file f */
fclose(f);
return(n_centrali);
}
/* dichiarazione della funzione che cerca la lista con tutte le centrali */
int aggiungi_vertice(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrali da inserire nella lista */
{
/* dichiarazione delle variabili locali alla funzione */
int indice, /* lavoro: indice delle centrali corrispondenti */
uguali; /* lavoro: controllo */
vertice_t *corr_p, /* lavoro: puntatore agli elementi della lista */
*prec_p,
*nuovo_p;
/* parte dalla testa e scorre ogni elemento della lista finché arriva alla fine (corr_p = NULL) oppure l'elemento */
/* da inserire è già stato inserito (uguali = 1) */
for(corr_p = prec_p = *testa_p, indice = 0, uguali = 0;
((corr_p !=NULL) && (uguali == 0));
prec_p = corr_p, corr_p = corr_p->succ_p, indice ++)
{
/* se la centrale da aggiungere è già presente si esce dal ciclo */
if((strcmp(corr_p->nome, centrali)) == 0)
uguali = 1;
}
if(uguali == 0)
{
/* aggiunta delle centrali e del relativo indice */
nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
strcpy(nuovo_p->nome, centrali);
nuovo_p->indice = indice;
nuovo_p->succ_p = corr_p;
if(corr_p == *testa_p)
*testa_p = nuovo_p;
else
prec_p->succ_p = nuovo_p;
}
else
indice--;
return(indice);
}
/* definizione della funzione per calcolare i collegamenti più convenienti */
void floyd_warshall(int grafo[][MAX_CENTRALI], /* input: grafo */
int dist[][MAX_CENTRALI], /* output: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* output: matrice per minimizzare i collegamenti */
int n_collegamenti) /* input: numero dei collegamenti */
{
/* dichiarazione delle variabili locali alla funzione */
int i, /* lavoro: variabile contatore i */
j, /* lavoro: variabile contatore j */
k; /* lavoro: variabile contatore k */
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
{
dist[i][j] = grafo[i][j];
padre[i][j] = (grafo[i][j] != INFINITO)?
i:
-1;
}
for(k = 0;
(k < n_collegamenti);
k++)
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
padre[i][j] = padre[k][j];
}
}
/* definizione della funzione che stampa a video il collegamento migliore */
void calcola_collegamenti(int dist[][MAX_CENTRALI], /* input: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* input: matrice per minimizzare i collegamenti */
vertice_t *testa_p) /* lavoro: puntatore alla testa della lista */
{
/* dichiarazione delle variabili locali alla funzione */
char partenza[N_COLLEGAMENTI], /* input: centrale di partenza */
arrivo[N_COLLEGAMENTI]; /* input: centrale di arrivo */
int indice_partenza, /* lavoro: indice rispetto alla centrale di partenza */
indice_arrivo, /* lavoro: indice rispetto alla centrale di arrivo */
esito, /* lavoro: esito della scanf */
carattere,
lung=0,
i,
j;
/* acquisizione della centrale di partenza */
printf("\nDigitare centrale di partenza\n";
esito = scanf("%s",
partenza);
for(i = 0;((carattere = getchar()) != '\n'); i++)
partenza[i] = carattere;
partenza[i]='Ciao a tutti, ci tengo a precisare che sono nuova nel forum e quindi non so bene le regole però ho un problema serio e urgente.
Ho buttato giù il codice per un progetto ovvero devo a partire da un file.txt leggere un numero n di centrali e e calcolare il percorso migliore dal punto di vista dei collegamenti tra di esse.
Il problema è che quando io lo compilo mi da segmentation fault quando vado ad inserire la centrale nel terminale e non capisco dove stia l'errore ( che secondo me è nella funzione cerca_in_lista ma non riesco a capire bene quale errore è.
Inoltre dovrei anche fare una funzione che mi calcoli i valori massimo minimo e medio dei percorsi minimi di comunicazione e volevo chiedervi una mano perché non penso di aver chiaro questo punto.
Il codice l'ho messo qui sotto ma non sapevo bene come scriververlo.
Spero di essere stata chiara, esaustiva e che possiate darmi una mano sia per l'errore sia per il codice della seconda richiesta ( visto che sono veramente settimane che ci lavoro e non riesco ).
Grazie.
/***************************************************************/
/* programma per calcolare la distanza tra le reti telefoniche */
/***************************************************************/
/******************************/
/* inclusione delle librerie */
/******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*****************************************/
/* definizione delle costanti simboliche */
/*****************************************/
#define INFINITO 5000
#define MAX_CENTRALI 100 /* massimo di centrali in input */
#define N_COLLEGAMENTI 100 /* lunghezza massima delle stringhe */
/*************************************/
/* definizione dei tipi di strutture */
/*************************************/
typedef struct vertice_grafo
{
char nome[N_COLLEGAMENTI];
int indice;
struct vertice_grafo *succ_p;
} vertice_t;
/*************************************/
/* dichiarazione delle funzioni */
/*************************************/
void inizializza(int matrice[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI]);
int acquisisci(vertice_t **testa_p,
int matrice[][MAX_CENTRALI]);
int aggiungi_vertice(vertice_t **testa_p,
char centrali[]);
void floyd_warshall(int grafo[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
int n_collegamenti);
void calcola_collegamenti(int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
vertice_t *testa_p);
int cerca_in_lista(vertice_t *testa_p,
char centrale[]);
/***************************************/
/* definizione delle funzioni */
/***************************************/
/* definizione della funzione main*/
int main()
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *testa_p = NULL; /* lavoro: puntatore alla testa della lista inizializzato a NULL */
int n_centrali, /* input: totale numero di centrali */
matrice[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che contiene i percorsi minimi per ogni collegamento possibile */
dist[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che consente di risalire al percorso da effettuare per minimizzare il percorso del collegamento */
padre[MAX_CENTRALI][MAX_CENTRALI];
/* inizializzazione delle matrici */
inizializza(matrice,
dist,
padre);
/* acquisizione dei dati di input */
n_centrali = acquisisci(&testa_p,
matrice);
/* applicazione dell'algoritmo per il calcolo del percorso più conveniente */
floyd_warshall(matrice,
dist,
padre,
n_centrali);
/* calcolo dei collegamenti */
calcola_collegamenti(dist,
padre,
testa_p);
return(0);
}
/* definizione della funzione che inizializza le matrici */
void inizializza(int matrice[][MAX_CENTRALI], /* input: matrice di adiacenza */
int dist[][MAX_CENTRALI], /* output: matrice del costo minimo per ogni collegamento possibile */
int padre[][MAX_CENTRALI]) /* oputput: matrice per minimizzare il costo dei collegamenti */
{
/* dichiarazione delle variabili locali della funzione */
int i, /* lavoro: variabile contatore i */
j; /* lavoro: variabile contatore j */
for(i=0;
(i < MAX_CENTRALI);
i++)
for(j=0;
(j < MAX_CENTRALI);
j++)
{
matrice[i][j] = ( i == j)?
0:
INFINITO;
dist[i][j] = padre[i][j] = 0;
}
}
/* dichiarazione della funzione che acquisisce i dati di input da file */
int acquisisci(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
int matrice[][MAX_CENTRALI]) /* output: matrice di adiacenza */
{
/* dichiarazione delle variabili locali della funzione */
int n_centrali, /* lavoro: numero di centrali */
esito, /* lavoro: esito della fscanf */
i, /* lavoro: variabile contatore i */
indice_p, /* lavoro: indice della centrale di partenza */
indice_a, /* lavoro: indice della centrale di arrivo */
charToInt=0; /* da char a int */
char charTmp, /* carattere corrente */
partenza[MAX_CENTRALI],/* input: centrale di partenza */
arrivo[MAX_CENTRALI]; /* input: centrale di arrivo */
FILE *f; /* lavoro: puntatore al file di input */
/* apro il file in modalità lettura */
f = fopen("file.txt",
"r";
/* acquisizione del numero di centrali */
esito=fscanf(f,
"%d",
&n_centrali);
if(esito)
while((charTmp = fgetc(f)) != EOF ){ /*leggo tt il file carattere x carattere fino la fine (eof)*/
if(charTmp=='\n'){ /* se il carattere temporaneo letto è 'a capo' */
charTmp = fgetc(f); /* allora leggo un altro carattere, il carattere successivo */
if(isdigit(charTmp)) /* se qst è una cifra la devo convertire in intero */
charToInt = charTmp-'0'; /* conversione da char a int */
for(i=0;
(i<charToInt);
i++){ /* lettura dei collegamenti di ogni centrale */
esito=fscanf(f,
"%s%s",
partenza,
arrivo);
printf("%d:%s %s\n",
charToInt,
partenza,
arrivo);
if(esito){
indice_p = aggiungi_vertice(testa_p,partenza);
indice_a = aggiungi_vertice(testa_p,arrivo);
matrice[indice_p][indice_a] = charToInt;
}
}
}
}
/* chiusura del file f */
fclose(f);
return(n_centrali);
}
/* dichiarazione della funzione che cerca la lista con tutte le centrali */
int aggiungi_vertice(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrali da inserire nella lista */
{
/* dichiarazione delle variabili locali alla funzione */
int indice, /* lavoro: indice delle centrali corrispondenti */
uguali; /* lavoro: controllo */
vertice_t *corr_p, /* lavoro: puntatore agli elementi della lista */
*prec_p,
*nuovo_p;
/* parte dalla testa e scorre ogni elemento della lista finché arriva alla fine (corr_p = NULL) oppure l'elemento */
/* da inserire è già stato inserito (uguali = 1) */
for(corr_p = prec_p = *testa_p, indice = 0, uguali = 0;
((corr_p !=NULL) && (uguali == 0));
prec_p = corr_p, corr_p = corr_p->succ_p, indice ++)
{
/* se la centrale da aggiungere è già presente si esce dal ciclo */
if((strcmp(corr_p->nome, centrali)) == 0)
uguali = 1;
}
if(uguali == 0)
{
/* aggiunta delle centrali e del relativo indice */
nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
strcpy(nuovo_p->nome, centrali);
nuovo_p->indice = indice;
nuovo_p->succ_p = corr_p;
if(corr_p == *testa_p)
*testa_p = nuovo_p;
else
prec_p->succ_p = nuovo_p;
}
else
indice--;
return(indice);
}
/* definizione della funzione per calcolare i collegamenti più convenienti */
void floyd_warshall(int grafo[][MAX_CENTRALI], /* input: grafo */
int dist[][MAX_CENTRALI], /* output: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* output: matrice per minimizzare i collegamenti */
int n_collegamenti) /* input: numero dei collegamenti */
{
/* dichiarazione delle variabili locali alla funzione */
int i, /* lavoro: variabile contatore i */
j, /* lavoro: variabile contatore j */
k; /* lavoro: variabile contatore k */
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
{
dist[i][j] = grafo[i][j];
padre[i][j] = (grafo[i][j] != INFINITO)?
i:
-1;
}
for(k = 0;
(k < n_collegamenti);
k++)
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
padre[i][j] = padre[k][j];
}
}
/* definizione della funzione che stampa a video il collegamento migliore */
void calcola_collegamenti(int dist[][MAX_CENTRALI], /* input: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* input: matrice per minimizzare i collegamenti */
vertice_t *testa_p) /* lavoro: puntatore alla testa della lista */
{
/* dichiarazione delle variabili locali alla funzione */
char partenza[N_COLLEGAMENTI], /* input: centrale di partenza */
arrivo[N_COLLEGAMENTI]; /* input: centrale di arrivo */
int indice_partenza, /* lavoro: indice rispetto alla centrale di partenza */
indice_arrivo, /* lavoro: indice rispetto alla centrale di arrivo */
esito, /* lavoro: esito della scanf */
carattere,
lung=0,
i,
j;
/* acquisizione della centrale di partenza */
printf("\nDigitare centrale di partenza\n";
esito = scanf("%s",
partenza);
for(i = 0;((carattere = getchar()) != '\n'); i++)
partenza[i] = carattere;
partenza[i]='{parsed_message}';
/* ricerca dell'indice corrispondente alla centrale di partenza */
indice_partenza = cerca_in_lista(testa_p,
partenza);
/* se la centrale non è in elenco il programma termina */
if((indice_partenza == -1) || (esito == 0))
printf("\nCentrale di partenza non presente in elenco o errore di lettura\n";
else
{
/* acquisizione della centrale di arrivo */
printf("\nDigitare centrale di arrivo\n";
esito = scanf("%s",
arrivo);
/* ricerca dell'indice corrispondente alla centrale di arrivo */
indice_arrivo = cerca_in_lista(testa_p,
arrivo);
/* se la centrale non è in elenco il programma termina */
if((indice_arrivo == -1) || (esito == 0))
printf("\nCentrale di arrivo non presente in elenco o errore di lettura\n";
else
{
/* stampa a video dei collegamenti: 1 - stampa della partenza */
printf("\nCollegamenti: %s",
partenza);
/* 2 - stampa dell'arrivo */
printf(" -> %s\n\n",
arrivo);
}
}
}
/* definizione della funzione che ricerca nell'indice che identifica una centrale */
int cerca_in_lista(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrale da ricercare nella lista */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
int indice = -1; /* lavoro: inizializzazione dell'indice rispetto ai collegamenti */
for (elem_p = testa_p;
((elem_p != NULL) && (indice == -1));
elem_p = elem_p->succ_p);
if(strcmp(elem_p->nome, centrali) == 0)
indice = elem_p->indice;
return(indice);
}
/* definizione della funzione che stampa a video il collegamento del viaggio */
void stampa_collegamento(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
int indice) /* lavoro: indice delle centrali corrispondenti */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
for (elem_p = testa_p;
((elem_p !=NULL) && (indice != elem_p->indice));
elem_p = elem_p->succ_p);
printf(" -> %s",
elem_p->nome);
}';
/* ricerca dell'indice corrispondente alla centrale di partenza */
indice_partenza = cerca_in_lista(testa_p,
partenza);
/* se la centrale non è in elenco il programma termina */
if((indice_partenza == -1) || (esito == 0))
printf("\nCentrale di partenza non presente in elenco o errore di lettura\n";
else
{
/* acquisizione della centrale di arrivo */
printf("\nDigitare centrale di arrivo\n";
esito = scanf("%s",
arrivo);
/* ricerca dell'indice corrispondente alla centrale di arrivo */
indice_arrivo = cerca_in_lista(testa_p,
arrivo);
/* se la centrale non è in elenco il programma termina */
if((indice_arrivo == -1) || (esito == 0))
printf("\nCentrale di arrivo non presente in elenco o errore di lettura\n";
else
{
/* stampa a video dei collegamenti: 1 - stampa della partenza */
printf("\nCollegamenti: %s",
partenza);
/* 2 - stampa dell'arrivo */
printf(" -> %s\n\n",
arrivo);
}
}
}
/* definizione della funzione che ricerca nell'indice che identifica una centrale */
int cerca_in_lista(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrale da ricercare nella lista */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
int indice = -1; /* lavoro: inizializzazione dell'indice rispetto ai collegamenti */
for (elem_p = testa_p;
((elem_p != NULL) && (indice == -1));
elem_p = elem_p->succ_p);
if(strcmp(elem_p->nome, centrali) == 0)
indice = elem_p->indice;
return(indice);
}
/* definizione della funzione che stampa a video il collegamento del viaggio */
void stampa_collegamento(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
int indice) /* lavoro: indice delle centrali corrispondenti */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
for (elem_p = testa_p;
((elem_p !=NULL) && (indice != elem_p->indice));
elem_p = elem_p->succ_p);
printf(" -> %s",
elem_p->nome);
}
Ho buttato giù il codice per un progetto ovvero devo a partire da un file.txt leggere un numero n di centrali e e calcolare il percorso migliore dal punto di vista dei collegamenti tra di esse.
Il problema è che quando io lo compilo mi da segmentation fault quando vado ad inserire la centrale nel terminale e non capisco dove stia l'errore ( che secondo me è nella funzione cerca_in_lista ma non riesco a capire bene quale errore è
.
Inoltre dovrei anche fare una funzione che mi calcoli i valori massimo minimo e medio dei percorsi minimi di comunicazione e volevo chiedervi una mano perché non penso di aver chiaro questo punto.
Il codice l'ho messo qui sotto ma non sapevo bene come scriververlo.
Spero di essere stata chiara, esaustiva e che possiate darmi una mano sia per l'errore sia per il codice della seconda richiesta ( visto che sono veramente settimane che ci lavoro e non riesco ).
Grazie.
/***************************************************************/
/* programma per calcolare la distanza tra le reti telefoniche */
/***************************************************************/
/******************************/
/* inclusione delle librerie */
/******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*****************************************/
/* definizione delle costanti simboliche */
/*****************************************/
#define INFINITO 5000
#define MAX_CENTRALI 100 /* massimo di centrali in input */
#define N_COLLEGAMENTI 100 /* lunghezza massima delle stringhe */
/*************************************/
/* definizione dei tipi di strutture */
/*************************************/
typedef struct vertice_grafo
{
char nome[N_COLLEGAMENTI];
int indice;
struct vertice_grafo *succ_p;
} vertice_t;
/*************************************/
/* dichiarazione delle funzioni */
/*************************************/
void inizializza(int matrice[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI]);
int acquisisci(vertice_t **testa_p,
int matrice[][MAX_CENTRALI]);
int aggiungi_vertice(vertice_t **testa_p,
char centrali[]);
void floyd_warshall(int grafo[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
int n_collegamenti);
void calcola_collegamenti(int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
vertice_t *testa_p);
int cerca_in_lista(vertice_t *testa_p,
char centrale[]);
/***************************************/
/* definizione delle funzioni */
/***************************************/
/* definizione della funzione main*/
int main()
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *testa_p = NULL; /* lavoro: puntatore alla testa della lista inizializzato a NULL */
int n_centrali, /* input: totale numero di centrali */
matrice[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che contiene i percorsi minimi per ogni collegamento possibile */
dist[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che consente di risalire al percorso da effettuare per minimizzare il percorso del collegamento */
padre[MAX_CENTRALI][MAX_CENTRALI];
/* inizializzazione delle matrici */
inizializza(matrice,
dist,
padre);
/* acquisizione dei dati di input */
n_centrali = acquisisci(&testa_p,
matrice);
/* applicazione dell'algoritmo per il calcolo del percorso più conveniente */
floyd_warshall(matrice,
dist,
padre,
n_centrali);
/* calcolo dei collegamenti */
calcola_collegamenti(dist,
padre,
testa_p);
return(0);
}
/* definizione della funzione che inizializza le matrici */
void inizializza(int matrice[][MAX_CENTRALI], /* input: matrice di adiacenza */
int dist[][MAX_CENTRALI], /* output: matrice del costo minimo per ogni collegamento possibile */
int padre[][MAX_CENTRALI]) /* oputput: matrice per minimizzare il costo dei collegamenti */
{
/* dichiarazione delle variabili locali della funzione */
int i, /* lavoro: variabile contatore i */
j; /* lavoro: variabile contatore j */
for(i=0;
(i < MAX_CENTRALI);
i++)
for(j=0;
(j < MAX_CENTRALI);
j++)
{
matrice[i][j] = ( i == j)?
0:
INFINITO;
dist[i][j] = padre[i][j] = 0;
}
}
/* dichiarazione della funzione che acquisisce i dati di input da file */
int acquisisci(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
int matrice[][MAX_CENTRALI]) /* output: matrice di adiacenza */
{
/* dichiarazione delle variabili locali della funzione */
int n_centrali, /* lavoro: numero di centrali */
esito, /* lavoro: esito della fscanf */
i, /* lavoro: variabile contatore i */
indice_p, /* lavoro: indice della centrale di partenza */
indice_a, /* lavoro: indice della centrale di arrivo */
charToInt=0; /* da char a int */
char charTmp, /* carattere corrente */
partenza[MAX_CENTRALI],/* input: centrale di partenza */
arrivo[MAX_CENTRALI]; /* input: centrale di arrivo */
FILE *f; /* lavoro: puntatore al file di input */
/* apro il file in modalità lettura */
f = fopen("file.txt",
"r"
;
/* acquisizione del numero di centrali */
esito=fscanf(f,
"%d",
&n_centrali);
if(esito)
while((charTmp = fgetc(f)) != EOF ){ /*leggo tt il file carattere x carattere fino la fine (eof)*/
if(charTmp=='\n'){ /* se il carattere temporaneo letto è 'a capo' */
charTmp = fgetc(f); /* allora leggo un altro carattere, il carattere successivo */
if(isdigit(charTmp)) /* se qst è una cifra la devo convertire in intero */
charToInt = charTmp-'0'; /* conversione da char a int */
for(i=0;
(i<charToInt);
i++){ /* lettura dei collegamenti di ogni centrale */
esito=fscanf(f,
"%s%s",
partenza,
arrivo);
printf("%d:%s %s\n",
charToInt,
partenza,
arrivo);
if(esito){
indice_p = aggiungi_vertice(testa_p,partenza);
indice_a = aggiungi_vertice(testa_p,arrivo);
matrice[indice_p][indice_a] = charToInt;
}
}
}
}
/* chiusura del file f */
fclose(f);
return(n_centrali);
}
/* dichiarazione della funzione che cerca la lista con tutte le centrali */
int aggiungi_vertice(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrali da inserire nella lista */
{
/* dichiarazione delle variabili locali alla funzione */
int indice, /* lavoro: indice delle centrali corrispondenti */
uguali; /* lavoro: controllo */
vertice_t *corr_p, /* lavoro: puntatore agli elementi della lista */
*prec_p,
*nuovo_p;
/* parte dalla testa e scorre ogni elemento della lista finché arriva alla fine (corr_p = NULL) oppure l'elemento */
/* da inserire è già stato inserito (uguali = 1) */
for(corr_p = prec_p = *testa_p, indice = 0, uguali = 0;
((corr_p !=NULL) && (uguali == 0));
prec_p = corr_p, corr_p = corr_p->succ_p, indice ++)
{
/* se la centrale da aggiungere è già presente si esce dal ciclo */
if((strcmp(corr_p->nome, centrali)) == 0)
uguali = 1;
}
if(uguali == 0)
{
/* aggiunta delle centrali e del relativo indice */
nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
strcpy(nuovo_p->nome, centrali);
nuovo_p->indice = indice;
nuovo_p->succ_p = corr_p;
if(corr_p == *testa_p)
*testa_p = nuovo_p;
else
prec_p->succ_p = nuovo_p;
}
else
indice--;
return(indice);
}
/* definizione della funzione per calcolare i collegamenti più convenienti */
void floyd_warshall(int grafo[][MAX_CENTRALI], /* input: grafo */
int dist[][MAX_CENTRALI], /* output: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* output: matrice per minimizzare i collegamenti */
int n_collegamenti) /* input: numero dei collegamenti */
{
/* dichiarazione delle variabili locali alla funzione */
int i, /* lavoro: variabile contatore i */
j, /* lavoro: variabile contatore j */
k; /* lavoro: variabile contatore k */
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
{
dist[i][j] = grafo[i][j];
padre[i][j] = (grafo[i][j] != INFINITO)?
i:
-1;
}
for(k = 0;
(k < n_collegamenti);
k++)
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
padre[i][j] = padre[k][j];
}
}
/* definizione della funzione che stampa a video il collegamento migliore */
void calcola_collegamenti(int dist[][MAX_CENTRALI], /* input: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* input: matrice per minimizzare i collegamenti */
vertice_t *testa_p) /* lavoro: puntatore alla testa della lista */
{
/* dichiarazione delle variabili locali alla funzione */
char partenza[N_COLLEGAMENTI], /* input: centrale di partenza */
arrivo[N_COLLEGAMENTI]; /* input: centrale di arrivo */
int indice_partenza, /* lavoro: indice rispetto alla centrale di partenza */
indice_arrivo, /* lavoro: indice rispetto alla centrale di arrivo */
esito, /* lavoro: esito della scanf */
carattere,
lung=0,
i,
j;
/* acquisizione della centrale di partenza */
printf("\nDigitare centrale di partenza\n"
;
esito = scanf("%s",
partenza);
for(i = 0;((carattere = getchar()) != '\n'); i++)
partenza[i] = carattere;
partenza[i]='Ciao a tutti, ci tengo a precisare che sono nuova nel forum e quindi non so bene le regole però ho un problema serio e urgente.
Ho buttato giù il codice per un progetto ovvero devo a partire da un file.txt leggere un numero n di centrali e e calcolare il percorso migliore dal punto di vista dei collegamenti tra di esse.
Il problema è che quando io lo compilo mi da segmentation fault quando vado ad inserire la centrale nel terminale e non capisco dove stia l'errore ( che secondo me è nella funzione cerca_in_lista ma non riesco a capire bene quale errore è
.
Inoltre dovrei anche fare una funzione che mi calcoli i valori massimo minimo e medio dei percorsi minimi di comunicazione e volevo chiedervi una mano perché non penso di aver chiaro questo punto.
Il codice l'ho messo qui sotto ma non sapevo bene come scriververlo.
Spero di essere stata chiara, esaustiva e che possiate darmi una mano sia per l'errore sia per il codice della seconda richiesta ( visto che sono veramente settimane che ci lavoro e non riesco ).
Grazie.
/***************************************************************/
/* programma per calcolare la distanza tra le reti telefoniche */
/***************************************************************/
/******************************/
/* inclusione delle librerie */
/******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*****************************************/
/* definizione delle costanti simboliche */
/*****************************************/
#define INFINITO 5000
#define MAX_CENTRALI 100 /* massimo di centrali in input */
#define N_COLLEGAMENTI 100 /* lunghezza massima delle stringhe */
/*************************************/
/* definizione dei tipi di strutture */
/*************************************/
typedef struct vertice_grafo
{
char nome[N_COLLEGAMENTI];
int indice;
struct vertice_grafo *succ_p;
} vertice_t;
/*************************************/
/* dichiarazione delle funzioni */
/*************************************/
void inizializza(int matrice[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI]);
int acquisisci(vertice_t **testa_p,
int matrice[][MAX_CENTRALI]);
int aggiungi_vertice(vertice_t **testa_p,
char centrali[]);
void floyd_warshall(int grafo[][MAX_CENTRALI],
int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
int n_collegamenti);
void calcola_collegamenti(int dist[][MAX_CENTRALI],
int padre[][MAX_CENTRALI],
vertice_t *testa_p);
int cerca_in_lista(vertice_t *testa_p,
char centrale[]);
/***************************************/
/* definizione delle funzioni */
/***************************************/
/* definizione della funzione main*/
int main()
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *testa_p = NULL; /* lavoro: puntatore alla testa della lista inizializzato a NULL */
int n_centrali, /* input: totale numero di centrali */
matrice[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che contiene i percorsi minimi per ogni collegamento possibile */
dist[MAX_CENTRALI][MAX_CENTRALI],
/* matrice che consente di risalire al percorso da effettuare per minimizzare il percorso del collegamento */
padre[MAX_CENTRALI][MAX_CENTRALI];
/* inizializzazione delle matrici */
inizializza(matrice,
dist,
padre);
/* acquisizione dei dati di input */
n_centrali = acquisisci(&testa_p,
matrice);
/* applicazione dell'algoritmo per il calcolo del percorso più conveniente */
floyd_warshall(matrice,
dist,
padre,
n_centrali);
/* calcolo dei collegamenti */
calcola_collegamenti(dist,
padre,
testa_p);
return(0);
}
/* definizione della funzione che inizializza le matrici */
void inizializza(int matrice[][MAX_CENTRALI], /* input: matrice di adiacenza */
int dist[][MAX_CENTRALI], /* output: matrice del costo minimo per ogni collegamento possibile */
int padre[][MAX_CENTRALI]) /* oputput: matrice per minimizzare il costo dei collegamenti */
{
/* dichiarazione delle variabili locali della funzione */
int i, /* lavoro: variabile contatore i */
j; /* lavoro: variabile contatore j */
for(i=0;
(i < MAX_CENTRALI);
i++)
for(j=0;
(j < MAX_CENTRALI);
j++)
{
matrice[i][j] = ( i == j)?
0:
INFINITO;
dist[i][j] = padre[i][j] = 0;
}
}
/* dichiarazione della funzione che acquisisce i dati di input da file */
int acquisisci(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
int matrice[][MAX_CENTRALI]) /* output: matrice di adiacenza */
{
/* dichiarazione delle variabili locali della funzione */
int n_centrali, /* lavoro: numero di centrali */
esito, /* lavoro: esito della fscanf */
i, /* lavoro: variabile contatore i */
indice_p, /* lavoro: indice della centrale di partenza */
indice_a, /* lavoro: indice della centrale di arrivo */
charToInt=0; /* da char a int */
char charTmp, /* carattere corrente */
partenza[MAX_CENTRALI],/* input: centrale di partenza */
arrivo[MAX_CENTRALI]; /* input: centrale di arrivo */
FILE *f; /* lavoro: puntatore al file di input */
/* apro il file in modalità lettura */
f = fopen("file.txt",
"r"
;
/* acquisizione del numero di centrali */
esito=fscanf(f,
"%d",
&n_centrali);
if(esito)
while((charTmp = fgetc(f)) != EOF ){ /*leggo tt il file carattere x carattere fino la fine (eof)*/
if(charTmp=='\n'){ /* se il carattere temporaneo letto è 'a capo' */
charTmp = fgetc(f); /* allora leggo un altro carattere, il carattere successivo */
if(isdigit(charTmp)) /* se qst è una cifra la devo convertire in intero */
charToInt = charTmp-'0'; /* conversione da char a int */
for(i=0;
(i<charToInt);
i++){ /* lettura dei collegamenti di ogni centrale */
esito=fscanf(f,
"%s%s",
partenza,
arrivo);
printf("%d:%s %s\n",
charToInt,
partenza,
arrivo);
if(esito){
indice_p = aggiungi_vertice(testa_p,partenza);
indice_a = aggiungi_vertice(testa_p,arrivo);
matrice[indice_p][indice_a] = charToInt;
}
}
}
}
/* chiusura del file f */
fclose(f);
return(n_centrali);
}
/* dichiarazione della funzione che cerca la lista con tutte le centrali */
int aggiungi_vertice(vertice_t **testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrali da inserire nella lista */
{
/* dichiarazione delle variabili locali alla funzione */
int indice, /* lavoro: indice delle centrali corrispondenti */
uguali; /* lavoro: controllo */
vertice_t *corr_p, /* lavoro: puntatore agli elementi della lista */
*prec_p,
*nuovo_p;
/* parte dalla testa e scorre ogni elemento della lista finché arriva alla fine (corr_p = NULL) oppure l'elemento */
/* da inserire è già stato inserito (uguali = 1) */
for(corr_p = prec_p = *testa_p, indice = 0, uguali = 0;
((corr_p !=NULL) && (uguali == 0));
prec_p = corr_p, corr_p = corr_p->succ_p, indice ++)
{
/* se la centrale da aggiungere è già presente si esce dal ciclo */
if((strcmp(corr_p->nome, centrali)) == 0)
uguali = 1;
}
if(uguali == 0)
{
/* aggiunta delle centrali e del relativo indice */
nuovo_p = (vertice_t *)malloc(sizeof(vertice_t));
strcpy(nuovo_p->nome, centrali);
nuovo_p->indice = indice;
nuovo_p->succ_p = corr_p;
if(corr_p == *testa_p)
*testa_p = nuovo_p;
else
prec_p->succ_p = nuovo_p;
}
else
indice--;
return(indice);
}
/* definizione della funzione per calcolare i collegamenti più convenienti */
void floyd_warshall(int grafo[][MAX_CENTRALI], /* input: grafo */
int dist[][MAX_CENTRALI], /* output: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* output: matrice per minimizzare i collegamenti */
int n_collegamenti) /* input: numero dei collegamenti */
{
/* dichiarazione delle variabili locali alla funzione */
int i, /* lavoro: variabile contatore i */
j, /* lavoro: variabile contatore j */
k; /* lavoro: variabile contatore k */
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
{
dist[i][j] = grafo[i][j];
padre[i][j] = (grafo[i][j] != INFINITO)?
i:
-1;
}
for(k = 0;
(k < n_collegamenti);
k++)
for(i = 0;
(i < n_collegamenti);
i++)
for(j = 0;
(j < n_collegamenti);
j++)
if(dist[i][j] > dist[i][k] + dist[k][j])
{
dist[i][j] = dist[i][k] + dist[k][j];
padre[i][j] = padre[k][j];
}
}
/* definizione della funzione che stampa a video il collegamento migliore */
void calcola_collegamenti(int dist[][MAX_CENTRALI], /* input: matrice dei collegamenti minimi */
int padre[][MAX_CENTRALI], /* input: matrice per minimizzare i collegamenti */
vertice_t *testa_p) /* lavoro: puntatore alla testa della lista */
{
/* dichiarazione delle variabili locali alla funzione */
char partenza[N_COLLEGAMENTI], /* input: centrale di partenza */
arrivo[N_COLLEGAMENTI]; /* input: centrale di arrivo */
int indice_partenza, /* lavoro: indice rispetto alla centrale di partenza */
indice_arrivo, /* lavoro: indice rispetto alla centrale di arrivo */
esito, /* lavoro: esito della scanf */
carattere,
lung=0,
i,
j;
/* acquisizione della centrale di partenza */
printf("\nDigitare centrale di partenza\n"
;
esito = scanf("%s",
partenza);
for(i = 0;((carattere = getchar()) != '\n'); i++)
partenza[i] = carattere;
partenza[i]='{parsed_message}';
/* ricerca dell'indice corrispondente alla centrale di partenza */
indice_partenza = cerca_in_lista(testa_p,
partenza);
/* se la centrale non è in elenco il programma termina */
if((indice_partenza == -1) || (esito == 0))
printf("\nCentrale di partenza non presente in elenco o errore di lettura\n"
;
else
{
/* acquisizione della centrale di arrivo */
printf("\nDigitare centrale di arrivo\n"
;
esito = scanf("%s",
arrivo);
/* ricerca dell'indice corrispondente alla centrale di arrivo */
indice_arrivo = cerca_in_lista(testa_p,
arrivo);
/* se la centrale non è in elenco il programma termina */
if((indice_arrivo == -1) || (esito == 0))
printf("\nCentrale di arrivo non presente in elenco o errore di lettura\n"
;
else
{
/* stampa a video dei collegamenti: 1 - stampa della partenza */
printf("\nCollegamenti: %s",
partenza);
/* 2 - stampa dell'arrivo */
printf(" -> %s\n\n",
arrivo);
}
}
}
/* definizione della funzione che ricerca nell'indice che identifica una centrale */
int cerca_in_lista(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrale da ricercare nella lista */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
int indice = -1; /* lavoro: inizializzazione dell'indice rispetto ai collegamenti */
for (elem_p = testa_p;
((elem_p != NULL) && (indice == -1));
elem_p = elem_p->succ_p);
if(strcmp(elem_p->nome, centrali) == 0)
indice = elem_p->indice;
return(indice);
}
/* definizione della funzione che stampa a video il collegamento del viaggio */
void stampa_collegamento(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
int indice) /* lavoro: indice delle centrali corrispondenti */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
for (elem_p = testa_p;
((elem_p !=NULL) && (indice != elem_p->indice));
elem_p = elem_p->succ_p);
printf(" -> %s",
elem_p->nome);
}';
/* ricerca dell'indice corrispondente alla centrale di partenza */
indice_partenza = cerca_in_lista(testa_p,
partenza);
/* se la centrale non è in elenco il programma termina */
if((indice_partenza == -1) || (esito == 0))
printf("\nCentrale di partenza non presente in elenco o errore di lettura\n"
;
else
{
/* acquisizione della centrale di arrivo */
printf("\nDigitare centrale di arrivo\n"
;
esito = scanf("%s",
arrivo);
/* ricerca dell'indice corrispondente alla centrale di arrivo */
indice_arrivo = cerca_in_lista(testa_p,
arrivo);
/* se la centrale non è in elenco il programma termina */
if((indice_arrivo == -1) || (esito == 0))
printf("\nCentrale di arrivo non presente in elenco o errore di lettura\n"
;
else
{
/* stampa a video dei collegamenti: 1 - stampa della partenza */
printf("\nCollegamenti: %s",
partenza);
/* 2 - stampa dell'arrivo */
printf(" -> %s\n\n",
arrivo);
}
}
}
/* definizione della funzione che ricerca nell'indice che identifica una centrale */
int cerca_in_lista(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
char centrali[]) /* input: centrale da ricercare nella lista */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
int indice = -1; /* lavoro: inizializzazione dell'indice rispetto ai collegamenti */
for (elem_p = testa_p;
((elem_p != NULL) && (indice == -1));
elem_p = elem_p->succ_p);
if(strcmp(elem_p->nome, centrali) == 0)
indice = elem_p->indice;
return(indice);
}
/* definizione della funzione che stampa a video il collegamento del viaggio */
void stampa_collegamento(vertice_t *testa_p, /* lavoro: puntatore alla testa della lista */
int indice) /* lavoro: indice delle centrali corrispondenti */
{
/* dichiarazione delle variabili locali della funzione */
vertice_t *elem_p; /* lavoro: puntatore all'elem_p all'interno della struttura */
for (elem_p = testa_p;
((elem_p !=NULL) && (indice != elem_p->indice));
elem_p = elem_p->succ_p);
printf(" -> %s",
elem_p->nome);
}
Ultima modifica effettuata da Massimo23 30/06/13 14:46
aaa
