Linked List problems

This is a discussion on Linked List problems within the C++ Programming forums, part of the General Programming Boards category; Hi, I have this simple file that is supposed to create a Node struct to form a linked list. Basically ...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    100

    Linked List problems

    Hi,

    I have this simple file that is supposed to create a Node struct to form a linked list. Basically what I want is for the user to be able to enter as many strings as he or she wants and for each new string the program creates a new "Node" and assigns 'nvalue' to the string and the 'ptr' of the last node, which is a node pointer, to point to the new node. Here is the code that I have implemented so far (just testing out basics), but it won't compile:

    Code:
    #include <cstdlib>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    struct Node
    {
        string nvalue;
        Node *ptr;
    }
    
    int main(int argc, char *argv[])
    { // line 14
        Node myNode;
        cin >> myNode.nvalue;
        cout << "You inputted: " << myNode.nvalue;
    
        System("Pause");
        return 0;
    }
    Error:
    Code:
    14 test.cpp new types may not be defined in a return type 
    14 test.cpp extraneous `int' ignored 
    14 test.cpp `main' must return `int' 
    14 test.cpp return type for `main' changed to `int'

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Same issues as before in the other board (you should have just let a mod move the other post instead of posting a new one... you could have sent a PM asking one to move it for you) you're missing the semicolon at the end of the struct declaration.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    Code:
    struct Node
    {
        string nvalue;
        Node *ptr;
    };

  4. #4
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Is there any good technique when creating multiple Nodes? Like when inside of a while loop that keeps looping until the user stops inputting data and each time creating a new node for each input, how would I best go about creating and naming those nodes?

    Code:
    int c = 0;
    while(getline(cin, temp)) 
    {
      Node myNode; // this would be overwritten each time
      myNode.nvalue = temp;
    }
    I can't have arrays because there is no way of telling how many nodes there will be - the user keeps inputting data until he or she decides they are done.

  5. #5
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    With a linked list you should be creating nodes dynamically, since they will be owned by the list and might outlive the function that creates them. That means using new to create a node. That also means you should delete nodes that are removed from the list and also delete the nodes in the list when it is destroyed.

  6. #6
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    I'm having a lot of trouble figuring out how to code this. My test program creates two Nodes then attempts to point the variable "Node *ptr" of the first node to the second node. Here is what I have:

    Code:
    #include <cstdlib>
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    struct Node
    {
        string nvalue;
        Node *ptr;
    };
    
    int main(int argc, char *argv[])
    {
        Node myNode;
        cin >> myNode.nvalue;
        cout << "Node 1 nvalue: " << myNode.nvalue;
    
        Node myNode2;
        cin >> myNode2.nvalue;
        cout << "Node 2 nvalue: " << myNode2.nvalue;
    
        myNode.ptr = myNode2;
    
        system("Pause");
        return 0;
    }
    Here is the error message:
    Code:
    23 test.cpp cannot convert `Node' to `Node*' in assignment
    I've been reading a lot of linked list tutorials but they have just made me even more confused. Is ->next a built in function? I keep seeing stuff like temp = temp->next but I never see any other reference to ->next. What exactly does "->" mean? Does anyone know of a good tutorial for linked lists?

  7. #7
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    You are trying to assign a Node object (myNode2) to a Node* (myNode.ptr). They are of different types. You need to take the address-of myNode2 and assign it to the pointer:
    Code:
    myNode.ptr = &myNode2;
    -> is used to access the members of a pointer to some object. If ptr is a pointer to an object of type Node (and actually points to a valid/real object and not some random memory address), then ptr->nvalue is the value of the string data member contained in the Node object pointed to by ptr.

    next is a common name for a pointer variable used in linked-lists. It is a pointer to the next object in the list (or null if it's the last node in the list).
    Last edited by hk_mp5kpdw; 10-10-2007 at 07:59 PM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Thanks! Now my test program works. I still have one main problem that is not technical but design oriented: how do I create an indefinite amount of nodes? Like I said above, the program is going to keep executing inside a while loop until the user ends the input. For each line of input the program will create a new node associated with the input. But I can't use arrays because the program won't know how many elements there are going to be. Otherwise I would do something like:

    Code:
    Node myNodes = new Node[20];
    int c = 0;
    string temp;
    while(getline(cin, temp))
    {
      myNodes[c] = new Node;
      myNodes[c].nvalue = temp;
      myNodes[(c-1)].ptr = &myNodes[c];
    }
    The above code may not be entirely correct, it is just a rough example.

  9. #9
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Nevermind my last question, I found a good tutorial that explains linked lists well.

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Ok, another question. I created this header file but I am not sure that the structuring is correct:

    queue.h
    Code:
    #ifndef QUEUE
    #define QUEUE
    #include <string>
    
    class queue
    {
        public:
            queue(void);
            bool push(std::string ss);
            std::string pop(void);
            std::string first(void) const;
            std::string last(void) const;
            bool err(void);
    
        private:
            struct Node
            {
                string nvalue;
                Node *pNext;
                Node *pPrev;
            };
    
            Node *pHead, *pTail;
    };
    
    #endif
    It also gives me a compile error at line 22 (bolded):
    Code:
    'string' does not name a type

  11. #11
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    string is a member of namespace std.
    so put std::string instead

  12. #12
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    Doh, I don't know how many times I have done that.

    New problem: My attempt at creating new Node objects from inside an instance of the class is not working. Here is my code:

    queue.h
    Code:
    /*
        Nick Bakewell
        10/10/07
    */
    #ifndef QUEUE
    #define QUEUE
    #include <string>
    
    class queue
    {
        public:
            queue(void);
            bool push(std::string ss);
            std::string pop(void);
            std::string first(void) const;
            std::string last(void) const;
            bool err(void);
    
        private:
            struct Node
            {
                std::string nvalue;
                Node *pNext;
                Node *pPrev;
            };
    
            Node *pHead, *pTail, *myNode;
    };
    
    #endif
    And my driver:
    Code:
    #include <cstdlib>
    #include <iostream>
    #include <string>
    #include "queue.h"
    
    using namespace std;
    
    int main(int argc, char *argv[])
    {
        queue myQueue();
        
        for(int i = 0; i < 5; i++)
        {
            myQueue.myNode = new Node; // line 14
            cin >> myQueue.myNode->nvalue; // line 15
            myQueue.AddNode(myQueue.myNode); // line 16
        }
    [...]
    The compiler is giving me this error:
    Code:
    14main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()' 
    14 main.cpp `Node' has not been declared 
    15 main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()' 
    16 main.cpp request for member `AddNode' in `myQueue', which is of non-class type `queue ()()' 
    16 main.cpp request for member `myNode' in `myQueue', which is of non-class type `queue ()()'
    queue.cpp
    Code:
    /*
        Nick Bakewell
        10/10/07
    */
    #include <iostream>
    #include <cstdlib>
    #include <string>
    #include "queue.h"
    
    using namespace std;
    
    queue::queue()
    : pHead(NULL), pTail(NULL), myNode(NULL)
    {}
    
    bool queue::push(string ss)
    {
        if(pHead == NULL)
        {
            pHead = myNode;
            myNode->pPrev = NULL;
        }
        else
        {
            pTail->pNext = myNode;
            myNode->pPrev = pTail;
        }
        pTail = myNode;
        myNode->pNext = NULL;
    
        return true;
    }
    
    string queue::pop()
    {
        Node *pTemp;
        pTemp = pTail;
    
        pTail = pTail->pPrev;
        pTail->pNext = NULL;
    
        return "\nPop: " + pTemp->nvalue + "\nNew last value: " + pTail->nvalue + "\n";
    }
        
    string queue::last()
    {
        return pTail->nvalue;
    }
    
    string queue::first()
    {
        return pHead->nvalue;
    }
    
    bool queue::err()
    {
        return false;
    }

  13. #13
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> queue myQueue();
    That should be queue myQueue; otherwise it declares a function.

    In your push function you need to use new to create a new node. In your pop function you need to use delete to delete the node you remove. Don't use new to create the node in main.

    Also, you call AddNode in main, but there is no AddNode in your queue.

  14. #14
    Registered User
    Join Date
    Sep 2007
    Posts
    100
    So I should delete pTemp inside of pop after I use it in the return statement?

    For my main method, you are saying that it should be structured like this?

    Code:
    int main(int argc, char *argv[])
    {
        queue myQueue;
        string temp;
    
        for(int i = 0; i < 5; i++)
        {
            cin >> temp;
            myQueue.push(temp);
        }
    [...]
    Then push would look like:

    Code:
    bool queue::push(string ss)
    {
        myNode = new Node;
        myNode->nvalue = ss;
    
        if(pHead == NULL)
        {
            pHead = myNode;
            myNode->pPrev = NULL;
        }
        else
        {
            pTail->pNext = myNode;
            myNode->pPrev = pTail;
        }
        pTail = myNode;
        myNode->pNext = NULL;
    
        return true;
    }
    I appreciate all of the help you're giving me and i'm sorry if I take a while to grasp this concept.

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If we listen to Bjarne Stroustrup, we shouldn't use "NULL", but rather use 0 (zero - not the letter O).

    I would also move this:
    Code:
       myNode->pNext = NULL;
    to just under where you set the nvalue = ss;

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Help!
    By mbk in forum C Programming
    Replies: 3
    Last Post: 01-31-2008, 02:54 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21