Please help. This needs to be in c++ Lab 4 Linked List Assigned on 03/05/18, Due
ID: 3733363 • Letter: P
Question
Please help. This needs to be in c++ Lab 4 Linked List Assigned on 03/05/18, Due on 03/14/18 Problem 1. Implement a sorted singly linked list and support the following operations bool SortedisEmpty): return true if the list is empty int SortedGetlength): return the length of the list bool SortedFind(int k, int& x): return the value of the kth element; int SortedSearch(int key): return the position of the element which is same as key (note: use the most efficient method); void Sortedinsertfint x): insert x to the right position in the sorted linked list; void SortedDelete(int k, int& x, bool& success): delete the kth element Part (1) Implement the aboved singly linked list allowing the duplicate element. Part (2) Implement the above singly linked list without allowing the duplicate element. Test your program for both parts with the following operations: a) Insert 5 b) Insert 7 c) Insert 9 d) Insert 11 e) Insert5 f) Print out the list 8) Insert 7 h) Print out the list i) Find the 3d element j) Search 7 k) Print out the length of the list l) Delete 7 m) Print out the list n) Search7
Explanation / Answer
/*
* C++ Program to Implement Singly Linked List
*/
#include<iostream>
using namespace std;
/*
* Node Declaration
*/
struct Node
{
int data;
struct Node *next;
}*head;
/*
* Class Declaration
*/
class sList
{
public:
Node* createNode(int);
void display();
void sortedInsert(struct Node **,struct Node *);
bool sortedEmpty();
int sortedLength(struct Node*);
bool sortedSearch(struct Node *,int k);
bool sortedFind(struct Node *, int k);
void sortedDelete(struct Node **,int k,bool * success);
sList()
{
head = NULL;
}
};
int main()
{
sList sl;
head = NULL;
int loc=0;
bool success;
sl.sortedInsert(&head,sl.createNode(5));
sl.sortedInsert(&head,sl.createNode(7));
sl.sortedInsert(&head,sl.createNode(9));
sl.sortedInsert(&head,sl.createNode(11));
sl.sortedInsert(&head,sl.createNode(5));
sl.display();
sl.sortedInsert(&head,sl.createNode(7));
sl.display();
cout<<"Element found at 3, 0 denotes false =? "<<sl.sortedFind(head,3)<<endl;
cout<<"Search for 7 = ? " <<sl.sortedSearch(head,7)<<endl;
cout<<"Current Length"<<sl.sortedLength(head)<<endl;
sl.sortedDelete(&head,7,&success);
sl.display();
cout<<"Search for 7 = ? " <<sl.sortedSearch(head,7)<<endl;
}
void sList::sortedInsert(struct Node** head_ref, struct Node* new_node)
{
struct Node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->data >= new_node->data)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->data < new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
Node *sList::createNode(int value)
{
struct Node *temp, *s;
temp = new(struct Node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->data = value;
temp->next = NULL;
return temp;
}
}
/*
* Display Elements of a link list
*/
void sList::display()
{
struct Node *temp;
if (head == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = head;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->data<<"->";
temp = temp->next;
}
cout<<"NULL"<<endl;
}
/* Given a reference (pointer to pointer) to the head of a list
and a key, deletes the first occurrence of key in linked list */
void sList::sortedDelete(struct Node **head_ref, int key,bool * success)
{
// Store head node
struct Node* temp = *head_ref, *prev;
*success=false;
int count=0;
// If head node itself holds the key to be deleted
if (temp != NULL && count == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
*success=true;
return;
}
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && count != key)
{
prev = temp;
temp = temp->next;
count++;
}
// If key was not present in linked list
if (temp == NULL)
return;
// Unlink the node from linked list
prev->next = temp->next;
*success=true;
free(temp); // Free memory
}
/* Counts the no. of occurences of a node
(search_for) in a linked list (head)*/
int sList::sortedLength(struct Node * head)
{
// Base case
if (head == NULL)
return 0;
// count is 1 + count of remaining list
return 1 + sList::sortedLength(head->next);
}
/* Checks whether the value x is present in linked list */
bool sList::sortedSearch(struct Node* head, int x)
{
struct Node* current = head; // Initialize current
int count=0;
while (current != NULL)
{
if (current->data == x&& count==x){
return true;
}
current = current->next;
count++;
}
return false;
}
bool sList::sortedEmpty()
{
if(head==NULL)
return true;
else return false;
}
bool sList::sortedFind(struct Node* head, int n)
{
int i;
struct Node *temp = head;
temp = head;
// 2) get the (n-len+1)th node from the begining
for (i = 0; i < n&&temp->next!=NULL; i++)
temp = temp->next;
if(i==n)
return true;
else return false;
}
Output:
Part 2 you have 2 modified