Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Programma in C per il calcolo del percorso migliore tra un numero n di centrali.
Forum - C/C++ - Programma in C per il calcolo del percorso migliore tra un numero n di centrali.

Avatar
Massimo23 (Normal User)
Newbie


Messaggi: 1
Iscritto: 30/06/2013

Segnala al moderatore
Postato alle 16:44
Domenica, 30/06/2013
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[j] = ( i == j)?
             0:
             INFINITO;
     dist[j] = padre[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[j] = grafo[j];
    padre[j] = (grafo[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[j] > dist[k] + dist[k][j])
    {
     dist[j] = dist[k] + dist[k][j];
     padre[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 = carattere;
partenza='\0';

/* 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 il 30/06/2013 alle 16:46
PM Quote