Linked List - Random Nodes - Page 2
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 3 FirstFirst 123 LastLast
Results 16 to 30 of 44

Thread: Linked List - Random Nodes

  1. #16
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    Quote Originally Posted by Paul McKenzie View Post
    Since this is not homework, then it is advantageous to use (and learn) the C++ standard library -- this is what it was designed for:

    The above is an example of using the C++ library to implement the first two requirements. There are no memory leaks, no calls to operator new, etc. It isn't even the greatest of code using the standard library, but it worked the first time I tried it. From here, you can implement the rest of your requirements, but think on a much higher-level, and not get bogged down in the weeds of dynamic memory allocation, writing your own containers, etc. As a matter of fact, requirement #5 on your list is taken care of since the map has details of all the entries, including the number of times a number was entered.

    From the code above, all that is needed is to know what a std::list is, what a std::map does, what iterators are, what algorithms such as find() do, etc. All of these are basic requirements to be a good C++ programmer in this day and age of C++ programming. Unless you're a student and this is a homework assignment, let the students (or experienced C++ STL library developers) worry about coding linked list classes.

    Regards,

    Paul McKenzie
    Dear Paul, when i insert the following code

    Code:
    myList.sort();
       IntList::iterator lt = myList.begin();
       while(lt != myList.end())
       {
           
          cout << *lt << " ";
           
           ++lt;
       }
    I do not get what i expect to get from your piece of code.

    let me give you a scenario:

    if the user enters the following integers: 1 2 3 4 22 25 26 27 22 22 22 23 22

    myList output is: 1 2 3 4 22 25 26 27 22 22 22 23 and
    myDups output is: 22
    myMap seems to be alright.

    what i really want the program to do, is simply have a list which should have the following output: 1 2 3 4 22 23 25 26 27.

    basically meaning that a single copy of every integer entered. Keeping in mind that the user can enter an integer mulitple times

  2. #17
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    Dear Paul, when i insert the following code
    Please post all of the code, not just what you "inserted" (since I have no idea where you "inserted" this code or what you really are running).

    Regards,

    Paul McKenzie

  3. #18
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    what i really want the program to do, is simply have a list which should have the following output: 1 2 3 4 22 23 25 26 27.
    Then if this is what you really wanted, then the solution becomes two lines:
    Code:
    #include <algorithm>
    //..
    myList.sort();
    myList.erase(std::unique(myList.begin(), myList.end()), myList.end());
    //..
    1) Sort the list.
    2) Call std::unique() to move duplicates to the end.
    3) Remove the duplicates that were accumulated from step 2).

    That is what the code above does.

    Please look at this full sample program:
    Code:
    #include <iostream>
    #include <list>
    #include <algorithm>
    #include <iterator>
    
    using namespace std;
    
    int main()
    {
        list<int> myList;
        for (int i = 0; i < 10; ++i )
        {
          myList.push_back(i);
          myList.push_back(i+10);
          myList.push_back(i);
        }
        
        // output the original list
        copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));
        cout << "\n";
        
        // sort the list
        myList.sort();
    
        // gather dup items and erase them
        myList.erase(unique(myList.begin(), myList.end()), myList.end());
    
        // output the list again
        copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));
    }
    Regards,

    Paul McKenzie

  4. #19
    Join Date
    Jul 2013
    Posts
    374

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    what i really want the program to do, is simply have a list which should have the following output: 1 2 3 4 22 23 25 26 27.

    basically meaning that a single copy of every integer entered. Keeping in mind that the user can enter an integer mulitple times
    Then enter the integers into a std:map as the user inputs them. There will be no multiple integers and the integers will be kept in sorted order.

  5. #20
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    Quote Originally Posted by Paul McKenzie View Post
    Please post all of the code, not just what you "inserted" (since I have no idea where you "inserted" this code or what you really are running).

    Regards,

    Paul McKenzie
    Code:
    #include <list>
    #include <map>
    #include <iostream>
    #include <algorithm>
    #include <fstream>
    
    typedef std::list<int> IntList;
    typedef std::map<int, int> IntMap;
    
    using namespace std;
    
    int main()
    {
        IntList myList;
        IntList myDups;
        IntMap myMap;
       // IntList * pNode; 
    
       
        int num;
        int i = 0;
        int a[] = {0};
        bool numOk;
        do
        {
              cin >> num;
              numOk = ( num >= 1 && num <= 60 );
              if ( numOk ) 
              {
                   // add to the linked list
                   myList.push_back(num);
    
                  // record this entry in the map
                   myMap[num]++;
              } 
       }  while (numOk);
        
       
       IntMap::iterator it = myMap.begin();
       while ( it != myMap.end() )
       {
           
           if ( it->second > 1 )
          {
                 
               myDups.push_back(it->first);
    
              
               myList.erase( find(myList.begin(), myList.end(), it->first));
           }
        //  cout << myMap[it] << " ";
           ++it;
            
       }
       
        //  std::ofstream(myList.begin(), myList.end(), "list.txt");
     cout << endl << endl;
     
    
       std::map<int,int>::iterator xt= myMap.begin();
       
       while ( xt != myMap.end() )
       {
             cout <<  xt -> first << " " << xt -> second << endl;
             ++xt;
             
        }
        
       cout << endl << endl;
       myList.sort();
       IntList::iterator lt = myList.begin();
       while(lt != myList.end())
       {
           
          cout << *lt << " ";
           
           ++lt;
       }
        cout << endl << endl;
        myDups.sort();
       IntList::iterator ptr = myDups.begin();
       while(ptr != myDups.end())
       {
           
          cout << *ptr << " ";
           
           ++ptr;
       } 
       /*
       do 
       {
         ;
         
         i++;
         }while(!myList.end());
         */  
       
       system ("PAUSE");
       
    }
    above is the code that i ran. It still did not give me my desired results
    Last edited by rockx; January 1st, 2014 at 03:43 PM.

  6. #21
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    I also need to know as to why does the program crash when i change

    Code:
    if ( it->second > 1 )
    to

    Code:
    while ( it->second > 1 )

  7. #22
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    I also need to know as to why does the program crash when i change

    Code:
    if ( it->second > 1 )
    to

    Code:
    while ( it->second > 1 )
    The two constructs are different. One is a simple, single comparison, the other is a loop with that while() statement called each time the loop iterates. So which iteration of that while() loop causes the crash, and second, why did you change to a while loop()?

    Regards,

    Paul McKenzie

  8. #23
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,844

    Re: Linked List - Random Nodes

    if the user enters the following integers: 1 2 3 4 22 25 26 27 22 22 22 23 22

    what i really want the program to do, is simply have a list which should have the following output: 1 2 3 4 22 23 25 26 27.

    basically meaning that a single copy of every integer entered. Keeping in mind that the user can enter an integer mulitple times
    If that is what you want, you are making very heavy weather of a simple task. With this code

    Code:
    #include <map>
    #include <iostream>
    #include <list>
    using namespace std;
    
    typedef map<int, int> IntMap;
    typedef list<int> IntList;
    
    int main()
    {
    IntMap	myMap;
    IntList myList;
    
    int num;
    
    	while ((cin >> num) && num >= 1 && num <= 60)
    		myMap[num]++;
       
    	for (IntMap::const_iterator xt = myMap.begin(); xt != myMap.end(); ++xt)
    		myList.push_back(xt->first);
    
    	copy(myList.begin(), myList.end(), ostream_iterator<int>(cout, " "));
    	cout << endl;
    
    	return 0;
    }
    and an input of
    Code:
    2 3 4 1 27 22 25 22 16 22 5 34 22
    This gives the required sorted output of
    Code:
    1 2 3 4 5 16 22 25 27 34
    and with your data
    Code:
    1 2 3 4 22 25 26 27 22 22 22 23 22
    the output is the expected
    Code:
    1 2 3 4 22 23 25 26 27
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  9. #24
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Going back a few posts.

    First you said this:
    I am currently working on a code using Linked List. I would like my code to do the following:

    1. User Enter integers between 1-60 (first List)
    2. The application to check for all the repeated entries, remove them from the initial list and store them on a second list
    3. Now that the first list has only one copy of each entry, the application should randomly select a node (using for loop multiple times). After the selection is made, the stored information on the node should be shown and that node to be deleted (but temporarily)
    4. After the required number of (5) node data has been printed, all the temporarily deleted nodes to be reinstored.
    5. Once thats done, the details of the second list to printed in a summary form i.e frequency of each integer entered.
    Now you later say this:
    what i really want the program to do, is simply have a list which should have the following output: 1 2 3 4 22 23 25 26 27.
    So which are the real set of requirements?

    If it is the latter, then the problem is simple, as 2kaud shows. If it is the former, then the solution is a little more work, but still in the same ballpark as the simple solution given by 2kaud and razzle.

    Regards,

    Paul McKenzie

  10. #25
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    ok, as stated in my first post. i want the user to enter any integer between 1-60 (inclusive).

    the user has the liberty to enter any particular integer more than two times.

    And the set of numbers i gave was just for a test run, the input will vary depending on the user input.

    What Paul had given earlier worked just fine, absolutely what i needed apart from only one thing. Any one List should contain a single copy of all the integers entered.

  11. #26
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    What Paul had given earlier worked just fine, absolutely what i needed apart from only one thing. Any one List should contain a single copy of all the integers entered.
    The map already has the integers entered. The "first" of each of the map entries is the entered integer.

    Regards,

    Paul McKenzie

  12. #27
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    2kaud's code has already solved the problem.

    Now this leaves two of my requirements unattended. these are 3 & 4.
    3. the application should randomly select a node (using for loop multiple times). After the selection is made, the stored information on the node should be shown and that node to be deleted (but temporarily)
    4. After the required number of (5) node data has been printed, all the temporarily deleted nodes to be reinstored.
    or the application should randomly pick 5 nodes without pick one node twice.

  13. #28
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Location
    Florida
    Posts
    12,228

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    2kaud's code has already solved the problem.
    Yeah, he's good at doing homework for people. Do you understand what he did?

  14. #29
    Join Date
    Apr 1999
    Posts
    27,446

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    the application should randomly select a node (using for loop multiple times)
    What you should do is write a few small applications that do each of these steps.
    Code:
    #include <list>
    #include <algorithm>
    #include <iterator>
    
    typedef std::list<int> IntList;
    
    using namespace std;
    
    int main()
    {
        IntList iList;
        int somedata[] = {1, 4, 6, 8, 12, 22, 35, 89, 100, 200, 203, 287};
        const int sz = sizeof(somedata) / sizeof(somedata[0]);
    
        copy(somedata, somedata + sz, back_inserter(iList));
        //..now experiment with iList
    }
    You have now a linked list of data (iList) populated with test data. No need for anything else.

    Now how do you select an item in the list by random? That requires calling a random number generator function that generates a number between 0 and iList.size() - 1. That number is then used to determine the index of the item in the list you're looking for. Once you do that, then you need to figure out how to get that number from the list.

    All of these steps can be accomplished by doing some research on the std::list class and how to gain access to certain elements using an index, how to use rand() and srand(), etc.

    Regards,

    Paul McKenzie

  15. #30
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    I am having trouble with the index of a List. I m ok with index's of arrays.

    And as for rand() and srand(), i dont think this would be of much trouble. I have used the two previously and i m ok with it

Page 2 of 3 FirstFirst 123 LastLast

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

This is a CodeGuru survey question.


Featured


HTML5 Development Center