In C++ Write a program that will read in a sequence of non-negative integers, te
ID: 3715186 • Letter: I
Question
In C++ Write a program that will read in a sequence of non-negative integers, terminated by ?1 and store them in a (singly) linked list. You are to insert the links into the list in such a way that the list is sorted at all times from smallest to largest. You are to then go through the list and remove all of the even integers. You should output the list after inputting all of the
integers and then after removing all of the even integers. You should test your program with the following data.
7, 10, 5, 7, 9, 4, 2, 6, 10, 12, 3, 12, 5, 5, 2, 7, 2, 12, -1.
Explanation / Answer
// File Name: SortedLinkedList
// Inserts the nodes in sorted order and also deletes the even number nodes
#include <stdlib.h>
#include <iostream>
using namespace std;
// Creates a structure for node
struct Node
{
// To store data
int value;
// Pointer to next node
struct Node* next;
};// End of structure
/*
* Function to insert a new node in a list.
* struct Node** headRef -> pointer to the head
* struct Node* newNode -> new node to insert
*/
void sortedInsert(struct Node** headRef, struct Node* newNode)
{
// Declares a temporary node to keep track of current node
struct Node* currentNode;
// Checks if head is null or head value is greater than or equals to the new node value
if (*headRef == NULL || (*headRef) -> value >= newNode -> value)
{
// new node points to the head node
newNode -> next = *headRef;
// head is now the new node
*headRef = newNode;
}// End of if condition
// Otherwise, locate the node before the point of insertion
else
{
// Current node is pointing to head
currentNode = *headRef;
// Loops while current node next is not null (end of linked list)
// and current node next node value is less than the new node value
while(currentNode -> next != NULL && currentNode -> next -> value < newNode -> value)
// Move to next node
currentNode = currentNode -> next;
// New node next is pointing to current node next
newNode -> next = currentNode -> next;
// Current node next is pointing to new node
currentNode -> next = newNode;
}// End of else
}// End of function
// Function to create a new node and returns it
struct Node *createNewNode(int data)
{
// Dynamically allocates memory to newNode
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
// Assigns parameter data to node value
newNode -> value = data;
// new node next is assigned null
newNode -> next = NULL;
// Returns new node
return newNode;
}// End of function
// Function to display linked list
void displayLinkedList(struct Node *headRef)
{
// Creates a temporary node points to head
struct Node *temp = headRef;
// Loops till temp is not null (end of linked list)
while(temp != NULL)
{
// Displays the data
cout<<temp -> value<<" ";
// Move to next node
temp = temp->next;
}// End of while
}// End of function
// Function to delete even value nodes and returns the head
struct Node* deleteEvenValueNodes(struct Node *head)
{
// Creates a temporary pointer points to head
struct Node *temp = head;
// Creates a temporary pointer assigned to NULL. To keep track of previous node
struct Node *prev = NULL;
// Checks if temp is null (no node available to delete)
if(temp == NULL)
// return temp
return temp;
// Otherwise checks if the temp next is NULL (only one node)
if(temp -> next == NULL)
{
// Checks if the value at the node is even
if(temp -> value % 2 == 0)
// return NULL
return NULL;
}
// Otherwise more than one node available
// Loops till end of the linked list
while(temp != NULL)
{
// Checks if the current node value is even
if(temp -> value % 2 == 0)
{
// Checks if previous node is NULL
if(prev == NULL)
{
// head is pointing to head next node
head = head -> next;
// temporary node points to head
temp = head;
}// End of if condition
// Otherwise
else
{
// previous node next node is pointing to temporary node next
prev -> next = temp -> next;
// temporary node is now pointing to temporary next node
temp = temp -> next;
}// End of else
}// End of if condition
// Otherwise not even
else
{
// Previous node points to temp
prev = temp;
// Move to next node
temp = temp -> next;
}// End of else
}// End of while loop
// Returns updated head
return head;
}// End of function
// main function definition
int main()
{
// Creates a node head as starting node
struct Node* head = NULL;
// Creates a node for new node
struct Node *newNode;
// To store the number entered by the user
int no;
// Loops till entered number is not -1
do
{
// Accept a number from the user
cout<<"Enter number to insert (-1 to stop): ";
cin>>no;
// Checks if the number is -1 come out of the infinite loop
if(no == -1)
break;
// Otherwise, calls the function to create a node
newNode = createNewNode(no);
// Calls the function to insert the new node in sorted order
sortedInsert(&head, newNode);
}while(1);// End of do - while loop
cout<<" Created Linked List ";
// Calls the function to display the linked list
displayLinkedList(head);
// Calls the function to delete even value nodes
head = deleteEvenValueNodes(head);
cout<<endl;
// Calls the function to display the linked list
displayLinkedList(head);
return 0;
}// End of main function
Sample Output:
Enter number to insert (-1 to stop): 7
Enter number to insert (-1 to stop): 10
Enter number to insert (-1 to stop): 5
Enter number to insert (-1 to stop): 7
Enter number to insert (-1 to stop): 9
Enter number to insert (-1 to stop): 4
Enter number to insert (-1 to stop): 2
Enter number to insert (-1 to stop): 6
Enter number to insert (-1 to stop): 10
Enter number to insert (-1 to stop): 12
Enter number to insert (-1 to stop): 3
Enter number to insert (-1 to stop): 12
Enter number to insert (-1 to stop): 5
Enter number to insert (-1 to stop): 5
Enter number to insert (-1 to stop): 2
Enter number to insert (-1 to stop): 7
Enter number to insert (-1 to stop): 2
Enter number to insert (-1 to stop): 12
Enter number to insert (-1 to stop): -1
Created Linked List
2 2 2 3 4 5 5 5 6 7 7 7 9 10 10 12 12 12
3 5 5 5 7 7 7 9