In this assignment, you are given several classes in the cpp file “DList.cpp”. Your task is...
In this assignment, you are given several classes in the cpp file “DList.cpp”. Your task is to
complete the implementation of the classes specified as below. Y
1 Your Task
You are given a class “Item” that contains one integer value, and two pointers. You are going to
build a doubly linked list class DLinkedList. I describe the tasks below.
Task 1:
Implement the constructors (default and copy) of DLinkedList. You need to make sure
that the copy constructor makes a separate copy of the list.
Task 2:
Implement push back, push front, pop back, pop front, get front, get back, display, swap.
The functions are pretty self explanatory from their names.
Task 3:
Implement Inserts. You should handle “insert an item” and “insert a list”.
Task 4:
Implement extract min, extract max. They return the pointer to the min/max item in
the list. If there is a tie, then choose arbitrarily among the mins/maxes.
Task 5:
Implement classes myQueue and myStack
using
DLinkedList. Do not re-write codes.
(This task is pretty easy. There should not be any loops).
Task 6:
Design some tests to test your DLinkedList in the main function. You don’t need to test
your Stack nor Queue, as checking them is easy, assuming your DLinkedList is correct.
below is the skeleton for the code:
#include <iostream>
using namespace std;
class Item
{
public:
int val;
Item *next, *pre;
Item()
{
val =0;
next=0;
pre=0;
}
Item(int val)
{
this->val = val;
next=0;
pre=0;
}
};
class DLinkedList
{
int size;
Item *front;
Item *back;
public:
DLinkedList();
DLinkedList(const DLinkedList &list);
void push_back(Item *a);
void push_front(Item *a);
Item * pop_front();
Item * pop_back();
void insert(Item *a, int t); // insert the item a after the t-th element
void insertlist(DLinkedList *list, int t); // insert the whole list a after the t-th element
void display(ostream &out);
int getSize();
Item * getfront();
Item * getback();
void swap(Item *p, Item *q); //swap two items pointed by p and q, you can assume that p and q are something in the list
Item * extractmin(Item * start); // return the pointer of the min element after "start",
// here you can assume user will always input a valid pointer start that points to an item in the list
Item * extractmax(Item * start); // return the pointer of the max element after "start"
};
class myStack
{
DLinkedList list;
public:
myStack();
int getSize();
void in(Item *a);
Item *top();
void out();
};
class myQueue
{
DLinkedList list;
public:
myQueue();
int getSize();
void in(Item *a);
Item *front();
void out();
};
int main() {
return 0;
}
Homework Answers
#include <iostream>
#include <stdlib.h>
using namespace std;
class Item
{
public:
int val;
Item *next, *prev;
Item()
{
val =0;
next=0;
prev=0;
}
Item(int val)
{
this->val = val;
next=0;
prev=0;
}
};
class DLinkedList
{
int size;
Item *front;
Item *back;
public:
int getSize() const
{
return size;
}
Item* getFront() const
{
return front;
}
Item* getBack() const
{
return back;
}
void setSize(int s)
{
size=s;
}
void setFront(Item *f)
{
front=f;
}
void setBack(Item *b)
{
back=b;
}
DLinkedList()
{
size=0;
front=back=NULL;
}
DLinkedList(const DLinkedList &list);
void push_back(Item *a);
void push_front(Item *a);
Item * pop_front();
Item * pop_back();
// insert the item a after the t-th element
void insert(Item *a, int t);
// insert the whole list a after the t-th element
void insertlist(const DLinkedList &list, int t);
void display(ostream &out);
void swap(Item *p, Item *q); //swap two items pointed by p and q, you can assume that p and q are something in the list
Item * extractmin(Item * start); // return the pointer of the min element after "start",
// here you can assume user will always input a valid pointer start that points to an item in the list
Item * extractmax(Item * start); // return the pointer of the max element after "start"
};
DLinkedList::DLinkedList(const DLinkedList &list)
{
if (list.getFront() == NULL)
{
this->setFront(NULL);
this->setBack(NULL);
}
else
{
this->setFront(new Item(list.front->val));
this->setSize(this->getSize()+1);
Item *current = this->getFront();
Item *objFront = list.getFront();
Item *currentObj = objFront;
while (currentObj->next != NULL)
{
current->next = new Item(currentObj->next->val);
currentObj = currentObj->next;
current->next->prev=current;
current = current->next;
}
this->setBack(current);
}
}
void DLinkedList::push_back(Item *a)
{
if(this->getSize()==0)
{
this->setFront(a);
this->setBack(a);
}
else
{
this->getBack()->next=a;
a->prev=this->getBack();
this->setBack(this->getBack()->next);
}
this->setSize(this->getSize()+1);
}
void DLinkedList::push_front(Item *a)
{
if(this->getSize()==0)
{
this->setFront(a);
this->setBack(a);
}
else
{
a->next=this->getFront();
this->getFront()->prev=a;
this->setFront(a);
}
this->setSize(this->getSize()+1);
}
Item* DLinkedList::pop_front()
{
Item *temp=this->getFront();
if(this->getSize()==0)
cout<<"\nList is empty!";
else if(this->getSize()==1)
{
this->setFront(NULL);
this->setBack(NULL);
}
else
{
this->setFront(this->getFront()->next);
this->getFront()->prev=NULL;
}
free(temp);
this->setSize(this->getSize()-1);
}
Item* DLinkedList::pop_back()
{
Item *temp=back;
if(this->getSize()==0)
cout<<"\nList is empty!";
else if(this->getSize()==1)
{
this->setFront(NULL);
this->setBack(NULL);
}
else
{
this->setBack(this->getBack()->prev);
this->getBack()->next=NULL;
}
free(temp);
this->setSize(this->getSize()-1);
}
// insert the item a after the t-th element
void DLinkedList::insert(Item *a, int t)
{
if(t==0)
push_front(a);
else if(t<0)
cout<<"\nInvalid position!";
else if(t==size)
push_back(a);
else
{
int i;
Item *temp;
if(t<=(this->getSize()/2))
{
temp=this->getFront();
for(i=0;i<t;i++)
{
temp=temp->next;
}
}
else
{
temp=this->getBack();
for(i=0;i<(size-t);i++)
{
temp=temp->prev;
}
}
a->next=temp->next;
a->prev=temp;
temp->next=a;
a->next->prev=a;
this->setSize(this->getSize()+1);
}
}
// insert the whole list a after the t-th element
void DLinkedList::insertlist(const DLinkedList &list, int t)
{
if(!list.getFront())
{
cout<<"\nThe list you want to append to the original list is empty!";
}
else
{
if(t==0)
{
list.getBack()->next=this->getFront();
this->getFront()->prev=list.getBack();
this->setFront(list.getFront());
}
else if(t<0)
cout<<"\nInvalid position!";
else if(t==this->getSize())
{
this->getBack()->next=list.getFront();
list.getFront()->prev=this->getBack();
this->setBack(list.getBack());
}
else
{
int i;
Item *temp;
if(t<=(this->getSize()/2))
{
temp=this->getFront();
for(i=0;i<t;i++)
{
temp=temp->next;
}
}
else
{
temp=this->getBack();
for(i=0;i<(this->getSize()-t);i++)
{
temp=temp->prev;
}
}
list.getBack()->next=temp->next;
list.getFront()->prev=temp;
temp->next=list.getFront();
list.getBack()->next->prev=list.getBack();
}
}
this->setSize(this->getSize()+list.getSize());
}
void DLinkedList::display(ostream &out)
{
if(this->getFront()==NULL)
out<<"List is empty!";
else
{
Item *temp=this->getFront();
while(temp)
{
out<<temp->val<<"->";
temp=temp->next;
}
}
}
void DLinkedList::swap(Item *p, Item *q)
{
int temp=p->val;
p->val=q->val;
q->val=temp;
}
Item* DLinkedList::extractmin(Item * start)
{
if(start->next==NULL)
return start;
else
{
Item* min=start;
start=start->next;
while(start)
{
if(start->val<min->val)
min=start;
}
return min;
}
}
Item * DLinkedList::extractmax(Item * start)
{
if(start->next==NULL)
return start;
else
{
Item* max=start;
start=start->next;
while(start)
{
if(start->val>max->val)
max=start;
}
return max;
}
}
class myStack
{
DLinkedList list;
public:
myStack();
int getSize()
{
return list.getSize();
}
void in(Item *a)
{
list.push_back(a);
}
Item *top()
{
return list.getBack();
}
void out()
{
Item* poppedItem=list.pop_back();
cout<<"\nElement popped out is: "<<poppedItem->val;
}
};
class myQueue
{
DLinkedList list;
public:
myQueue();
int getSize()
{
return list.getSize();
}
void in(Item *a)
{
list.push_front(a);
}
Item *front()
{
return list.getFront();
}
void out()
{
Item* poppedItem=list.pop_back();
cout<<"\nElement popped out is: "<<poppedItem->val;
}
};
int main()
{
return 0;
}
Add Answer to:
In this assignment, you are given several classes in the cpp
file “DList.cpp”. Your task is...
I was told I need three seperate files for these classes is there anyway to tie...
I was told I need three seperate files for these classes is there anyway to tie all these programs together into one program after doing that. I'm using netbeans btw. import java.util.ArrayList; import java.util.Scanner; /** * * */ public class MySorts { public static void main(String[] args) { Scanner input = new Scanner(System.in); String sentence; String again; do { System.out .println("Enter a sentence, I will tell you if it is a palindrome: ");...
The class pictured below is designed to implement an integer queue using two stacks. Assume the...
The class pictured below is designed to implement an integer
queue using two stacks. Assume the stack methods all work as
desired (though their implementations are not shown).
.(a) Trace what happens in the following situation, showing
intermediate steps (values of variables, what is in the stacks, and
what is in the queue at various points in the methods, not just the
results of the methods).
• Start with an empty queue. Enqueue 5, then 16, then 7. Dequeue
twice....
In c++ show both .cpp and .hpp file for the class: class Task { private: //...
In c++ show both .cpp and .hpp file for the class: class Task { private: // These three member variables store the basic information about a task string title; string location; // This pointer will point to a dynamically-allocated array // of THREE strings. Each element contains the name of a supply required for this task. // This should start out set to NULL. string * tags; // This integer stores the number of elements in the tags array. int...
Q1: You can find a file that defines the CircularlyLinked List class similar to what we...
Q1: You can find a file that defines the CircularlyLinked List class similar to what we discussed in the class. Download the file and work on it. Your task is to: 1. Complete the missing methods in the file as discussed in the class. Search for the comment/" MISSING / in the file to see the methods that need to be completed. 2. Add the following methods to the class a. public Node getMin 1. Task: find the node with...
Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time...
Doubly Linked List The assignment is to modify the below code in any way (like changing the method of a function). Time complexity is omitted. Any methods/functions below could be changed into something different. I was thinking of changing the method of getting size of list and maybe change from numbers to letters for nodes. import java.util.Scanner; /* Class Node */ class Node { protected int data; protected Node next, prev; /* Constructor */ public Node() { next = null;...
JAVA LANG PLEASE: I have follwed these below guidelines but when i run my queue test...
JAVA LANG PLEASE: I have follwed these below guidelines but when i run my queue test it is not executing but my stack is working fine, can you fix it please! MyQueue.java Implement a queue using the MyStack.java implementation as your data structure. In other words, your instance variable to hold the queue items will be a MyStack class. enqueue(String item): inserts item into the queue dequeue(): returns and deletes the first element in the queue isEmpty(): returns true or false...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD COMMENTS: stackARRAY: #include<iostream> #define SIZE...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD
COMMENTS:
stackARRAY:
#include<iostream>
#define SIZE 100
#define NO_ELEMENT -999999
using namespace std;
class Stack {
int arr[SIZE]; // array to store Stack elements
int top;
public:
Stack() {
top = -1;
}
void push(int); // push an element into Stack
int pop(); // pop the top element from Stack
int topElement(); // get the top element
void display(); // display Stack elements from top to bottom
};
void Stack...
PROGRAMMING 1. The LinkList class that we discussed in class is implemented using pointer t constructed...
PROGRAMMING 1. The LinkList class that we discussed in class is implemented using pointer t constructed with a list of nodes, and the first node pointer points to the front I a) (10 pts) Complete the following class declaration which is similar to Linklist class ecter class (Write only the prototypes and the private data field; definitions will follow the class declaration) template stypenane T> olass Linkedveoter t private olass Node publie T info Node "next typedet Node *nodePtr publie...
IntList Recursion Assignment Specifications: You will add some additional recursive functions to your IntList class as...
IntList Recursion Assignment Specifications: You will add some additional recursive functions to your IntList class as well as make sure the Big 3 are defined. IntNode class I am providing the IntNode class you are required to use. Place this class definition within the IntList.h file exactly as is. Make sure you place it above the definition of your IntList class. Notice that you will not code an implementation file for the IntNode class. The IntNode constructor has been defined...
The class pictured below is designed to implement an integer
queue using two stacks. Assume the stack methods all work as
desired (though their implementations are not shown).
.(a) Trace what happens in the following situation, showing
intermediate steps (values of variables, what is in the stacks, and
what is in the queue at various points in the methods, not just the
results of the methods).
• Start with an empty queue. Enqueue 5, then 16, then 7. Dequeue
twice....
Q1: You can find a file that defines the CircularlyLinked List class similar to what we discussed in the class. Download the file and work on it. Your task is to: 1. Complete the missing methods in the file as discussed in the class. Search for the comment/" MISSING / in the file to see the methods that need to be completed. 2. Add the following methods to the class a. public Node getMin 1. Task: find the node with...
HI USING C++ CAN YOU PLEASE PROGRAM THIS ASSIGNMENT AND ADD
COMMENTS:
stackARRAY:
#include<iostream>
#define SIZE 100
#define NO_ELEMENT -999999
using namespace std;
class Stack {
int arr[SIZE]; // array to store Stack elements
int top;
public:
Stack() {
top = -1;
}
void push(int); // push an element into Stack
int pop(); // pop the top element from Stack
int topElement(); // get the top element
void display(); // display Stack elements from top to bottom
};
void Stack...
PROGRAMMING 1. The LinkList class that we discussed in class is implemented using pointer t constructed with a list of nodes, and the first node pointer points to the front I a) (10 pts) Complete the following class declaration which is similar to Linklist class ecter class (Write only the prototypes and the private data field; definitions will follow the class declaration) template stypenane T> olass Linkedveoter t private olass Node publie T info Node "next typedet Node *nodePtr publie...
Most questions answered within 3 hours.
-
Complete the following reactions which form ethers (A
and B) and cyclic ethers (C-E) as major...
asked 16 minutes ago -
in a perfectly elastic collision what is the velocity of ball A
if the original direction...
asked 45 minutes ago -
PLEASE ANSWER ALL
1) The pressure of the atmosphere decreases with increasing
altitude in the
Choose...
asked 59 minutes ago -
A simple random sample of 25,000 individuals are surveyed in
order to determine the prevalence of...
asked 1 hour ago -
People who do very detailed work close up, such as jewelers,
often can see objects clearly...
asked 1 hour ago -
14 years ago, Blue Lake Corp. issued 30 year to maturity
zero-coupon bonds with a par...
asked 56 minutes ago -
Warnerwoods Company uses a perpetual inventory system. It
entered into the following purchases and sales transactions...
asked 52 minutes ago -
Equivalent Units of Conversion Costs
The Rolling Department of Oak Ridge Steel Company had 6,842 tons...
asked 57 minutes ago -
what does the concept of "core competence" mean? why
is this concept important? How would you...
asked 1 hour ago -
__________ is a type of visualization that is linked to strategy
and used within a formal...
asked 1 hour ago -
A national magazine stated that at most,12% of millennials
have a pool membership. Formulate an appropriate...
asked 1 hour ago -
Can
you provide the mechanism for enamine hydrolysis. Any example will
work, thank you.
asked 1 hour ago