for customer requests to fly from one city to another city. To support flight it
ID: 3533128 • Letter: F
Question
for customer requests to fly from one city to another city. To support flight itinerary generation, it is necessary to build a
database of all available flights.
For this assignment, implement a pointer based
sortedListClass. This class should keep records/nodes in
ascending order of the city name.
cities.dat
: First line of the data file gives the total number of cities served by the company. Next, the names of cities the
airline serves, one name per line, for example:
16
s? total number of cities served by the company
Albuquerque
Chicago
San-Diego
Explanation / Answer
// rigth now i am posting my previous code , i know you don't want to include ternary trees concept in the code , i will post the another alternate code for you but it will take some time and this time the code will include the concept of list and their functions. Actually right now i don'i have enough time to post the alternate code for you beacause only 30 minutes left to answer, i am just posting the previous code so that later on i can give the correct code means the code which not includes trees, thank you
#include<iostream>
#include<stdlib.h>
#include<fstream>
using namespace std;
typedef struct TstNode
{
char data;
int isEndOfString;
struct TstNode* left;
struct TstNode* eq;
struct TstNode* right;
}TstNode;
class SortedListClass
{
private:
struct TstNode* root;
char* fileName;
TstNode* insertInTst(TstNode* root,char* cityName);
public :
int cityCount;
SortedListClass(char* fname)
{
root=NULL;
fileName=fname;
}
TstNode* getRoot()
{
return root;
}
void displayAllCityNames(TstNode* root,char* cityName);
int read();
void writeHelp(ofstream&,TstNode* root,char* cityName);
int searchInTst(struct TstNode* root,char*cityName);
int deleteCityName(struct TstNode* root,char*cityName);
int write();
};
int SortedListClass:: read()
{
ifstream in(fileName);
char cityName[100];
if(!in)
{
cout << "Cannot open input file. ";
exit(0);
}
else
{
in>>cityCount;
while(in)
{
in>>cityName;
if(in)
{
root=insertInTst(root,cityName);
}
}
in.close();
}
return cityCount;
}
int SortedListClass:: write()
{
ofstream out(fileName);
char cityName[100];
int cityCount=0;
if(!out)
{
cout << "Cannot open input file. ";
exit(0);
}
else
{
out<<cityCount<<" ";
writeHelp(out,root,cityName);
out.close();
}
}
void SortedListClass:: writeHelp(ofstream& out,TstNode* root,char* cityName)
{
if(!root)
return;
static int i=0;
writeHelp(out,root->left,cityName);
cityName[i]=root->data;
if(root->isEndOfString)
{
cityName[i+1]='';
out<<cityName<<endl;
}
i++;
writeHelp(out,root->eq,cityName);
i--;
writeHelp(out,root->right,cityName);
}
TstNode* SortedListClass:: insertInTst(TstNode* root,char* cityName)
{
if(root==NULL)
{
root=(TstNode*) malloc(sizeof(TstNode));
root->data=*cityName;
root->isEndOfString=0;
root->left=root->right=root->eq=NULL;
}
if(*cityName<root->data)
root->left=insertInTst(root->left,cityName);
else if(*cityName==root->data)
{
if(*(cityName+1))
root->eq=insertInTst(root->eq,cityName+1);
else
root->isEndOfString=1;
}
else
root->right=insertInTst(root->right,cityName);
return root;
}
int SortedListClass::searchInTst(struct TstNode* root,char*cityName)
{
if(!root)
return -1;
if(*cityName<root->data)
return searchInTst(root->left,cityName);
else if(*cityName>root->data)
return searchInTst(root->right,cityName);
else if(*cityName==root->data)
{
if(root->isEndOfString==1&&*(cityName+1)==0)
return 1;
return searchInTst(root->eq,cityName+1);
}
}
int SortedListClass::deleteCityName(struct TstNode* root,char*cityName)
{
if(!root)
return 0;
if(*cityName<root->data)
return deleteCityName(root->left,cityName);
else if(*cityName>root->data)
return deleteCityName(root->right,cityName);
else if(*cityName==root->data)
{
if(root->isEndOfString==1&&*(cityName+1)==0)
{
root->isEndOfString=0;
write();
return 1;
}
return deleteCityName(root->eq,cityName+1);
}
}
void SortedListClass:: displayAllCityNames(TstNode* root,char* cityName)
{
if(!root)
return;
static int i=0;
displayAllCityNames(root->left,cityName);
cityName[i]=root->data;
if(root->isEndOfString)
{
cityName[i+1]='';
printf("%s ",cityName);
}
i++;
displayAllCityNames(root->eq,cityName);
i--;
displayAllCityNames(root->right,cityName);
}
int main()
{
char fileName[30];
char cityName[100];
int cityCount=0;
cout<<"enter the file name to be read ";
cin>>fileName;
SortedListClass obj(fileName);;
cityCount=obj.read();
cout<<" ..........city names in sorted order ................. "<<endl;
obj.displayAllCityNames(obj.getRoot(),cityName);
cout<<" total no of city= "<<cityCount<<endl;
cout<<"enter the city name to be searched ";
cin>>cityName;
int found=obj.searchInTst(obj.getRoot(),cityName);
if(found==1)
cout<<"This city is found ";
else
cout<<"This city is not served ";
for(int i=0;i<3;i++)
{
cout<<"enter the city to be deleted ";
cin>>cityName;
int found=obj.searchInTst(obj.getRoot(),cityName);
if(found==1)
{
obj.deleteCityName(obj.getRoot(),cityName);
cout<<" ..........city names after delete operation................. "<<endl;
cityCount=obj.read();
obj.displayAllCityNames(obj.getRoot(),cityName);
}
else
cout<<"This city does not exit ";
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.