Must be a C++ Program!! Part 1: Setup an array or a link list data structure usi

Question

Must be a C++ Program!!

Part 1:

Setup an array or a link list data structure using the sample data below that will allow the user to search for a route from Airport A to Airport B. Example: If the user enters ATL for Airport A and JAN for Airport B, your program should return “Yes, there is a route from ATL to JAN. If the user enters UTH for Airport A and CHI for Airport B, your program should return “No, there is not a route from UTH to CHI.

Part 2:

Setup a linked list data structure using the sample data below that will allow the user to search, insert, and delete flight destinations from there respectable airports. Example: Given the Airport A and Airport B, I’m given the option to search for a direct flight to a specific location (Airport B), add a new flight destination (Airport B) to Airport A, and delete a destination flight (Airport B) from Airport A.

Sample data file:

Airport

Flights To

JAN

ATL : MEM : HOU : LAX

ATL

SAN : LAX : UTH

MEM

LAX

HOU

UTH : SAN

SAN

JAN : MEM : HOU

UTH

SAN

LAX

ATL : MEM : HOU : SAN

CHI

MEM : ATL

Airport

Flights To

JAN

ATL : MEM : HOU : LAX

ATL

SAN : LAX : UTH

MEM

LAX

HOU

UTH : SAN

SAN

JAN : MEM : HOU

UTH

SAN

LAX

ATL : MEM : HOU : SAN

CHI

MEM : ATL

Explanation / Answer

Hi, I have used STL lists and created a struct which contains information about source and their list of direct flights.

#include <iostream>
#include<list>
#include<string>
using namespace std;

//mystruct to add a source and list of destincations
struct MyList {
string source;
list<string> destinations;
};

list<MyList> myList;
list<string> visitedSources;

bool checkVisited(string s) {
list<string>::iterator it;
for(it = visitedSources.begin(); it!=visitedSources.end(); ++it) {
if(*it == s)
return true;
}
return false;
}

//to add the data in myList by source and destincations
void add(string source,string d1, string d2, string d3, string d4 ) {
MyList item1;
item1.source = source;
list<string> destinations;
destinations.push_back(d1);
  
if(d2 != "")
destinations.push_back(d2);
if(d3 != "")
destinations.push_back(d3);
if(d4 != "")
destinations.push_back(d4);
  
item1.destinations = destinations;
  
myList.push_back(item1);
}

//recursive function to find path from source to des
bool findPath(string source, string des, bool direct) {
visitedSources.push_back(source);
list<MyList>::iterator myListIt = myList.begin();
for(myListIt = myList.begin(); myListIt != myList.end(); ++myListIt) {
if((*myListIt).source == source) {
list<string> destinations =(*myListIt).destinations;
list<string>::iterator it;
for(it=destinations.begin(); it != destinations.end(); ++it) {
  
//check if the list of destinations for this source contains our destination
if(*it == des)
return true;
  
//check if this current destination can act as source to reach our main destination
if(!direct && !checkVisited(*it) && findPath(*it,des, direct))
return true;
}
break;
}
}
return false;
}

//solution for part 1
void part1() {
cout<<"Enter Airport A :";
string source;
cin>>source;
cout<<endl<<"Enter Airport B :";
string des;
cin>>des;
cout<<endl;
  
if(findPath(source,des, false))
cout<<"Yes, there is a route from "<<source<<"to "<<des<<endl;
else
cout<<"No, there is not a route from "<<source<<" to "<<des<<endl;
  
  
}

//search a direct flight
void searchDirectFlight(string source, string des) {
if(findPath(source,des, true))
cout<<endl<<"Yes, there is a direct flight from "<<source<<"to "<<des<<endl;
else
cout<<endl<<"No, there is not a direct flight from "<<source<<" to "<<des<<endl;
}

//add a new destination
void addNewFlight(string s, string d) {
list<MyList>::iterator myListIt = myList.begin();
for(myListIt = myList.begin(); myListIt != myList.end(); ++myListIt) {
if((*myListIt).source == s) {
(*myListIt).destinations.push_back(d);
break;
}
}
}

//delete a destination
void deleteFlight(string s, string d) {
list<MyList>::iterator myListIt = myList.begin();
for(myListIt = myList.begin(); myListIt != myList.end(); ++myListIt) {
if((*myListIt).source == s) {
(*myListIt).destinations.remove(d);
break;
}
}
}

void part2() {
cout<<"Please enter your choice. 1.Search a direct flight 2.Add a new direct flight 3.Delete a direct flight.";
cout<<endl;
int num;
cin>>num;
  
string source, destination;
cout<<"Enter source :";
cin>>source;
  
cout<<endl<<"Enter destination ";
cin>>destination;
  
if(num ==1 ) {
searchDirectFlight(source,destination);
} else if(num == 2) {
addNewFlight(source,destination);
  
} else
deleteFlight(source,destination);
}

int main() {
  
  
add("JAN","ATL","MEM","HOU","LAX");
add("ATL","SAN","LAX","UTH","");
add("MEM","LAX","","","");
add("HOU","UTH","SAN","","");
add("SAN","JAN","MEM","HOU","");
add("UTH","SAN","","","");
add("LAX","ATL","MEM","HOU","SAN");
add("CHI","MEM","ATL","","");
  
cout<<"Choose a number. 1. to find route 2.To search, add or delete direct flight"<<endl;
  
  
   int num;
   cin>>num;
  
   if(num == 1)
   part1();
   else
   part2();
  
   return 0;
}

Sample Outputs :

Output 1 :

Choose a number.
1. to find route
2.To search, add or delete direct flight

1

Enter Airport A : ATL
Enter Airport B : JAN
Yes, there is a route from ATLto JAN

Output 2 :

Choose a number.
1. to find route
2.To search, add or delete direct flight

2
Please enter your choice.
1.Search a direct flight
2.Add a new direct flight
3.Delete a direct flight.

1
Enter source : JAN
Enter destination CHI

No, there is not a direct flight from JAN to CHI

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.