requires you to implement several methods for the Linked List class. I give you
ID: 3551399 • Letter: R
Question
requires you to implement several methods for the Linked List class. I give you a main program that serves as a tester for the Linked List class. The linked List class consists of two files - Node.cpp and Node.h. You are NOT to modify the main program or the Node.h . You are only to modify the Node.cpp and Node.h. You will add the prototypes of the new functions into the .h file and add the code bodies to the .cpp file.
Please send the Node.Cpp and Node.h to the answer~~~ thank you. i reallt confuse with this problem.
in additon, the main.cpp is '
Explanation / Answer
/* Add bool isPresent (Node *head, string data);
in your Node.h
This is working code
DropBox link all file : https://www.dropbox.com/sh/jrnk77e0nqx2sxp/83iWc_h9HJ
*/
#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
using namespace std;
#include "Node.h"
void insertAtFront( Node * &list, string data )
{
Node * tmp = new Node;
tmp->data = data;
tmp->next = list;
list = tmp;
}
void insertAtTail( Node * &list, string data ) //
{
if (!list)
insertAtFront( list, data );
else
insertAtTail( list->next, data );
}
void removeAtFront( Node * &list )
{
Node * deadNode = list;
list = deadNode->next;
delete deadNode;
}
void removeNode( Node * &list, string data )
{ // remove the node with this data value in it
if ( !list) return;
if ( list->data == data )
removeAtFront( list );
else
removeNode( list->next, data );
}
void removeAtTail( Node * &list )
{
if ( !list) return;
if ( !list->next )
removeAtFront( list );
else
removeAtTail( list->next );
}
void printList( Node * list )
{
Node * cur = list;
while (cur)
{
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
// FUNCTIONS
void deleteList(Node * &list){
while(NULL!=list){
removeAtFront(list);
}
}
void insertInOrder( Node * &list, string data ){
Node * current;
/* Special case for the head end */
if (list == NULL || (list)->data >= data)
{
insertAtFront(list,data);
}
else
{
/* Locate the node before the point of insertion */
current = list;
while (current->next!=NULL && current->next->data < data)
{
current = current->next;
}
Node * tmp = new Node;
tmp->data = data;
tmp->next = current->next;
current->next = tmp;
}
}
Node * reversal( Node * list){
if (NULL == list)
{ // Empty list
Node * t=new Node();
return t;
}
Node* head = new Node();
string x=list->data;
head->data=x;
head->next=list->next;
Node* prev = NULL;
Node* current = new Node();
string s=list->data;
current->data=s;
list=list->next;
while (list != NULL)
{
Node* n=new Node();
s=list->data;
n->data = s;
n->next=current;
current->next = prev;
prev = current;
current = n;
list=list->next;
}
// current->next = prev;
// for deep reversal
list=head;
return current;
}
bool equals( Node * list1, Node * list2 ){
bool f=false;
bool t=true;
while(1)
{
/* base case */
if(list1 == NULL && list2 == NULL)
{ return t; }
if(list1 == NULL && list2 != NULL)
{ return f; }
if(list1 != NULL && list2 == NULL)
{ return f; }
if(list1->data != list2->data)
{ return f; }
/* If we reach here, then a and b are not NULL and their
data is same, so move to next nodes in both lists */
list1 = list1->next;
list2 =list2->next;
}
}
Node * listCopy( Node * list ){ // returns a ptr to deep copy of incoming list
Node* head = new Node();
string x=list->data;
head->data=x;
head->next=list->next;
if (NULL == list)
{ // Empty list
Node * t=NULL;
return t;
}
Node * headPtr=new Node();
Node * tailPtr = new Node();
string s=list->data;
headPtr->data=s;
headPtr->next=NULL;
tailPtr = headPtr;
list = list->next;
while (list != NULL)
{
string currentData = list->data;
insertAtTail(tailPtr, currentData);
list = list->next;
}
list=head;
return headPtr;
}
Node * setUnion( Node * list1, Node * list2 ){ // returns a new list that is union of the two lists
Node *result = NULL;
Node *t1 = list1;
Node *t2 = list2;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{
insertInOrder(result,t1->data);
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
while (t2 != NULL)
{
if (!isPresent(result, t2->data))
insertInOrder(result, t2->data);
t2 = t2->next;
}
return result;
}
Node * setIntersect( Node * list1, Node * list2 ){ // returns a new list that is intersections of the two lists
Node *result = NULL;
Node *t1 = list1;
// Traverse list1 and search each element of it in list2. If the element
// is present in list 2, then insert the element to result
while (t1 != NULL)
{
if (isPresent(list2, t1->data))
insertInOrder(result, t1->data);
t1 = t1->next;
}
return result;
}
Node * setDiff( Node * list1, Node * list2 ){ // returns a new list that is list1 - list2
Node *result = NULL;
Node *t1 = list1;
Node *t2 = list2;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{ if (!isPresent(list2, t1->data)){
insertInOrder(result,t1->data);
}
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
/* while (t2 != NULL)
{
if (!isPresent(list1, t2->data))
insertAtTail(&result, t2->data);
t2 = t2->next;
} */
return result;
}
Node * setXor( Node * list1, Node * list2 ){ // returns a new list that is xor of the two lists
Node *result = NULL;
Node *t1 = list1;
Node *t2 = list2;
// Insert all elements of list1 to the result list
while (t1 != NULL)
{ if (!isPresent(list2, t1->data)){
insertInOrder(result,t1->data);
}
t1 = t1->next;
}
// Insert those elements of list2 which are not present in result list
while (t2 != NULL)
{
if (!isPresent(list1, t2->data))
insertInOrder(result, t2->data);
t2 = t2->next;
}
return result;
}
/* A utilty function that returns true if data is present in linked list
else return false */
bool isPresent (Node *head, string data)
{
Node *t = head;
while (t != NULL)
{
if (t->data == data)
return 1;
t = t->next;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.