Data structure in C++ So my professor told me I had these problems for my code..
ID: 3863112 • Letter: D
Question
Data structure in C++
So my professor told me I had these problems for my code.. how can I fix these?? thank you!!
1. In your insert you are not updating previous->next->prev to
point to the new node.
2. Similarly for del. Check your list-modifying methods to make
sure they are correctly updating *both* the next and prev
pointers.
3. operator+ returns a dlist, not an int.
My code:
#include "dlist.h"
dlist::node*dlist::at(int n){
node*current = head();
while(n != 0){
current= current->next;
n--;
}
return current;
}
void dlist::insert(node *previous, int value){
node*n = new node{value, previous -> next,previous};
previous -> next = n;
}
void dlist::del(node* which){
node*c= which -> next;
which -> next = which-> next-> next;
delete c;
}
void dlist::push_back(int value){
node*c = tail();
insert(c,value);
}
void dlist::push_front(int value){
insert(head(), value);
}
void dlist::pop_front(){
node*n = head();
n = head() -> next;
delete n;
}
void dlist::pop_back(){
node*n = tail();
n = tail() -> prev;
delete n;
}
int dlist::size(){
node*c = head();
int s = 0;
while(c){
c = c -> next;
s++;
}
return s;
}
bool dlist::empty(){
if(size() == 0)
return true;
else
return false;
}
std::ostream& operator<< (std::ostream& out, dlist& l){
dlist::node*c = l.head();
while(true){
out << c;
c = c-> next;
return c;
}
}
bool operator== (dlist& a, dlist& b){
dlist::node* ca = a.head();
dlist::node* cb = b.head();
while(ca&&cb){
if(ca-> next != cb->next)
return false;
else{
ca = ca->next;
cb = cb->next;
}
}
if(ca== nullptr && cb == nullptr)
return true;
else
return false;
}
dlist operator+ (dlist& a, dlist& b){
dlist::node* ca = a.head();
dlist::node* cb = b.head();
int result;
while(ca&&cb){
ca + cb = result;
ca = ca -> next;
cb = cb -> next;
}
return result;
}
dlist reverse(dlist& l){
dlist l2;
dlist::node* c = l.head();
while(c->next!=l.tail()){
l2.push_front(c->next->value);
c = c-> next;
}
return l2;
}
"dlist.h"
#pragma once
/*
dlist.h
Doubly-linked lists of ints
*/
#include
class dlist {
public:
dlist() { }
// Implement the destructor, to delete all the nodes
~dlist();
struct node {
int value;
node* next;
node* prev;
};
node* head() const { return _head; }
node* tail() const { return _tail; }
// **** Implement ALL the following methods ****
// Returns the node at a particular index (0 is the head).
node* at(int);
// Insert a new value, after an existing one
void insert(node *previous, int value);
// Delete the given node
void del(node* which);
// Add a new element to the *end* of the list
void push_back(int value);
// Add a new element to the *beginning* of the list
void push_front(int value);
// Remove the first element
void pop_front();
// Remove the last element
void pop_back();
// Get the size of the list
int size();
// Returns true if the list is empty (size == 0)
bool empty();
private:
node* _head = nullptr;
node* _tail = nullptr;
};
// **** Implement ALL the following functions ****
/* out << l
Prints a list to the ostream out. This is mostly for your convenience in
testing your code; it's much easier to figure out what's going on if you
can easily print out lists!
*/
std::ostream& operator<< (std::ostream& out, dlist& l);
/* a == b
Compares two lists for equality, returning true if they have the same
elements in the same positions. (Hint: it is *not* enough to just compare
pointers! You have to compare the values stored in the nodes.)
*/
bool operator== (dlist& a, dlist& b);
/* a + b
Returns a new list consisting of all the elements of a, followed by all the
elements of b (i.e., the list concatenation).
*/
dlist operator+ (dlist& a, dlist& b);
/* reverse(l)
Returns a new list that is the *reversal* of l; that is, a new list
containing the same elements as l but in the reverse order.
*/
dlist reverse(dlist& l);
Explanation / Answer
/*
I Have modified the code and commented the reasons behind it.
Kindly remove your existing commented code before verifying.
*/
void dlist::insert(node *previous, int value){
// Assuming insert is never called on
// empty list
node*n = new node{value, previous -> next,previous};
previous -> next = n;
// Check if next is not null
if(n->next != null){
n->next->prev = n;
}
}
void dlist::del(node* which){
node*c= which -> next;
if(which->prev != null)
which->prev->next = c;
if(c != null)
c->prev = which->prev;
delete which;
}
void dlist::push_back(int value){
// We have to check if the list is empty
if(empty()){
node* c = new node(value,null,null);
node* h = head();
node* t = tail();
h = c;
t = h;
}
else{
node*c = tail();
insert(c,value);
}
}
void dlist::push_front(int value){
// Can't use this as it will insert after existing head and not at the beginning
// insert(head(), value);
node* h = head();
if(h == null){
h = new node(value,null,null);
t = h;
}
else{
node* h = head();
node* c = new node(value,null,null);
c->next = h;
h->prev = c;
h = c;
}
}
void dlist::pop_front(){
node*n = head();
if(n != null){
node* temp = n;
n = n->next;
delete temp;
}
}
void dlist::pop_back(){
node*n = tail();
if(n != null){
node* temp = n;
if(n->prev != null){
n->prev->next = null;
}
n = n->prev;
delete temp;
}
}
int operator+ (dlist& a, dlist& b){
// Assuming the value contained in
// two lists have to be added
dlist::node* ca = a.head();
dlist::node* cb = b.head();
int result;
while(ca&&cb){
result = ca->value + cb->value;
ca = ca -> next;
cb = cb -> next;
}
return result;
}
dlist reverse(dlist& l){
dlist l2;
dlist::node* c = l.head();
/*
Wont work as for eg. head is never added to the reversed list
while(c->next!=l.tail()){
l2.push_front(c->next->value);
c = c-> next;
}
*/
while(c != null){
l2.push_front(c->value);
c = c->next;
}
return l2;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.