C++ only: For this assignment you will build a doubly linked list class. The nam

Question

C++ only:

For this assignment you will build a doubly linked list class. The name of your class is dList, and each entry in the linked list should store 2 different values, a key (integer) and a type (character). A struct (or class) defining the nodes of the linked list should appear outside of the dList class definition and should be named “node”. The class should support the following operations:

You should be careful to manage your memory and implement a destructor, but it is not required to implement a copy constructor or assignment operator for the class. You may use dummy header and tail nodes if you want. Your code should be in a file named dList.cpp and the sample main below should compile and work without modification. You are not allowed any include files in dList.cpp, notice that the main function will include iostream before the dList.cpp file.

MAIN:

#include
using namespace std;
#include "dList.cpp"
#define SMALL 200
#define MAX 100000
#define ROUNDS 100
int main(){
int i, x[MAX];
char ch[MAX];
for(i=0;i dList A(x,ch,SMALL), B;
A.out(10);
node *tmp = A.search(2*SMALL-8);
A.moveFront(tmp);
A.out(10);
A.moveBack(tmp);
A.out(10);
A.find('b');
A.sort();
A.out(10);
A.out(10,'b');
A.addBack(500,'d');
A.addFront(501,'z');
A.out(10);
A.out(10,'b');
B.addFront(1,'a');
B.addBack(2,'b');
B.out(2);
for(int j=0; j cout << endl << "round " << j << endl;
for(i=0;i dList A(x,ch,MAX);
node *tmp = A.search(2*MAX-8);
A.moveFront(tmp);
A.moveBack(tmp);
A.sort();
A.out(10);
A.out(10,'b');
}
}

dList() dList(int[], char[l,int) Default constructor. Should create an empty list. Constructor where the first two parameters are arrays and the third is the length of the arrays. The constructor should initialize the list with the contents of the arravs. void addFront(int, char)Creates a new node at the front of the list. void addBack(int, char)Creates a new node at the back of the list. node *search(int) Searches the list for the occurrence of the int parameter in the list and returns a pointer to the node containing that key. Outputs all keys that have the type equal to the character parameter. Should start at the front of the list and output the keys in list order. void find(char) void moveFront(node *) Moves the node pointed to by the parameter to the front of the void moveBack(node*)Moves the node pointed to by the parameter to the back of the void out(int, char = ) | Outputs the first k elements of the list, where k is the int list. list. parameter. The char parameter can be either 'f, or 'b·T is the default value. If the char is the output starts at the front of the list. If the char is 'b', start at the end of the list and work backwards. Should perform a O(n lg n) time sorting algorithm on the items in the list. The list should be in increasing order based on the integer key after this operation. void sort()

Explanation / Answer

#include<iostream>

using namespace std;

class DLL

{

private:

    class node

    {

    public:

        int data;

        node* next;

        node* prev;

        node(int x)

        {

            data = x;

            next = NULL;

            prev = NULL;

        }

    };

public:

    node* head;

    node* tail;

    int count;

    DLL();       

    void addFront(int);     

    void addBack(int);

   

};

DLL::DLL(){

    head = tail = NULL;

    count = 0;

}

void DLL::addFront(int x){

    node* n = new node(x);

    n->next = head;

    n->prev = NULL;

    if (head != NULL)

        head->prev = n;

        head = n;

        count++;

    if (tail == NULL)

        tail = n;

}

void DLL::addBack(int x){

    node* n = new node(x);

    n->next = NULL;

    n->prev = tail;

    tail = n;

    count++;

}

void moveToFront(node * n)

{

if (head == n)

    {

      return;

    }

else if (tail == n)

    {

      n->prev->next = 0;

      tail = n->prev;

    }

else

    {

      n->prev->next = n->next;

    }

head->prev = n;

n->next = head;

n->prev = 0;

head = n;

}

void insertionSort(struct Node** head_ref)

{

    struct Node* sorted = NULL;

    struct Node* current = *head_ref;

    while (current != NULL) {

        struct Node* next = current->next;

         current->prev = current->next = NULL;

       sortedInsert(&sorted, current);

         current = next;

    }

    *head_ref = sorted;

}

void sortedInsert(struct Node** head_ref, struct Node* newNode)

{

    struct Node* current;

     if (*head_ref == NULL)

        *head_ref = newNode;

     else if ((*head_ref)->data >= newNode->data) {

        newNode->next = *head_ref;

        newNode->next->prev = newNode;

        *head_ref = newNode;

    }

    else {

        current = *head_ref;

         while (current->next != NULL &&

               current->next->data < newNode->data)

            current = current->next;

         newNode->next = current->next;

         if (current->next != NULL)

            newNode->next->prev = newNode;

        current->next = newNode;

        newNode->prev = current;

    }

}

void search()          

{  

    int p;

    cout<<"enter no to search"<<endl;

    cin>>p;

    temp1=start;

    while(temp1->next!=NULL)

    {

        if(temp1->data==p)

        {

            cout<<temp1->data<<" is stored in "<< temp1->next<<endl;

        }

        temp1=temp1->next;

    }

}

int main()

{

    DLL list;

    list.addBack(40);

    list.addBack(50);

    list.addBack(60);

    list.addFront(30);

    list.addFront(20);

    list.addBack(70);

    list.addBack(80);

    list.addFront(10);

insertionSort(&head);

void search();

        return 0;

        }

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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