Nella lingua di Algolandia, le parole sono definite da un insieme di regole R; ogni regola ha la forma XY; in una parola una lettera X può essere seguita da una lettera Y solo se XY è una regola.
Rappresentate il problema usando la struttura dati grafo orientato di cui trovate in calce un'implementazione parziale.
Scrivete le 3 funzioni sottospecificate e completate il programma in modo che:
invochi la funzione read
per leggere da standard input un insieme R di regole (si veda sotto la specifica del formato dell'input) e memorizzarle in un grafo;
legga da standard input una lettera K e invochi la funzione followers
per stampare tutte le lettere che possono seguire K;
invochi la funzione max
per stampare, in ordine alfabetico, tutte e sole le lettere che possono essere seguite dal massimo numero di lettere rispettando R;
Se lo ritenete utile, potete scrivere funzioni aggiuntive e/o modificare le porzioni di codice fornite, ma NON potete modificare la funzione main
.
read
NB: Per leggere una regola della forma XY potete usare scanf( " %c%c", &x, &y )
con x
e y
definite opportunamente.
followers
max
Eseguendo
./soluzione
avendo nel flusso di ingresso:
18
AB AH BC BD DE EF FG GC HI HJ JK KL LM LN MK NO NP PA
A
il programma emette sul flusso di uscita:
HB
ABHLN
Infatti:
A
può essere seguita da B
oppure H
ABHLN
può essere seguita da 2 lettere e tutte le altre lettere possono essere seguite al massimo da una lettera.Eseguendo
./soluzione
avendo nel flusso di ingresso:
12
WU XP RY XU WY AW ZR TN GL KD LW WA
A
il programma emette sul flusso di uscita:
W
W
Infatti:
A
può essere seguita solo da W
W
può essere seguita da 3 lettere (U
, Y
e A
) e tutte le altre lettere possono essere seguite al massimo da due lettere.#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
struct element { // elemento di lista
char ch;
struct element *next; // prossimo elemento
};
struct graph {
int n, m;
struct element **A; // vettore delle liste di adiacenza
};
typedef struct graph *Graph;
Graph newGraph( int n ); /* alloca una struttura grafo con n nodi */
void addEdge( Graph g, char x, char y); /* inserisce l'arco x -> y */
void printGraph( Graph g ); /* stampa su standard output le liste di adiacenza di g */
// funzione read
...
// funzione followers
...
// funzione max
...
int main( int argc, char *argv[]){
Graph g = read();
char c;
scanf( " %c", &c );
followers(g,c);
max(g);
return 0;
}
/* crea una struttura grafo con n nodi */
Graph newGraph( int n ){
Graph g = malloc(sizeof(struct graph));
if(!g) {
fprintf(stderr,"Errore di Allocazione\n");
exit(EXIT_FAILURE);
}
g -> n = n;
g -> A = calloc( n, sizeof( struct element* ) ); // vettore delle liste di adiacenza: g -> A [i] e' la lista dell'i-esimo nodo
return g;
}
// inserimento in liste di adiacenza
struct element *list_insert( struct element *list, char ch ) {
struct element *new = malloc( sizeof( struct element ) );
new -> ch = ch;
new -> next = list;
return new;
}
// inserisce nel grafo l'arco x -> y
void addEdge( Graph g, char x, char y){
g->A[x-'A'] = list_insert(g->A[x-'A'],y);
}
/* stampa su standard output le liste di adiacenza di g */
void printGraph( Graph g ){
printf( "\n************** stampo grafo\n" );
int n = g -> n;
struct element **al = g -> A;
struct element *curr;
printf( "%d nodi\n%d archi\n", n, g -> m );
for ( int i = 0; i < n; i++ ) {
printf( "%c:", 'A'+i );
for ( curr = al[i]; curr != NULL; curr = curr -> next ) {
printf( " %c", curr -> ch );
}
printf( "\n" );
}
printf( "fine stampa grafo *************************\n\n");
}