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.
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