You must also write a function that converts the linked list to an array, to be

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();
}

Explanation / Answer

#include "Node.hpp" #include "LLSE.hpp" #include #include #include using namespace std; LLSE::LLSE() { first = NULL; last = NULL; size = 0; } LLSE::~LLSE() { Node *tmp = first; for(int i = 0; i next; delete first; first = tmp; } } void LLSE::printLL() { Node *tmp = first; while (tmp != NULL) { cout 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() { Node* tmp=first; Node* tmp2; Node* key = first; while (tmp->next != NULL){ //take key out. tmp holds place of last sorted node key = tmp->next; tmp->next = key->next; //need to handle last //insert key in order //put key at front if it belongs there if (key->count count){ key->next = first; first = key; } else{ tmp2 = first; while (key->count > tmp2->next->count && tmp2 != tmp){ tmp2 = tmp2->next; } if (tmp2 == tmp){ //add key to end of sorted section key->next = tmp->next; tmp->next = key; tmp = key; } else{ //add key in between tmp2 and tmp2->next key->next = tmp2->next; tmp2->next = key; } } } last = tmp; } // Convert the linked list to an array of nodes and return that array Node *LLSE::convertToArray() { Node* arr = new Node[size]; Node* tmp = first; for (int j = 0; jnext; } return arr; } // For the quicksort - the partition int LLSE::partition(int beg,int end) { int p = beg; Node pivot= wordarr[p]; Node tmp; for (int i = beg+1;i

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.