Il progetto dice:
case 1: /*stampa lista*/
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("\niscrizione effettuata con successo");
break;
case 2: /* Se l'utente preme il tasto 2 si cerca se c'e il libro e richiedere un libro tramite il codice*/
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("accesso effettuata con successo");
break;io avevo pensato ad un file ma il prof vuole tramite i grafi...potresti aiutarmi?
no gestione di voli in c con grafi
si esatto ogni nodo e una destinazione tipo napoli- milano ho un arco da napoli a milano con nodi intermedi all'interno che rappresentano le tratte
si gli scali si.....
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
struct TList {
int target;
int peso;
struct TList* next;
};
typedef struct TList* List;
struct TGraph {
List *adj;
int nodes_count;
char** cityNames;
};
typedef struct TGraph* Graph;
Graph initGraph(int nodes_count, char** cityNames) {
Graph G = (Graph)malloc(sizeof(struct TGraph));
assert(G != NULL);
G->adj = (List *)calloc(nodes_count, sizeof(List));
assert(G->adj != NULL);
G->nodes_count = nodes_count;
G->cityNames = cityNames;
return G;
}
void freeGraph(Graph G) {
if (G != NULL) {
if (G->nodes_count > 0) {
int i = 0;
for (i = 0; i < G->nodes_count; i++) {
freeList(G->adj[i]);
}
}
free(G);
}
}
void printGraphAux(Graph G) {
if (G != NULL) {
int x = 0;
for (x = 0; x < G->nodes_count; x++) {
printf("(city: %s, id:%d): -> ", G->cityNames[x], x);
printList(G->adj[x]);
printf("\n");
}
}
}
void printGraph(Graph G) {
printGraphAux(G);
printf("\n\n");
}
void addEdge(Graph G, int source, int target, int peso) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = appendNodeList(G->adj[source], target, peso);
}
}
List removeEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = removeNodeList(G->adj[source], target);
}
return G->adj[source];
}
void addNode(Graph G, char* newCity) {
if (G != NULL) {
List * old=G->adj;
char** old_matrix = G->cityNames;
int i=0;
G->adj = (List *)calloc(G->nodes_count+1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count+1, sizeof(char*));
assert(G->cityNames != NULL);
for(i=0;i<G->nodes_count;i++){
G->adj[i]=old[i];
G->cityNames[i] = old_matrix[i];
}
G->nodes_count += 1;
G->adj[G->nodes_count-1] = NULL;
G->cityNames[G->nodes_count-1] = (char*) calloc(strlen(newCity)+1, sizeof(char));
assert(G->cityNames[G->nodes_count-1] != NULL);
strcpy(G->cityNames[G->nodes_count-1], newCity);
}
}
void removeNode(Graph G, int node_to_remove) {
if (G != NULL) {
int i = 0;
int x = 0;
List *tmp = G->adj;
char** old_matrix = G->cityNames;
G->adj = (List *)calloc(G->nodes_count-1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count-1, sizeof(char*));
assert(G->cityNames != NULL);
for (i = 0; i < G->nodes_count; i++) {
if (i != node_to_remove) {
G->adj[x] = checkListRemoval(tmp[i], node_to_remove);
G->cityNames[x] = old_matrix[i];
x++;
} else {
free(old_matrix[i]);
freeList(tmp[i]);
}
}
free(tmp);
free(old_matrix);
G->nodes_count -= 1;
}
}
List checkListRemoval(List L, int node_to_remove) {
if (L != NULL) {
L->next = checkListRemoval(L->next, node_to_remove);
if (L->target == node_to_remove) {
List tmp = L->next;
free(L);
return tmp;
} else if (L->target > node_to_remove) {
L->target -= 1;
}
}
return L;
}
int menu(void){
int scelta; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * Benvenuto in gestione prenotazione voli\n* * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Accesso amministratore\n");
printf(" 2. Accesso utente\n");
printf(" 3. Uscire\n");
printf("Inserisci scelta:");
scanf("%d",&scelta); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(scelta<0 || scelta>3) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &scelta);
return scelta;
}
return scelta;
}
int menuUtente(void){
int sceltaUt; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * * UTENTE\n* * * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Effettua Iscrizione\n");
printf(" 2. effettua accesso\n");
printf("Inserisci scelta:");
scanf("%d",&sceltaUt); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(sceltaUt<0 || sceltaUt>2) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &sceltaUt);
return sceltaUt;
}
return sceltaUt;
}
int menuAmministratore(void){
int sceltaAmministratore; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * * AMMINISTRATORE \n* * * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Inserisci destinazione \n");
printf(" 2. Stampa destinazioni\n");
printf(" 3. Cancella destinazione\n");
printf("Inserisci scelta:");
scanf("%d",&sceltaAmministratore); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(sceltaAmministratore<0 || sceltaAmministratore>3) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &sceltaAmministratore);
return sceltaAmministratore;
}
return sceltaAmministratore;
}
struct TGraph* Graph_init_from_file()
{
char* city[40];
int n = 0;
struct TGraph *temp;
struct TGraph *Graph = NULL;
Graph = initGraph(n,city);
FILE *filehandler;
filehandler = fopen("destinazioni.txt", "r");
if(filehandler != NULL){
while(!feof(filehandler)){
fgets(city, 40, filehandler);
strtok(city,"\n");
temp = initGraph(20, city);
addNode(Graph,temp);
}
fclose(filehandler);
}
return Graph;
}
int main() {
int scelta;
int sceltaUt;
int sceltaAmministratore;
char email;
char pwd;
// Graph G = NULL;
char destinazione ;
char emailAmministratore;
char pwdAmministratore;
int n;
char deleteDestinazione;
while((scelta = menu())){
switch (scelta) /* Creo uno switch con 5 case, uno per ogni possibile scelta */
{
case 1:
printf("Inserisci email: ");
scanf("%s", &emailAmministratore);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwdAmministratore);
while((sceltaAmministratore = menuAmministratore())){
switch (sceltaAmministratore) {
case 1: //stampa archivio contenente le destinazioni e le tratte
break;
case 2: //inserisce voli e tratte
break;
case 3: //elimina tratte e destinazioni
printf("Inserisci destinazione da eliminare: ");
scanf("%s", &deleteDestinazione);
break;
}
}
return 0;
break;
case 2: /* Se l'utente preme il tasto 2 si cerca se c'e il libro e richiedere un libro tramite il codice*/
while((sceltaUt = menuUtente())){
switch (sceltaUt) {
case 1:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("\niscrizione effettuata con successo");
break;
case 2:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("accesso effettuata con successo");
break;
}
}
return 0;
case 3: /*Se l'utente vuole uscire dalla biblioteca*/
printf("Grazie per aver scelto il servizio di gestione prenotazione voli, torna a trovarci!\n");
return 0;
break;
default: /*Se l'utente sbaglia ad inserire il numero*/
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
break;
} /*Fine switch*/
} /*Fine do*/
return 0;
} /*Fine main*/no ti da errore perche vanno incluse altre funzioni di libreria ora posto l'intero codice
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Graph.h"
#include "List.h"
#include "nodo.h"
#define dim 50
int main() {
int scelta;
int sceltaUt;
int sceltaAmministratore;
char email;
char pwd;
// Graph G = NULL;
char emailAmministratore;
char pwdAmministratore;
char deleteDestinazione;
struct nodo *grafo[dim];
char citta;
// int n = 0,
int num;
while((scelta = menu())){
switch (scelta) /* Creo uno switch con 5 case, uno per ogni possibile scelta */
{
case 1:
printf("Inserisci email: ");
scanf("%s", &emailAmministratore);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwdAmministratore);
while((sceltaAmministratore = menuAmministratore())){
switch (sceltaAmministratore) {
case 1: //stampa archivio
inizializza(grafo);
aggiungi_nodo(1,"Napoli",grafo);
aggiungi_nodo(2,"Milano",grafo);
aggiungi_nodo(3,"Genova",grafo);
aggiungi_nodo(4,"Firenze",grafo);
aggiungi_nodo(5,"Roma",grafo);
aggiungi_nodo(6,"Torino",grafo);
aggiungi_nodo(7,"Venezia",grafo);
aggiungi_nodo(8,"Palermo",grafo);
aggiungi_nodo(9,"Bari",grafo);
aggiungi_nodo(10,"Perugia",grafo);
aggiungi_nodo(11,"Parma",grafo);
aggiungi_nodo(12,"Reggio Calabria",grafo);
aggiungi_nodo(13,"Trento",grafo);
aggiungi_nodo(14,"Aosta",grafo);
aggiungi_nodo(15,"Ancona",grafo);
aggiungi_nodo(16,"Pescara",grafo);
aggiungi_nodo(17,"Potenza",grafo);
aggiungi_nodo(18,"Catania",grafo);
aggiungi_nodo(19,"Reggio Emilia",grafo);
aggiungi_nodo(20,"Cagliari",grafo);
aggiungi_arco(1,2,grafo);
aggiungi_arco(1,3,grafo);
aggiungi_arco(1,4,grafo);
aggiungi_arco(3,4,grafo);
aggiungi_arco(2,3,grafo);
aggiungi_arco(1,5,grafo);
aggiungi_arco(5,6,grafo);
aggiungi_arco(5,8,grafo);
aggiungi_arco(6,7,grafo);
aggiungi_arco(7,8,grafo);
aggiungi_arco(3,9,grafo);
aggiungi_arco(2,10,grafo);
aggiungi_arco(9,11,grafo);
aggiungi_arco(6,11,grafo);
aggiungi_arco(11,12,grafo);
aggiungi_arco(12,4,grafo);
aggiungi_arco(2,13,grafo);
aggiungi_arco(13,9,grafo);
aggiungi_arco(14,8,grafo);
aggiungi_arco(7,15,grafo);
aggiungi_arco(15,16,grafo);
aggiungi_arco(6,17,grafo);
aggiungi_arco(17,18,grafo);
aggiungi_arco(18,19,grafo);
aggiungi_arco(13,19,grafo);
aggiungi_arco(19,20,grafo);
aggiungi_arco(20,2,grafo);
visitaInProfondita(1,grafo);
printf("\n\n");
break;
case 2: //inserisci
printf("Inserisci nuemro destinazione:\n");
scanf("%d", &num);
printf("Inserisci città:\n");
scanf("%s", &citta);
break;
case 3://elimina tratta e destinazione
printf("Inserisci destinazione da eliminare: ");
scanf("%s", &deleteDestinazione);
break;
}
}
return 0;
break;
case 2:
while((sceltaUt = menuUtente())){
switch (sceltaUt) {
case 1:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("\niscrizione effettuata con successo");
break;
case 2:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("accesso effettuata con successo");
break;
}
}
return 0;
case 3: /*Se l'utente vuole uscire */
printf("Grazie per aver scelto il servizio di gestione prenotazione voli, torna a trovarci!\n");
return 0;
break;
default: /*Se l'utente sbaglia ad inserire il numero*/
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
break;
} /*Fine switch*/
} /*Fine do*/
return 0;
} /*Fine main*/#ifndef Graph_List_h
#define Graph_List_h
struct TList {
int target;
int peso;
struct TList* next;
};
typedef struct TList* List;
// Inizializza un nuovo nodo
List initNodeList(int target, int peso);
// Aggiunge un nodo alla fine della lista
// controllandone l'esistenza
// La funzione ritorna sempre la testa della lista
List appendNodeList(List L, int target, int peso);
// Aggiunge un nodo in testa alla lista
// senza controllare l'esistenza
// La funzione ritorna sempre la testa della lista
List addNodeHead(List L, int target, int peso);
// Rimuove solo un occorrenza di un nodo con il target specificato
// dalla lista
// La funzione ritorna sempre la testa della lista
List removeNodeList(List L, int target);
// Dealloca la lista interamente
void freeList(List L);
// Stampa la lista
void printList(List L);
#endif#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include "List.h"
List initNodeList(int target, int peso) {
List L = (List)malloc(sizeof(struct TList));
assert(L != NULL);// controllo che vi sia ancora memoria disponibile
L->target = target;
L->peso = peso;
L->next = NULL;
return L;
}
List appendNodeList(List L, int target, int peso) {
if (L != NULL) {
if (L->target != target) {
L->next = appendNodeList(L->next, target, peso);
}
//else target gia' presente in lista e non sono ammessi duplicati, quindi non si fa nulla
} else {
L = initNodeList(target, peso);
}
return L;
}
List addNodeHead(List L, int target, int peso) {
List G = initNodeList(target, peso);
if (L != NULL) {
G->next = L;
}
return G;
}
List removeNodeList(List L, int target) {
if (L != NULL) {
if (L->target == target) {
List tmp = L->next;
free(L);
return tmp;
}
L->next = removeNodeList(L->next, target);
}
return L;
}
void freeList(List L) {
if (L != NULL) {
freeList(L->next);
free(L);
}
}
void printList(List L) {
if (L != NULL) {
printf(" (destinazione:%d, peso:%d) ", L->target, L->peso);
printList(L->next);
}
}#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>
#include "Graph.h"
#include "List.h"
#include "Queue.h"
Graph initGraph(int nodes_count, char** cityNames) {
Graph G = (Graph)malloc(sizeof(struct TGraph));
assert(G != NULL);
G->adj = (List *)calloc(nodes_count, sizeof(List));
assert(G->adj != NULL);
G->nodes_count = nodes_count;
G->cityNames = cityNames;
return G;
}
void freeGraph(Graph G) {
if (G != NULL) {
if (G->nodes_count > 0) {
int i = 0;
for (i = 0; i < G->nodes_count; i++) {
freeList(G->adj[i]);
}
}
free(G);
}
}
void printGraphAux(Graph G) {
if (G != NULL) {
int x = 0;
for (x = 0; x < G->nodes_count; x++) {
printf("(city: %s, id:%d): -> ", G->cityNames[x], x);
printList(G->adj[x]);
printf("\n");
}
}
}
void printGraph(Graph G) {
printGraphAux(G);
printf("\n\n");
}
void addEdge(Graph G, int source, int target, int peso) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = appendNodeList(G->adj[source], target, peso);
}
}
List removeEdge(Graph G, int source, int target) {
assert(G != NULL);
assert(source < G->nodes_count);
assert(target < G->nodes_count);
if (source != target) {
G->adj[source] = removeNodeList(G->adj[source], target);
}
return G->adj[source];
}
void addNode(Graph G, char* newCity) {
if (G != NULL) {
List * old=G->adj;
char** old_matrix = G->cityNames;
int i=0;
G->adj = (List *)calloc(G->nodes_count+1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count+1, sizeof(char*));
assert(G->cityNames != NULL);
for(i=0;i<G->nodes_count;i++){
G->adj[i]=old[i];
G->cityNames[i] = old_matrix[i];
}
G->nodes_count += 1;
G->adj[G->nodes_count-1] = NULL;
G->cityNames[G->nodes_count-1] = (char*) calloc(strlen(newCity)+1, sizeof(char));
assert(G->cityNames[G->nodes_count-1] != NULL);
strcpy(G->cityNames[G->nodes_count-1], newCity);
}
}
void removeNode(Graph G, int node_to_remove) {
if (G != NULL) {
int i = 0;
int x = 0;
List *tmp = G->adj;
char** old_matrix = G->cityNames;
G->adj = (List *)calloc(G->nodes_count-1, sizeof(List));
assert(G->adj != NULL);
G->cityNames = (char**)calloc(G->nodes_count-1, sizeof(char*));
assert(G->cityNames != NULL);
for (i = 0; i < G->nodes_count; i++) {
if (i != node_to_remove) {
G->adj[x] = checkListRemoval(tmp[i], node_to_remove);
G->cityNames[x] = old_matrix[i];
x++;
} else {
free(old_matrix[i]);
freeList(tmp[i]);
}
}
free(tmp);
free(old_matrix);
G->nodes_count -= 1;
}
}
List checkListRemoval(List L, int node_to_remove) {
if (L != NULL) {
L->next = checkListRemoval(L->next, node_to_remove);
if (L->target == node_to_remove) {
List tmp = L->next;
free(L);
return tmp;
} else if (L->target > node_to_remove) {
L->target -= 1;
}
}
return L;
}
int menu(void){
int scelta; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * Benvenuto in gestione prenotazione voli\n* * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Accesso amministratore\n");
printf(" 2. Accesso utente\n");
printf(" 3. Uscire\n");
printf("Inserisci scelta:");
scanf("%d",&scelta); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(scelta<0 || scelta>3) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &scelta);
return scelta;
}
return scelta;
}
int menuUtente(void){
int sceltaUt; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * * UTENTE\n* * * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Effettua Iscrizione\n");
printf(" 2. effettua accesso\n");
printf("Inserisci scelta:");
scanf("%d",&sceltaUt); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(sceltaUt<0 || sceltaUt>2) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &sceltaUt);
return sceltaUt;
}
return sceltaUt;
}
int menuAmministratore(void){
int sceltaAmministratore; /*Questa variabile sarà utilizzata nella switch per decidere che cosa fare...*/
printf("* * * * * * * * * * * * * * * * * * * * * * * * AMMINISTRATORE \n* * * * * * * * * * * * * * * * * * * * * * * * \n");
printf(" 1. Stampa destinazioni\n");
printf(" 2. Inserisci destinazione \n");
printf(" 3. Cancella destinazione\n");
printf("Inserisci scelta:");
scanf("%d",&sceltaAmministratore); /*Viene inserito nella variabile var il numero inserito dall'utente e di conseguenza inserito nel ciclo Switch*/
while(sceltaAmministratore<0 || sceltaAmministratore>3) {
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
printf("Scelta: ");
scanf("%d", &sceltaAmministratore);
return sceltaAmministratore;
}
return sceltaAmministratore;
}
List bfs(Graph G, int source, int target){
assert(G != NULL); // controllo che il grafo non sia nullo
assert(source < G->nodes_count || target < G->nodes_count); // controllo che i vertici inseriti appartengano al grafo
Queue Q = initQueue();
int* visit_path = (int*)calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
int* current_weight = (int*) calloc(G->nodes_count, sizeof(int));
assert (current_weight != NULL);
// calloc inizializza gli interi a zero, che nella enum corrisponde a WHITE
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
enqueue(Q, source);
visited[source] = BLACK;
// il nodo di partenza e' raggiungibile da se stesso con un percoso nullo
visit_path[source] = source;
current_weight[source] = 0;
int target_found = 0;
int v;
while(!isEmptyQueue(Q) && !target_found){
// non occorre controllare che la coda abbiamo terminato l'operazione correttamente
// dato che in questo punto del codice sicuramente non e' vuota;
dequeue(Q, &v);
for(List iter = G->adj[v]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
enqueue(Q, iter->target);
// segno di aver visitato il vertice in cui termina l'arco
visited[iter->target] = BLACK;
// segno che il vertice in questione e' raggiungibile con un arco partendo dal vertice v
visit_path[iter->target] = v;
// bcalcolo il peso del percorso
current_weight[iter->target] = current_weight[v] + iter->peso;
if(iter->target == target){
target_found = 1;
break;
}
}
}
}
freeQueue(Q);
List path = NULL;
if(target_found != 0) {
// genera il percorso da source a target(se presente) e lo inserisce in una lista
path = generatePath(visit_path, current_weight, source, target);
}
free(visited);
free(visit_path);
free(current_weight);
return path;
}
List dijkstra(Graph G, int source, int target){
assert(G != NULL); // controllo che il grafo non sia nullo
assert(source < G->nodes_count || target < G->nodes_count); // controllo che i vertici inseriti appartengano al grafo
Queue Q = initQueue();
int* visit_path = (int*)calloc(G->nodes_count, sizeof(int));
assert(visit_path != NULL);
// a differenza dell bfs, dijkstra deve tenere traccia anche del peso dei percorsi finora analizzati
int* current_weight = (int*) calloc(G->nodes_count, sizeof(int));
assert(current_weight != NULL);
// calloc inizializza gli interi a zero, che nella enum corrisponde a WHITE
GraphColor* visited = (GraphColor*) calloc(G->nodes_count, sizeof(GraphColor));
assert(visited != NULL);
enqueue(Q, source);
visited[source] = BLACK;
// il nodo di partenza e' raggiungibile da se stesso con un percoso nullo
visit_path[source] = source;
current_weight[source] = 0; // questa assegnazione e' inutile ma rende piu' semplice da capire l'algoritmo
int target_found = 0;
int v;
while(!isEmptyQueue(Q)){
// non occorre controllare che la coda abbiamo terminato l'operazione correttamente
// dato che in questo punto del codice sicuramente non e' vuota;
dequeue(Q, &v);
for(List iter = G->adj[v]; iter != NULL; iter = iter->next){
if(visited[iter->target] == WHITE){
enqueue(Q, iter->target);
// segno di aver visitato il vertice in cui termina l'arco
visited[iter->target] = BLACK;
// segno che il vertice in questione e' raggiungibile con un arco partendo dal vertice v
visit_path[iter->target] = v;
// calcolo il peso del percorso
current_weight[iter->target] = current_weight[v] + iter->peso;
if(iter->target == target){
target_found = 1;
}
}else if(visited[iter->target] == BLACK && (current_weight[iter->target] > current_weight[v] + iter->peso)){
// nel caso un vertice venga raggiunto da un percorso "piu' leggero", cambio il predecessore, ed il peso, del nodo in questione
visit_path[iter->target] = v;
current_weight[iter->target] = current_weight[v] + iter->peso;
}
}
}
freeQueue(Q);
List path = NULL;
if(target_found != 0){
// genera il percorso da source a target(se presente) e lo inserisce in una lista
path = generatePath(visit_path, current_weight, source, target);
}
free(visited);
free(visit_path);
free(current_weight);
return path;
}
List generatePath(int* visit_info, int* weight_info, int source, int target){
if(source == target){
return initNodeList(source, weight_info[source]);
}else{
List path = generatePath(visit_info, weight_info, source, visit_info[target]);
path = appendNodeList(path, target, weight_info[target]);
return path;
}
}
int getCityIndex(Graph G, char* key){
assert(G != NULL);
assert(G->cityNames != NULL);
int index = -1;
int i;
for(i=0; i<G->nodes_count; i++){
if(!strcmp(G->cityNames[i], key)){
index = i;
break;
}
}
return index;
}#ifndef Graph_Graph_h
#define Graph_Graph_h
#include "List.h"
struct TGraph {
List *adj;
int nodes_count;
char** cityNames;
};
typedef struct TGraph* Graph;
// Dealloca l'intero grafo
void freeGraph(Graph G);
// Inizializza un nuovo grafo vuoto specificando in ingresso quanti nodi saranno nel grafo
Graph initGraph(int nodes_count, char** cityNames);
// Stampa il grafo
void printGraph(Graph G);
// Aggiunge un arco, specificando sorgente, target e peso
void addEdge(Graph G, int source, int target, int peso);
// Rimuovi un arco specificando sorgente e target,restituisce la lista degli archi modifcata
List removeEdge(Graph G, int source, int target);
// Aggiungi un nodo
void addNode(Graph G, char* newCity);
// Rimuovi un nodo dal grafo, sistemando gli indici e riallocando la memoria
void removeNode(Graph G, int node_to_remove);
List checkListRemoval(List L, int node_to_remove);
// Crea un nuovo grafo e lo popola in base alla scelta effettuata dal menu
Graph graphCreationMenu(int n);
// Menu per la modifica e gestione dei grafi
void graphEditorMenu(Graph);
int menu(void);
int menuUtente(void);
int menuAmministratore(void);
typedef enum{WHITE, GREY, BLACK} GraphColor;
// ricerca del percorso minimo dal vertice source a quello target
List bfs(Graph G, int source, int target);
// minimizza il percorso considerando il peso degli archi del grafo (funziona solo se tutti gli archi hanno peso positivo)
List dijkstra(Graph G, int source, int target);
// estrapola da visit_info il percorso da source a target
List generatePath(int* visit_info, int* weight_info, int source, int target);
// cerca il numero del vertice associato al nome di una particolare citta'
int getCityIndex(Graph G, char* key);
#endif#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "nodo.h"
#define dim 50
void inizializza(struct nodo *a[])
{
int i;
for(i=0 ; i<dim ; i++)
a[i]=NULL;
}
void aggiungi_nodo(int tipo , char *v ,struct nodo *a[])
{
int t=tipo-1;
if(a[t]==NULL)
a[t]=malloc(sizeof(struct nodo));
a[t]->tipo=tipo;
a[t]->val=v;
a[t]->flag=false;
a[t]->inizio=NULL;
}
void aggiungi_arco( int n1 , int n2 , struct nodo *grafo[])
{
grafo[n1-1]->inizio=inserisciInTesta(grafo[n1-1]->inizio,n2);
grafo[n2-1]->inizio=inserisciInTesta(grafo[n2-1]->inizio,n1);
}
struct lista *inserisciInTesta(struct lista *inizio , int nodo)
{
struct lista *temp= malloc(sizeof(struct lista));
temp->succ=inizio;
temp->nodo=nodo;
return temp;
}
void visitaInProfondita(int n , struct nodo *grafo[])
{
struct lista *temp=grafo[n-1]->inizio;
printf("\n nodo: %d città: %s" , n , grafo[n-1]->val);
grafo[n-1]->flag=true;
while(temp !=NULL)
{
if(grafo[(temp->nodo)-1]->flag ==false)
visitaInProfondita(temp->nodo , grafo);
temp=temp->succ;
}
}#ifndef nodo_h
#define nodo_h
#define dim 50
typedef enum {false,true} boolean;
struct lista{
int nodo;
struct lista *succ;
};
struct nodo{
char *val;
int tipo;
boolean flag;
struct lista *inizio;
};
void inizializza(struct nodo *a[]);
void aggiungi_nodo(int tipo , char *v ,struct nodo *a[]);
void aggiungi_arco( int n1 , int n2 , struct nodo *grafo[]);
struct lista * inserisciInTesta(struct lista *inizio , int nodo);
void visitaInProfondita(int n , struct nodo *grafo[]);
#endif /* nodo_h */a me non da errori..comuqne sono riuscita a stampare utilizzato un vettore e poi richiamando la funzione di inizializza grafo e poi la funzione di stampa ora per inserire un nodo utilizzando le funzioni che ho già realizzato in Graph.c potresti aiutarmi a realizzarle?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "Graph.h"
#include "List.h"
int main() {
int scelta;
int sceltaUt;
int sceltaAmministratore;
char email;
char pwd;
char destinazione ;
char emailAmministratore;
char pwdAmministratore;
char deleteDestinazione;
Graph g = NULL;
char* nomiCitta[20] = {"Napoli" /*vertice 0*/, "Milano" /*vertice 1*/, "Genova" /*vertice 2*/, "Firenze" /*vertice 3*/, "Roma" /*vertice 4*/, "Torino" /*vertice 5*/, "Venezia" /*vertice 6*/, "Palermo" /*vertice 7*/, "Bari" /*vertice 8*/, "Perugia" /*vertice 9*/,"Parma" /*vertice 10*/,"Calabria" /*vertice 11*/,"Trento" /*vertice 12*/,"Aosta" /*vertice 13*/,"Ancona" /*vertice 14*/,"Pescara" /*vertice 15*/,"Potenza" /*vertice 16*/,"Catania" /*vertice 17*/,"Reggio Emilia" /*vertice 18*/,"Cagliari" /*vertice 19*/};
while((scelta = menu())){
switch (scelta) /* Creo uno switch con 5 case, uno per ogni possibile scelta */
{
case 1:
printf("Inserisci email: ");
scanf("%s", &emailAmministratore);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwdAmministratore);
while((sceltaAmministratore = menuAmministratore())){
switch (sceltaAmministratore) {
case 1://stampa archivo
g = initGraph(20, nomiCitta);
printGraph(g);
break;
case 2://inserisci
printf("Inserisci la destinazione che desideri inserire:");
scanf("%s", &destinazione);
addNode(g,destinazione);
break;
case 3://cancella
printf("Inserisci destinazione da eliminare: ");
scanf("%s", &deleteDestinazione);
break;
}
}
return 0;
break;
case 2:
while((sceltaUt = menuUtente())){
switch (sceltaUt) {
case 1:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("\niscrizione effettuata con successo");
break;
case 2:
printf("Inserisci l'email: ");
scanf ("%s", &email);
printf("Inserisci password(max 7 caratteri): ");
scanf("%s", &pwd);
printf("accesso effettuata con successo");
break;
}
}
return 0;
case 3: /*Se l'utente vuole uscire*/
printf("Grazie per aver scelto il servizio di gestione prenotazione voli, torna a trovarci!\n");
return 0;
break;
default: /*Se l'utente sbaglia ad inserire il numero*/
printf("Questo tasto non consente di effetuare scelte! Riprova!\n");
break;
} /*Fine switch*/
} /*Fine do*/
return 0;
} /*Fine main*/
