Objectives: • Implement a linked list • Use structures to create nodes for a lin
ID: 3723996 • Letter: O
Question
Objectives:
• Implement a linked list
• Use structures to create nodes for a linked list
• Use pointers to manipulate a linked list
Problem: Doc Brown has configured the DeLorean to go back to the days of the Roman Empire. Unfortunately, the Roman Empire does not use Arabic numerals which is going to make it difficult for Doc to do the proper calculations he needs to get back home. Before he heads back in time, he wants you to create a Roman numeral converter for him.
Details: • Roman numerals are as follows: o 1 = I o 5 = V o 10 = X o 50 = L o 100 = C o 500 = D o 1000 = M • Determine if the input given is Roman numeral or Arabic. • Convert from given type to the missing type. • All numbers will be in the range of 1 – 4999. • Store the file contents in a linked list. o Add the node to the beginning of the list • All manipulation of the data will happen in the linked list. o Convert each piece of data to its unlisted counterpart • Write the contents of the linked list back to the file at the end of the program. • The file may contain invalid data. o If invalid data is identified, ignore the entry in the file. • Invalid data: o Arabic numeral outside the given rage. o Invalid characters in Roman numeral. o Invalid characters in Arabic numeral. • User will be able to search and sort the data. • Use a linear search o Search can be for Arabic or Roman numeral o Do not ask user what type of numeral to search for (-5 points if user is asked) User can type in Arabic or Roman numeral You have to figure out what they typed • Implement sorting algorithm of your choice o Sorting algorithm will move nodes (-10 points) o Do not exchange node data o All sorts will sort in ascending order Arabic: smallest to largest number Roman: alphabetical • Comment your code generously. Refer to the grading rubric for more details. • Use as few variables as possible. Don’t waste memory holding a calculation just so you can print it out one time.
User Interface and Input: Create a simple menu interface allowing the user to search and sort the data. The menu will consist of 3 options: 1. Search 2. Sort 3. Exit If the user selects the sort option, provide a sub menu: 1. Sort by Roman numeral 2. Sort by Arabic numeral All user input will be valid. Remember that the file input may not be valid.
File Structure: • The file will contain an unknown quantity of numbers to convert. • Each number will be on a separate line. • The number will be either Arabic or Roman • Each line of the file will have the same format o Roman numeral field – 16 characters • Fixes the 4888 issue Arabic numeral field – 4 characters • The last line may or may not have a new line at the end • Only one of the fields will hold a value on each line o If a field does not hold a value, it will contain all spaces. o If the Roman numeral field contains a space as the first character, you know that the line contains an Arabic numeral
Output: If the user enters the option to search, state whether the item was found or not found ( ) in the console window. If the user enters the option to sort, display the sorted values to the console window. Only display the values for the type of data sorted. For example, if Roman numerals are sorted, only display the Roman numerals in alphabetic order. At the end of the program, write the linked list back to the file used for input.
In C++ please. Thank you.
Explanation / Answer
main.cpp
#include <iostream>
#include "BaseNode.h"
#include "DoubleLinkNode.h"
#include "LinkedList.h"
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <fstream>
#include <string>
using namespace std;
string ConvertToRoman(int);
int ConvertToArabic(string);
void SortRoman(LinkedList&);
void SortArabic(LinkedList&);
bool search(LinkedList&,string);
int main( int argc, char *argv[])
{
if(argc==1)
string filename=argv[0];
LinkedList list;
const int romeNum=15, arabicNum=4;
ifstream nameFile;
nameFile.open(filename, ios::binary);
char ch;
int x;
int position;
//cout<<"before if ";
if (nameFile)
{
bool firstLine=true;
while (!nameFile.eof())
{
DoubleLinkNode* line=new DoubleLinkNode;
nameFile.get(ch);
position=nameFile.tellg();
position=position-1;
if(position == -2) break;
if (ch==' ')
{
nameFile.seekg(15, ios::cur);
bool insert=true;
int sum=0;
for (int i=0;i<arabicNum;i++)
{
nameFile.get(ch);
x = ch - '0';
if (ch==' ') break;
else if(x>9||x<0) //if x is not a number, then ignore the line.
{
insert=false;
break;
}
sum = sum*10 + x;
}
if(sum>4999||sum<1) //if the Arabic numeral is greater than 4999 or less than 1, ignore the line.
{
insert=false;
}
if(insert)
{
//cout<<"FF";
line->setArabic(sum);
line->setRoman(ConvertToRoman(sum)); //insert the data into a node.
//cout<<"SSS";
}
nameFile.seekg(position, ios::beg);
nameFile.seekg(22,ios::cur);
}
else
{
nameFile.seekg(position, ios::beg);
string rom;
for (int i=0;i<romeNum;i++)
{
nameFile.get(ch);
if (ch==' ') break;
rom+=ch;
}
//cout<<rom<<endl;
bool insert=true;
if(ConvertToArabic(rom)>4999||ConvertToArabic(rom)<1) //if the converted numeral is greater than 4999 or less than 1, ignore the line.
{
insert=false;
}
else
{
for(unsigned int i=0;i<rom.length();i++)
{
//cout<<rom[i]<<" ";
if(rom[i]!='I'&&rom[i]!='V'&&rom[i]!='X'&&rom[i]!='L'&&rom[i]!='C'&&rom[i]!='D'&&rom[i]!='M') //if there is no roman numeral, ignore the line.
{
insert=false;
break;
}
}
}
if(insert)
{
//cout<<"F";
line->setRoman(rom);
line->setArabic(ConvertToArabic(rom)); //insert the data into a node.
//cout<<"A";
}
nameFile.seekg(position, ios::beg);
nameFile.seekg(22, ios::cur);
}
if(firstLine)
{
list.setHead(line);
list.setTail();
firstLine=false;
//cout<<"int this if statement"<<endl;
}
else
{
//cout <<"in the else statement" << endl;
list+=line;
}
//cout<<list.getHead()->getArabic()<<" "<<list.getHead()->getRoman()<<endl;
//cout<<list.getTail()->getArabic()<<" "<<list.getTail()->getRoman()<<endl;
//cout<<"FF";
}
}
nameFile.close();
SortArabic(list);
bool exit=false;
while(!exit)
{
int answer;
cout<<"1. Search"<<endl; //show the options.
cout<<"2. Add"<<endl;
cout<<"3. Delete first"<<endl;
cout<<"4. Delete last"<<endl;
cout<<"5. Delete specific node"<<endl;
cout<<"6. Exit"<<endl;
cout<<"Choose an option by typing a number. ";
cin>>answer;
if(answer==1)
{
string input;
cout<<"Type the value to search. ";
cin>>input;
if(search(list,input)) //search.
cout<<input<<" found."<<endl;
else
cout<<input<<" not found."<<endl;
}
else if(answer==2)
{
DoubleLinkNode* add=new DoubleLinkNode;
cin>>*add;
if(add->getArabic()==0&&add->getRoman()=="")
cout<<"Type something!"<<endl;
else if(add->getArabic()==0)
add->setArabic(ConvertToArabic(add->getRoman()));
else
add->setRoman(ConvertToRoman(add->getArabic()));
list+=add;
//cout<<list.getTail()->getArabic();
SortArabic(list);
}
else if(answer==3)
{
--list;
}
else if(answer==4)
{
list--;
}
else if(answer==5)
{
string input;
cout<<"Type the value to delete. ";
cin>>input;
if(search(list,input)) //search.
{
DoubleLinkNode* ptr=list.getHead();
if(input[0]<='9'&&input[0]>='0')
{
int tempInput=atoi(input.c_str());
while(ptr->getArabic()!=tempInput)
ptr=ptr->getNext();
}
else
{
while(ptr->getRoman()!=input)
ptr=ptr->getNext();
}
if(!ptr->getPrev())
{
--list;
}
else if(!ptr->getNext())
{
list--;
}
else
{
DoubleLinkNode* prePtr=ptr->getPrev();
DoubleLinkNode* postPtr=ptr->getNext();
prePtr->setNext(postPtr);
postPtr->setPrev(prePtr);
ptr->setNext(nullptr);
ptr->setPrev(nullptr);
delete ptr;
}
}
else
cout<<input<<" not found."<<endl;
}
else if(answer==6)
{
exit=true;
}
else
cout<<"Invalid number."<<endl;
}
ofstream newLine("numbers.txt");
newLine.close();
/*DoubleLinkNode* out=list.getTail();
while(out)
{
cout<<out->getArabic()<<" "<<out->getRoman()<<endl;
out=out->getPrev();
}*/
//nameFile2.close();
list.print();
list.~LinkedList();
}
string ConvertToRoman(int i)
{
string str;
int thousands=i/1000;
int hundreds=i%1000/100;
int tens=i%1000%100/10;
int> if (thousands>0&&thousands<=4)
for (int i=0;i<thousands;i++)
{
str+="M";
}
if (hundreds>0&&hundreds<4)
for (int i=0;i<hundreds;i++)
{
str+="C";
}
else if (hundreds==4)
{
str+="CD";
}
else if (hundreds==5)
{
str+="D";
}
else if (hundreds>5&&hundreds<9)
{
str+="D";
for (int i=0;i<hundreds-5;i++)
{
str+="C";
}
}
else if(hundreds==9)
{
str+="CM";
}
if (tens>0&&tens<4)
{
for(int i=0;i<tens;i++)
{
str+="X";
}
}
else if (tens==4)
{
str+="XL";
}
else if (tens==5)
{
str+="L";
}
else if (tens>5&&tens<9)
{
str+="L";
for (int i=0;i<tens-5;i++)
{
str+="X";
}
}
else if(tens==9)
{
str+="XC";
}
if (ones>0&&ones<4)
{
for(int i=0;i<ones;i++)
{
str+="I";
}
}
else if (ones==4)
{
str+="IV";
}
else if (ones==5)
{
str+="V";
}
else if (ones>5&&ones<9)
{
str+="V";
for(int i=0;i<ones-5;i++)
{
str+="I";
}
}
else if (ones==9)
{
str+="IX";
}
return str;
}
int ConvertToArabic(string s)
{
int sum=0;
for(unsigned int i=0;i<s.length();i++)
{
char p=s[i-1];
char c=s[i];
char c2=s[i+1];
if (c=='M')
{
if(p=='C');
else
sum+=1000;
}
else if (c=='D')
{
if(p=='C');
else
sum+=500;
}
else if (c=='C'&&c2=='M')
{
sum+=900;
}
else if (c=='C'&&c2=='D')
{
sum+=400;
}
else if (c=='C')
{
if(p=='X');
else
sum+=100;
}
else if (c=='L')
{
if(p=='X');
else
sum+=50;
}
else if (c=='X'&&c2=='C')
{
sum+=90;
}
else if (c=='X'&&c2=='L')
{
sum+=40;
}
else if (c=='X')
{
if(p=='I');
else
sum+=10;
}
else if (c=='V')
{
if(p=='I');
else
sum+=5;
}
else if (c=='I'&&c2=='X')
{
sum+=9;
}
else if (c=='I'&&c2=='V')
{
sum+=4;
}
else if (c=='I')
{
sum+=1;
}
}
return sum;
}
void SortRoman(LinkedList &list)//selection sort
{
int count=0;
DoubleLinkNode* num=list.getHead();
while(num)
{
num=num->getNext();
count++;
}
DoubleLinkNode* ptr;
DoubleLinkNode* temp;
DoubleLinkNode* prePtr;
DoubleLinkNode* postPtr;
bool swap;
do
{
ptr=list.getHead();
swap=false;
for(int i=1;i<count;i++)
{
//cout<<ptr->arabic<<" "<<ptr->next->arabic<<endl;
if(ptr->getRoman()>ptr->getNext()->getRoman())
{
if(i==1) //arrange the nodes.
{
temp=ptr->getNext();
postPtr=temp->getNext();
ptr->setNext(postPtr);
ptr->setPrev(temp);
temp->setNext(ptr);
temp->setPrev(nullptr);
postPtr->setPrev(ptr);
list.setHead(temp);
ptr=list.getHead();
}
else if(i==(count-1))
{
temp=ptr->getNext();
prePtr=ptr->getPrev();
ptr->setNext(nullptr);
ptr->setPrev(temp);
temp->setPrev(prePtr);
temp->setNext(ptr);
prePtr->setNext(temp);
}
else
{
temp=ptr->getNext();
prePtr=ptr->getPrev();
postPtr=temp->getNext();
ptr->setNext(postPtr);
ptr->setPrev(temp);
temp->setNext(ptr);
temp->setPrev(prePtr);
prePtr->setNext(temp); //link the previous node with arranged nodes.
postPtr->setPrev(ptr);
ptr=temp;
}
swap=true;
//cout<<ptr->arabic<<" "<<ptr->next->arabic<<" "<<ptr->next->next->arabic<<endl;
}
ptr=ptr->getNext();
}
}while(swap);
// list.setTail();
//print(head);
}
void SortArabic(LinkedList &list)//selection sort
{
int count=0;
DoubleLinkNode* num=list.getHead();
while(num)
{
num=num->getNext();
count++;
}
//cout<<count;
DoubleLinkNode* ptr;
DoubleLinkNode* temp;
DoubleLinkNode* prePtr;
DoubleLinkNode* postPtr;
bool swap;
do
{
ptr=list.getHead();
//cout<<ptr->getArabic()<<" "<<ptr->getNext()->getArabic()<<endl;
swap=false;
for(int i=1;i<count;i++)
{
if(ptr->getArabic()>ptr->getNext()->getArabic())
{
//cout<<ptr->getArabic()<<" ";
if(i==1) //arrange the nodes.
{
temp=ptr->getNext();
postPtr=temp->getNext();
ptr->setNext(postPtr);
ptr->setPrev(temp);
temp->setNext(ptr);
temp->setPrev(nullptr);
postPtr->setPrev(ptr);
list.setHead(temp);
ptr=list.getHead();
}
else if(i==(count-1))
{
temp=ptr->getNext();
prePtr=ptr->getPrev();
ptr->setNext(nullptr);
ptr->setPrev(temp);
temp->setPrev(prePtr);
temp->setNext(ptr);
prePtr->setNext(temp);
}
else
{
temp=ptr->getNext();
prePtr=ptr->getPrev();
postPtr=temp->getNext();
ptr->setNext(postPtr);
ptr->setPrev(temp);
temp->setNext(ptr);
temp->setPrev(prePtr);
prePtr->setNext(temp); //link the previous node with arranged nodes.
postPtr->setPrev(ptr);
ptr=temp;
}
swap=true;
//cout<<ptr->arabic<<" "<<ptr->next->arabic<<" "<<ptr->next->next->arabic<<endl;
}
ptr=ptr->getNext();
//cout<<"SSSS";
}
}while(swap);
list.setTail();
//print(head);
}
bool search(LinkedList &list, string s)
{
int count=0;
DoubleLinkNode* num=list.getHead();
while(num)
{
num=num->getNext();
count++;
}
int left=1, right=count, middle;
bool found=false;
if(s[0]<='9'&&s[0]>='0')
{
int sum=0;
int x;
for(unsigned int i=0;i<s.length();i++) //change the string s to int.
{
x=s[i]-'0';
sum=sum*10+x;
}
while(!found&&left<=right) //do the binary search.
{
DoubleLinkNode* ptr=list.getHead();
//print(head);
middle=(left+right)/2;
for(int i=0;i<middle-1;i++) //get to the middle node.
{
ptr=ptr->getNext();
}
if(ptr->getArabic()==sum) //if found, swap 'found' true.
found=true;
else if(ptr->getArabic()>sum)
{
right=middle-1;
}
else
left=middle+1;
}
if(found)
{
return true;
}
else
{
return false;
}
}
else
{
SortRoman(list); //sort the list.
while(!found&&left<=right)
{
DoubleLinkNode* ptr=list.getHead();
//print(head);
middle=(left+right)/2;
for(int i=0;i<middle-1;i++) //move to the middle node.
{
ptr=ptr->getNext();
}
if(ptr->getRoman()==s) //if found, swap 'found' true.
found=true;
else if(ptr->getRoman()>s)
{
right=middle-1;
}
else
left=middle+1;
}
SortArabic(list);
//print(head);
if(found)
{
return true;
}
else
{
return false;
}
//print(head);
}
}
BaseNode.cpp
#include "BaseNode.h"
#include <iomanip>
#include <string>
BaseNode::BaseNode()
{
roman="";
arabic=0;//ctor
}
BaseNode::BaseNode(string r,int a)
{
roman=r;
arabic=a;
}
BaseNode::BaseNode(const BaseNode& obj)
{
roman=obj.roman;
arabic=obj.arabic;
}
string BaseNode::getRoman()
{
return roman;
}
int BaseNode::getArabic()
{
return arabic;
}
ostream& operator<<(ostream &strm,const BaseNode &obj)
{
strm<<left<<setw(15)<<obj.roman<<" "<<setw(4)<<obj.arabic<<endl;
return strm;
}
istream& operator>>(istream &strm,BaseNode &obj)
{
cout<<"Type in Arabic or Roman numeral.";
string s;
strm>>s;
if(s[0]<='9'&&s[0]>='0')
{
int sum=0;
int x;
for(int i=0;i<s.length();i++) //change the string s to int.
{
x=s[i]-'0';
sum=sum*10+x;
}
obj.arabic=sum;
}
else
obj.roman=s;
return strm;
}
BaseNode::~BaseNode()
{
//dtor
}
BaseNode.h
#include "BaseNode.h"
#include <iomanip>
#include <string>
BaseNode::BaseNode()
{
roman="";
arabic=0;//ctor
}
BaseNode::BaseNode(string r,int a)
{
roman=r;
arabic=a;
}
BaseNode::BaseNode(const BaseNode& obj)
{
roman=obj.roman;
arabic=obj.arabic;
}
string BaseNode::getRoman()
{
return roman;
}
int BaseNode::getArabic()
{
return arabic;
}
ostream& operator<<(ostream &strm,const BaseNode &obj)
{
strm<<left<<setw(15)<<obj.roman<<" "<<setw(4)<<obj.arabic<<endl;
return strm;
}
istream& operator>>(istream &strm,BaseNode &obj)
{
cout<<"Type in Arabic or Roman numeral.";
string s;
strm>>s;
if(s[0]<='9'&&s[0]>='0')
{
int sum=0;
int x;
for(int i=0;i<s.length();i++) //change the string s to int.
{
x=s[i]-'0';
sum=sum*10+x;
}
obj.arabic=sum;
}
else
obj.roman=s;
return strm;
}
BaseNode::~BaseNode()
{
//dtor
}
DoubleLinkNode.cpp
#include "DoubleLinkNode.h"
DoubleLinkNode::DoubleLinkNode()
{
next=nullptr;
prev=nullptr;//ctor
}
DoubleLinkNode* DoubleLinkNode::getNext()
{
return next;
}
DoubleLinkNode* DoubleLinkNode::getPrev()
{
return prev;
}
void DoubleLinkNode::setRoman(string r)
{
roman=r;
}
void DoubleLinkNode::setArabic(int a)
{
arabic=a;
}
void DoubleLinkNode::setNext(DoubleLinkNode* n)
{
next=n;
}
void DoubleLinkNode::setPrev(DoubleLinkNode* p)
{
prev=p;
}
DoubleLinkNode::~DoubleLinkNode()
{
//dtor
}
DoubleLinkNode.h
#ifndef DOUBLELINKNODE_H
#define DOUBLELINKNODE_H
#include "BaseNode.h"
class DoubleLinkNode : public BaseNode
{
public:
DoubleLinkNode();
DoubleLinkNode(DoubleLinkNode* n,DoubleLinkNode* p,string r,int a):BaseNode(r,a)
{
next=n;
prev=p;
}
DoubleLinkNode(const DoubleLinkNode& obj):BaseNode(obj)
{
next=obj.next;
prev=obj.prev;
}
DoubleLinkNode* getNext();
DoubleLinkNode* getPrev();
virtual void setArabic(int);
virtual void setRoman(string);
void setNext(DoubleLinkNode*);
void setPrev(DoubleLinkNode*);
virtual ~DoubleLinkNode();
protected:
private:
DoubleLinkNode* next;
DoubleLinkNode* prev;
};
#endif // DOUBLELINKNODE_H
LinkedList.cpp
#include "LinkedList.h"
#include <fstream>
#include <iomanip>
#include <iostream>
LinkedList::LinkedList()
{
head=nullptr;
tail=nullptr;//ctor
}
LinkedList::LinkedList(DoubleLinkNode* h)
{
head=h;
setTail();
}
DoubleLinkNode* LinkedList::getHead()
{
return head;
}
DoubleLinkNode* LinkedList::getTail()
{
return tail;
}
void LinkedList::setHead(DoubleLinkNode* &h)
{
head=h;
}
void LinkedList::setTail()
{
tail=head;
while(tail->getNext())
tail=tail->getNext();
}
void LinkedList::print()
{
const int romeNum=15;
const int arabicNum=4;
ofstream file("numbers.txt",ios::app);
if(head)
{
// cout<<left<<setw(romeNum)<<head->getRoman()<<" ";
// cout<<left<<setw(arabicNum)<<head->getArabic()<<" ";
file<<left<<setw(romeNum)<<head->getRoman()<<" ";
file<<left<<setw(arabicNum)<<head->getArabic()<<" ";
head->setPrev(nullptr);
head=head->getNext();
file.close();
print();
}
}
void LinkedList::operator+=(DoubleLinkNode* &d)
{
tail->setNext(d);
d->setPrev(tail);
tail=d;
}
LinkedList& LinkedList::operator--()
{
head=head->getNext();
head->setPrev(nullptr);
return *this;
}
LinkedList& LinkedList::operator--(int)
{
DoubleLinkNode* ptr=tail->getPrev();
ptr->setNext(nullptr);
tail=ptr;
return *this;
}
void LinkedList::destroy()
{
if(head)
{
head->setPrev(nullptr);
head=head->getNext();
destroy();
}
}
LinkedList::~LinkedList()
{
destroy();
//dtor
}
LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "DoubleLinkNode.h"
class LinkedList
{
public:
LinkedList();
LinkedList(DoubleLinkNode*);
DoubleLinkNode* getHead();
DoubleLinkNode* getTail();
void setHead(DoubleLinkNode*&);
void setTail();
void print();
void operator+=(DoubleLinkNode*&);
LinkedList& operator--();
LinkedList& operator--(int);
void destroy();
~LinkedList();
protected:
private:
DoubleLinkNode* head;
DoubleLinkNode* tail;
};
#endif // LINKEDLIST_H
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.