Gli esercizi
Testi e soluzioni di alcuni esercizi
Trasformazione delle liste di adiacenza di un grafo nella matrice di adiacenza equivalente
Date le liste di adiacenza di un grafo G=(V,E), costruisce e stampa la matrice di adiacenza dello stesso grafo.
/* ** lista_matrice.c ** ** Legge in input un grafo G(V,E) memorizzando le liste di adiacenza. ** Quindi costruisce la matrice di adiacenza dello stesso grafo e la ** stampa. ** ** Marco Liverani (liverani@mat.uniroma3.it) - Gennaio 1999 */ #include <stdlib.h> #include <stdio.h> #define MAX 50 struct nodo { int info; struct nodo *next; }; /* ** leggi_lista ** ** legge in input una sequenza di numeri interi fino a quando ** l'utente non digita "-1". I numeri letti vengono man mano ** memorizzati in una lista. La funzione restituisce un puntatore ** al primo elemento della lista (l'indirizzo di memoria del ** primo elemento della lista). */ struct nodo *leggi_lista(void) { int a; struct nodo *p, *primo; primo = NULL; scanf("%d", &a); while (a != -1) { p = malloc(sizeof(struct nodo)); p->info = a; p->next = primo; primo = p; scanf("%d", &a); } return(primo); } /* ** leggi_grafo ** ** per ogni vertice del grafo ne legge la lista di adiacenza. ** Restituisce il numero di vertici. */ int leggi_grafo(struct nodo **l) { int i, n; printf("Numero dei vertici: "); scanf("%d", &n); for (i=0; i<n; i++) { printf("%d: ", i); *(l+i) = leggi_lista(); } return(n); } /* ** stampa_lista ** ** visualizza in output una lista di adiacenza; si aspetta come ** parametro l'indirizzo di memoria (il puntatore) del primo ** elemento della lista. */ void stampa_lista(struct nodo *primo) { while (primo != NULL) { printf("%d -> ", primo->info); primo = primo->next; } printf("NULL\n"); return; } /* ** stampa_matrice ** ** stampa la matrice; accetta come parametri il puntatore ** al primo elemento, il numero di righe ed il numero di ** colonne. */ void stampa_matrice(int *m, int righe, int colonne) { int i, j; for (i=0; i<righe; i++) { for (j=0; j<colonne; j++) { printf("%2d ", *(m+i*MAX+j)); } printf("\n"); } return; } /* ** costruisci_matrice ** ** Accetta come parametro il puntatore al primo elemento della ** matrice di adiacenza da costruire, il numero di vertici del ** grafo ed il puntatore al primo elemento dell'array dei ** puntatori alle liste di adiacenza e costruisce la matrice. */ void costruisci_matrice(int *m, int n, struct nodo **l) { int i, j; struct nodo *p, *primo; for (i=0; i<n; i++) { for (j=0; j<n; j++) { *(m+i*MAX+j) = 0; } p = *(l+i); while (p != NULL) { *(m+i*MAX+ p->info) = 1; p = p->next; } } return; } /* ** main ** ** la funzione principale richiama tutte le altre. */ int main(void) { struct nodo *lista[MAX]; int matrice[MAX][MAX]; int i, n; n = leggi_grafo(&lista[0]); for (i=0; i<n; i++) { printf("%d: ", i); stampa_lista(lista[i]); } costruisci_matrice(&matrice[0][0], n, &lista[0]); stampa_matrice(&matrice[0][0], n, n); return(0); }