La lingua di Algolandia - parte 1

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:

Se lo ritenete utile, potete scrivere funzioni aggiuntive e/o modificare le porzioni di codice fornite, ma NON potete modificare la funzione main.

Funzione read

NB: Per leggere una regola della forma XY potete usare scanf( " %c%c", &x, &y ) con x e y definite opportunamente.

Funzione followers

Funzione max

Esempio

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:

  1. A può essere seguita da B oppure H
  2. ciascuna delle lettere ABHLN può essere seguita da 2 lettere e tutte le altre lettere possono essere seguite al massimo da una lettera.

Esempio

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:

  1. A può essere seguita solo da W
  2. W può essere seguita da 3 lettere (U, Y e A) e tutte le altre lettere possono essere seguite al massimo da due lettere.

Programma da completare

#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");

}