Thread: Linked lists questions

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    tmp = tmp->next means "move tmp to the next node", which is exactly what you need to do to traverse the list. You are not, in any way shape or form, modifying the content of the list. tmp must of course be set to something useful at the start of the function, and you need to check in every iteration that tmp is not NULL.

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

  2. #17
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    after doing this all day i came up with this.
    now I cannot sort the list. the program freezes. can anyone see what I am doing wrong .


    Code:
    #include <iostream>
    using namespace std;
    
    /* Recursive functions
    insertion
    retrieval
    pointer based sorted linked list of integers
    also if 0 is entered it keeps inserting until 0 is entered.
    */
    
    
    struct node
    {
       int item;
       node *next;
    };
    
    
    // takes in the head pointer 
    // item to be inserted
    //building the list here
    
    void insertion(node *&HeadPtr, int NumberToInsert) {
    HeadPtr->item=NumberToInsert;
    HeadPtr->next=new node;
    node *tmp=HeadPtr;
    tmp->next=new node;
    
    do {
    cout << "Please input the number to insert: 0 to quit ";
    cin >> NumberToInsert;  
    tmp->item=NumberToInsert;
    
    if (tmp->item==0)
    {
       tmp->next=NULL;
    } //end if
    
    else
    {
    
    tmp->next=new node;
    tmp=tmp->next;
    } // end else
    
    
    }while (NumberToInsert!=0);  //end do -while 
    
    
    
    
    node *tmp2=HeadPtr;
    
    tmp2=HeadPtr;
    
     //sort the list
    
    while (tmp2!=NULL)
    {
       if (tmp2->item >tmp2->next->item)
           {
    
            int temp=tmp2->item;
            tmp2->item=tmp2->next->item;
            tmp2->next->item=temp;
       }
        else
        {tmp2==NULL;}
    }  
    
    
    tmp2=HeadPtr;
    
    // traverse the list
    while (tmp2!=NULL)
    {
       cout << tmp2->item << " ";
       tmp2=tmp2->next;
       
    } // end while
    
    }
    
    int main() {
    int number=-1;
    node *HeadPtr=new node;
    
    insertion(HeadPtr, number); 
    
       system("pause");
        return 0;
        
    }

  3. #18
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Would it be possible for you to format your code like this:
    Code:
    #include <iostream>
    using namespace std;
    
    /* Recursive functions
       insertion
       retrieval
       pointer based sorted linked list of integers
       also if 0 is entered it keeps inserting until 0 is entered.
    */
    
    
    struct node
    {
        int item;
        node *next;
    };
    
    
    // takes in the head pointer 
    // item to be inserted
    //building the list here
    
    void insertion(node *&HeadPtr, int NumberToInsert) 
    {
        HeadPtr->item=NumberToInsert;
        HeadPtr->next=new node;
        node *tmp=HeadPtr;
        tmp->next=new node;
    
        do {
    	cout << "Please input the number to insert: 0 to quit ";
    	cin >> NumberToInsert;  
    	tmp->item=NumberToInsert;
    
    	if (tmp->item==0)
    	{
    	    tmp->next=NULL;
    	} //end if
    
    	else
    	{
    	    tmp->next=new node;
    	    tmp=tmp->next;
    	} // end else
    
        } while (NumberToInsert!=0);  //end do -while 
    
    
    
    
        node *tmp2=HeadPtr;
    
        tmp2=HeadPtr;
    
        //sort the list
    
        while (tmp2!=NULL)
        {
    	if (tmp2->item >tmp2->next->item)
    	{
    	    int temp=tmp2->item;
    	    tmp2->item=tmp2->next->item;
    	    tmp2->next->item=temp;
    	}
    	else
    	{
    	    tmp2==NULL;
    	}
        }  
    
    
        tmp2=HeadPtr;
    
    // traverse the list
        while (tmp2!=NULL)
        {
    	cout << tmp2->item << " ";
    	tmp2=tmp2->next;
       
        } // end while
    
    }
    
    int main() 
    {
        int number=-1;
        node *HeadPtr=new node;
    
        insertion(HeadPtr, number); 
    
        system("pause");
        return 0;
        
    }
    I have no idea what you are actually doing in your code, but I would suggest that you start by separating your input loop from your insertion, and moving the "sort" code to a different function. But before you even start sorting, make sure you can just insert things.

    Write a separate function that prints/traverses the list, so that you can check what the list looks like at any given time [before and after insert for example].

    Oh, and your sort code is incomplete - it walks through the list once, but it needs to walk as many times as necessary to get the smallest item at one end and the largest at the other.

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

  4. #19
    Registered User
    Join Date
    Jul 2008
    Posts
    80

    getting the sorting function to repeat until sorted

    I took some time to try to understand linked list. I split up the functions to do separate things. But now whatever i do, i cannot get m sorting function to sort correctly. can anyone see how to repeat it until its sorted?

    Code:
    #include <iostream>
    using namespace std;
    
    /* Recursive functions
    insertion
    retrieval
    pointer based sorted linked list of integers
    also if 0 is entered it keeps inserting until 0 is entered.
    */
    
    
    struct node
    {
       int item;
       node *next;
    };
    
    
    // takes in the head pointer 
    // item to be inserted
    //building the list here
    
    void insertion(node *&HeadPtr, int NumberToInsert) {
    HeadPtr->item=NumberToInsert;
    HeadPtr->next=new node;
    node *tmp=HeadPtr;
    tmp->next=new node;
    
    do {
    cout << "Please input the number to insert: 0 to quit ";
    cin >> NumberToInsert;  
    tmp->item=NumberToInsert;
    
    if (tmp->item==0)
    {
       tmp->next=NULL;
    } //end if
    
    else
    {
    
    tmp->next=new node;
    tmp=tmp->next;
    } // end else
    
    }while (NumberToInsert!=0);  //end do -while 
    } //end insertion
    
    int traverser(node *&HeadPtr) {
    node *tmp2=HeadPtr;
    
    // traverse the list
    while (tmp2!=NULL)
    {
       cout << tmp2->item << " ";
       tmp2=tmp2->next;
       
    } // end while
     cout << "\n";
    } // end traverser
    
    int sort(node *&HeadPtr)
    {
        node *tmp=HeadPtr;
        node *tmp3=tmp;
        int temp;
        
        while (tmp3->item!=0)
           {
           if (tmp3->item < tmp3->next->item)
           {
                 tmp3=tmp3->next;
           }
           
           if (tmp->item = 0)  //unsure
           {
           }
           
           else
           { 
              temp=tmp3->item;
              tmp3->item=tmp3->next->item;
              tmp3->next->item=temp;
              tmp3=tmp3->next;          
           }  
           
           } // end while
               
    } // end sort
    
    
    int main() {
    int number=-1;
    node *HeadPtr=new node;
    
    insertion(HeadPtr, number); 
    
    traverser(HeadPtr);
    sort(HeadPtr);
    traverser(HeadPtr);
    
       system("pause");
        return 0;
    }

  5. #20
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You are still not doing what I said: Make a function that takes as a parameter an integer and a headptr, and inserts that into the list.

    What I'm saying is that your insert function should not ask for a number or check if the number is zero.

    Your sort loop probably needs to walk the entire list several times - consider a list of:
    1 5 2 4 3 that you want sorted to 1 2 3 4 5
    When you get to 5, you swap it with 2, so you have 1 2 5 4 3.

    Also, your logic in the sort function is flawed, as you always swap, even if the numbers are the in order.

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

  6. #21
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    i thought i was taking a headptr in. HeadPtr is the first node that is empty. and it inserts a number when it is in the insertion function?
    since i dont know how to do it recursively, i at least want to learn how to do it normally.

    my assignment says

    2. Write recursive functions that perform insertion and retrieval operations on a pointer-based sorted linked list of integers. The insertion function should be void, taking a head pointer and the item to be inserted as parameters. The retrieval function should take a head pointer and the item to be retrieved as parameters, and should return the item's position, or -1 if the item is not found in the list. Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed. Example:
    Enter numbers to be inserted (0 to end): 34 23 1 45 7 0
    The list is: 1 7 23 34 45
    Enter numbers to be retrieved (0 to end): 23 8 45 0
    23 is at position 3
    8 is not in the list
    45 is at position 5
    Note that the program should be able to handle requests to retrieve items that are not in the list.
    Last edited by Emeighty; 09-08-2008 at 04:05 AM.

  7. #22
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Ok, to clarify what I mean: the code that doesn't belong in the function is marked in red:
    Code:
    void insertion(node *&HeadPtr, int NumberToInsert) {
    HeadPtr->item=NumberToInsert;
    HeadPtr->next=new node;
    node *tmp=HeadPtr;
    tmp->next=new node;
    
    do {
    cout << "Please input the number to insert: 0 to quit ";
    cin >> NumberToInsert;  
    tmp->item=NumberToInsert;
    
    if (tmp->item==0)
    {
       tmp->next=NULL;
    } //end if
    
    else
    {
    
    tmp->next=new node;
    tmp=tmp->next;
    } // end else
    
    }while (NumberToInsert!=0);  //end do -while 
    } //end insertion
    --
    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.

  8. #23
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    the assignment says for me to

    Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed. Example:
    Enter numbers to be inserted (0 to end): 34 23 1 45 7 0

    is what i am doing incorrect?

  9. #24
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Emeighty View Post
    the assignment says for me to

    Use these procedures to write a program that inputs a series of integers, inserting them into a list until 0 is entered. Then a second series of integers is input, until 0 is entered, and the position of each integer in the list is displayed. Example:
    Enter numbers to be inserted (0 to end): 34 23 1 45 7 0

    is what i am doing incorrect?
    Yes, but car factories do not provide petrol for your car either, do they? You should have a loop, yes.

    In fact, your function does not insert the number passed into the function - it uses it to read in a new value.

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

  10. #25
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    so i would insert the first number in the head outside of the insertion function. Then in the insertion function it would take that head in, then add more numbers to the list until 0 is entered. is this the order?

  11. #26
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Emeighty View Post
    so i would insert the first number in the head outside of the insertion function. Then in the insertion function it would take that head in, then add more numbers to the list until 0 is entered. is this the order?
    No, you would have a loop in your MAIN, that calls your insert function once for each number entered, and the loop ends when 0 is entered.

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

  12. #27
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    ok, i think i get that. for the sort, how would i get it repeat itself ?


    Code:
    do 
    {
    cout << "Please insert the first number : " ;
    cin >> number ;
    insertion(HeadPtr, number);
     
    } while (number!=0);

  13. #28
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Yes, that looks good.

    As to sorting, you need an outer loop and an inner loop. In the outer loop, you just set up the pointer to the start of the list. In the inner loop, you swap items that are out of order and move to the next item. The inner loop ends when you have gone through the list completely. The outer loop ends when you haven't swapped anything [which means that all items are in order].

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

  14. #29
    Registered User
    Join Date
    Jul 2008
    Posts
    80
    I know this is getting repetitive. Pretty ridiculous, i need a Live breathing teacher, If anyone is out there PLEASE pm me. I am willing to pay you for your time. Me paying you will save me money actually. I am not sure on the rules of the website about asking for help, im very desperateactually. have 2 assignments and a final in about 3 weeks. and still dont see everything the book is trying to teach, and the online teacher doesnt clarify.

    anyway,

    My program is falling apart. I'm talking very bad. i scrapped the whole thing because i had to change the insertion.
    The goal of what i am looking to do is one thing, then i can move on to something else .
    Insert a number in if the HeadPtr is empty or NULL.

    I've tried
    if (HeadPtr==NULL)
    {
    do something;
    }

    and

    if (HeadPtr==0)
    {
    do something;
    }

    what is it that is needed to get to the inside of the if statement?

    this is the whole program i am starting over with.

    Code:
    #include <iostream>
    using namespace std;
    
    /* Recursive functions
    insertion
    retrieval
    pointer based sorted linked list of integers
    also if 0 is entered it keeps inserting until 0 is entered.
    */
    
    
    struct node
    {
       int item;
       node *next;
    };
    
    
    // takes in the head pointer 
    // item to be inserted
    //building the list here
    
    void insertion(node *HeadPtr, int NumberToInsert) 
    {
    
    if (HeadPtr=NULL) //If the HeadPtr is empty insert the number
    {
    
    HeadPtr->item=NumberToInsert;
    cout << "The HeadPtr->item is : " << HeadPtr->item << endl;
    } //end if
    
    }
    
    void traverser (node *HeadPtr) {
         cout << "Using Traverser the HeadPtr->item is :" << HeadPtr->item << endl;
    }
    
    int main() {
    int number;
    node *HeadPtr=new node;
    HeadPtr==NULL;
    
    while (number!=0) 
    {
    cout << "Please insert the first number: "; 
    cin >> number;
    }
    insertion( HeadPtr, number);
    //traverser(HeadPtr);
       system("pause");
        return 0;
    }

  15. #30
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    If you don't learn to indent your code, as you've already been asked to, then I wont be reading it, and neither will a lot of other people.

    It's like closing your eyes and saying "I can't see the bug!".
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

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, 08:27 PM