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

Thread: Linked List - Random Nodes

  1. #31
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    Quote Originally Posted by GCDEF View Post
    Yeah, he's good at doing homework for people. Do you understand what he did?
    It has already been established earlier that this is not homework.
    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.

  2. #32
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    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
    Do you need a List or would a Vector be OK for your needs?
    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.

  3. #33
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    I am having trouble with the index of a List. I m ok with index's of arrays.
    Use std::advance() to get to a certain item in a list (a std::list does not have random access iterators, so you must use advance() to get to an item, as opposed to a vector).

    But again, all of this is easily discovered by doing a little research on the web.

    Regards,

    Paul McKenzie

  4. #34
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    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.

  5. #35
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,132

    Re: Linked List - Random Nodes

    Quote Originally Posted by 2kaud View Post
    It has already been established earlier that this is not homework.
    The principal is the same. Do you really think the OP learned from or understood your posting? I don't. He got the output he wanted and he's moved to the next part, but learned nothing. I just don't see how giving code like that helps anybody.

  6. #36
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    This isnt a homework question.

    and yes i have learnt a few new things. And yes i understood both Paul's and 2kauds code. Ive questioned things that i did not understand

    Quote Originally Posted by 2kaud View Post
    Do you need a List or would a Vector be OK for your needs?
    Vectors would b just fine. anything as long as its dynamic

  7. #37
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    This isnt a homework question

    I have learnt a few things from the code given by Paul and 2kaud

    Quote Originally Posted by 2kaud View Post
    Do you need a List or would a Vector be OK for your needs?
    Vectors would just be fine. Anything would work as long as its Dynamic

  8. #38
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,132

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    This isnt a homework question

    I have learnt a few things from the code given by Paul and 2kaud
    I didn't ask if you'd learned a few things. I asked specifically if you understand the code he posted. This isn't a knock on you as you're just a beginner, but I'm betting you don't. Which leads me to question whether just posting code that the OP can't understand with no explanation is really actually helping anybody long term. It got you past your immediate sticking point, but if you don't know how or why, I don't think it helped you.

  9. #39
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    Vectors would just be fine. Anything would work as long as its Dynamic
    If vectors would be OK, I would consider using them instead of lists as it would make your random accessing requirement a little easier as you can then just use the [] notation rather than having to use advance().

    In my code from post #23, just change list<int> to vector<int> and include <vector> rather than <list>. You can then access the elements as myList[2] etc.
    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.

  10. #40
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    ive now used Vectors with all the proper declarations.

    Code:
    for(int i = 0; i < 5; i++)
       {
    	   randomIndex = rand() % myList.size();
    	   cout << myList[randomIndex] << " ";
       }
    however i stil face the problem of the repetition. indexes are selected more than once, despite having a large selection of indices.

    I m not that good with Vectors

  11. #41
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    ive now used Vectors with all the proper declarations.

    Code:
    for(int i = 0; i < 5; i++)
       {
    	   randomIndex = rand() % myList.size();
    	   cout << myList[randomIndex] << " ";
       }
    however i stil face the problem of the repetition. indexes are selected more than once, despite having a large selection of indices.

    I m not that good with Vectors
    This has nothing to do with vectors. You are seeming to use them fine. The issue is about rand(). It will produce the number in the desired range, but there is no guarantee that the random numbers produced will be unique. It is highly likely that there will be repeats. If you don't want the same index to be selected then you will need to maintain a container (set?) of previously produced random numbers and loop producing the number until one is produced that hasn't been used before, then add that nunber to the set.
    Last edited by 2kaud; January 3rd, 2014 at 05:32 PM. Reason: Typing issues
    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.

  12. #42
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    I dont know how to do that

  13. #43
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,573

    Re: Linked List - Random Nodes

    I dont know how to do that
    At the risk of detention from the Headmaster (I'm looking at you GCDEF ), have a look at this code. Its based upon my example from post #23.

    Code:
    #include <map>
    #include <iostream>
    #include <vector>
    #include <set>
    #include <ctime>
    using namespace std;
    
    typedef map<int, int> IntMap;
    typedef vector<int> IntList;
    typedef set<int> IntSet;
    
    int main()
    {
    IntMap	myMap;
    IntList myList;
    IntSet mySet;
    
    int num;
    
    	srand(time(NULL));
    
    	while ((cin >> num) && num >= 1 && num <= 60)
    		myMap[num]++;
    
    	myList.reserve(myMap.size());	//Avoid memory reallocation for the vector as size as known
       
    	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;
    
    	for (int i = 0, mysize = myList.size(); i < mysize; i++) {
    		int randomIndex;
    		while (mySet.count(randomIndex = rand() % mysize));
    		mySet.insert(randomIndex);
    		cout << myList[randomIndex] << " ";
            }
    
    	return 0;
    }
    It will output all the unique numbers entered first in sorted ascending order and then in a random order. Obtaining a unique random number is based upon using a set to hold the numbers already used. Sets are containers that store unique elements. See http://www.cplusplus.com/reference/set/set/
    So every time a random number is generated, it is checked to see if it is already in the set. If it is then count is not 0 and we generate another number. If count is 0, we have a unique random number so exit the while loop and add the number to the set.

    Given the input
    Code:
    2 3 4 1 27 22 25 22 16 22 5 34 22 90
    one output is
    Code:
    1 2 3 4 5 16 22 25 27 34
    2 27 1 34 5 25 22 4 3 16
    Obviously, the condition on i in the for loop determines how many of the numbers are output in a random order. The condition must be less than mysize.
    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.

  14. #44
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    i think il drop the ball here. Now il need this piece of code in March/April.

    Well neverthelss it was really good to get the info from 2kaud and Paul. it ws some new lessons for me. i put the real test to this code on Jan 4th, and randomising it basically failed to achieve the ultimate goal.
    --------------------------------------------------
    Please pardon me for having bad English.

Page 3 of 3 FirstFirst 123

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