- Posts: 720
- Joined: 01-March 05
After talking to my professor, I found out I can do the projects for my operating systems class in C++. What a relief, as now I can work with that which I am more familiar with.
My troubles in debugging my dequeue implementation have not gone away fully, however, and thus I still need help.
I can push and pop off the front no issue. My problem is, I'm not sure if everything is OK. Right now, my biggest problem seems to be an incorrect count - which is making me question if everything is ship shape with my push and pop functions.
(it currently shows a value one more than the number of values I try pushing in my test program). I would appreciate it greatly if someone could check my code, and help me if there are in fact any issues.
EDIT: I realized that in my push and pop functions I might be able to consolidate a few lines of condition checking, see comment in function for issue I face there.
Here is the code I have so far:
EDIT: 7:18PM: Replaced the copypaste of list.cpp with the current version of my code.
node.h: Contains the definition for my node class.
node.cpp: Contains the function implementations for my node class.
list.h: Contains the definition for my list class.
list.cpp: Contains the function implementations for my list class.
main.cpp: The test program for my linked list.
My troubles in debugging my dequeue implementation have not gone away fully, however, and thus I still need help.
I can push and pop off the front no issue. My problem is, I'm not sure if everything is OK. Right now, my biggest problem seems to be an incorrect count - which is making me question if everything is ship shape with my push and pop functions.
(it currently shows a value one more than the number of values I try pushing in my test program). I would appreciate it greatly if someone could check my code, and help me if there are in fact any issues.
EDIT: I realized that in my push and pop functions I might be able to consolidate a few lines of condition checking, see comment in function for issue I face there.
Here is the code I have so far:
EDIT: 7:18PM: Replaced the copypaste of list.cpp with the current version of my code.
node.h: Contains the definition for my node class.
Spoiler
#ifndef NODE_H #define NODE_H #include <stddef.h> // So NULL is not undeclared/undefined // TYPEDEFS: typedef int nodeInfo; // CLASS DEFINITION: // node class: class node{ public: // CONSTRUCTOR(S) AND DESTRUCTOR: // Constructor: node(const nodeInfo inData = 0, node * inNext = NULL, node * inPrev = NULL); // Default parameters for data, next, prev // Destructor: ~node(); // ACCESSORS AND MUTATORS: // Accessors: nodeInfo getData() const; node * getNext(); const node * getNext() const; node * getPrev(); const node * getPrev() const; // Mutators: void setData(const nodeInfo & inData); void setNext(node * inNext = NULL); void setPrev(node * inPrev = NULL); // OVERLOADED OPERATORS operator=(const node * copyNode); operator==(const node * compareNode); private: nodeInfo data; // Node data value node * next; // In a linked list, the next node node * prev; // In a linked list, the previous node }; #endif
node.cpp: Contains the function implementations for my node class.
Spoiler
#include "node.h" // NODE CLASS FUNCTION IMPLEMENTATIONS // CONSTRUCTOR(S) AND DESTRUCTOR: // Constructor(s): node::node(const nodeInfo inData, node * inNext, node * inPrev){ // Default parameters for data, next, prev data = inData; next = inNext; prev = inPrev; } // Destructor: node::~node(){ //delete next; //delete prev; //next = NULL; //prev = NULL; } // ACCESSORS AND MUTATORS: // Accessors: nodeInfo node::getData() const{ return data; } node * node::getNext(){ return next; } const node * node::getNext() const{ return next; } node * node::getPrev(){ return prev; } const node * node::getPrev() const{ return prev; } // Mutators: void node::setData(const nodeInfo & inData){ data = inData; } void node::setNext(node * inNext){ next = inNext; } void node::setPrev(node * inPrev){ prev = inPrev; } // OVERLOADED OPERATORS node::operator=(const node * copyNode){ data = copyNode->data; next = copyNode->next; prev = copyNode->prev; } node::operator==(const node * compareNode){ return ((data == compareNode->getData()) && (next == compareNode->getNext()) && (prev == compareNode->getPrev())) ? true : false; }
list.h: Contains the definition for my list class.
Spoiler
#ifndef LIST_H #define LIST_H #include <stddef.h> // So NULL is not undeclared/undefined #include "node.h" // TYPEDEFS typedef int listInfo; // CLASS DEFINITION: // list class: class list{ public: // CONSTRUCTOR(S) AND DESTRUCTOR: // Constructor(s): list(list * inCopyList = NULL); // Default constructor -> can take a list to copy, but doesn't have to (param/arg value defaults to NULL) // Destructor: ~list(); // ACCESSORS AND MUTATORS: // Accessors: bool isEmpty(); // Return true if the only element on the list is the header, otherwise return false bool findInList(const listInfo value); // Return true if the value appears in the list, otherwise, return false size_t getLength(); // Return the length of the list size_t getLength() const; // Return the length of the list - const version of the function node * getHead(); // Return the head node of our list const node * getHead() const; // Return the head node of our list - const version of the function node * getTail(); // Return the tail node of our list const node * getTail() const; // Return the tail node of our list - const version of the function // Mutators: void initializeList(const listInfo & inData = 0); // Initialize the list with the header pointing at itself void pushFront(const listInfo & inData); // Adds a value to the front of the list void pushBack(const listInfo & inData); // Adds a value to the back of the list listInfo popFront(); // Remove and return the value at the front of the list listInfo popBack(); // Remove and return the value at the back of the list void copyList(list * inCopyList); // Copy the contents from one list into this list. void clearList(); // Clear the list, setting the head (and tail) to NULL // OVERLOADED OPERATORS: void operator=(list * inCopyList); bool operator==(list * inCompareList); private: node * head; // The head of our list node * tail; // The tail of our list }; #endif // LIST_H
list.cpp: Contains the function implementations for my list class.
Spoiler
#include "list.h" // list CLASS FUNCTION IMPLEMENTATIONS: // CONSTRUCTOR(S) AND DESTRUCTOR: // Constructor(s): // Default Constructor: Can take in a list as an argument, default argument is NULL as per function definition in list.h list::list(list * inCopyList){ // If inCopyList is NULL, or inCopyList is empty, just set head and tail to NULL if((inCopyList == NULL) || inCopyList->isEmpty()){ head = NULL; tail = NULL; } // Otherwise, fill this list by popping off from the rear of the copy list, // and push them onto the front of this list, preserving order. else{ // "copy" the list by pushing onto the front of THIS list values being // popped off the back of the list passed to the function. while(!inCopyList->getHead()){pushFront(inCopyList->popBack());} } } // Destructor: list::~list(){ } // ACCESSORS AND MUTATORS: // Accessors: // Return true if the only element on the list is the header, otherwise return false bool list::isEmpty(){ return ((head == NULL) || ((head->getNext()) == NULL) || ((head->getNext()) == head)) ? true : false; } // Return true if the value appears in the list, otherwise, return false bool list:: findInList(const listInfo value){ node * tmpNode; // Create a temporary node for iterating through the nodes in the list bool result = false; // Create a second variable to hold our return value, initialized false so it only changes if we find our value, // Iterate through the list checking each node's value // Since the list can be circular, checks against the node being // NULL, OR having a next node pointing back at the head. for(tmpNode = head; ((tmpNode != NULL) && (tmpNode->getNext() != head)); tmpNode = tmpNode->getNext()){ if((tmpNode->getData()) == value){result = true;} } delete [] tmpNode; // Free the memory allocated to tmpNode tmpNode = NULL; return result; } // Return the length of the list size_t list::getLength(){ const node * cursor; size_t len = 0; for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){ ++len; } return len; } // Return the length of the list - const version of the function size_t list::getLength() const{ const node * cursor; size_t len = 0; for (cursor = head; ((cursor != NULL) && (cursor->getNext() != head)); cursor = cursor->getNext()){ ++len; } return len; } // Return the head node of our list node * list::getHead(){ return head; } // Return the head node of our list - const version of the function const node * list::getHead() const{ return head; } // Return the tail node of our list node * list::getTail(){ return tail; } // Return the tail node of our list - const version of the function const node * list::getTail() const{ return tail; } // Mutators: // Initialize the list with the header pointing at itself void list::initializeList(const listInfo & inData){ head = new node(inData, head, head); tail = head; } // Adds a value to the front of the list void list::pushFront(const listInfo & inData){ if(isEmpty() || (head == NULL) || (tail == head)){initializeList(inData);} else{head = new node(inData, head, tail);} } // Adds a value to the back of the list void list::pushBack(const listInfo & inData){ if(isEmpty() || (tail == NULL) || (tail == head)){initializeList(inData);} else{ node * newBack = new node(inData, head, tail); tail->setNext(newBack); tail = newBack; } } // Remove and return the value at the front of the list listInfo list::popFront(){ if(isEmpty()){return -1;} // If our list is already empty, we needn't do anything more listInfo nodeData = head->getData(); // Retrieve our head's node data if(head == tail){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null else{ // Otherwise, we need to remove that node node * removed = head; head = head->getNext(); delete removed; } return nodeData; } // Remove and return the value at the back of the list listInfo list::popBack(){ if(isEmpty()){return -1;} // If our list is already empty, we needn't do anything more listInfo nodeData = tail->getData(); // Retrieve our tail's node data if(tail == head){head = NULL; tail = NULL;}// If this is the last node on the list, we can set both to null else{ // Otherwise, we need to remove that node node * removed = tail; tail = removed->getPrev(); tail->setNext(head); delete removed; } return nodeData; } // Copy the contents from one list into this list void list::copyList(list * inCopyList){ // If the list pointer is NULL, or the list is empty, just set head and tail to NULL if((inCopyList == NULL) || inCopyList->isEmpty()){return;} if(!isEmpty()){return;} // "copy" the list by pushing onto the front of THIS list values being // popped off the back of the list passed to the function. while(!inCopyList->getHead()){pushFront(inCopyList->popBack());} } // Clear the list, setting the head (and tail) to NULL void list::clearList(){ if(head == NULL){return;} while(head != tail){ popFront(); } head = NULL; tail = NULL; } // OVERLOADED OPERATORS: void list::operator=(list * inCopyList){ clearList(); copyList(inCopyList); } bool list::operator==(list * inCompareList){ bool isEqual = true; if((inCompareList == NULL) || (isEmpty() != inCompareList->isEmpty()) || (getLength() != inCompareList->getLength())){ isEqual = false; } node * a = getHead(); node * b = inCompareList->getHead(); while((a->getNext() != head) || (a->getNext() != inCompareList->getHead())){ if (a->getData() != b->getData()){isEqual = false;} a = a->getNext(); b = b->getNext(); } return isEqual; }
main.cpp: The test program for my linked list.
Spoiler
#include <cstdlib> #include <iostream> #include <stdio.h> #include "list.h" int main(){ list * list1 = new list(); std::cout << "New empty list created. List length: " << list1->getLength() << " nodes.\n\n"; for(int count = 0; count < 10; count++){ std::cout << "Putting value " << count << " into a node being inserted at the front of the list\n"; list1->pushFront(count); } std::cout << "List length: " << list1->getLength() << " nodes.\n\n"; std::cout << "Popping a node off the front of the list, with value of " << list1->popFront() << ".\n"; std::cout << "List length: " << list1->getLength() << " nodes.\nClearing list...\n"; list1->clearList(); std::cout << "List length: " << list1->getLength() << " nodes.\n\n"; for(int count = 0; count < 10; count++){ std::cout << "Putting value " << count << " into a node being inserted at the back of the list\n"; list1->pushBack(count); } std::cout << "List length: " << list1->getLength() << " nodes.\n\n"; listInfo inFindInfo; std::cout << "Enter a value to find in the list: "; std::cin >> inFindInfo; bool searchResult = list1->findInList(inFindInfo); if(searchResult){std::cout << "\nValue was found in the list.\n";} else{std::cout << "\nValue was NOT found in the list.\n";} //std::cout << "Popping a node off the back of the list, with value of " << list1->popBack() << ".\n"; //std::cout << "List length: " << list1->getLength() << " nodes.\n\n"; std::cout << "Creating a second linked list, copying list 1 to it...\n"; list * list2 = new list(list1); //list * list2 = new list(); //list2->copyList(list1); std::cout << "The length of this new list is " << list1->getLength() << ".\n\n"; std::cout << "Clearing the first list...\n"; list1->clearList(); std::cout << "First list new length: " << list1->getLength() << " nodes.\n\n"; std::cout << "Clearing the second list...\n"; list2->clearList(); std::cout << "Second list new length: " << list2->getLength() << " nodes.\n\n"; std::cout << "Both lists cleared. Freeing memory allocated to the list objects...\n\n"; delete [] list1; delete [] list2; list1 = NULL; list2 = NULL; std::cout << "Memory of both list objects deallocated. Program complete.\n"; return 0; }
This post has been edited by Travelsonic: 31 October 2016 - 06:18 PM