Can someone PLEASE help me get this linked list to work so I can test the sort a
ID: 3734177 • Letter: C
Question
Can someone PLEASE help me get this linked list to work so I can test the sort and search functions? Can you fix the insertFirstElement and the insert function?
I have also provided the sample file.
Thank you so much.
#include <iostream>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <string>
#include<cstring>
#include <list>
#include <cstdlib>
using namespace std;
struct Node
{
int data;
struct Node *next;
}*head;
// Number struct
struct Number
{
char roman[16];
char arabic[5];
};
// function prototypes
typedef Number* NumberPtr;
int convertRomanToArabic(string);
string convertArabicToRoman(int);
void sort();
void linearSearch(struct Number, int);
void insertFirstElement(NumberPtr&, char, char);
void insert(NumberPtr&, char, char);
// main function
int main()
{
// open the file to read
ifstream inFile;
ofstream outFile;
inFile.open("numbers.txt", ios::in);
// exit from the program if the input file does not exist
if (inFile.fail())
{
cout << "Input file could not be opened." << endl;
exit(1);
}
// declare the required variables
list<Number> lst;
Number num;
string str;
int si; // space index
int count = 0;
int choice;
// read data from the file
inFile.seekg(0); // go to the first line
while (!inFile.eof())
{
num.roman[15] = '';
num.arabic[4] = '';
inFile.read((char *)&num, sizeof(Number));
if (num.roman[0] == ' ')
{
str = num.arabic;
// cout<<str<<endl;
si = str.find(' ');
str = str.substr(0, si);
string rom = convertArabicToRoman(atoi(str.c_str()));
strcpy(num.roman, rom.c_str());
}
else
{
str = num.roman;
// cout<<str<<endl;
si = str.find(' ');
str = str.substr(0, si);
for(int i=0;i<si;i++){
num.roman[i] = str[i];
}
for(int i=si;i<15;i++){
num.roman[i] ='';
}
int arab = convertRomanToArabic(str);
stringstream ss;
ss << arab;
string s = ss.str();
strcpy(num.arabic, s.c_str());
cout<<num.arabic<<endl;
}
lst.push_back(num);
count++;
// inFile.read((char *)&num, sizeof(Number));
}
// close the file
inFile.close();
// open the file to write
outFile.open("output.txt", ios::out);
// write data to the file
list<Number>::iterator itr = lst.begin();
while (itr != lst.end())
{
outFile << left << setw(15) << (*itr).roman << " " << setw(4) << (*itr).arabic;
//outFile <<(*itr).roman;
itr++;
if(itr != lst.end())
outFile << endl;
}
// close the file
outFile.close();
cout<<"1. Search"<<endl;
cout<<"2. Sort"<<endl;
cout<<"3. Exit"<<endl;
cin >> choice;
if (choice == 1)
{
linearSearch(num,count);
}
else if (choice == 2)
{
sort();
}
else if (choice == 3)
{
return 0;
}
else
{
cout << "Invalid option" << endl;
}
char rom;
char arab;
NumberPtr head = new Number;
while (inFile >> num.roman >> num.arabic)
{
cout << num.roman << endl;
cout << num.arabic << endl;
insertFirstElement (Number*, rom, arab);
}
return 0;
}
//function that converts roman numerals to arabic numbers
int convertRomanToArabic(string str)
{
int arabic = 0;
char ch; // current character
char nch; // next character
if (str.length() == 0)
{
return 0;
}
for (unsigned int i = 0; i < str.length() - 1; i++)
{
ch = str[i];
nch = str[i + 1];
if (ch == 'M')
arabic += 1000;
else if (ch == 'D')
arabic += 500;
else if (ch == 'C' && (nch == 'D' || nch == 'M'))
arabic -= 100;
else if (ch == 'C')
arabic += 100;
else if (ch == 'L')
arabic += 50;
else if (ch == 'X' && (nch == 'L' || nch == 'C'))
arabic -= 10;
else if (ch == 'X')
arabic += 10;
else if (ch == 'V')
arabic += 5;
else if (ch == 'I' && (nch == 'V' || nch == 'X'))
arabic -= 1;
else if (ch == 'I')
arabic += 1;
else
{
cout << "Invalid roman numeral." << ch << endl;
exit(1);
}
}
ch = str[str.length() - 1];
if (ch == 'M')
arabic += 1000;
else if (ch == 'D')
arabic += 500;
else if (ch == 'C')
arabic += 100;
else if (ch == 'L')
arabic += 50;
else if (ch == 'X')
arabic += 10;
else if (ch == 'V')
arabic += 5;
else if (ch == 'I')
arabic += 1;
else
{
cout << "Invalid roman numeral." << ch << endl;
exit(1);
}
return arabic;
}
//function that coverts arabic numbers to roman numerals
string convertArabicToRoman(int arabic)
{
string roman;
int curr;
if (arabic >= 5000)
{
curr = arabic / 1000;
for (int i = 0; i < curr; i++)
{
roman += 'M';
}
arabic = arabic % 1000;
}
if (arabic >= 100)
{
curr = arabic / 100;
if (curr == 9)
{
roman += "CM";
}
else if (curr >= 5)
{
roman += 'D';
for (int i = 0; i < curr - 5; i++)
{
roman += 'C';
}
}
else if (curr == 4)
{
roman += "CD";
}
else if (curr >= 1)
{
for (int i = 0; i < curr; i++)
{
roman += 'C';
}
}
arabic = arabic % 100;
}
if (arabic >= 10)
{
curr = arabic / 10;
if (curr == 9)
{
roman += "XC";
}
else if (curr >= 5)
{
roman += 'L';
for (int i = 0; i < curr - 5; i++)
{
roman += 'X';
}
}
else if (curr == 4)
{
roman += "XL";
}
else if (curr >= 1)
{
for (int i = 0; i < curr; i++)
{
roman += 'X';
}
}
arabic = arabic % 10;
}
if (arabic >= 1)
{
curr = arabic;
if (curr == 9)
{
roman += "IX";
}
else if (curr >= 5)
{
roman += 'V';
for (int i = 0; i < curr - 5; i++)
{
roman += 'I';
}
}
else if (curr == 4)
{
roman += "IV";
}
else if (curr >= 1)
{
for (int i = 0; i < curr; i++)
{
roman += 'I';
}
}
}
return roman;
}
void insertFirstElement(int number, struct Node **head)
{
struct Node *newNode = new Node;
newNode->data = number;
newNode->next = NULL;
if(*head == NULL)
{
*head = newNode;
}
else
{
struct Node *current = *head;
while(current->next != NULL)
{
current = current->next;
}
current->next = newNode;
}
}
void insert(Node **head)
{
if(head == NULL)
return;
Node* temp = *head;
*head = temp->next;
delete temp;
}
void sort()
{
struct Node *ptr, *s, *prev;
if (head == NULL)
{
cout << "List is empty" << endl;
return;
}
ptr = head;
while ( ptr && ptr->next ) // check preset and next
{
if ( ptr->data > ptr->next->data ) // check next element is greater than or not
{
if ( prev == NULL ) // for first condition, when head needs to change
{
s = ptr->next; // save next
ptr->next = ptr->next->next; // connect next to next next
s->next = ptr; // connect previous
head = s; // change the head
ptr = head; // reset the ptr
}
else if ( prev && ptr->next->next ) // when swap is not for first element
{
s = ptr->next;
ptr->next = ptr->next->next;
s->next = ptr;
prev->next = s;
ptr = head;
prev = NULL; // reset prev
}
else if ( prev && ptr->next ) // condition for last elements
{
s = ptr->next;
ptr->next = NULL; // last element connect to null
s->next = ptr;
prev->next = s;
ptr = head;
prev = NULL;
}
}
else // executes first elements need not to be swap
{
prev = ptr;
ptr = ptr->next;
}
}
}
void linearSearch(Number num, int size)
{
int value, position = 0;
cout << "Enter the value to be searched: ";
cin >> value;
struct Node *s;
s = head;
while (s != NULL)
{
position++;
if (s->data == value)
{
cout<<"Element "<<value<<" is found at position "<<position<<endl;
return;
}
s = s->next;
}
cout<<"Element "<<value<<" not found"<<endl;
}
Sample Input: numbers.txt
Explanation / Answer
Here you have to use malloc to allocate the memory. Because the way you are doing will de-allocate memory as soon as function exits.
void insertFirstElement(int number, struct Node **head)
{
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = number;
newNode->next = NULL;
if(*head == NULL)
{
*head = newNode;
}
else
{
struct Node *current = *head;
while(current->next != NULL)
{
current = current->next;
}
current->next = newNode;
}
}
void insert(Node **head)
{
if(head == NULL)
return;
struct Node* temp = (struct Node*) malloc(sizeof(struct Node));
*temp = *head;
*head = temp->next;
delete temp;
}
THUMBS UP IF YOU ARE SATISFIED WITH ANSWER OTHERWISE REPLY WITH YOUR CONCERN.