CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8

Thread: Dealing with Nodes

  1. #1
    Join Date
    Jun 2017
    Posts
    13

    Dealing with Nodes

    Currently working on a project and I would appreciate all the help that I can get.

    Here is the first part of the assignment:

    Instructions:
    Code:
    In this file, you declare a class named StringList.
     StringList is a modified version of NumberList class (Chapter 17), that is designed to store C++ strings
    in a linked list.
     Therefore, each node must store a string, not a number.
     The node structure must be declared within class, and a private attribute head points to the starting node.
     The class provides a default constructor that creates an empty linked list, and a destructor that releases
    all the nodes.
     The class also provides public member functions for inserting and deleting a node (see below for details).
     It also provides a public member function for displaying the list.
    Here is what I have so far, this is the StringList.h file.. Everything seems to be coming back error free.
    Code:
    #ifndef STRINGLIST_H
    #define STRINGLIST_H
    
    #include <iostream>
    #include <string>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    
    class StringList
    {
    private:
      //Declare a structure for the list
      struct listNode
      {
        string name;
        string a;
        struct listNode *next;
      };
    
      //Points to the starting Node
      listNode *head;
    
    public:
      //Constructor
      StringList()
      {
        head = NULL;
      }
    
      //Destructor
      ~StringList();
    
      //List Operations
      void insertNode(string a);
      void deleteNode(string a);
      void displayList() const;
      void deleteFront();
      void deleteBack();
      void clear();
    };
    
    #endif


    Here is the second part of the assignment, this I'm extremely confused about.
    Code:
    In this file, you provide definitions for the default constructor and the destructor for StringList.
     Make sure the destructor visits every node in the list and deletes every one of them from the heap.
     Define insertFront function to insert a new node into the front of the list. Therefore, the new node will
    be the new first node in the list. This function takes a string as a parameter.
     Define insertBack function to insert a new node into the back of the list. Therefore, the new node will be
    the new last node in the list. This function takes a string as a parameter.
     Define deleteFront function to delete the first node from the list. This function takes no parameter.
     Define deleteBack function to delete the last node from the list. This function takes no parameter.
     Define display function that displays the current contents (strings) of the list (display strings in a single
    line, separated by a space). This function takes no parameter.

    Here is what I have so far, I would appreciate if someone can guide in the right direction and teaching me how to define those four functions. Here is my StringList.cpp
    Code:
    #include <iostream>
    #include "StringList.h"
    
    using namespace std;
    
    //Constructor definition
    StringList::StringList()
    {
      head = nullptr;
    }
    
    //Destructor definition
    StringList::~StringList()
    {
      delete head;
      clear();
    }
    
    //deleteFront
    StringList::deleteFront()
    {
      if(head != NULL)
      {
        listNode *tmp = head -> next;
        delete head;
        head = tmp;
      }
    }
    
    StringList::displayList()
    {
      listNode *nodePtr;
    
      if(!head)
      {
        cout << "List is empty";
        return;
      }
      nodePtr = head;
      cout << "Here is the list: \n\t";
    
      while (nodePtr)
      {
        cout << nodePtr -> a << " -> ";
      }
      nodePtr = nodePtr -> next;
    }

  2. #2
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,262

    Re: Dealing with Nodes

    Code:
    StringList()
      {
        head = NULL;
      }
    ...
    //Constructor definition
    StringList::StringList()
    {
      head = nullptr;
    }
    You are defining the body of the default constructor in both the .h and .cpp files??

    Code:
    StringList::~StringList()
    {
      delete head;
      clear();
    }
    No. Assuming that clear() removes the entries from the list, it would also delete head. Also, clear() needs to use the value from head to traverse the list to remove the nodes. delete head should be the last thing done, not the first. Have you got the code for clear()?

    StringList is a modified version of NumberList class
    Have got the code for NumberList? Changing from storing a number to storing a string is quite trivial.

    Code:
    nodePtr = head;
      cout << "Here is the list: \n\t";
    
      while (nodePtr)
      {
        cout << nodePtr -> a << " -> ";
      }
      nodePtr = nodePtr -> next;
    Note that this would usually be coded as
    Code:
    for (auto nodePtr = head; nodePtr; nodePtr = nodePtr->next)
        cout << nodePtr -> a << " -> ";
    Define deleteBack function
    This requires the list to be traversed and then the last node deleted. The next pointer from the node prior to the one deleted is then set to nullptr.

    Define insertFront function
    Insert a new node at the front of the list. This needs head to be adjusted accordingly.

    Define insertBack function
    Insert a new node at the end of the list. This needs the list to be traversed to the end and then a new node added to the end with the next pointer of the was last node set to point to the the new last node.

    this I'm extremely confused about....someone can guide in the right direction
    If you are still having problems, you'll need to be more specific about the issues you are having. This exercise is just a simple single linked list.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.4)

  3. #3
    Join Date
    Jun 2017
    Posts
    13

    Re: Dealing with Nodes

    So this is what I have so far in StringList.h

    Code:
    – In this file, you declare a class named StringList.
    – StringList is a modified version of NumberList class (Chapter 17), that is designed to store C++ strings
    in a linked list.
    – Therefore, each node must store a string, not a number.
    – The node structure must be declared within the class, and a private attribute head points to the starting node.
    – The class provides a default constructor that creates an empty linked list, and a destructor that releases
    all the nodes.
    – The class also provides public member functions for inserting and deleting a node (see below for details).
    – It also provides a public member function for displaying the list.
    Code:
    #ifndef STRINGLIST_H
    #define STRINGLIST_H
    
    #include <iostream>
    #include <string>
    #include <string.h>
    #include <stdio.h>
    
    using namespace std;
    
    class StringList
    {
    private:
      //Declare a structure for the list
      struct listNode
      {
        string a;
        listNode *next;
      };
    
      //Points to the Node
      listNode *head;
      listNode *back;
    
    public:
      //Constructor
      StringList();
    
      //Destructor
      ~StringList();
    
      //List Operations
      void displayList();
      void deleteFront();
      void deleteBack();
      void insertFront(string a);
      void insertBack(string a);
    };
    
    #endif
    NO ERRORS
    _________________________________________________



    This is my second part:

    Code:
    – In this file, you provide definitions for the default constructor and the destructor for StringList.
    – Make sure the destructor visits every node in the list and deletes every one of them from the heap.
    – Define insertFront function to insert a new node into the front of the list. Therefore, the new node will
    be the new first node in the list. This function takes a string as a parameter.
    – Define insertBack function to insert a new node into the back of the list. Therefore, the new node will be
    the new last node in the list. This function takes a string as a parameter.
    – Define deleteFront function to delete the first node from the list. This function takes no parameter.
    – Define deleteBack function to delete the last node from the list. This function takes no parameter.
    – Define display function that displays the current contents (strings) of the list (display strings in a single
    line, separated by a space). This function takes no parameter.
    Code:
    #include <iostream>
    #include "StringList.h"
    
    using namespace std;
    
    //Constructor definition
    StringList::StringList()
    {
      head = nullptr;
    }
    
    //Destructor definition
    StringList::~StringList()
    {
      delete head;
      delete back;
    }
    
    //Inserting Front
    void StringList::insertFront(string a)
    {
      listNode *temp = new listNode;
      temp -> a;
      temp -> next = head;
      head = temp;
    }
    
    //Inserting Back
    void StringList::insertBack(string a)
    {
      listNode *temp = new listNode;
      temp -> a;
      temp -> next = back;
      head = temp;
    }
    
    //deleteFront
    void StringList::deleteFront()
    {
      if(head != NULL)
      {
        listNode *tmp = head -> next;
        delete head;
        head = tmp;
      }
    }
    
    void StringList::deleteBack()
    {
      if(head != NULL)
      {
        listNode *tmp = back -> next;
        delete back;
        back = tmp;
      }
    }
    
    void StringList::displayList()
    {
      listNode *nodePtr;
    
      if(!head)
      {
        cout << "List is empty" << endl;
        return;
      }
      for (auto nodePtr = head; nodePtr; nodePtr = nodePtr -> next)
        cout << nodePtr -> a << " " << endl;
    }
    NO ERRORS:

    _________________________________________________________________

    This is my third and final page:

    Code:
    – In this file, you define main function that tests StringList class.
    – You must first create a StringList object.
    1
    – Then start inserting new nodes, one at a time. Alternate between inserting into the front and into the
    back. Make sure to add at least 6 nodes.
    – Then start deleting nodes, one at a time. Alternate between deleting from the front and from the back.
    – Make sure all the nodes are deleted before terminating the program.
    – After each insertion or deletion, call display member function to display the updated list.
    – Make sure all the member functions are tested and shown to work properly, without missing any of them.
    – Note that the display function must be called pretty much every time a node is inserted or deleted.
    Otherwise the respective functionality will not be properly demonstrated and could lead to loss of points.
    – Also note that each member function should properly work regardless of the current list configuration
    (empty list, one-node list, or multiple-node list).
    Code:
    #include <iostream>
    #include <string>
    #include <iomanip>
    #include "StringList.h"
    #include "StringList.cpp"
    
    using namespace std;
    
    int main() {
    
    //Then start inserting new nodes, one at a time. Alternate between inserting into the front and into the
    //back. Make sure to add at least 6 nodes.
      StringList::StringList myList()
      {
        for(i = 0, i < 6, i++)
        {
          a++;
    //After each insertion or deletion, call display member function to display the updated list.
          myList.displayList();
        }
    //Then start deleting nodes, one at a time. Alternate between deleting from the front and from the back.
        for(i = 0, i < 6, i++)
        {
          a--;
        }
      }
    
      return 0;
    }
    Code:
    This one I had the most trouble with:
    1. How to insert up to 6 nodes & then delete them.
    2. Making sure that their all being displayed using displayList.
    Please help guide me in the right direction, and tell me where I'm making the biggest mistakes. I'm a total newbie when it comes to lists.
    Last edited by Semirxbih; July 21st, 2017 at 12:36 AM.

  4. #4
    Join Date
    Jun 2017
    Posts
    13

    Re: Dealing with Nodes

    The First and the Second page are error free, still need help with the final page.

    Unsure on how to insert one node at a time, which totals up to 6 & how to delete them one at a time.
    Last edited by Semirxbih; July 21st, 2017 at 12:54 AM.

  5. #5
    Join Date
    Jun 2017
    Posts
    13

    Re: Dealing with Nodes

    This is my new updated code on the final page:

    Code:
    – Then start inserting new nodes, one at a time. Alternate between inserting into the front and into the
    back. Make sure to add at least 6 nodes.
    – Then start deleting nodes, one at a time. Alternate between deleting from the front and from the back.
    – Make sure all the nodes are deleted before terminating the program.
    – After each insertion or deletion, call display member function to display the updated list.
    – Make sure all the member functions are tested and shown to work properly, without missing any of them.
    – Note that the display function must be called pretty much every time a node is inserted or deleted.
    Otherwise the respective functionality will not be properly demonstrated and could lead to loss of points.
    – Also note that each member function should properly work regardless of the current list configuration
    (empty list, one-node list, or multiple-node list).
    Code:
    #include <iostream>
    #include <string>
    #include <iomanip>
    #include "StringList.h"
    #include "StringList.cpp"
    
    using namespace std;
    
    int main() {
    
        string numbers = "Numbers:";
        StringList myList;
    
        for(int i = 0; i < 6; i++)
        {
            myList.insertBack(numbers + ' ' + to_string(i));
            myList.displayList();
        }
    
        return 0;
    }
    Needing to figure out how I can delete the nodes one by one.

  6. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,262

    Re: Dealing with Nodes

    Some comments

    Code:
    StringList::StringList()
    {
      head = nullptr;
    }
    back also needs to be initialised.

    Code:
    StringList::~StringList()
    {
      delete head;
      delete back;
    }
    No. You need to traverse the list deleting each node in the list. This is just deleting the head and back nodes and not the other ones.

    Code:
    void StringList::insertFront(string a)
    {
      listNode *temp = new listNode;
      temp -> a;
      temp -> next = head;
      head = temp;
    }
    The highlighted line extracts the value of a from the node but doesn't use it. It doesn't set the value of a in the node.
    If this is the first node to be inserted in the list, then back also needs to be set correctly.

    Code:
    void StringList::insertBack(string a)
    {
      listNode *temp = new listNode;
      temp -> a;
      temp -> next = back;
      head = temp;
    }
    No. Inserting at back isn't quite the same as inserting at head. The comment re a from above apply. back points to the last node of the list (usually called the tail). So the next pointer from the current value of back needs to be set to point to the new node and then back is set to point to the new node so that back always points to the last node in the list. head is only set if this is the first node inserted into the list.

    Code:
    void StringList::deleteFront()
    {
      if(head != NULL)
      {
        listNode *tmp = head -> next;
        delete head;
        head = tmp;
      }
    }
    head would be tested against nullptr (used to initialise), rather than NULL. Also, what about if there is only 1 node in the list?

    Code:
    void StringList::deleteBack()
    {
      if(head != NULL)
      {
        listNode *tmp = back -> next;
        delete back;
        back = tmp;
      }
    }
    No. To delete at back in a single forward linked list, you need to traverse the list to find the node preceeding the back one. The back one is then deleted, back set to the proceeding one and the next pointer set to nullptr to indicate end of list.

    Once these issues are sorted, then you can test the list. Insert some nodes at the front into list1 and display the list. Insert some nodes at the back of list2 and display the list. Once these are shown to be working, then you can start testing the delete functions. Once these are all shown to work, then you can do what the exercise requires - alternate insert and then alternate deletion.
    Last edited by 2kaud; July 21st, 2017 at 03:24 AM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.4)

  7. #7
    Join Date
    Jun 2017
    Posts
    13

    Re: Dealing with Nodes

    Here is my updated version 2kaud:

    StringList.cpp
    Code:
    #include <iostream>
    #include "StringList.h"
    
    using namespace std;
    
    //Constructor definition
    StringList::StringList()
    {
      head = nullptr;
      back = nullptr;
    }
    
    //Destructor definition
    StringList::~StringList()
    {
      delete head;
      delete back;
    }
    
    //Inserting Front
    void StringList::insertFront(string aStr)
    {
      listNode *temp = new listNode;
      temp -> next = head;
      temp -> str = aStr;
      head = temp;
    }
    
    //Inserting Back
    void StringList::insertBack(string aStr)
    {
      listNode *temp = new listNode;
      temp -> str = aStr;
      temp -> next = back;
      back = temp;
    }
    
    //deleteFront
    void StringList::deleteFront()
    {
      if(head != NULL)
      {
        listNode *tmp = head -> next;
        delete head;
        head = tmp;
      }
    }
    
    void StringList::deleteBack()
    {
      if(head != NULL)
      {
        listNode *tmp = back -> next;
        delete back;
        back = tmp;
      }
    }
    
    void StringList::displayList()
    {
      listNode *nodePtr;
    
      if(!head)
      {
        cout << "List is empty" << endl;
        return;
      }
      for (auto nodePtr = head; nodePtr; nodePtr = nodePtr -> next)
        cout << nodePtr -> str << " " << endl;
    }
    Hw5.cpp

    Code:
    #include <iostream>
    #include <string>
    #include <iomanip>
    #include "StringList.h"
    #include "StringList.cpp"
    
    using namespace std;
    
    int main() {
    
        string numbers = "Numbers:";
        StringList myList;
    
        for(int i = 0; i < 6; i++)
        {
            myList.insertFront(numbers + ' ' + to_string(i));
            myList.displayList();
            
            myList.insertBack(numbers + ' ' + to_string(i));
            myList.displayList();
        }
    
        return 0;
    }
    Now I'm not sure how to call the numbers to be deleted right after, and how to insert nodes randomly from back and front.

  8. #8
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,262

    Re: Dealing with Nodes

    Code:
    //Destructor definition
    StringList::~StringList()
    {
      delete head;
      delete back;
    }
    No. See my comments re this in post #6

    Code:
    void StringList::insertFront(string aStr)
    ...
    Yes, but what about back when the list is initially empty - as per my comment in post #6?

    Code:
    void StringList::insertBack(string aStr)
    {
      listNode *temp = new listNode;
      temp -> str = aStr;
      temp -> next = back;
      back = temp;
    }
    No. This isn't inserting properly at back. temp is the new node added at back, so its next pointer will be nullptr as its the last. The previous last (as pointed to by back) needs to point to the new node. What about head if the list is initially empty?

    Code:
    void StringList::deleteBack()
    ...
    No. See my comments in post #6.

    Code:
    void StringList::deleteFront()
    ...
    What about back if there is only 1 node in the list?

    For testing, consider
    Code:
    for (int i = 0; i < 6; i++)
    {
        (i %2) ? myList.insertFront(numbers + ' ' + to_string(i)) :  myList.insertBack(numbers + ' ' + to_string(i));
        myList.displayList();
    }
    
    for (int i = 0; i < 6; i++)
    {
        (i %2) ? myList.deleteFront() :  myList.deleteBack();
        myList.displayList();
    }
    For deleteFront() and deleteback(), the function doesn't indicate whether it succeeded or not. Consider having them return a bool to indicate success or fail.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++17 Compiler: Microsoft VS2019 (16.7.4)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)