//Program needs to follow basic skeleton (Methods, and main) here I provided. Tr
ID: 3801690 • Letter: #
Question
//Program needs to follow basic skeleton (Methods, and main) here I provided. Trying to create Double Linked list Class with seperate Node class that points to next and prev. I tried filling in as much as I can.
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <class TYPE>
class Node{ //node class holds data value and pointer
public:
Node* next;
Node* prev;
int value;
Node* head;
};
template <class TYPE>
class DLinkedList{
public:
DLinkedList(); //Constructor
~DLinkedList(); //Destructor
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>* ) const; //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)
};
template <class TYPE>
DLinkedList<TYPE>::DLinkedList(){ //constructor
head = new Node<TYPE>(0, NULL);
}
template <class TYPE>
DLinkedList<TYPE>::~DLinkedList(){ //destructor
makeEmpty();
template <class TYPE>
const DLinkedList<TYPE>& DLinkedList<TYPE>::operator=(const DLinkedList<TYPE>& Rhs){ //assignment operator
if (this == &Rhs)return Rhs;
makeEmpty();
if(Rhs.isEmpty()) return *this;
Node<TYPE> *temp;
temp=Rhs.head;
do{
insertFirst(temp->value);
temp=temp->next;
}while(temp!=NULL);
return *this;
}
template <class TYPE>
Node<TYPE>* DLinkedList<TYPE>::insert(const TYPE & e, Node<TYPE>* current){
Node<TYPE>* temp= new Node<TYPE>(e, current -> next);
current -> next = temp;
return temp;
}
template <class TYPE>
Node<TYPE>* DLinkedList<TYPE>::isFirst( )const{
return head;
}
DLinkedList::next(Node<TYPE>* ) const){
return Node->next;
}
DLinkedList::precedent(Node<TYPE>*){
return Node->prev;
}
template <class TYPE>
Node<TYPE>* DLinkedList<TYPE>::remove(Node<TYPE>* N){
Node<TYPE>* temp= N -> next;
N -> next = N -> next -> next;
delete temp;
return N->next;
}
template <class TYPE>
bool DLinkedList<TYPE>::isEmpty()const{
return (head->next==NULL);
}
template <class TYPE>
void DLinkedList<TYPE>::display(){
cout << " Displaying List: ";
if(head->next==NULL) cout<<"This list is empty"<<endl;
else{
Node<TYPE>* curr = head->next;
while (curr!=NULL){
cout << curr->value << " ";
curr=curr->next;
}
}
cout << endl << endl;;
}
}
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;
}
}
Explanation / Answer
#include<conio.h>
#include<stdlib.h
#include<dos.h
#include <iostream.h>
#include<string.h>
#include<fstream.h>
usingnamespace std;
struct node
{
int data;
node *next;
node *previous;
};
void addnode();
void deletenode();
void display();
void show();
void search();
node *start=NULL, *tmp1, *tmp2, *tmp3;
int main()
{
char ch;
do
{
char i;
cout<<"Press 'A' to add node , 'D' to delete"<<endl;
cout<<" 'S' for search, 'V' for display ,'e' for backward display"<<endl;
cin>>k;
switch (k)
{
case'A':
addnode();
break;
case'D':
deletenode();
break;
case'V' :
display();
break;
case'S':
search();
break;
case'E':
show();
break;
default:
cout<<"invalid input"<<
break;
}
cout<<"want to continue more yes/no"<<endl;
cin>>choice;
}
while(choice!='n');
return 0;
}
void addnode()
{
char r;
tmp1=new node;
cout<<"enter int to store"<<endl;
cin>>tmp1->data;
cout<<"press 'S' to add in start,'M' for midd , 'E' for end"<<endl;
cin>>r;
switch (r)
{
case'S':
{
start=tmp1;
tmp1->next=NULL;
tmp1->prev=NULL;
}
else
{
tmp2=start;
tmp1->next=tmp2;
tmp1->prev=NULL;
start=tmp1;
tmp2->prev=tmp1;
}
break;
case'E':
{
start=tmp1;
tmp1->next=NULL;
tmp1->prev=NULL;
}
else
{
tmp2=start;
while(tmp2->next!=NULL)
tmp2=tmp2->next;
tmp2->next=tmp1;
tmp1->prev=tmp2;
tmp1->next=NULL;
}
break;
case'M':
cout<<"enter node "<<endl;
cin>>num;
tmp2=start;
for(int k=0;k<num;k++)
{
if(start==NULL)
cout<<"given node not available"<<endl;
else
{
tmp3=tmp2;
tmp2=tmp2->next;
}
}
tmp1->next=tmp2;
tmp3->next=tmp1;
tmp1->prev=tmp3;
tmp2->prev=tmp1;
break;
}
}
void display()
{
tmp3=start;
if(start==NULL)
cout<<"no node to show"<<endl;
else
{
while(tmp3->next!=NULL)
{
cout<<"Data stored is "<<tmp3->data<<" at "<<tmp3<<endl;
tmp3=tmp3->next;
}
cout<<"Data stored is "<<tmp3->data<<" at "<<tmp3<<endl;
}
}
void search()
{
int p;
cout<<"enter to search"<<endl;
cin>>p;
tmp1=start;
while(tmp1->next!=NULL)
{
if(tmp1->data==p)
{
cout<<tmp1->data<<" is stored in "<< temp1->next<<endl;
}
tmp1=tmp1->next;
}
}
void deletenode()
{
char d;
cout<<"press 'S' to delete from start,'M' for midd , 'E' for end"<<endl;
cin>>d;
switch (d)
{
case'S':
{
cout<<"no node to delete"<<endl;
}
else
{
tmp1=start;
start=start->next;
start->previous=NULL;
delete tmp1;
}
break;
case'E':
{
cout<<"no node to delete"<<endl;
}
else
{
tmp1=start;
while(tmp1->next!=NULL)
{
tmp2=tmp1;
tmp1=tmp1->next;
}
delete tmp1;
tmp2->next=NULL;
}
break;
case'M':
cout<<"enter node you want to delete"<<endl;
cin>>num;
tmp1=start;
for(int k=1;k<num;++)
{
if(start==NULL)
cout<<" node does not exist"<<endl;
else
{
tmp2=tmp1;
tmp1=tmp1->next;
}
}
tmp3=tmp1->next;
tmp2->next=tmp3;
tmp3->previous=tmp2;
delete tmp1;
break;
}
}
void show()
{
tmp3=start;
if(start==NULL)
cout<<"no node to display"<<endl;
else
{
while(tmp3->next!=NULL)
{
tmp3=tmp3->next;
}
while(tmp3->previous!=NULL)
{
cout<<"Data stored is "<<tmp3->data<<" at "<<tmp3<<endl;
tmp3=tmp3->previous;
}
cout<<"Data stored is "<<tmp3->data<<" at "<<tmp3<<
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.