Complete the following using the code below: 1. Consider the Linked List.h and L
ID: 3672437 • Letter: C
Question
Complete the following using the code below:
1. Consider the Linked List.h and LinkedList.cpp files given to you.
Write a member function of the LinkedList class called BubbleSort() that sorts the items of the linked list in ascending order using the bubble sort algorithm.
Write a driver function to insert the following integers (15, 20, 30, 7, 8) into the linked list. Call the member function BubbleSort() from the main to sort the linked list.
2. Consider that a sorted list of integers (e.g., 1, 1, 2, 2, 5, 5, 5, 5, 5, 5, 5, 8, 8, 9, 10, 11, 11) is provided to you.
a) Your goal is to write a program to find the occurrences of an integer (e.g., 5) in the array using binary search. If your code finds the occurrences of the element in O(n) complexity, you will be given full credit.
#include <iostream>
using namespace std;
#include "LinkedList.h"
//-- Default constructor
LinkedList::LinkedList()
{
mySize = 0;
first = NULL;
}
//-- Definition of the copy constructor
LinkedList::LinkedList(const LinkedList & origList)
{
mySize = origList.mySize;
first = NULL;
if (mySize == 0)
return;
Node * origPtr, * lastPtr;
first = new Node(origList.first->data); // copy first node
lastPtr = first;
origPtr = origList.first->next;
while (origPtr != NULL)
{
lastPtr->next = new Node(origPtr->data);
origPtr = origPtr->next;
lastPtr = lastPtr->next;
}
}
//-- Definition of the destructor
LinkedList::~LinkedList()
{
Node * prev = first;
Node * ptr;
while (prev != NULL)
{
ptr = prev->next;
delete prev;
prev = ptr;
}
//----- LinkedList.h -----
#ifndef LINKEDLIST
#define LINKEDLIST
#include <iostream>
using namespace std;
typedef int ElementType;
class LinkedList
{
public:
LinkedList(); // constructor
~LinkedList(); // destructor
LinkedList(const LinkedList & original); //copy constructor
void insert(ElementType item, int pos);
void erase(ElementType item);
void display(ostream & out) const;
/*--------------------------------------------------------------------
Display the contensts of this LinkedList.
Precondition: ostream out is open
Postcondition: Elements of this LinkedList have been output to out.
--------------------------------------------------------------------*/
private:
class Node
{
public:
ElementType data;
Node * next;
//------ Node OPERATIONS
//-- Default constrctor: initializes next member to
Node()
: next(NULL)
{ }
//-- Explicit-value constructor: initializes data member to dataValue
//-- and next member to 0
Node(ElementType dataValue)
: data(dataValue), next(NULL)
{ }
};
Node * first;
int mySize;
};
#endif
}
Explanation / Answer
1.
First add given below line in LinkedList.h :
/* Bubble sort the given linked lsit */
void bubbleSort(Node *start);
/* function to swap data of two nodes a and b*/
void swap(Node *a, Node *b);
Then ass below given methods in LinkedList.cpp :
/* Bubble sort the given linked lsit */
void LinkedList:: bubbleSort(Node *start)
{
int swapped, i;
Node *ptr1;
Node *lptr = NULL;
/* Checking for empty list */
if (ptr1 == NULL)
return;
do
{
swapped = 0;
ptr1 = start;
while (ptr1->next != lptr)
{
if (ptr1->data > ptr1->next->data)
{
swap(ptr1, ptr1->next);
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
}
while (swapped);
}
/* function to swap data of two nodes a and b*/
void LinkedList::swap(Node *a, Node *b)
{
ElementType temp = a->data;
a->data = b->data;
b->data = temp;
}
Driver Function: Main
int main()
{
int arr[] = {12, 56, 2, 11, 1};
int list_size, i;
/* start with empty linked list */
LinkedList *start;
/* Create linked list from the array arr[].
Created linked list will be 1->11->2->56->12 */
for (i = 0; i< 6; i++)
list.insert(arr[i], 0);
/* sort the linked list */
list.bubbleSort(start);
return 0;
}
2.
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);
/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]
/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);
/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of x. Note that we
are only looking in the subarray after first occurrence */
j = last(arr, i, n-1, x, n);
/* return count */
return j-i+1;
}
/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}
Run on IDE
Time Complexity: O(Logn)