Step 2: In this experiment you will investigate the implementation of a singly-l
ID: 3684464 • Letter: S
Question
Step 2: In this experiment you will investigate the implementation of a singly-linked list with a header node. Enter, save, compile and execute the following program in MSVS. Call the new project “LinkedListExp2” and the program “LinkedList2.cpp”. Answer the questions below:
#include <iostream>
using namespace std;
class LIST_NODE
{
public:
int data; // data element of node
LIST_NODE *next; // pointer element of node
};
class LINKED_LIST_CLASS
{
public:
LINKED_LIST_CLASS(); // default constructor
LINKED_LIST_CLASS(LINKED_LIST_CLASS &); // copy constructor
~LINKED_LIST_CLASS(); // destructor
void Add(int); // mutator
void Print(); // accessor
private:
LIST_NODE *front; // pointer to front of list (header node)
};
LINKED_LIST_CLASS::LINKED_LIST_CLASS()
{
cout << endl << "The default constructor has been called. ";
front = new LIST_NODE;
front->next = 0; //initialize next field to null
front->data = -10000;
}
LINKED_LIST_CLASS::LINKED_LIST_CLASS(LINKED_LIST_CLASS & org)
{
cout << endl << "The copy constructor has been called. ";
front = new LIST_NODE;
front->next = 0;
front->data = -10000;
LIST_NODE *p = org.front->next;
LIST_NODE *back = 0;
while(p!=0)
{
if (back == 0)
{
front->next = new LIST_NODE;
back = front->next;
back->next = 0;
back->data = p->data;
}
else
{
back->next = new LIST_NODE;
back = back->next;
back->data = p->data;
back->next = 0;
}
p=p->next;
}
}
LINKED_LIST_CLASS::~LINKED_LIST_CLASS()
{
cout << endl << "The destructor has been called. ";
while (front->next != 0)
{
LIST_NODE *p = front->next;
front->next = front->next->next;
delete p;
}
delete front;
front = 0;
}
void LINKED_LIST_CLASS::Add(int item)
{
LIST_NODE *p = new LIST_NODE;
p->data = item;
if (front->next== 0) // empty list
{
front->next = p;
p->next = 0;
}
else // list has information and is not empty
{
p->next = front->next;
front->next = p
;
}
}
void LINKED_LIST_CLASS::Print()
{
cout << endl;
for(LIST_NODE *p = front->next; p != 0; p = p->next)
{
cout<<p->data;
if (p->next != 0)
{
cout << "-->";
}
}
cout << endl << endl;
}
int main()
{
LINKED_LIST_CLASS L1;
L1.Add(5);
L1.Add(10);
L1.Add(29);
L1.Print();
LINKED_LIST_CLASS L2 = L1;
L2.Print();
return 0;
}
Question 1:What is the output of the program in Step 2?
Question 2:Please draw the list object, L2, for the program in Step 2.
Question 3:What is the purpose of the back pointer in the copy constructor for the program in Step 2?
Question 4:Is the front of L2 ever equal to 0 or null? Please explain your answer.
Question 5:What are the contents of the header node for L2?
Step 3: In this experiment you will investigate the implementation of a singly-linked list with a header node. Enter, save, compile and execute the following program in MSVS. Call the new project “LinkedListExp3” and the program “LinkedList3.cpp”. Answer the questions below:
#include <iostream>
using namespace std;
class LIST_NODE
{
public:
int data; // data element of node
LIST_NODE *next; // pointer element of node
};
class LINKED_LIST_CLASS
{
public:
LINKED_LIST_CLASS(); // default constructor
LINKED_LIST_CLASS(LINKED_LIST_CLASS &); // copy constructor
~LINKED_LIST_CLASS(); // destructor
void Add(int); // mutator
void Print(); // accessor
LIST_NODE * Search(int); // accessor
void Remove(int); // mutator
bool Is_Empty(); // accessor
private:
LIST_NODE *front; // pointer to front of list
};
LINKED_LIST_CLASS::LINKED_LIST_CLASS()
{
cout << endl << "The default constructor has been called. ";
front = new LIST_NODE;
front->next = 0; // initialize the next field to null
front->data = -10000;
}
LINKED_LIST_CLASS::LINKED_LIST_CLASS(LINKED_LIST_CLASS & org)
{
cout << endl << "The copy constructor has been called. ";
front = new LIST_NODE;
front->next = 0;
front->data = -10000;
LIST_NODE *p = org.front->next;
LIST_NODE *back = 0;
while(p!=0)
{
if (back == 0)
{
front->next = new LIST_NODE;
back = front->next;
back->next = 0;
back->data = p->data;
}
else
{
back->next = new LIST_NODE;
back = back->next;
back->data = p->data;
back->next = 0;
}
p=p->next;
}
}
LINKED_LIST_CLASS::~LINKED_LIST_CLASS()
{
cout << endl << "The destructor has been called. ";
while (front->next != 0)
{
LIST_NODE *p = front->next;
front->next = front->next->next;
delete p;
}
delete front;
front = 0;
}
void LINKED_LIST_CLASS::Add(int item)
{
LIST_NODE *p = new LIST_NODE;
p->data = item;
if (front->next== 0) // empty list
{
front->next = p;
p->next = 0;
}
else // list has information and is not empty
{
p->next = front->next;
front->next = p;
}
}
void LINKED_LIST_CLASS::Print()
{
cout << endl;
for(LIST_NODE *p = front->next; p != 0; p = p->next)
{
cout << p->data;
if (p->next != 0)
{
cout << "-->";
}
}
cout<<endl<<endl;
}
LIST_NODE * LINKED_LIST_CLASS::Search(int key)
{
for(LIST_NODE *p = front->next; p!=0; p=p->next)
{
if (p->data == key)
return p;
}
return 0; // key not found in list
}
void LINKED_LIST_CLASS::Remove(int key)
{
LIST_NODE *p = Search(key);
if (Is_Empty())
{
cout << key << " is not in the list. No removal performed! ";
}
else
{
LIST_NODE *q = front;
while (q->next->data != key)
{
q = q->next;
}
q->next = p->next; // CRITICAL STEP!!!!
delete p;
}
}
bool LINKED_LIST_CLASS::Is_Empty()
{
return front->next == 0;
}
int main()
{
LINKED_LIST_CLASS L1;
L1.Add(5);
L1.Add(10);
L1.Add(29);
L1.Print();
LINKED_LIST_CLASS L2 = L1;
L2.Print();
L1.Remove(10);
L1.Print();
return 0;
}
Question 1:What is the output of the program in Step 3?
Question 2:Referring to the program in Step 3, please explain the order in which nodes are removed from a list.
Question 3:Is the Search() function called by any member functions of the linked list class for the program in Step 3?
Question 4:Please add a statement to the program in Step 3 that tests the Search() function. What did you add?
Question 5:Please add pre-condition, post-conditions and descriptions for each member function of the LINKED_LIST_CLASS. Answer with your new version of the program.
Explanation / Answer
Answer for Question 1:
The output of the given code after excution will print the list
in the order of insrted elements,
29->10->5
Answer for Question 2:
The order of the objects of L2 for the given code:
L1 is assigned to L2 ..so the output is similar to L1
i.e 29 -> 10-> 5
Answer for Question 3:
In Copy constructor back pointer is used swap the links between the nodes
to reverse the list elements
Answer for Question 4:
L2 Pointer is equal is null because after reverse the list of elements
made the front node to last node .
Answer for Question 5:
The contents of L2 header is data and Copy constructor
and print the list..
Second part of the code :
Answer for Question 1:
The order of the elements of the node is ..
29-> 10-> 5
of L1 and L2 objects
Answer for Question 2:
The order of the elements are removed is first 5 and then 10 and then 25
Answer for Question 3:
Yes the remove function will call the search function to find the
elements which is be delete is present in the list or not..
Answer for Question 4:
The search function will actually search the elements of the given list
L1.Search(10);
L2.Search(20);
Answer for Question 5:
The pre condition of the list is empty list and doesn't have the elements
The post condition o the list is delee the element by element from the list by passing element .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.