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

//node.h

class node{

public:

int val1;

char val2;

node *next;

node *prev;

node(int v1, char v2){

val1 = v1;

val2 = v2;

}

};

//dList.cpp

#include <iostream>

using namespace std;

class dList

{

public:

node *head;

dList() {}

dList(int *v1, char *v2, int n)

{

int i = 0;

while (i < n)

{

addBack(v1[i], v2[i]);

i++;

}

}

void addFront(int v1, char v2)

{

if (head == NULL)

head = new node(v1, v2);

else

{

node *temp = new node(v1, v2);

temp->next = head;

head->prev = temp;

head = temp;

}

}

void addBack(int v1, char v2)

{

if (head == NULL)

head = new node(v1, v2);

else

{

node *temp = head;

while (temp->next != NULL)

{

temp = temp->next;

}

node *n = new node(v1, v2);

temp->next = n;

n->prev = temp;

}

}

node *search(int v1)

{

if (head != NULL)

{

node *temp = head;

while (temp != NULL)

{

if (temp->val1 == v1)

{

return temp;

}

temp = temp->next;

}

}

return NULL;

}

void find(char v)

{

if (head != NULL)

{

node *temp = head;

while (temp != NULL)

{

if (temp->val2 == v)

{

cout<<"Key: "<<temp->val1<<endl;

}

temp = temp->next;

}

}

}

void moveFront(node *n)

{

node *temp = head;

if (head != NULL && head != n)

{

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

n->next = head;

n->prev = NULL;

head->prev = n;

head = n;

}

}

void moveBack(node *n)

{

if (head != NULL)

{

node *temp = head;

while (temp->next != NULL)

{

temp = temp->next;

}

if (temp != n)

{

if (head == n)

{

head = head->next;

n->next = NULL;

n->prev = temp;

}

else

{

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

}

temp->next = n;

n->next = NULL;

n->prev = temp;

}

}

}

void out(int n, char s = 'f')

{

if (s == 'f')

{

node *temp = head;

int i = 0;

while (i < n && temp != NULL)

{

cout << "Int val: " << temp->val1 << ", Char Val: " << temp->val2 << endl;

temp = temp->next;

i++;

}

}

else

{

node *temp = head;

while (temp->next != NULL)

{

temp = temp->next;

}

int i = 0;

while (i < n && temp != NULL)

{

cout << "Int val: " << temp->val1 << ", Char Val: " << temp->val2 << endl;

temp = temp->prev;

i++;

}

}

}

void sort(){

node *temp = head;

while(temp!=NULL){

node *temp1 = temp;

while(temp1!=NULL){

if(temp->val1 > temp1->val1){

int k;

char c;

k = temp->val1;

c = temp->val2;

temp->val1 = temp1->val1;

temp->val2 = temp1->val2;

temp1->val1 = k;

temp1->val2 = c;

}

temp1=temp1->next;

}

temp = temp->next;

}

}

};

//main.cpp

#include <iostream>

#include "Node.h"

#include "dList.cpp"

using namespace std;

#define SMALL 200

#define MAX 100000

#define ROUNDS 100

int main()

{

dList *A = new dList();

A->addBack(1, 'A');

A->addBack(3, 'C');

A->addBack(2, 'B');

node *n = A->search(1);

A->moveFront(n);

A->find('C');

A->sort();

A->out(3, 'b');

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.