I would like some assistance, included .cpp and header files as well as pdf Head
ID: 3829541 • Letter: I
Question
I would like some assistance, included .cpp and header files as well as pdf
Header file
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <string>
#include <cstdlib>
template <class T>
class LinkedList
{
private:
struct Node
{
T data;
Node* next;
Node* prev;
};
Node* head;
Node* tail;
int count;
public:
LinkedList()
{
head = NULL;
tail = NULL;
count = 0;
};
LinkedList(T value)
{
head = new Node;
head->data = value;
head->next = NULL;
head->prev = NULL;
tail = head;
count = 1;
};
void addNode(T value)
{
Node *temp = new Node;
temp->data = value;
temp->next = NULL;
temp->prev = NULL;
if(head == NULL)
{
head = temp;
tail = temp;
}
else
{
Node *temp2 = head;
while(temp2 != NULL && temp2->data < value)
{
temp2 = temp2->next;
}
if(temp2 == NULL)
{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
else if(temp2 == head)
{
temp2->prev = temp;
temp->next = temp2;
head = temp;
}
else
{
temp->prev = temp2->prev;
temp2->prev->next = temp;
temp2->prev = temp;
temp->next = temp2;
}
}
count++;
};
void deleteNode(T value)
{
if(head == NULL)
{
return;
}
Node *temp = head;
while(temp != NULL && temp->data != value)
{
temp = temp->next;
}
if(temp == NULL)
{
return;
}
else if(temp == head && temp == tail)
{
head = NULL;
tail = NULL;
}
else if(temp == head)
{
head = temp->next;
head->prev = NULL;
}
else if(temp == tail)
{
tail = temp->prev;
tail->next = NULL;
}
else
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
}
count--;
delete temp;
};
LinkedList(const LinkedList& list2)
{
head = NULL;
tail = NULL;
count = 0;
Node *temp = list2.head;
while(temp != NULL)
{
addNode(temp->data);
temp = temp->next;
}
};
~LinkedList()
{
while(head != NULL)
{
deleteNode(head->data);
}
};
int getSize()
{
return count;
};
bool isEmpty()
{
return head == NULL;
};
const LinkedList& operator = (const LinkedList& left)
{
head = NULL;
tail = NULL;
count = 0;
Node *temp = left.head;
while(temp != NULL)
{
addNode(temp->data);
}
return *this;
};
friend std::ostream& operator << (std::ostream& out, const LinkedList& ll)
{
Node *temp = ll.head;
while(temp != NULL)
{
out << "Value = " << temp->data << std::endl;
temp = temp->next;
}
return out;
}; // << operator overload
double getHead()
{
return head->data;
}
};
#endif
The .cpp file
#include <iostream>
#include <fstream>
#include <cstdlib>
#include "LinkedList.h"
using namespace std;
void BucketSort(double *dA, int size)
{
// Declare the needed Linked List
// Write code to sort the values into the correct Linked List
// Sort the Linked List if needed
// Bring the Linked List back into the Array.
}
int main()
{
double dA[10];
for(int i = 0; i < 10; i++)
{
dA[i] = (double)rand() / 10000;
}
// print the original array
// Call the counting sort method with the appropriate parameters
// Print the sorted Array
return 0;
}
Explanation / Answer
// C++ program to sort an array using bucket sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
// 1) Create n empty buckets
vector<float> b[n];
// 2) Put array elements in different buckets
for (int i=0; i<n; i++)
{
int bi = n*arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
// 3) Sort individual buckets
for (int i=0; i<n; i++)
sort(b[i].begin(), b[i].end());
// 4) Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}
/* Driver program to test above funtion */
int main()
{
float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
int n = sizeof(arr)/sizeof(arr[0]);
bucketSort(arr, n);
cout << "Sorted array is ";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}
Output:
// C++ program to sort an array using bucket sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
// 1) Create n empty buckets
vector<float> b[n];
// 2) Put array elements in different buckets
for (int i=0; i<n; i++)
{
int bi = n*arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
// 3) Sort individual buckets
for (int i=0; i<n; i++)
sort(b[i].begin(), b[i].end());
// 4) Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}
/* Driver program to test above funtion */
int main()
{
float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
int n = sizeof(arr)/sizeof(arr[0]);
bucketSort(arr, n);
cout << "Sorted array is ";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
}