Gli esercizi
Testi e soluzioni di alcuni esercizi
Trasformazione di una matrice di adiacenza di un grafo in liste di adiacenza
Data in input la matrice di adiacenza di un grafo G(V,E), costruire e stampare le liste di adiacenza dello stesso grafo.
/* ** matrice_lista.c ** ** Legge in input un grafo G(V,E) come matrice di adiacenza. Costruisce ** le liste di adiacenza relative allo stesso grafo e le 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; }; /* ** 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; } /* ** leggi_grafo ** ** legge il grafo e costruisce la matrice di adiacenza. Accetta in ** input l'indirizzo di memoria (il puntatore) del primo elemento ** della matrice. Restituisce il numero di vertici. */ int leggi_grafo(int *m) { int i, j, n; printf("Numero dei vertici: "); scanf("%d", &n); for (i=0; i<n; i++) { for (j=0; j<n; j++) { *(m+i*MAX+j) = 0; } printf("%d: ", i); while (j != -1) { *(m+i*MAX+j) = 1; scanf("%d", &j); } } 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; } /* ** costruisci_liste ** ** Accetta come parametro il puntatore al primo elemento della ** matrice di adiacenza e costruisce le liste di adiacenza relative. */ void costruisci_liste(int *m, int n, struct nodo **l) { int i, j; struct nodo *p, *primo; for (i=0; i<n; i++) { *(l+i) = NULL; for (j=0; j<n; j++) { if (*(m+i*MAX+j) == 1) { p = malloc(sizeof(struct nodo)); p->info = j; p->next = *(l+i); *(l+i) = p; } } } 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(&matrice[0][0]); stampa_matrice(&matrice[0][0], n, n); costruisci_liste(&matrice[0][0], n, &lista[0]); for (i=0; i<n; i++) { printf("%d: ", i); stampa_lista(lista[i]); } return(0); }