#ifndef _GRAFO_H
#define _GRAFO_H
//LIBRERIE:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//STRUTTURE:
struct ListaAdiacenza{//struttura per gli elementi della lista di adiacenza
char Info;//nome del nodo
int Peso;//peso dell'arco entrante dal nodo relativo al primo elemento della riga della lista di adiacenza
struct ListaAdiacenza *PuntDestra;//puntatore all'elemento successivo della riga
struct ListaAdiacenza *PuntSotto;//puntatore all'elemento successivo della colonna (!=NULL solo per la prima colonna)
};
struct ListaNodi{//struttura per insiemi di nodi
char Info;//nome del nodo
struct ListaNodi *PuntProssimo;//puntatore all'elemento successivo
};
struct ListaArchi{//struttura per gli elementi della lista di adiacenza
char InfoUscente;//nome del nodo in cui l'arco è uscente
char InfoEntrante;//nome del nodo in cui l'arco è entrante
int Peso;//peso dell'arco
struct ListaArchi *PuntProssimo;//puntatore all'elemento successivo
};
//ALIAS
typedef ListaAdiacenza *PuntLista; //Assegnazione dell'alias PuntLista a ListaAdiacenza *
typedef ListaNodi *PuntNodi; //Assegnazione dell'alias PuntNodi a ListaNodi *
//FUNZIONI E PROCEDURE
//AggiungiNodo
void AggiungiNodo(PuntLista PuntStart, char InfoNodo){
//Variabili locali:
PuntLista PuntCorrente;
PuntLista PuntNuovo;
PuntNuovo = (PuntLista) malloc(sizeof(ListaAdiacenza)); //Chiede spazio in memoria
if(PuntNuovo != NULL){
PuntNuovo->Info = InfoNodo; //Viene inserito il carattere nel campo Info
PuntNuovo->Peso = 0; //Viene posto il peso del primo elemento di ogni riga a 0
PuntNuovo->PuntDestra=NULL;
PuntNuovo->PuntSotto=NULL;
PuntCorrente = PuntStart;
if(PuntCorrente==NULL)
PuntStart=PuntNuovo;
else{
//Si scende al nodo in basso fin quando non abbiamo NULL
while(PuntCorrente->PuntSotto!=NULL)
PuntCorrente=PuntCorrente->PuntSotto;
PuntCorrente->Sotto = PuntNuovo;
}
}
//AggiungiArco
bool AggiungiArco(PuntLista PuntStart, char InfoPartenza, char InfoArrivo, int PesoArco){
//Variabili locali:
bool errore = true;
PuntLista PuntCorrente;
PuntLista PuntRiga;
PuntLista PuntNuovo;
PuntNuovo = (PuntLista) malloc(sizeof(ListaAdiacenza)); //Chiede spazio in memoria
if(PuntNuovo != NULL){
PuntNuovo->Info = InfoArrivo; //Viene inserito il carattere nel campo lettera
PuntNuovo->Peso = PesoArco; //Viene inializzato lo stato della lettera a non marcato (0)
PuntNuovo->PuntDestra = NULL;
PuntNuovo->PuntSotto = NULL;
PuntCorrente = PuntStart;
PuntRiga = PuntStart;
while(PuntRiga!=NULL){
if(PuntRiga->Info == InfoPartenza){
PuntCorrente = PuntRiga;
while(PuntCorrente->PuntDestra!=NULL)
PuntCorrente = PuntCorrente->PuntDestra;
PuntCorrente->PuntDestra = PuntNuovo;
errore = false;
PuntRiga = NULL;
}
else
PuntRiga = PuntRiga->PuntSotto;
}
return errore;
}
//EliminaArco
bool EliminaArco(PuntLista PuntStart, char InfoPartenza, char InfoArrivo){
//Variabili locali:
bool errore = true;
PuntLista PuntCorrente;
PuntLista PuntPrecedente;
PuntLista PuntRiga;
PuntLista PuntEliminatore;
PuntRiga = PuntStart;
while(PuntRiga!=NULL){
if(PuntRiga->Info == InfoPartenza){
PuntCorrente = PuntRiga->PuntDestra;
PuntPrecedente = PuntRiga;
while(PuntCorrente!=NULL){
if(PuntCorrente->Info == InfoArrivo){
PuntEliminatore=PuntCorrente;
PuntPrecedente->PuntDestra = PuntCorrente->PuntDestra;
free(PuntEliminatore);
errore = false;
PuntCorrente = NULL;
PuntRiga = NULL;
}
else{
PuntPrecedente=PuntCorrente;
PuntCorrente=PuntCorrente->PuntDestra;
}
}
}
else
PuntRiga = PuntRiga->PuntSotto;
}
return errore;
}
//EliminaNodo
bool EliminaNodo(PuntLista PuntStart, char InfoNodo){ //Elimina il nodo e tutti gli archi connessi
//Variabili locali:
PuntLista PuntCorrente;
PuntLista PuntPrecedente;
PuntLista PuntRiga;
PuntLista PuntEliminatore;
PuntLista PuntEliminatoreSucc;
PuntPrecedente = PuntStart;
PuntCorrente = PuntStart->PuntSotto;
bool errore = true;
bool uscita;
//Si scende al nodo in basso fin quando non abbiamo NULL
while(PuntCorrente!=NULL){
if(PuntCorrente->Info == InfoNodo){
PuntEliminatore = PuntCorrente;
PuntEliminatoreSucc = PuntEliminatore->PuntDestra;
PuntPrecedente->PuntSotto = PuntEliminatore->Sotto;
free(PuntEliminatore); //Elimina il primo elemento della riga
while(PuntEliminatoreSuccessivo != NULL){ //Elimina tutti gli elementi della riga
PuntEliminatore = PuntEliminatoreSuccessivo;
PuntEliminatoreSuccessivo = PuntEliminatoreSuccessivo->PuntDestra;
free(PuntEliminatore);
}
PuntCorrente = NULL;
errore = false;
}
else{
PuntPrecedente = PuntCorrente;
PuntCorrente = PuntCorrente->PuntSotto;
}
}
PuntRiga=PuntStart;
while(PuntRiga!=NULL){
uscita = EliminaArco(PuntStart, PuntRiga->Info, InfoNodo);
PuntRiga = PuntRiga->Sotto;
}
return errore;
}
//LunghezzaCammino
int LunghezzaCammino(PuntNodi PrimoNodo, PuntLista PuntStart){
PuntNodi PuntNodoPartenza;
PuntNodi PuntNodoArrivo;
PuntLista PuntRicerca;
int lunghezza = 0;
bool trovato;
bool errore = false;
if(PrimoNodo!=NULL){
PuntNodoPartenza = PrimoNodo;
PuntNodoArrivo = PrimoNodo->PuntProssimo;
while(PuntNodoArrivo != NULL){
PuntRicerca = PuntStart;
trovato=false;
while(PuntRicerca!=NULL){
if(PuntRicerca->Info == PuntNodoPartenza->Info){
while(PuntRicerca!=NULL){
if(PuntRicerca->Info == PuntNodoArrivo->Info){
lunghezza = lunghezza + PuntRicerca->Peso;
PuntRicerca = NULL;
trovato = true;
}
PuntRicerca = PuntRicerca->PuntDestra;
}
}
PuntRicerca = PuntRicerca->PuntSotto;
}
if(trovato == false)
errore=true;
PuntNodoPartenza = PuntNodoArrivo;
PuntNodoArrivo = PuntNodoArrivo->PuntProssimo;
}
}
if(errore == false)
return -1;
else
return lunghezza;
}
#endif
Rispondi quotando
