You must also write a function that converts the linked list to an array, to be
ID: 3776804 • Letter: Y
Question
You must also write a function that converts the linked list to an array, to be used by the quicksort.
The insertionSort must sort the linked list.
The quickSort should be written using the array you converted from the linked list.
The heapsort kind of makes an array anyhow, so use that.
#include "Node.hpp"
#include "LLSE.hpp"
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
LLSE::LLSE() {
first = NULL;
last = NULL;
size = 0;
}
LLSE::~LLSE() {
Node *tmp = first;
for(int i = 0; i < size; i++) {
tmp = first->next;
delete first;
first = tmp;
}
}
void LLSE::printLL() {
Node *tmp = first;
while (tmp != NULL) {
cout << tmp->count <<":"<<tmp->word << endl;
tmp = tmp->next;
}
}
void LLSE::addFirst(string w) {
first = new Node(w);
last = first;
size = 1;
}
void LLSE::insertUnique(string w) {
Node *tmp = first;
if (tmp == NULL) {
addFirst(w);
}
else {
while (tmp != NULL && tmp->word < w) {
tmp = tmp->next;
}
if ((tmp!= NULL) && (tmp->word == w)) {
tmp->count++;
}
else {
Node *tmp2 = new Node(w);
if (tmp != NULL) {
if (tmp->prev != NULL) {
tmp->prev->next = tmp2;
tmp2->prev = tmp->prev;
}
else {
first = tmp2;
}
tmp2->next = tmp;
tmp->prev = tmp2;
}
else {
last->next = tmp2;
tmp2->prev = last;
last = tmp2;
}
size++;
}
}
}
// Write an insertion Sort on the linked list (not an array,
// a linked list!
void LLSE::insertionSortLL() {
}
// Convert the linked list to an array of nodes and return that array
Node *LLSE::convertToArray() {
}
// For the quicksort - the partition
int LLSE::partition(int beg,int end) {
}
// your recursive quicksort
void LLSE::quickSort( int beg, int end) {
}
//Take the linked list and create a binary heap
Node *LLSE::makeHeap() {
}
//Sort the heap array using heapsort
void LLSE::heapSort() {
}
#include "Node.hpp"
#include <iostream>
#include <string>
using namespace std;
Node::Node(string s) {
count = 1;
next = NULL;
prev = NULL;
word = s;
}
#ifndef NODE_HPP_
#define NODE_HPP_
#include <iostream>
#include <string>
using namespace std;
class Node {
friend class Document;
friend class LLSE;
Node *next;
Node *prev;
int count;
string word;
public:
Node(string w);
Node();
};
#endif /* NODE_HPP_ */
#include "Document.hpp"
#include <iostream>
#include <stdlib.h>
using namespace std;
int main() {
cout << "hi" << endl;
Document doc("Monet.txt");
doc.readFile();
doc.pickSort(0);
return 0;
}
#include "Document.hpp"
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <fstream>
#include <chrono>
using namespace std;
Document::Document(string f) {
filename = f;
wordlist = new LLSE();
}
string Document::strip(string w){
int x = strlen(w.c_str());
string neww="";
cout << w << ":" << x << endl;
char punct[] = {'!', '.', ',',':', ';',''','"','(',')'};
for (int i = 0; i < x; i++) {
bool flag = false;
for (int j = 0; j < 9; j++) {
if (w[i] == punct[j]) {
flag = true;
j = 9;
}
}
if (!flag) {
neww += tolower(w[i]);
}
}
return neww;
}
bool Document::checkFunctionWords(string w) {
int i = 0;
while (i< fwlen && w != fw[i] ) {
i++;
}
if (i != fwlen) {
return true;
}
return false;
}
void Document::pickSort(int i) { // 0 = insertionSort, 1 = QuickSort, 2= heapSort
if (i == 0) {
wordlist->insertionSortLL();
}
else if (i == 1) {
wordlist->wordarr= wordlist->convertToArray();
wordlist->quickSort(0,wordlist->size-1);
}
else if (i == 2) {
wordlist->heapSort();
}
}
void Document::readFile() {
cout << filename << endl;
ifstream infile(filename.c_str(),ios::in); // open file
if (!infile.is_open()) {
return;
}
string word;
while (infile>>word) { // loop getting single characters
word = strip(word);
if (!checkFunctionWords(word)) {
cout << word << " is valid " << endl;
wordlist->insertUnique(word);
}
else {
cout << word << " removed" << endl;
}
}
wordlist->printLL();
}