for customer requests to fly from one city to another city. To support flight it
ID: 3532881 • 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
// i have used the concept of ternary search trees to implements all the functions you want
// i was not having time to check whether all the functions are working properly on all differen cases
// so if you found any problem comment
//you can take this code as a reference
#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.