Implement a linked list that maintains a list integers in sorted order. Thus, if
ID: 3790512 • Letter: I
Question
Implement a linked list that maintains a list integers in sorted order. Thus, if the list initially contains 2, 5 and 8, and we insert 1, 3, and 10, then l will be inserted at the start of the list, 3 will be inserted between 2 and 5, and 10 will be inserted at the end. This program takes a file name as argument from the command line. The file will have a number of lines. Each line contains a character (either 'I' or 'd') followed by a tab character and an integer number. For each of the line that starts with 'i', your program should insert the number in the linked list in sorted order if it is not already there. Your program should not insert any duplicate values. If the line starts with a 'd', your program should delete the value if it is present in the linked list. Your program should silently ignore it if the requested value is not present in the linked list. At the end of the execution, your program should print all the values of the linked list in sorted order. The values should be in a single line separated by tabs. There should be no leading or trailing white space in the output. Your program should print "error (and nothing else) if the file does not exist or it contains lines with improper structure. Your program should print a blank line if the input file is empty or the resulting linked list has no nodes. Let's assume we have 3 text files with the following contents file1.txt is empty and file2 txt i 10 i 12 d 10 i 5 file3 .txt d 7 i 10 i 5 i 10 d 10 ./third file1.txt ./third file2 .txt 5 12 ./third file3 txt 5/third file4.txt errorExplanation / Answer
C++ code:
#include <bits/stdc++.h>
using namespace std;
class node
{
public:
int data;
node* next = NULL;
};
int main()
{
cout << "Please enter filename" << endl;
string filename;
cin >> filename;
node* head = new node();
head = NULL;
node* tmp = new node();
string line;
ifstream myfile (filename.c_str());
// ifstream myfile ("input.txt");
if (myfile.is_open())
{
while ( getline (myfile,line) )
{
string buf; // Have a buffer string
stringstream ss(line); // Insert the string into a stream
vector<string> tokens; // Create vector to hold our words
while (ss >> buf)
tokens.push_back(buf);
string inst = tokens[0].c_str() ;
int v = atoi(tokens[1].c_str() ) ;
if(inst == "i")
{
tmp = head;
node* newnode = new node();
newnode->data = v;
if (tmp == NULL || tmp->data >= v)
{
newnode->next = tmp;
head = newnode;
}
else
{
/* Locate the node before the point of insertion */
tmp = head;
while (tmp->next!=NULL && tmp->next->data < v)
{
tmp = tmp->next;
}
if(tmp->next ==NULL)
{
newnode->next = tmp->next;
tmp->next = newnode;
}
else if(tmp->next->data != v)
{
newnode->next = tmp->next;
tmp->next = newnode;
}
}
}
else
{
tmp = head;
if(tmp == NULL)
{
;
}
else if(tmp->data == v)
{
head = head->next;
}
else
{
while (tmp != NULL && tmp->next!=NULL && tmp->next->data != v)
{
tmp = tmp->next;
}
if(tmp->next ==NULL || tmp == NULL)
{
;
}
else
{
tmp->next = (tmp->next)->next;
}
}
}
}
tmp = head;
if(tmp == NULL)
{
cout << "error" << endl;
}
while(tmp != NULL)
{
cout << tmp->data << " ";
tmp = tmp->next;
}
cout << " ";
myfile.close();
}
else
{
cout << "Unable to open file" << endl;
exit(1);
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.