home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / CataniaB / teach-act / testi-esami / labo-6.97 / indegree.txt < prev   
Text File  |  1999-03-11  |  3KB  |  143 lines
  1. Esercitazione di Programmazione C
  2. Giovedi' 5 Giugno 1997 
  3.  
  4. Dato un grafo orientato  G=(V,E), dove V e' l'insieme dei vertici
  5. ed  E l'insieme degli archi) si vuole calcolare il 
  6. grado in ingresso di ogni suo vertice v, cioe', 
  7. il numero di archi entranti in v. 
  8.  
  9. Considerate un file  "input" contenente i seguenti dati:
  10.  
  11. -  un intero N  che denota la cardinalita' di V in modo che  
  12.    V sia uguale a 1,...,N;
  13. -  la sequenza di archi (nel file non e' indicata la cardinalita'
  14.    di E) ognuno indicato da una coppia di interi u v
  15.       (i.e., l'arco u -> v con u,v in V). 
  16.  
  17. Utilizzando le liste di adiacenza per rappresentare 
  18. il grafo, scrivete un programma C che:  
  19.  
  20.  legge i dati del file "input" e costruisce il grafo 
  21.  (cioe' inizializza la tabella di adiacenza);
  22.  calcola il grado di ingresso di ogni vertice;
  23.  stampa su video il grafo cioe': l'insieme dei vertici con 
  24.  l'indicazione del grado, la lista degli archi e il numero 
  25.  di archi del grafo.   
  26.  
  27. Ad esempio dato il file "input" 
  28.  
  29. 4
  30. 1 2   3 1    1 3    1 3    1 4   4 2   3 1
  31.  
  32. l'output deve contenere  le seguenti informazioni:
  33.  
  34. Vertici(con il grado tra parentesi): 1(2)  2(2)  3(1)  4(2) 
  35. Archi: (1 1)(1 4)(1 3)(1 2)(3 4)(3 1)(4 2)
  36. Numero degli archi: 7
  37.  
  38. SOLUZIONE:
  39.  
  40.  
  41. #include <stdio.h>
  42. #include <string.h>
  43.  
  44. /* liste di adiacenza */
  45.  
  46. typedef struct cella* lista;
  47. struct cella 
  48.  { int x; 
  49.    lista next; 
  50.  };
  51.  
  52. /* tabella di adiacenza: 
  53.     per ogni vertice memorizzo il grado di ingresso
  54.     e la lista dei vertici adiacenti.  
  55. */
  56. struct vertice 
  57.  { 
  58.    int grado_in; 
  59.    lista archi; 
  60.  } Grafo[20];
  61.  
  62. /* Tutto nel programma principale */
  63. main()
  64. {
  65.  FILE *in; 
  66.  
  67.  int E,N;      /* Numero archi(E) e vertici(N) */ 
  68.  int v,w,V,W; 
  69.  lista aux;
  70.  
  71.  in=fopen("input","r");
  72.  if (in==stdin) printf("Quanti vertici?[Max 20]"); 
  73.  fscanf(in,"%d",&N);         /* Numero dei vertici: {1,...,N} */
  74.  
  75.  for (v=0;v<=N;v++)          /* Inizializzo le liste di adiacenza */
  76.   {
  77.     Grafo[v].archi=NULL;
  78.     Grafo[v].grado_in=0;
  79.   }
  80.  
  81. /* Lettura e inserimento (nella tabella di adiacenza) degli archi */
  82.  
  83.  if (in==stdin) printf("Archi?[V W]\n"); 
  84.  
  85.  while (fscanf(in,"%d %d",&V,&W)!=EOF)                                    
  86.    if ((V<1 || V>N || W <1 || W>N) && in==stdin) 
  87.       printf("Out of range\n");
  88.    else
  89.     {    
  90.       aux=Grafo[V].archi;
  91.  
  92. /* Controllo se l'arco esiste gia */
  93.  
  94.       while (aux!=NULL && aux->x != W) aux=aux->next;
  95.  
  96. /* Se non c'e' lo aggiungo alla lista di adiacenza di V */
  97.  
  98.       if (aux==NULL)
  99.        { 
  100.          aux=(lista)malloc(sizeof(struct cella));
  101.          aux->x=W; 
  102.          aux->next=NULL;
  103.          aux->next=Grafo[V].archi; 
  104.          Grafo[V].archi=aux; 
  105.          E++;  
  106.        }  
  107.      }
  108.  
  109. /* Calcolo del grado in ingresso */
  110.  
  111.  for (v=1;v<=N;v++)   
  112.   for (w=1;w<=N;w++)   
  113.    { 
  114.      aux=Grafo[w].archi;
  115.      while(aux!=NULL) 
  116.         if (aux->x !=v) aux=aux->next;
  117.         else
  118.          {    
  119.            (Grafo[v].grado_in)++;
  120.            break;         /* p[er hp v occorre al +1 volta nella LdA di w*/
  121.          }
  122.     }    
  123.  
  124. /* Stampa del Grafo */
  125.  
  126.   printf("Vertici(Grado):");
  127.   for (v=1;v<=N;v++)     
  128.     printf("%d(%d) ",v,Grafo[v].grado_in);
  129.  
  130.   printf("\nArchi:");
  131.   for (v=1;v<=N;v++)    
  132.    { 
  133.      aux=Grafo[v].archi;
  134.      while(aux!=NULL)     
  135.       {  
  136.         printf("(%d %d)",v,aux->x);
  137.         aux=aux->next;
  138.       } 
  139.     }
  140.   printf("\nNo. archi:%d\n",E);
  141. }
  142.  
  143.