Linked lists questions

This is a discussion on Linked lists questions within the C++ Programming forums, part of the General Programming Boards category; Since i am not hearing or understanding anything, I am going to start from scratch. I am aware there are ...

  1. #31
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    clueless

    Since i am not hearing or understanding anything, I am going to start from scratch. I am aware there are pretty talented people on this site. If it takes me making myself look very ignorant to learn something, so be it. I don't now what questions to aks and how to ask them, so i will a question worded a few times.
    So is the book grammer different than actually grammer used?

    indent....is it?
    Code:
         
    
    function()
    {        something;
    }
    
    or 
    
              function() {
           
             something;
    }
    
    
    or is it 
    
    
      function () 
    {
                something
    
    }
    Last edited by Emeighty; 09-09-2008 at 01:24 AM.

  2. #32
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I write like this:
    Code:
    int function(paramters)
    {
        do something;
        if (stuff)
        {
             do others
        }
        else if (x)
        {
            switch(y)
            {
               case 'a':
                  Some code here
                  break;
               default:
                  break;
        }
        else
        {
            something else. 
        }
    }
    However, the most important part is that each new level is "deeper" than the previous level, and that the code is consistent. Most editors have a "auto-indent" feature that can be used to format your code (and that will maintain correct format for you, if you like - I use Emacs, and it's near on impossible to get it wrong, but you probably want to set "stroustrup" style instead of the default).

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

  3. #33
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    ok, I found the indent feature on the Dev-CPP compiler and the "find matching braces " feature and enabled it.

    For the program, I am trying to fill the HeadPtr only if it is empty.
    My questions are.
    1. Is a new node an empty node?
    2. Is a node pointing to NULL an empty node?
    3. If 1, or 2 arent empty nodes what is an empty node?


    My program below does not output what is in the if statement. The goal is to fill it only if the HeadPtr is empty.

    Code:
    #include <iostream>
    using namespace std;
    
    struct node
    {
       int item;
       node *next;
    };
    
    void insertion( node *&HeadPtr, int NumberToInsert)
    {    
         if (HeadPtr == new node)
         {
    	  	cout << "Inside first if " << endl;
         } //end if
    		
    }// end insertion
    
    int main() 
    {   
        int number= -1;
        node *HeadPtr=new node;
       
        insertion (HeadPtr, number);
        system("pause");
        return 0;
    } //end main

  4. #34
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    if (HeadPtr == new node)
    This is almost certain NEVER be true - only if you recently did "delete HeadPtr" and you didn't set HeadPtr to 0 as well as being "lucky" enough to get the same address that you just deleted.

    Your check should be:
    Code:
    if (HeadPtr == 0)
    ...
    --
    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.

  5. #35
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    I changed up a few things and got the same result, the program skips the if and goes straight to the else.

    How would an empty node be defined?
    Also the equivilant operator == makes a difference, when
    Is = used for variable numbers, and == used for other than integer variables

    HeadPtr=0 the program freezes
    HeadPtr==0 it skips the if and goes straight to else.

    Code:
    #include <iostream>
    using namespace std;
    
    struct node
    {
       int item;
       node *next;
    };
    
    void insertion( node *HeadPtr, int NumberToInsert)
    {    
         if (HeadPtr == 0)
         {
         	cout << "Inside first if " << endl;
    	  	HeadPtr->item=NumberToInsert;
    	  	cout << HeadPtr->item;
         } //end if
    	
           else
        {
    	 	cout << " In the else: " << endl;
        }//end else	
    }// end insertion
    
    int main() 
    {   
        int number= -1;
        node *HeadPtr=new node;
        HeadPtr==0;
        while (number !=0) 
        {
        cout <<" Please input the number to insert: " ;
    	cin >> number;
        insertion (HeadPtr, number);
        }
    	
    	system("pause");
        return 0;
    } //end main

  6. #36
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Meah, I expect it does:
    Code:
        node *HeadPtr=new node;
        HeadPtr==0;
    The first line of those above allocates memory and sets HeadPtr to the newly allocated memory. The second line compares HeadPtr with zero and throws away the result. If you enable compiler warnings (in the Dev-CPP compiler options settings - search for a recent post by Dino to find where they are if you can't find it), it should give you a warning about "statement has no effect" which is usually a good warning to tell you that the line probably doesn't do what you wanted it to do.

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

  7. #37
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    The final touches

    I finally (with lots of help) came up with the code for this linked. But the only thing i cant get right is the retrieve function. I am able to retrieve things that are in the list, but if it's not in the list, the program crashes. can anyone see whats going on in that function that i am not seeing?

    Code:
    #include <iostream>
    using namespace std;
    
    
    struct node
        {
        int  number;
        node *next;
        };
    
     class List
         {
    
         public:
    
          List();
         ~List();
          node *Head();
         node *createnode(int);
         void insert(node *, int);
         void traverse(node *);
         void retrieve(node *, int);
         
         private:
         node *TheHead;
        
         };
    
     List::List() 
         {
         TheHead = NULL;
         }
    
     node *List::Head()
          {
          return TheHead;
          }
     List::~List() {}  //Destructor
    
      node *List::createnode(int NumberToInsert)
         {        
            node *NewOne = new node;
            NewOne ->number = NumberToInsert;
            NewOne ->next = NULL;
            return NewOne;
         }
    
      void List::insert(node *pPointer, int ANumber) 
         {
         node *tmp = new node;
         
         tmp = createnode(ANumber);
    
         tmp -> next = pPointer;
    
         TheHead = tmp;
         } 
    
     void List ::traverse(node *CurPtr)
         {
               node *current = CurPtr;
               
               while (current !=NULL)
                   {
                   cout << current ->number << " ";
                   current = current ->next;
                    }           
               cout << "\n";
         }
    
    
     void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
            {
            node *tmp = pPointer;
            int position=0;
    
            while (tmp != NULL && tmp->number != XNumber)
                {
                tmp=tmp->next;
                position++;
                }
            
            if (tmp ->number != XNumber )
                {
                cout << XNumber << " Is at position " << position << endl;
                }
             else 
                {
                 cout << XNumber << "Is not in the list " << end;
                }
         }
     int main()
         { 
         
         List s;
         node * pPointer = s.Head();
         
         int TheNumber=-1;
         int RetrievedNumber = -1;
         
         while (TheNumber != 0)
              {
              cout << "Please enter in a number: enter 0 to quit: " ;
              cin >> TheNumber;
              s.insert(s.Head() , TheNumber);
              }
    
         s.traverse(s.Head());
    
         while (RetrievedNumber !=0)
             {
             cout << "Please enter the number to be retrieved , 0 to quit: " ;
             cin >> RetrievedNumber ;
             s.retrieve(s.Head(), RetrievedNumber);
             }
       
         system("pause");
         return 0;
         }
    Last edited by Emeighty; 09-12-2008 at 08:32 AM.

  8. #38
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    That looks much better.

    Here's a few "constructive criticism" comments:
    Code:
      node *List::createnode(int NumberToInsert)
         {        
            node *NewOne = new node;
            NewOne ->number = NumberToInsert;
            NewOne ->next = NULL;
            return NewOne;
         }
    Most of this would normally go into a node constructor. Basically all but the new and return lines, and with the middle of this function "disappearing", you'd probably not need a function at all, just use new in the actual code where you currently call createnode.

    Code:
      void List::insert(node *pPointer, int ANumber) 
         {
         node *tmp = new node;
         
         tmp = createnode(ANumber);
    
         tmp -> next = pPointer;
    
         TheHead = tmp;
         }
    This would make more sense if you didn't have a pPointer argument, but rather used TheHead - as that is what you are essentially doing anyways by using s.Head() in insert - and passing anyting else, such as a node in the middle of the list, TheHead would point at the new node, TheHead->next is then pointing to the middle of the list, so anything BEFORE the new node is lost.

    Likewise, I doubt that traverse needs to have an argument of a node pointer - just use TheHead internally.

    in retrieve:
    Code:
            if (tmp ->number != XNumber )
                {
                cout << XNumber << " Is at position " << position << endl;
                }
             else 
                {
                 cout << XNumber << "Is not in the list " << end;
                }
    Not a good idea to test if tmp->number != XNumber, since if tmp is NULL, you'd be trying to read an invalid memory address. The better method would be to check if tmp is NULL - then you DIDN'T find it. [By the way, I expect this ALWAYS says "is not in the list", since either you FOUND the numer, OR XNumber is different from tmp->number.]

    And again, I think retrievenumber should search based on TheHead, rather than using an argument.


    Code:
         List s;
         node * pPointer = s.Head();
    1. pPointer will always be NULL here.
    2. pPointer is never used in main().


    Code:
    List::~List() {}  //Destructor
    Sorry for the random order: Don't you think it would be a good idea to destroy any list you have in the destructor.

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

  9. #39
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    I changed up the code for the retrieve function , and it works like a charm !!!!
    OH boy this was a challenging question. 2 more to go.

    the new code is

    Code:
    void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
            {
            node *tmp = pPointer;
            int position=0;
    
            while (tmp != NULL && tmp->number != XNumber)
                {
                tmp=tmp->next;
                position++;
                }
            if (tmp == NULL )
                {
                cout << XNumber << " is not in the list " << endl;
                }
            else if (tmp->number = XNumber )
                {
                cout << XNumber << " is located in position " << position << endl;
                }
            else 
                {
                cout << " this is 0 " << endl;
                }
    For the arguments of pPointer. My assignment has me bring in a node and a number as a parameter. Im not understanding how to bring in TheHead directly into the insert and retrieve functions. If i try , it says that i cannot and

    illegal reference to non-static member 'List::TheHead displays.

    i got changed up the parameters in the main.
    but i am not sure what u mean by , destroying the list, do u mean using the delete command?

    here is the full code after the mods i did. pPointer doesnt like me changing it at all.


    Code:
    #include <iostream>
    using namespace std;
    
    
    struct node
        {
        int  number;
        node *next;
        };
    
     class List
         {
    
         public:
    
          List();
         ~List();
          node *Head();
         node *createnode(int);
         void insert(node *, int);
         void traverse(node *);
         void retrieve(node *, int);
         
         private:
         node *TheHead;
        
         };
    
     List::List() 
         {
         TheHead = NULL;
         }
    
     node *List::Head()
          {
          return TheHead;
          }
     List::~List() {}  //Destructor
    
      node *List::createnode(int NumberToInsert)
         {        
            node *NewOne = new node;
            NewOne ->number = NumberToInsert;
            NewOne ->next = NULL;
            return NewOne;
          }
      void List::insert(node *pPointer, int ANumber) 
         {
         node *tmp = new node;
         
         tmp = createnode(ANumber);
    
         tmp -> next = pPointer;
    
         TheHead = tmp;
         } 
    
     void List ::traverse(node *CurPtr)
         {
               node *current = CurPtr;
               
               while (current !=NULL)
                   {
                   cout << current ->number << " ";
                   current = current ->next;
                    }           
               cout << "\n";
         }
    
    
     void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
            {
            node *tmp = pPointer;
            int position=0;
    
            while (tmp != NULL && tmp->number != XNumber)
                {
                tmp=tmp->next;
                position++;
                }
            if (tmp == NULL )
                {
                cout << XNumber << " is not in the list " << endl;
                }
            else if (tmp->number = XNumber )
                {
                cout << XNumber << " is located in position " << position << endl;
                }
            else 
                {
                cout << " this is 0 " << endl;
                }
    
             }
     int main()
         { 
         
         List s;
         
         s.Head();
    
         int TheNumber=-1;
         int RetrievedNumber = -1;
         
         while (TheNumber != 0)
              {
              cout << "Please enter in a number: enter 0 to quit: " ;
              cin >> TheNumber;
              s.insert(s.Head() , TheNumber);
              }
    
         s.traverse(s.Head());
    
         while (RetrievedNumber !=0)
             {
             cout << "Please enter the number to be retrieved , 0 to quit: " ;
             cin >> RetrievedNumber ;
             s.retrieve(s.Head(), RetrievedNumber);
             }
       
         system("pause");
         return 0;
         }

  10. #40
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    For the arguments of pPointer. My assignment has me bring in a node and a number as a parameter. Im not understanding how to bring in TheHead directly into the insert and retrieve functions.
    Well, then it's likely that you shouldn't be doing this inside a class, and not have "TheHead" inside a class.

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

  11. #41
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    Recusively inserting to list

    I am trying to insert numbers into this linked list recursively, but the only way that works is if the inserted number is less than the head. Can anyone exlain how i can fix my error?

    Code:
      #include <iostream>
    using namespace std;
    
    
    struct node
        {
        int  number;
        node *next;
        };
    
     class List
         {
    
         public:
    
          List();
         ~List();
          node *Head();
         node *createnode(int);
         void insert(node *, int);
         void traverse(node *);
         void retrieve(node *, int);
         
         private:
         node *TheHead;
        
         };
    
     List::List() 
         {
         TheHead = NULL;
         }
    
     node *List::Head()
          {
          return TheHead;
          }
     List::~List() {}  //Destructor
    
      node *List::createnode(int NumberToInsert)
         {        
            node *NewOne = new node;
            NewOne ->number = NumberToInsert;
            NewOne ->next = NULL;
            return NewOne;
          } 
      void List::insert(node *pInsertedHead, int ANumber)    
         {
          
         node *tmp = new node;  // creates a new node for the new number(ANumber) to be inserted into
         
         tmp = createnode(ANumber); // ANumber is inserted into the new node tmp       
    
           if (TheHead ==NULL || TheHead ->number >=ANumber)
             {
             tmp->next = TheHead;
              TheHead =tmp;
             
           }
              
          else
              {
                 if(pInsertedHead !=NULL && pInsertedHead->number <= ANumber)
                   {
                   insert(pInsertedHead->next, ANumber); 
                   
    
                   }
                   
              } 
                  
                  
          }
           
          
     void List ::traverse(node *CurPtr)
         {
               node *current = CurPtr;
               
               while (current !=NULL)
                   {
                   cout << current ->number << " ";
                   current = current ->next;
                    }           
               cout << "\n";
         }
    
    
     void List::retrieve(node *pPointer, int XNumber) //performs retrieve on a sorted list 
            {
            node *tmp = pPointer;
            int position=0;
    
            while (tmp != NULL && tmp->number != XNumber)
                {
                tmp=tmp->next;
                position++;
                }
            if (tmp == NULL )
                {
                cout << XNumber << " is not in the list " << endl;
                }
            else if (tmp->number = XNumber )
                {
                cout << XNumber << " is located in position " << position << endl;
                }
            else 
                {
                cout << " this is 0 " << endl;
                }
    
             }
     int main()
         { 
         
         List s;
         
         s.Head();
    
         int TheNumber=-1;
         int RetrievedNumber = -1;
         
         while (TheNumber != 0)
              {
              cout << "Please enter in a number: enter 0 to quit: " ;
              cin >> TheNumber;
              s.insert(s.Head() , TheNumber);
              }
    
         s.traverse(s.Head());
    
         while (RetrievedNumber !=0)
             {
             cout << "Please enter the number to be retrieved , 0 to quit: " ;
             cin >> RetrievedNumber ;
             s.retrieve(s.Head(), RetrievedNumber);
             }
       
         system("pause");
         return 0;
         }

  12. #42
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
         node *tmp = new node;  // creates a new node for the new number(ANumber) to be inserted into
         
         tmp = createnode(ANumber); // ANumber is inserted into the new node tmp
    is definitely not right in the place it is, since you'd be leaking memory like the proverbial sieve if you have a long list and try to insert something at the tail of the list.

    If you are passing in a node to insert at, you should not be using TheHead inside your function.

    --
    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 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. Question On Linked Lists
    By Zildjian in forum C Programming
    Replies: 8
    Last Post: 10-23-2003, 11:57 AM
  3. How to use Linked List?
    By MKashlev in forum C++ Programming
    Replies: 4
    Last Post: 08-06-2002, 07:11 AM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. Linked Lists -- Again!!! Help!!
    By Leeman_s in forum C++ Programming
    Replies: 4
    Last Post: 01-22-2002, 07:27 PM

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