Scrivere una funzione che prende come parametro un grafo e restituisce una lista che contiene i nodi del grafo che hanno almeno due successori. Dare la dichiarazione di tipo della lista, e scrivere tutte le funzioni su liste necessarie alla soluzione del problema. Si assuma che le dichiarazioni di tipo del grafo, e le operazioni fondamentali, siano già state scritte. La funzione deve andare bene, senza modifiche, con entrambe le rappresentazioni dei grafi.
Esempio: se la funzione riceve come parametro il grafo qui sotto a sinistra, deve restituire la lista (1 2 4), dal momento che questi sono i nodi che hanno due (o più) successori.
Il programma driver, che contiene la definizione di grafo, con le operazioni di lettura da file, è 4-6-2001-driver.c Questo programma contiene già la funzione di stampa di una lista, ma il tipo lista deve essere definito: la soluzione, che comprende anche la definizione del tipo lista, va messa nel punto del programma in cui appare il commento /* inserire qui la soluzione */
Alcuni file con possibili dati di input, e le corrispondenti soluzioni, sono riportate qui sotto. La soluzione è composta di due parti: la prima è la stampa del grafo stesso (un utile controllo per verificare se il grafo è stato scritto su file correttamente), la seconda è la stampa del risultato della funzione (la lista dei nodi con almeno due successori).
[an error occurred while processing this directive]
Ad alto livello si può descrivere la soluzione del problema come segue: per ogni nodo del grafo, se ha almeno due successori, lo si mette nella lista. Il primo livello di raffinamento dell'algoritmo è quindi quello che segue:
per ogni nodo del grafo
se il nodo ha almeno due successori
metti il nodo in lista
Per prima cosa, la lista deve essere inizialmente vuota. La scansione dei nodi del grafo corrisponde a un ciclo for, mentre per l'inserimento in lista possiamo usare la funzione di inserimento in testa a una lista. Per quello che riguarda il controllo del numero dei successori, possiamo usare una funzione che calcola il numero dei successori di un nodo. La funzione che si ottiene è quindi la seguente:
TipoLista ListaDueSuccessori(TipoGrafo g) {
TipoLista l;
int i;
l=NULL;
for(i=0; i<=NUMNODI-1; i++)
if( NumeroSuccessori(g, i) >= 2 )
InserisciTestaLista(&l, i);
return l;
}
Sviuppiamo ora le funzioni usate da questa. Per l'inserimento in lista non abbiamo problemi (è una delle funzioni sulle liste vista a lezione). Il conteggio del numero dei successori si può fare usando un contatore che parte da 0. Per ogni nodo, se c'è un arco dal nodo passato a questo, si incrementa il contatore.
Conteggio successori di i:
contatore=0;
per ogni nodo j
se c'è un arco da i a j
incrementa contatore
Alla fine, il contatore contiene il numero dei successori del nodo. L'implementazione è a questo punto immediata:
int NumeroSuccessori(TipoGrafo g, int i) {
int j, nsucc;
nsucc=0;
for(j=0; j<=NUMNODI-1; j++)
if(TestEsisteArco(g, i, j))
nsucc++;
return nsucc;
}
Si noti che questa funzione usa TestEsisteArco. È importante notare che il testo dell'esercizio richiede che la funzione da implementare sia fatta in modo tale da funzionare, senza modifiche, con entrambe le rappresentazioni dei grafi. Questo significa che l'unico modo possibile per verificare l'esistenza di archi è quello di usare TestEsisteArco (assumere che si stia usando la matrice di adiacenza o la lista dei successori è un errore).
Si può risolvere il problema anche usando una singola funzione. Quando possibile, è bene invece cercare di ridurre il problema da risolvere in sottoproblemi, dato che questo facilita l'operazione di soluzione, e permette di evitare maggiormente la generazione di errori nel codice.