I need help with my c++ code to continue from here. #include <iostream> #include

Question

I need help with my c++ code to continue from here.

#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>

using namespace std;

template <class TYPE>

class Node{
public:
    Node ();
    Node (const Node& orig);
    Node* getNext();
    Node* getprev();
    bool hasNext();
    bool hasPrev();
    void setNext ( Node* newNext);
    void setPrev (Node* newPrev);
    int getVal();
    void setVal(Node* value);
private:
    Node* next;
    int value;
};

Node::Node(){
    next = NULL;
}

Node::Node(const Node& orig){
    Node = orig.next;
    val = orig.val;
}

bool Node::hasNext(){
    if (next != NULL)
        return true;
    else
        return false;
}

bool Node::hasPrev(){
    if (next == NULL)
        prev = orig.val;
}

Node* Node::getNext(){
    return next;
    }

Node* Node::getprev(){
    return prev;
    }

Node* Node::getVal(){
    return val;
}

void Node* Node::setVal(int value){
    val = value;
}

void Node* Node::setNext(Node* newNext) {
    if (newNext = = NULL)
        next = NULL;
    else
        next = newNext -> next;
}

void Node* Node::setVal(Node* newPrev){
    prev = newPrev -> prev;
}

template <class TYPE>

class DLinkedList{

public:
    DLinkedList(); //Constructor
    head = NULL;

    ~DLinkedList(); //Destructor
     makeEmpty();
const DLinkedList& operator=(const DLinkedList&); // Assignment operator

Node<TYPE>* insert(const TYPE &, Node<TYPE>* );    //
Node<TYPE>* isFirst();                //returns a reference to header node
Node<TYPE>* next(Node<TYPE>* ) const; //reference to next node
Node<TYPE>* precedent(Node<TYPE>* N); //reference to previous node
Node<TYPE>* remove(Node<TYPE>* N); // removes the node to the right of N
bool isEmpty () const;    // returns true if list is empty
void display (ostream & ); // write to a file the elements of the linked list
Node<TYPE>* Min(Node<TYPE>* H); // finds the min value in a list headed by H
void sort(); // sorts the list (selection sort)

};

DLinkedList::DLinkedList(){
}

DLinkedList::DLinkedList& operator=(const DLinkedList&){
}

DLinkedList::insert(const TYPE &, Node<TYPE>*){

}

DLinkedList::isFirst(){

}

DLinkedList::next(){

}

DLinkedList::precedent(Node<TYPE>* N){

}

DLinkedList::remove(Node<TYPE>* N){

}

DLinkedList::isEmpty(){

}

void DLinkedList::display(){
    return DLinkedList;
}

DLinkedList::Min(Node <TYPE>* H){

}

void DLinkedList::sort(){

}

int main(){
DLinkedList<int> theList; //initialize an empty list
int size; //the size of list to be sorted
int n;
char filename[80];
cout << "Enter an output filename: ";
cin >> filename;
ofstream out;
out.open(filename);
cout << "Enter the size of the list " << endl;
cin >> size;
srand(time(0));
Node<int> *temp =theList.isFirst();
for (int i = 1; i <size; i++){
    n = rand() % 100;
    temp = theList.insert(n, temp);
}

out << "The original list is:";
theList.display(); //displays the generated list
theList.sort();   //sort using recursive selection sort
out << "The sorted list is: ";
theList.display(); //display the sorted list
out.close();
return 0;

}

}

You are asked to write a program that implements a templated doubly linked list class DLinkedList including a recursive Selection Sort method. In addition to the appropri- ate constructor and destructor, the assignment operator, you should implement the follow- ing class methods (and any others if needed): Node TYPE> insert (const TYPE &, Node TYPE inserts a node Node

Explanation / Answer

class QuickSort_using_Doubly_LinkedList{
Node head;

/* a node of the doubly linked list */
static class Node{
private int data;
private Node next;
private Node prev;

Node(int d){
data = d;
next = null;
prev = null;
}
}

Node lastNode(Node node){
while(node.next!=null)
node = node.next;
return node;
}


Node partition(Node l,Node h)
{
int x = h.data;

Node i = l.prev;

for(Node j=l; j!=h; j=j.next)
{
if(j.data <= x)
{

i = (i==null) ? l : i.next;
int temp = i.data;
i.data = j.data;
j.data = temp;
}
}
i = (i==null) ? l : i.next; // Similar to i++
int temp = i.data;
i.data = h.data;
h.data = temp;
return i;
}

/* A recursive implementation of quicksort for linked list */
void _quickSort(Node l,Node h)
{
if(h!=null && l!=h && l!=h.next){
Node temp = partition(l,h);
_quickSort(l,temp.prev);
_quickSort(temp.next,h);
}
}


public void quickSort(Node node)
{

Node head = lastNode(node);


_quickSort(node,head);
}

public void printList(Node head)
{
while(head!=null){
System.out.print(head.data+" ");
head = head.next;
}
}

void push(int new_Data)
{
Node new_Node = new Node(new_Data); /* allocate node */

if(head==null){
head = new_Node;
return;
}

new_Node.next = head;

head.prev = new_Node;

new_Node.prev = null;

head = new_Node;
}

public static void main(String[] args){
QuickSort_using_Doubly_LinkedList list = new QuickSort_using_Doubly_LinkedList();


list.push(5);
list.push(20);
list.push(4);
list.push(3);
list.push(30);


System.out.println("Linked List before sorting ");
list.printList(list.head);
System.out.println(" Linked List after sorting");
list.quickSort(list.head);
list.printList(list.head);

}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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