mardi 5 avril 2016

Working on a B-List data structure and I am met with crashing error

I am working on a B-List Data structure for a school project. The basic idea is to make a hybrid data structure that combines the ideas of a doubly linked list and a partially filled array ... also when inserting or deleting a node I want to insert/delete the element inside the array and not the entire node. I have completed the is_empty(), size(), front(), back(), add_front(Element e), add_back(Element e) functions. (Note that for the assignment I am to convert the functions from the std::deque functions to my own for this project, hence the other functions having deque stuff)

When running the program I am met with the windows message that my project.exe has stopped working as seen below in the image attached.

The header file I have attached is also accompanied by a main.cpp file which tests the functions and should not be modified which I have also attached.

windows crash message

Here is the B-list Header:

 #pragma once

    #include <cassert>
    #include <deque>
    using std::deque;

// TODO: delete the following #include
#include <deque>

const int B_NODE_CAPACITY = 16;

// TODO: create a template class called BNode that represents a
// doubly-linked node holding a fixed-capacity array of
// B_NODE_CAPACITY elements.
template <class Element>
struct BNode {

    BNode() { // default constructor
        node[B_NODE_CAPACITY]; //element of BNode holding an array of B_NODE_CAPACITY elements.
        node_size = (sizeof(node) / sizeof(*node));

        Nhead = &node[0]; //pointers to head/tail elem in each "array"
        if (node_size == 0) {
            Ntail = nullptr;
        }
        else {
            Ntail = &node[node_size-1];
        }
    }

    ~BNode() {
        auto temp = Nhead->next;
        while (temp != Ntail) {
            auto temp_next = temp->next;
            delete temp;
            temp = temp_next;
        }
        // Clean up the sentinels created in the constructor.
        delete Nhead;
        delete Ntail;
    }

    Element node[B_NODE_CAPACITY]; //element of BNode holding an array of B_NODE_CAPACITY elements.
    int node_size = 0;
    int index = 0; //used for indexing elements.

    BNode <Element> * next = nullptr; //pointers to next/prev elem in each "array"
    BNode <Element> * prev = nullptr;

    Element * Nhead = nullptr; //pointers to head/tail elem in each "array"
    Element * Ntail = nullptr;
};


template <typename Element>
class BList {
public:
    // These two statements tell the compiler to delete the the copy and
    // assignment constructors.  If you get an error at these lines, you are
    // attempting to copy a list, so don't do that! (because the destructor 
    // will double delete your nodes)!
    BList(const BList&) = delete;
    BList& operator=(const BList&) = delete;

    BList() {
        list_head = nullptr;
        list_tail = nullptr;
    }

    ~BList() {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        /* wrong
        auto temp = list_head->next;
        while (temp != list_tail) {
        auto temp_next = temp->next;
        delete temp;
        temp = temp_next;
        }
        // Clean up the sentinels created in the constructor.
        delete list_head;
        delete list_tail;
        */
    }

    bool is_empty() {

        return list_head == nullptr;
    }

    int size() {

        int size = 0;
        BNode <Element> * temp = list_head;
        while (temp != nullptr) {
            size += temp->node_size;
            temp = temp->next;
        }

        return size;
    }

    Element front() {

        assert(list_head != nullptr); // make sure the list is not empty
        return list_head->node[0];
    }

    Element back() {

        assert(list_head != nullptr); // make sure the list is not empty
        return list_tail->node[(list_tail->node_size) - 1];
    }

    void add_front(Element e) {


        if (list_head->node_size = B_NODE_CAPACITY || list_head == nullptr) { // create a new Node if the node is full or the list is empty
            BNode <Element> * temp = new BNode <Element>;
            temp->node[0] = e; // inserts element at the beggining of the arrray
            temp->prev = nullptr;
            temp->next = list_head;
            list_head->prev = temp;
            list_head = temp;
        }

        else {// else: slide the elements of the array down one and insert at beggining
            int holder = 0;
            for (int i = list_head->node_size; i >= 0; i--) {
                holder = list_head->node[i];
                if (i == 0) {
                    list_head->node[i] = e;
                }
                else {
                    list_head->node[i] = list_head->node[i - 1];
                }
                list_head->node[i+1] = holder;
            }
        }
    }

    void add_back(Element e) {

        if (list_tail->node_size = B_NODE_CAPACITY || list_tail == nullptr) { // create a new Node if the node is full or the list is empty
            BNode <Element> * temp = new BNode <Element>;
            temp->node[0] = e; // inserts element at the beggining of the arrray
            temp->next = nullptr;
            temp->prev = list_tail;
            list_tail->next = temp;
            list_tail = temp;
        }

        else {// else: insert the element at the end of the array
            list_tail->node[list_tail->node_size] = e; // inserts element at the end of the arrray
        }
    }

    void remove_front() {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        assert(list_head != nullptr); // make sure the list is not empty
        deque_.pop_front();
    }

    void remove_back() {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        assert(list_head != nullptr); // make sure the list is not empty
        deque_.pop_back();
    }

    Element get(int index) {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        check_index(index);
        return deque_.at(index);
    }

    void set(int index, Element e) {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        check_index(index);
        deque_.at(index) = e;
    }

    void clear() {
        // TODO: re-implement this function to operate on BNode objects
        // instead of just using std::deque
        deque_.clear();
    }

private:
    // TODO: change this from a std::deque to head and tail pointers
    // into a doubly-linked list of BNode objects.
    std::deque<Element> deque_;

    BNode <Element> * list_head = nullptr;
    BNode <Element> * list_tail = nullptr;

    void check_index(int index) {
        assert(index >= 0 && index < size());
    }

};

Here is the main.cpp for testing:

    #include <cassert>
#include <iostream>

#include "blist.h"

using namespace std;


void GenerateBack(BList<int>& list, int start, int end) {
  for (int i = start; i < end; i++)
      list.add_back(i);
}

void GenerateFront(BList<int>& list, int start, int end) {
  for (int i = start; i < end; i++)
      list.add_front(i);
}

void AddBackTest() {
  cout << "BList::add_back" << endl;
  BList<int> empty, one, three, thousand;

  assert(empty.is_empty());
  assert(one.is_empty());
  assert(three.is_empty());
  assert(thousand.is_empty());
  assert(0 == empty.size());
  assert(0 == one.size());
  assert(0 == three.size());
  assert(0 == thousand.size());

  GenerateBack(one,      1, 2);
  GenerateBack(three,    1, 4);
  GenerateBack(thousand, 1, 1001);

  cout << "BList::is_empty" << endl;
  assert(empty.is_empty());
  assert(!one.is_empty());
  assert(!three.is_empty());
  assert(!thousand.is_empty());

  cout << "BList::size" << endl;
  assert(0 == empty.size());
  assert(1 == one.size());
  assert(3 == three.size());
  assert(1000 == thousand.size());

  cout << "BList::front" << endl;
  assert(1 == one.front());
  assert(1 == three.front());
  assert(1 == thousand.front());

  cout << "BList::back" << endl;
  assert(1 == one.back());
  assert(3 == three.back());
  assert(1000 == thousand.back());
}

void AddFrontTest() {
  cout << "BList::add_front" << endl;
  BList<int> hundred;

  for (int i = 0; i < 100; i++) {
    hundred.add_front(i);
    assert(!hundred.is_empty());
    assert(hundred.size() == (i+1));
    assert(hundred.front() == i);
    assert(hundred.back() == 0);
  }

  for (int i = 0; i < 100; i++) {
    // std::cout << "i: " << i << " = " << hundred.get(99-i) << "\n";
    assert(hundred.get(i) == 99-i);
  }
}


void RemoveFrontTest() {
  cout << "BList::remove_front" << endl;
  BList<int> hundred;
  GenerateBack(hundred, 0, 100);

  for (int i = 0; i < 100; ++i) {
    assert(hundred.size() == 100-i);
    assert(hundred.front() == i);
    assert(hundred.back() == 99);
    hundred.remove_front();
  }
}

void RemoveBackTest() {
  cout << "BList::remove_back" << endl;

  BList<int> hundred;
  GenerateBack(hundred, 0, 100);

  // simultaneously remove elements from both ends
  for (int f = 0, b = 99, size = 100; f < 50; f++, b--, size-=2) {
    assert(!hundred.is_empty());
    assert(hundred.front() == f);
    assert(hundred.back() == b);

    // std::cout << "size: " << size << " = " << hundred.size() << "\n";
    assert(hundred.size() == size);

    hundred.remove_front();
    hundred.remove_back();
  }

  assert(hundred.is_empty());
}


void GetTest() {
  cout << "BList::get" << endl;

  BList<int> thousand;
  GenerateBack(thousand, 0, 1001);

  for (int i = 0; i < 1000; i++) {
    assert(thousand.get(i) == i);
  }
}

void SetTest() {
  cout << "BList::set" << endl;

  BList<int> hundred;
  GenerateBack(hundred, 0, 101);

  for (int i = 0; i < 100; i++) {
    hundred.set(i, -i);
    assert(hundred.get(i) == -i);
  }
}

// This main() function performs unit tests to confirm that the BList
// class is implemented properly.
int main() {
  cout << "BList tests:" << endl << endl;

  AddBackTest();
  AddFrontTest();
  RemoveFrontTest();
  RemoveBackTest();
  GetTest();
  SetTest();

  return 0;
}

Thanks in advance for the help!!!!

Aucun commentaire:

Enregistrer un commentaire