Fly2.c

/* FLY2.C - Demonstration of data structures, simulating an airport.
**
** This program demonstrates linked lists, trees, recursion, and data
** file loading, to simulate a program that would find the direct path
** between two airports.
**
** Mario Giannini
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/** Forward declarations */
typedef struct _tagAIRPORT AIRPORT;

/** Flights Connect airports */
typedef struct _tagFLIGHT {
	int ID;
	char Airline[26];
	int Miles;
	AIRPORT *Departs, *Arrives;
	} FLIGHT;

/* Airports have many flights */
typedef struct _tagAIRPORT {
	char Name[4], FullName[36];
	FLIGHT **Flights;
	int FlightCount;
	struct _tagAIRPORT *Next;
	} AIRPORT;

/** Prototypes make life easier */
int _FindRoute( AIRPORT *Dep, AIRPORT *Arr );

#define IsDeparting(A,F) (F->Departs==A)
#define IsArriving(A,F) (F->Arrives==A)
#define FlightNum(A,x) (A->Flights[x])
#define IsConnecting(F1,F2) (F1->Arrives == F2->Departs )

static AIRPORT *World;
/* FindAirport - Locates an AIRPORT node via Name */
AIRPORT *FindAirport( char *Name )
{
	AIRPORT *Ret;
	for( Ret = World; Ret && stricmp( Ret->Name, Name ) ; Ret = Ret->Next )
			;
	return( Ret );
}

/* CreateAirport - Creates new airport, and adds to global linked list */
AIRPORT * CreateAirport( char *Name, char *FullName )
{
	AIRPORT *Air;
	if( (Air=calloc(1,sizeof(AIRPORT))) == NULL )
		return(NULL);
	strcpy( Air->Name, Name );
	strcpy( Air->FullName, FullName );
	if( World == NULL )
		World = Air;
	else
	{
		Air->Next=World;
		World=Air;
	}
	return( Air ); 
}

/* ListAirports - Lists all airports in the global linked list */
void ListAirports( void )
{
	AIRPORT *Start = World;
	for( Start=World; Start; Start=Start->Next )
		printf("%s: %s\n", Start->Name, Start->FullName );
}

/* Connect - Connects 2 airports, by creating a flight */
FLIGHT * Connect( AIRPORT *Dep, AIRPORT *Arr, char *Airline, int Miles )
{
	FLIGHT *Flight;
	void *Tmp;

	if( (Flight=calloc(1,sizeof(FLIGHT))) == NULL )
		return(NULL);
	if( (Tmp=realloc( Dep->Flights, (Dep->FlightCount+1)*sizeof(FLIGHT*))) == NULL )
	{
		free( Flight );
		return( NULL );
	}
	Dep->Flights = Tmp;

	if( (Tmp=realloc( Arr->Flights, (Arr->FlightCount+1)*sizeof(FLIGHT*))) == NULL )
	{
		free( Flight );
		return( NULL );
	}
	Arr->Flights = Tmp;

	Flight->Miles = Miles;
	strcpy( Flight->Airline, Airline );
	Flight->Departs = Dep;
	Flight->Arrives = Arr;
	Dep->Flights[Dep->FlightCount++]=Flight;
	Arr->Flights[Arr->FlightCount++]=Flight;
	return( Flight );
}

/* DumpAirport - Displays all flights for an airport */
void DumpAirport( AIRPORT *Airport )
{
	int i;
	printf("%s has:\n", Airport->FullName );
	for( i=0; i<Airport->FlightCount; i++ )
	{
		printf( "\t%d: %s ", i, Airport->Flights[i]->Airline );

		if( Airport->Flights[i]->Departs == Airport )
			printf("flies to %s\n", Airport->Flights[i]->Arrives->FullName );
		else
			printf("arrives from %s\n", Airport->Flights[i]->Departs->FullName );
	}
}

FLIGHT *FlightList[10];
int FlightCount;
FLIGHT *BestFlightList[10];
int BestFlightCount;

/* DumpFlightList - Dumps the flight list that FindRoute created */
void DumpFlightList( void )
{
	int i;
	for( i=0; i < BestFlightCount; i++ )
		printf("Take %s from %s to %s\n", BestFlightList[i]->Airline, 
			BestFlightList[i]->Departs->FullName, BestFlightList[i]->Arrives->FullName);
}

/* FindRoute - Determines most direct path between 2 airports */
int FindRoute ( AIRPORT *Dep, AIRPORT *Arr )
{
	int i, j;
	BestFlightCount=FlightCount = 0;

	if( Dep == NULL || Arr == NULL )
	{
		printf("Bad airport!\n");
		return(0);
	}

/* First sweep: direct flights */
	for( i=0; i < Dep->FlightCount; i++ ) 
	{
		if( IsDeparting( Dep, FlightNum(Dep,i) ) )
		{
			if( IsArriving( Arr, FlightNum(Dep,i) ) )
			{
				BestFlightList[BestFlightCount++] = FlightNum(Dep,i);
				return(1);
			}
		}
	}

/* Second Sweep: connecting flights */
	for( i=0; i < Dep->FlightCount; i++ ) 
	{
		if( IsDeparting( Dep, FlightNum(Dep,i) ) )
		{
			for(j=0; j<Arr->FlightCount; j++ )
			{
				if( IsConnecting( FlightNum(Dep,i), FlightNum( Arr,j ) ) )
				{
					BestFlightList[BestFlightCount++] = FlightNum(Dep,i);
					BestFlightList[BestFlightCount++] = FlightNum(Arr,j);
					return(1);
				}
			}
		}
	}

	return( _FindRoute( Dep, Arr ) );
}

/* _FindRoute - The recursive version of FindRoute */
int _FindRoute( AIRPORT *Dep, AIRPORT *Arr )
{
	int i;

	
	if( Dep == Arr )
	{
		if( BestFlightCount == 0 || BestFlightCount > FlightCount )
		{
			printf("Found a%s way!\n", BestFlightCount == 0 ? "" : " better");
			BestFlightCount=FlightCount;
			memmove( BestFlightList, FlightList, FlightCount*sizeof(void*));
		}
		return(1);
	}

	/** OK, brute force recursion */	
	for( i=0; i < Dep->FlightCount; i++ ) 
	{
		if( IsDeparting(Dep,FlightNum(Dep,i)) )
		{
			FlightList[FlightCount++] = FlightNum(Dep,i);
			_FindRoute( Dep->Flights[i]->Arrives, Arr );
			FlightCount--;
		}
	}
	return( BestFlightCount > 0 ? 1 : 0 );
}

/* InitWorld - Loads airport and flight data from data file */
InitWorld( char *File )
{
	int i=0;
	FILE *Input;
	AIRPORT *apDep, *apArr;
	char Buffer[81], *Small, *Long, *Miles, *Dep, *Arr, *Air;

	if( (Input=fopen(File,"r")) != NULL )
	{
		while( fgets( Buffer, sizeof(Buffer), Input ) )
		{
			if( Buffer[0] )
				Buffer[ strlen(Buffer)-1 ] = '\0';
			if( strnicmp( Buffer, "AIRPORT: ", 9 ) == 0 )
			{
				Small = strtok( Buffer+9, "," );
				Long = strtok( NULL, "," );
				while( *Long && *Long==' ' )
					Long++;
				while( *Small && *Small==' ' )
					Small++;
				CreateAirport( Small, Long );
			}
			if( strnicmp( Buffer, "CONNECT: ", 9 ) == 0 )
			{
				Dep = strtok( Buffer+9, "," );
				Arr = strtok( NULL, "," );
				Air = strtok( NULL, "," );
				Miles = strtok( NULL, "," );
				while( *Dep && *Dep==' ' )
					Small++;
				while( *Arr && *Arr==' ' )
					Arr++;
				while( *Air && *Air==' ' )
					Air++;
				while( *Miles && *Miles==' ' )
					Miles++;
				apDep = FindAirport( Dep );
				apArr = FindAirport( Arr );
				if( apDep == NULL || apArr == NULL )	
					printf("Oops\n");
				else
					Connect( apDep, apArr, Air, atoi(Miles) );
			}
		}
		fclose(Input);
	}
	return(i);
}

void main( void )
{
	char From[10], To[10];

	InitWorld( "FLY.DAT" );

	ListAirports();
	printf("From: " );
	gets(From);
	printf("to: ");
	gets(To);
	if( FindRoute( FindAirport(From), FindAirport(To) ) == 0 )
		printf("Can't get there from here\n");
	else
		DumpFlightList();

}