don't click here

Help with some C++ for a class - implementing a dequeue

Discussion in 'Technical Discussion' started by Travelsonic, Oct 14, 2016.

  1. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    So, for my class, we were given the following header for a doubly linked list, and asked to implement some functions which I will post a bit later, when I reach the point where I am asking for help. For now I wanna focus on the list, node definitions given to us:

    Now, here's my problem. Last time I did data structures, I used C++, with classes. I didn't touch structs... in fact, at the college I was enrolled in at the time, the only time I touched structs was in a beginning programming class, and it was for like 1 assignment, before even learning about pointers., nor did I alias any with typedefs, so this for me has been a bit confusing as hell so far as how to work backwards, look at how I need to handle the List object, and the underlying node. Specifically, I'm not sure I am doing it right Also, it's been a couple of years since I really did anything C++.

    So... NodeType is a pointer to a NodeType.... and List is typedefed as a NodePtr, so... I can treat the List object as a pointer to a NodeType?
     
  2. SupperTails66

    SupperTails66

    Tech Member
    1,109
    7
    18
    In C++, the only difference between a class and a struct is that, until you make an explicit public:/private:/protected: declaration, every member of a class is private by default and every member of a struct is public by default. Or at least that's how it's explained in Programming Principles and Practices Using C++; if there's some further technical distinction, someone better versed in the language than I am can tell you, but it's probably not relevant to your needs anyway.

    Your interpretation of the typedefs is correct (assuming you meant to say "NodePtr is a pointer to a NodeType"). The terminology here seems a bit strange to me -- without seeing the rest of the code, I'm not sure why you would typedef NodePtr to List. It probably makes more sense in context.
     
  3. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    The rest of the header includes the definitions of the functions we need to implement.
    Now, here's another problem: I noticed that the functions taking in a pointer to a List are taking in a pointer. This shows how long it has been since last doing C++, but wouldn't I still be passing by value, creating a copy of,it, rather than modifying the original? Wouldn't I need to add the address-of operator so it is actually being passed by reference? IF so, I am gonna hit a brick wall quickly, as my prof. seems to not want ANY changes to the declarations for the functions we are going to be implementing. Then again, part of me feels like I am missing something, a trick so to speak that would let me get away with not explicitly using the address-of operator, or I am just a grade-a dumbass. >_<
     
  4. SF94

    SF94

    Tech Member
    NodePtr is of type NodeType*, and List is the same as NodePtr. I still get confused by typedefs sometimes, which is why I now prefer using.


    Pretty much. They'll both perform this job functionally the same as far as usage goes. Once compiled though, a class will have a vtable, whereas a struct typically won't. But that doesn't really matter here.

    So you're confused by the functions that take List*? The functions that take in List* (where List is NodeType*, meaning List* is NodeType**) do so in order to change where your NodeType* is pointing. So if you have a List variable, you would in fact need to pass it in using &. This will give the function a pointer to your pointer. POINTERS EVERYWHERE!

    In case my explanation wasn't clear, I'll use clearList as an example. Here's what our (fake) definition of clearList looks like.

    This is effectively the same as taking in a pointer to say, an int, and changing its value by *value = 1234. The only difference is that our value is yet another pointer.
    Now let's put it to use:

     
  5. SupperTails66

    SupperTails66

    Tech Member
    1,109
    7
    18
    Whoops, ninja'd. Here's what I wrote before I saw the previous post, in case it helps:

    First, this is actually C code. I'm guessing you'll be asked to do an object-oriented rewrite of this into a "proper" List class in a future assignment.

    Remember, List has been typedefed to a pointer; List* is actually a pointer to a pointer (specifically, it's the same as writing NodeType**). That means you're altering the pointer to the List, not the nodes themselves. For example:

    Code (Text):
    1. void func(List* list) {
    2.   list = NULL;
    3. }
    4.  
    5. List lst;
    6. initializeList(lst);
    7. List samelst = lst;
    8. func(lst);               // lst is now NULL, but the list data is intact
    9.                          // and can be accessed through samelst
    The name of the List typedef somewhat obscures this; personally I would have called it "ListPtr", but perhaps the idea is to maintain consistency if you do rewrite this in C++ later.
     
  6. SF94

    SF94

    Tech Member
    Much cleaner than my example! :specialed:
     
  7. Black Squirrel

    Black Squirrel

    no reverse gear Wiki Sysop
    8,544
    2,465
    93
    Northumberland, UK
    steamboat wiki
    What's the goal here - to make your own linked list, or to familiarise yourself with typedefs? Or maybe just pointers?

    Because if it's the former, the first thing I'd do is completely ignore all the typedefs until the very end, because they're not helping anyone in this context (the idea of writing "List list" at any point sounds like really bad news to me). Or rename the typedefs so that they're not horrible - whatever floats your boat.

    I think the jist of everything pointer related has already been explained, and structs are basically classes where everything is public.


    (alternatively use the standard list, and when someone asks, claim it's faster and better than anything you can make and it's already been widely adopted :specialed: )
     
  8. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    Can't - have to implement the functions given to us.
     
  9. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,161
    65
    28
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    There is nothing else, that is literally all of the differences between class and struct in c++.

    The class has a vtable if and only if it has virtual member functions, or inherits from a base class or struct that has virtual member functions. Likewise for struct.
     
  10. SF94

    SF94

    Tech Member
    Oh right, duh. It even says it right in the article I linked. As for structs, I guess I never thought to use virtual functions in structs in any of my programs (that I've disassembled out of curiosity, at least).
     
  11. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    So I have made a hell of a lot of progress.

    I think.

    But now, I am stuck here, with this function to implement:
    (and, conversely, the popBack function) because of the use of the const qualifier for the parameter. Remember, it has been a few years since I touched this stuff. I am obviously supposed to modify the list so I pop off the node, but the fact that the list is being passed as a const is throwing me off a little.
     
  12. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    Pardon the double post... god, I feel dumb, it seems maybe the use of const is so we are forced to utilize pointers...? I thought I'd be able to go through a pointer referencing the original list, but I KNOW I am doing something wrong. I am ready to pull my hair out of my head.
    For example, PushFront, here is what I tried to throw together, not working right (no seg faults luckily).

    So far as the node not actually appearing to be inserted properly. Again, been easily 2 1/2 years at LEAST since I last did this, not as if I am freshly trying to learn C/C++. :P

    So, I did a little thing in my function to dump addresses - seems my problem is not changing what IS the head, as that address is being changed correctly, but setting the next node in that new head to be what WAS previously the head. Ugh.
     
  13. SF94

    SF94

    Tech Member
    If I understand your code correctly, you were trying to change the value of the "list" parameter (the location that it points to). Is that right? If so, it seems like you don't have the hang of pointers yet. I don't blame you; it can be pretty confusing. Let me try to explain what your code is doing:

    Your variable here, listPtr, is a local variable. By assigning it to the value of "list", what you're doing is: "listPtr, you now point to the same data that list does".

    This is all fine so far.

    Here however, you're doing the same thing you did in the first quote. "listPtr, you now point to the same data that newHead does." This will not modify the original pointer or the data it points to in any way. That being said, the data that is pointed at by a const pointer cannot be modified using that const pointer (at least, in MSVC++ 2015) (e.g: it points to constant data or should be treated as such; therefore it cannot be changed). I also don't know what the ListInfo type is, so I don't know whether or not it would have anything useful in it for this situation.
     
  14. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    ListInfo is typedef'd from an int type.
     
  15. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    I am confused as to what the hell I should do - seeing I can't change the parameters for the functions the prof. gave us (wants us to keep it all as-is)/the parameter is const.
     
  16. Black Squirrel

    Black Squirrel

    no reverse gear Wiki Sysop
    8,544
    2,465
    93
    Northumberland, UK
    steamboat wiki
    const is another thing I'd probably ignore in this case until the very end. Because again, further layer of complication that will mess with your understanding of linked lists.


    Basically it's just:
    - make a new node
    - give it a value
    - tell the node at the front of the list to point to your new node


    best bet is to get it working, then worry about which bits might be accidentally modified later.
     
  17. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    OK update: I went to the prof. last week, was told I can go use C++ (which means going to an implementation using classes) - just about got the damn thing working. Such a relief., being able to use what I am used to, have done before. Not that I don't want to learn how to do this in C, but I've got some catching up to do, and the fact I can do this with C++ instead of having to do it in C means I can do that very quickly.
     
  18. Travelsonic

    Travelsonic

    Member
    827
    20
    18
    That said, pardon the double post, I am still having one minor issue with popping nodes off the back of the list (and maybe pushing them on the back as well) - pushing and popping off the front of the list I have down OK (I think), doing so from the other end gives me segmentaton faults though.

    Here are the linked list class function implementations I have done:

    #include "list.h"
    // list CLASS FUNCTION IMPLEMENTATIONS:
    // CONSTRUCTOR(S) AND DESTRUCTOR:
    // Constructor(s):
    list::list(){
    head = NULL;
    tail = NULL;
    }
    // Destructor:
    list::~list(){
    while(head != tail){
    popFront();
    }
    delete head;
    delete tail;
    head = NULL;
    tail = NULL;
    }
    // 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){
    if((head != NULL) && (tail != NULL)){return;} // Prevents us from just calling it again without clearing the list first.
    head = new node(inData, head, head);
    tail = head;
    }
    // Adds a value to the front of the list
    void list::pushFront(const listInfo & inData){
    if(head == NULL){initializeList(inData); return;}
    head = new node(inData, head, tail);
    head->getNext()->setPrev(head);
    }
    // Adds a value to the back of the list
    void list::pushBack(const listInfo & inData){
    if(tail == NULL){initializeList(inData); return;}
    tail->setNext(new node(inData));
    tail = tail->getNext();
    }
    // Remove and return the value at the front of the list
    listInfo list::popFront(){
    if(head==NULL){return -1;}
    listInfo nodeData = head->getData(); // Retrieve the data from the head 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(tail==NULL){return -1;}
    listInfo nodeData = tail->getData(); // Retrieve the data from the head node
    node * removed = tail;
    tail = tail->getPrev();
    delete removed;
    return nodeData;
    }
    // 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;
    }


    Probably some mundane, stupid fucking thing I am messing up...