C++ Suggested point values are marked in parentheses. In all questions that invo
ID: 3716055 • Letter: C
Question
C++
Suggested point values are marked in parentheses. In all questions that involve writing methods, be sure to think of whether method arguments and return values should be references to const data, whether or not the method should be const, etc.
The next two questions involve the following data types:
Also assume that current is a pointer to a node in the middle of a singly linked list, and that newNode is a pointer to a newly allocated node.
(2) What is recursion?
(4) Write a code fragment (not a complete method) that will insert newNode at the front of a non-empty list.
(4) Write a code fragment that will insert newNode at the rear of a non-empty list.
(4) Write a code fragment that will insert newNode into the list after the node pointed to by current.
Explanation / Answer
2) Recursion is a process in which a function calls itself. Since function calls itself ,,it goes into infinite loop if condition is not there to return from recursive function
//below example shows recursive function to print numbers upto n in
void print(int n)
{
if (n == 0)
{
return;
}
else
{
cout << n << endl;
print(n - 1);
}
}
Above recursive function has terminating statement which is if n == 0 ,,returns from recursive function
4) insert at front
void insert_front(T val)
{
Node<T> *cur, *newNode;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
}
else
{
cur = head;
head = newNode;
head->next = cur;
while (cur->next != NULL)
{
cur = cur->next;
}
tail = cur;
}
}
4) insert at rear
void insert_rear(T val)
{
Node<T> *newNode;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
if (tail == NULL)
{
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
}
4) insert after some node
void insert_After(T afterVal,T val)
{
Node<T> *cur = head,*newNode,*tmp;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
while (cur->data!= afterVal)
{
cur = cur->next;
}
tmp = cur->next;
cur->next = newNode;
newNode->next = tmp;
}
---------------------------------------------------------------------------------
//complete program with output
#include<iostream>
#include<string>
using namespace std;
template <class T>
struct Node
{
T data;
Node<T>* next;
};
template <class T>
class List
{
private:
Node<T>* head;
Node<T>* tail;
public:
List()
{
head = NULL;
tail = NULL;
}
void insert_front(T val)
{
Node<T> *cur, *newNode;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
}
else
{
cur = head;
head = newNode;
head->next = cur;
while (cur->next != NULL)
{
cur = cur->next;
}
tail = cur;
}
}
void insert_rear(T val)
{
Node<T> *newNode;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
if (tail == NULL)
{
tail = newNode;
}
else
{
tail->next = newNode;
tail = newNode;
}
}
void insert_After(T afterVal,T val)
{
Node<T> *cur = head,*newNode,*tmp;
newNode = new Node<T>;
newNode->data = val;
newNode->next = NULL;
while (cur->data!= afterVal)
{
cur = cur->next;
}
tmp = cur->next;
cur->next = newNode;
newNode->next = tmp;
}
void print()
{
Node<T> *cur = head;
while (cur != NULL)
{
cout << cur->data << " ";
cur = cur->next;
}
cout << endl;
}
};
int main()
{
List<int> lst;
//insert at front
lst.insert_front(2);
lst.insert_front(3);
lst.insert_front(4);
lst.insert_front(1);
//print list after insert at front
cout << "After inserting 4 values at front: " << endl;
lst.print();
//inser at rear
lst.insert_rear(5);
lst.insert_rear(6);
lst.insert_rear(7);
lst.insert_rear(8);
cout << "After inserting 4 values at rear: " << endl;
lst.print();
//insert after 6
cout << "Insert value 10 after node with val 6: " << endl;
lst.insert_After(6, 10);
lst.print();
cout << "Insert value 11 after node with val 10: " << endl;
lst.insert_After(10, 11);
lst.print();
//now try mixed insertion at front , rear and after
lst.insert_front(12);
cout << "After inserting value 12 at front: " << endl;
lst.print();
lst.insert_rear(13);
cout << "After inserting value 13 at rear: " << endl;
lst.print();
cout << "Insert value 14 after node with val 2: " << endl;
lst.insert_After(2,14);
lst.print();
}
/*
After inserting 4 values at front:
1 4 3 2
After inserting 4 values at rear:
1 4 3 2 5 6 7 8
Insert value 10 after node with val 6:
1 4 3 2 5 6 10 7 8
Insert value 11 after node with val 10:
1 4 3 2 5 6 10 11 7 8
After inserting value 12 at front:
12 1 4 3 2 5 6 10 11 7 8
After inserting value 13 at rear:
12 1 4 3 2 5 6 10 11 7 8 13
Insert value 14 after node with val 2:
12 1 4 3 2 14 5 6 10 11 7 8 13
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.