In C++ using my code below, I am trying to add two functions cut Middle (cuts/sp
ID: 3745741 • Letter: I
Question
In C++ using my code below, I am trying to add two functions cutMiddle (cuts/splits the list down the middle into two equal sized list) and cutAt (cuts/splits the list at a given item/node into two list). Please include comments in the code to better help me understand.
CODE:
#include <iostream>
using namespace std;
struct node {
int number;
node* next;
};
bool isNull(node*& first);
int menu();
void insertFirst(node*& first, node*& last, int number);
void insert(node*& first, node*& last, int number);
void remove(node*& first, node*& last);
void printList(node* current);
bool isNull(node*& first)
{
// if the list is empty
if (first == NULL)
return true;
// if the list is not empty
else
return false;
}
int menu()
{
int selection;
cout << "Menu Selection ";
cout << "1. Add an item. ";
cout << "2. Remove an item. ";
cout << "3. Show list. ";
cout << "4. Exit system. ";
cin >> selection;
return selection;
}
int getLength(node* first)
{
node* trav = first;
int count = 0;
// loop untill list ends
while (trav)
{
count++;
// go to next node
trav = trav->next;
}
return count;
}
void insertFirst(node*& first, node*& last, int number)
{
// create a new node
node* temp = new node;
// The linked list current state is NULL (empty), A node with a new number should be the only one
// and be first in the list.
if (first == NULL)
temp->number = 1;
else
temp->number = number;
// make temp point to current first node of the list
temp->next = first;
// make temp as the new first node
first = temp;
// if the list was empty
if (last == NULL)
last = temp;
}
// check if x is the smaller than smallest number in list
bool ifSmallest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the smallest
if (trav->number < x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
// check if x is the larger than largest number in list
bool ifLargest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the largest
if (trav->number > x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
void insert(node*& first, node*& last, int number)
{
if (isNull(first))
insertFirst(first, last, number);
// if number is smaller than the smallest number in the list
else if (ifSmallest(first, number))
insertFirst(first, last, number);
// if number is larger than the largest number in the list
// node goes at the last of the list
else if (ifLargest(first, number))
{
node* temp = new node;
temp->number = number;
temp->next = NULL;
last->next = temp;
last = temp;
}
// The new number should be inserted inserted in the middle of the link list.
else {
// get the length of the list
int len = getLength(first);
node* trav = first;
int i;
// go to the node before the middle node
for (i = 0; i < len - 2; i++)
trav = trav->next;
// adjust the pointer
node* temp = new node;
temp->number = number;
temp->next = trav->next;
trav->next = temp;
}
}
void remove(node*& first, node*& last)
{
if (isNull(first))
cout << "The list is already empty. ";
else if (first == last)
{
delete first;
first == NULL;
last == NULL;
}
else {
node* temp = first;
first = first->next;
delete temp;
}
}
void printList(node* current)
{
if (isNull(current))
cout << "The list is empty ";
else {
cout << "The list contatins: ";
while (current != NULL)
{
cout << current->number << endl;
current = current->next;
}
}
}
int main()
{
node* first = NULL;
node* last = NULL;
int selection;
int number;
do {
selection = menu();
switch (selection)
{
case 1:
cout << "Please enter a selection number: ";
cin >> number;
insert(first, last, number);
break;
case 2:
remove(first, last);
break;
case 3:
printList(first);
break;
case 4:
exit(0);
default:
cout << "System exit ";
}
} while (selection != '4');
return 0;
}
Explanation / Answer
#include <iostream>
using namespace std;
struct node {
int number;
node* next;
};
bool isNull(node*& first);
int menu();
void insertFirst(node*& first, node*& last, int number);
void insert(node*& first, node*& last, int number);
void remove(node*& first, node*& last);
void printList(node* current);
bool isNull(node*& first)
{
// if the list is empty
if (first == NULL)
return true;
// if the list is not empty
else
return false;
}
int menu()
{
int selection;
cout << "Menu Selection ";
cout << "1. Add an item. ";
cout << "2. Remove an item. ";
cout << "3. Show list. ";
cout<< "4. cut Middle. ";
cout<< "5. cut At. ";
cout << "6. Exit system. ";
cin >> selection;
return selection;
}
int getLength(node* first)
{
node* trav = first;
int count = 0;
// loop untill list ends
while (trav)
{
count++;
// go to next node
trav = trav->next;
}
return count;
}
void insertFirst(node*& first, node*& last, int number)
{
// create a new node
node* temp = new node;
// The linked list current state is NULL (empty), A node with a new number should be the only one
// and be first in the list.
if (first == NULL)
temp->number = 1;
else
temp->number = number;
// make temp point to current first node of the list
temp->next = first;
// make temp as the new first node
first = temp;
// if the list was empty
if (last == NULL)
last = temp;
}
// check if x is the smaller than smallest number in list
bool ifSmallest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the smallest
if (trav->number < x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
// check if x is the larger than largest number in list
bool ifLargest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the largest
if (trav->number > x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
void insert(node*& first, node*& last, int number)
{
if (isNull(first))
insertFirst(first, last, number);
// if number is smaller than the smallest number in the list
else if (ifSmallest(first, number))
insertFirst(first, last, number);
// if number is larger than the largest number in the list
// node goes at the last of the list
else if (ifLargest(first, number))
{
node* temp = new node;
temp->number = number;
temp->next = NULL;
last->next = temp;
last = temp;
}
// The new number should be inserted inserted in the middle of the link list.
else {
// get the length of the list
int len = getLength(first);
node* trav = first;
int i;
// go to the node before the middle node
for (i = 0; i < len - 2; i++)
trav = trav->next;
// adjust the pointer
node* temp = new node;
temp->number = number;
temp->next = trav->next;
trav->next = temp;
}
}
void remove(node*& first, node*& last)
{
if (isNull(first))
cout << "The list is already empty. ";
else if (first == last)
{
delete first;
first == NULL;
last == NULL;
}
else {
node* temp = first;
first = first->next;
delete temp;
}
}
void printList(node* current)
{
if (isNull(current))
cout << "The list is empty ";
else {
cout << "The list contatins: ";
while (current != NULL)
{
cout << current->number << endl;
current = current->next;
}
}
}
node *cutMiddle(node** first){ //takes head pointer along with its reference
node *head=NULL,*temp=(*first);
int length=getLength(*first)/2; //takes half of the length of list
while(length){
if(length==1){ //if the element is second last one
head=(*first)->next;
(*first)->next=NULL;
}else
*first = (*first)->next;
length--; //decrements the length
}
*first =temp;
return head;
}
node *cutAt(node ** first,int item){ //takes head pointer along with its reference
node *head=NULL,*temp=(*first);
if((*first)->number==item){ //for checking whether the first node has the item user has entered
head=(*first);
*first=NULL;
} else { //for checking whether the number is in the list or not
while((*first)->next!=NULL){
if(item==(*first)->number){
head=(*first)->next;
(*first)->next=NULL;
}else
*first = (*first)->next;
}
if((*first)->number==item){ //if the number is the last element in the list
head=NULL;
}
*first =temp;
}
return head;
}
int main()
{
node* first = NULL;
node* last = NULL;
node* head = NULL;
int selection;
int number,item;
do {
selection = menu();
switch (selection)
{
case 1:
cout << "Please enter a selection number: ";
cin >> number;
insert(first, last, number);
break;
case 2:
remove(first, last);
break;
case 3:
printList(first);
break;
case 4:
head =cutMiddle(&first);
printList(first);
printList(head);
break;
case 5:
cout<<"Enter an item :";
cin>>item;
head =cutAt(&first,item);
printList(first);
printList(head);
case 6:
//exit(0);
default:
cout << "System exit ";
}
} while (selection != '4');
return 0;
}