Please help me with this c++ code , thank you in advance :) (1) Implement the co
ID: 3889737 • Letter: P
Question
Please help me with this c++ code , thank you in advance :)
(1) Implement the concepts of a union, and difference as defined noted in Chapter 1 questions 6, and 8 using a linked list. You should not use arrays, dynamic arrays or the STL vector or STL list classes.
You will be linking a series of nodes together to implement a single linked list class. Define a Node as a struct that holds a character (like they did in the book) and a pointer to another Node:
struct Node {
char data;
Node* next;
};
Then define a LinkedList class which has (at a minimum) these member functions:
bool insertAtFront();
bool insertBeforePosition(int index);
bool insertAtBack();
bool deleteAtFront();
bool deleteBeforePosition(int index);
bool deleteAtBack();
Implement each of these functions to provide the correct functionality. These functions return true if successful in inserting or deleting, otherwise they return false (indicating the operation was not successful).
Finally, create an overloaded + operator to handle the Union of two linked lists and an overloaded - operator to handle the Difference of two linked lists.
Because we are dealing with pointers you should have both a LinkedList Constructor and Destructor. Remember that you do not directly call a Constructor or Destructor Function. The Destructor is automatically called when the variable loses scope or the program ends. Remember, that we are dealing with not just one dynamically allocated Node (with the new operator), but many, so you will have to start at the head of the list and go until the Node points to nullptr. Then keep deleting the previous Node pointer until there are no Nodes left to delete.
(2) To verify your set class, write a main function that takes two lines of characters from the input file input.txt and store each line of characters into two separate linked lists. Then using these two lists, perform the Union and set Difference of the characters from the file, and print the results to the console.
(3) Please also complete an asymptotic (Big O) analysis of your insertAtFront() and insertAtBack() member functions. Place this in a file called analysis.txt.
Explanation / Answer
As far as complexity:
for insertAtFront() its O(1) since it does not depend on the size of the list. It just replaces the start of the list. Hence it is O(1) and independent of the size of list.
for insertAtBack(), its O(n) since it depends on the number of elements in the list. It should traverse till end of list and then insert. So it depends on list size and hence O(n).
#include <iostream>
#include <fstream>
using namespace std;
struct Node
{
char data;
Node *next;
};
class LinkedList
{
Node *start;
public:
LinkedList()
{
start=NULL;
}
~LinkedList()
{
if(start!=NULL)
{
Node *p,*q;
p=start;
while(p!=NULL)
{
q=p->next;
delete p;
p=q;
}
}
}
bool insertAtFront(Node *p)
{
if(p==NULL)
return false;
if(start==NULL)
start=p;
else
{
p->next=start;
start=p;
}
return true;
}
bool insertBeforePosition(int index,Node *p)
{
if(start==NULL || p==NULL)
{
return false;
}
else
{
Node *idxNode=start,*prev=NULL;
int i=1;
while(i<index && idxNode!=NULL)
{
prev=idxNode;
idxNode=idxNode->next;
i++;
}
if(idxNode==NULL)
{
return false;
}
else
{
p->next=idxNode;
if(prev==NULL)
start=p;
else
prev->next=p;
return true;
}
}
}
bool insertAtBack(Node *p)
{
if(p==NULL)
return false;
if(start==NULL)
start=p;
else
{
Node *temp=start;
while(temp->next!=NULL)
temp=temp->next;
temp->next=p;
}
return true;
}
bool deleteAtFront()
{
if(start==NULL)
return false;
else
{
Node *p=start;
start=p->next;
delete p;
}
return true;
}
bool deleteAtBack()
{
if(start==NULL)
return false;
else
{
Node *last=start,*lastButOne=NULL;
while(last->next!=NULL)
{
lastButOne=last;
last=last->next;
}
if(lastButOne==NULL)
start=NULL;
else
{
lastButOne->next=NULL;
delete last;
}
}
return true;
}
bool deleteBeforePosition(int index)
{
if(start==NULL || index ==1)
return false;
else
{
Node *prev=start,*idxNode=prev->next,*q=NULL;
int i=1;
while(i<index-1)
{
q=prev;
prev=idxNode;
idxNode=idxNode->next;
i++;
}
if(prev==start)
{
start=idxNode;
}
else
{
if(q!=NULL)
{
q->next=idxNode;
}
}
delete prev;
}
return true;
}
LinkedList operator +(LinkedList &list)
{
LinkedList newList;
Node *p=start,temp;
while(p!=NULL)
{
if(newList.findData(p->data)==-1)
{
Node *q=new Node();
q->data=p->data;
q->next=NULL;
newList.insertAtBack(q);
}
p=p->next;
}
p=list.start;
while(p!=NULL)
{
if(newList.findData(p->data)==-1)
{
Node *q=new Node();
q->data=p->data;
q->next=NULL;
newList.insertAtBack(q);
}
p=p->next;
}
return newList;
}
int findData(char data)
{
if(start==NULL)
return -1;
else
{
Node *q=start;
int index=1;
while(q!=NULL && q->data!=data)
{
q=q->next;
index++;
}
if(q==NULL)
return -1;
else
return index;
}
}
LinkedList operator -( LinkedList &list)
{
LinkedList newList;
Node *p=start,temp;
while(p!=NULL)
{
if(list.findData(p->data)==-1)
{
Node *q=new Node();
q->data=p->data;
q->next=NULL;
newList.insertAtBack(q);
}
p=p->next;
}
return newList;
}
void display()
{
Node *p=start;
cout<<" ";
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<" ";
}
};
int main()
{
ifstream file;
char buffer[256];
int line =0;
LinkedList list[2];
file.open("c:\test\input.txt");
if(!file.is_open())
{
cout<<"Error opening file !";
return(1);
}
while(!file.eof() && line<2)
{
file.getline(buffer,256);
for(int i=0;buffer[i]!='';i++)
{
Node *p=new Node();
p->data=buffer[i];
p->next=NULL;
list[line].insertAtBack(p);
}
line++;
}
cout<<"List 1:";
list[0].display();
cout<<" List 2:";
list[1].display();
LinkedList sum=list[0]+list[1],diff=list[0]-list[1];
cout<<" List 1 + List 2:";
sum.display();
cout<<" List 1 - List 2:";
diff.display();
All the functions are working as intended.
Node *p=new Node();
p->data='Z';
p->next=NULL;
list[0].insertAtFront(p);
list[1].deleteAtFront();
list[1].deleteAtBack();
p=new Node();
p->data='Y';
p->next=NULL;
list[0].insertBeforePosition(2,p);
list[1].deleteBeforePosition(3);
list[0].display();
list[1].display();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.