Can someone please help me out i need it to run on Xcode. I am super stuck Lab 4
ID: 3739150 • Letter: C
Question
Can someone please help me out i need it to run on Xcode. I am super stuck 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 SortedlsEmptyl): 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 Sortedinsert(int 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 Insert f) Print out the list g) Insert 7 h) Print out the list i) Find the 3d element Search 7 k) Print out the length of the list l) Delete 7 m) Print out the list n) Search7Explanation / Answer
CODE:
#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;
}
void sList::sortedDelete(struct Node **head_ref, int key,bool * success)
{
struct Node* temp = *head_ref, *prev;
*success=false;
int count=0;
if (temp != NULL && count == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
*success=true;
return;
}
while (temp != NULL && count != key)
{
prev = temp;
temp = temp->next;
count++;
}
if (temp == NULL)
return;
prev->next = temp->next;
*success=true;
free(temp);
}
/* Counts the no. of occurences of a node
(search_for) in a linked list (head)*/
int sList::sortedLength(struct Node * head)
{
if (head == NULL)
return 0;
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;
for (i = 0; i < n&&temp->next!=NULL; i++)
temp = temp->next;
if(i==n)
return true;
else return false;
}
Result:
Elements of list are:5->5->7->9->11->NULL
Elements of list are:5->5->7->7->9->11->NULL
Element found at 3, 0 denotes false =? 1
Search for 7 = ? 0
Current Length6
Elements of list are:5->5->7->7->9->11->NULL
Search for 7 = ? 0