none
Linked Lists

    Question

  • I am currently working on a code using Linked List. I would like my code to do the following:

    1. User Enters integers between 1-60 in the 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

    A couple of friends have helped me get to the following code.

    #include <list>
    #include <map>
    #include <iostream>
    #include <algorithm>
    
    typedef std::list<int> IntList;
    typedef std::map<int, int> IntMap;
    
    using namespace std;
    
    int main()
    {
        IntList myList;
        IntList myDups;
        IntMap myMap;
    
       
        int num;
        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));
           }
           
           ++it;
       }
    }

    Now that the first list has only one copy of each entry, the application should randomly select five nodes (using a loop). After the selection is made, the stored information on the node should be shown and that node to be deleted (but temporarily).  Once the data from the fifth node is shown, all the deleted nodes to be re-stored to the original, without creating a duplicate. If the user wishes to select another set of (5) nodes, he/she has the liberty to do so.

    Together with this, the statistics of the second list to be shown in a summary.

    Tuesday, December 24, 2013 10:39 PM

Answers

  • You obviously know how to create loops.  You should have no trouble seeding and using the random number generator to select nodes.  (You can use the modulus operator, %, to convert the random number into a valid index into myList.)

    Your comment about restoring the selected values without creating duplicates implies that the random selection process can select the same node multiple times.  But this is inconsistent with the requirement that the node be deleted after it is selected.  Please clarify.

    One method of restoring myList after the selection process is done would be to encapsulate the process in a function which takes myList (not a reference, not a pointer, the actual list) as an argument.  In this way, whatever the function does to the local copy of the list, such as deleting nodes, would not affect the "real" list in main.  When the function returns, myList will appear as restored.

    Just as your input loop was able to determine when the user had finished entering numbers, the selection/display/restore process in main (even if it is just a statement to call the function described above) should be embedded in a loop that asks the user if he want to select another set of random nodes or not.

    As an aside, your duplicate removal process removes all nodes which have a duplicate value.  Normally when removing duplicates is required, the intent is to remove all but one and leave that one unduplicated copy in the list.

    Monday, December 23, 2013 6:30 PM
  • Ok, in simple terms i have created confusions. now let me clear everything up.


    The above posted code allows the user to enter numbers into a dynamic array (linked list).


    1. THe user has the liberty to enter any number mulitple times.

    2. The code removes all the duplicates and stores them into another list (myDups), so that the myList contains a single copy of each integer entered (1-60).

    3. Now the code should randomly select five nodes and output the data (ofstream or cout to the screen). However the case shouild be such that no one node is selected more than ONCE. In other words if a node is selected in a single run, it should not be available for a second pick unless all the required 5 nodes have been picked.

    4. Once the five nodes have been selected and the data revealed to the user, the five nodes should again be available for selection if the user wants to make another set of selection......this gives the user the liberty to make as many set of 5 selections as possible.

    5. When the user has done all the selection in sets of five (5). the application should provide the the statistics of the second list, myDups in a summary. The summary should have all the integers entered and the frequency of occurence of each integer.

    Logically i know whats to be done, but i really dont know how to code it.

    What i have in mind is that an iterator should start from the TAIL of the list and traverse back to the HEAD and select random nodes.....either in a loop or in a single run. but i dont know how to code this.

    0 - A linked list is different than a dynamic array.  It may appear the same to the user but as the coder you should not confuse the two.

    2 - My original assessment was incorrect.  The code you posted removes only the first entry in myList that contains a duplicated value.  If that value was entered more than twice, myList will still contain duplicates.  Consider the input sequence 2 1 2 3 2 0.  myList contains nodes with 2, 1, 2, 3, and 2 in that order.  myMap contains the entries (2,3), (1,1), and (3,1) in whatever order.  When iterator it eventually points to the entry containing (2,3), find will return an iterator that points to myList node and erase will remove that node.  myList will now contain nodes with 1, 2, 3, 2 in that order.  At this point you increment iterator it and therefore will never attempt to process another node containing 2.

    3 - There seem to be two choices:

         a - You can change IntList so instead of a bare int each node contains a struct which an int and a bool as members.  When you randomly select a node, you test the bool.  If it is false, you set it and use the int.  If it is true, you pick another random node.  After processing all five random nodes, you reset all the bool members to false.

         b - You copy the selected node to a new list called myChosen and the delete the node from myList.  After processing all five random nodes, you copy the nodes back to myList and empty myChosen.  This has the undesired side effect of reordering myList.

    4 - See 3 above.

    5 - myDups has no information about any integer that was entered only once.  But myMap does have all the information you need.

    If you are selecting nodes at random, don't bother reading nodes sequentially.  Let the iterator handle it.  For random node R, IntList::iterator r = myList.begin()+R gets you where you want.

    Surely you can write a loop that iterates 5 times.  In each iteration, generate a random number.  Use that number to select a node from myList.

    Wednesday, December 25, 2013 6:05 AM

All replies

  • I am currently working on a code using Linked List. I would like my code to do the following:

    1. User Enters integers between 1-60 in the 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

    A couple of friends have helped me get to the following code.

    #include <list>
    #include <map>
    #include <iostream>
    #include <algorithm>
    
    typedef std::list<int> IntList;
    typedef std::map<int, int> IntMap;
    
    using namespace std;
    
    int main()
    {
        IntList myList;
        IntList myDups;
        IntMap myMap;
    
       
        int num;
        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));
           }
           
           ++it;
       }
    }

    Now that the first list has only one copy of each entry, the application should randomly select five nodes (using a loop). After the selection is made, the stored information on the node should be shown and that node to be deleted (but temporarily).  Once the data from the fifth node is shown, all the deleted nodes to be re-stored to the original, without creating a duplicate. If the user wishes to select another set of (5) nodes, he/she has the liberty to do so.

    Together with this, the statistics of the second list to be shown in a summary. basically meaning, the frequency of each Integer to be in a tabulated form.

    Sunday, December 22, 2013 1:20 AM
  • Hi.

    I wish I could help you but I am more skilled in .NET than in C++.

    This forum is primarily used for Microsoft Learning and Microsoft Certification. Perhaps you could get a helpful response on the C++ forum, located here:
    http://social.msdn.microsoft.com/Forums/vstudio/en-US/home?forum=vcgeneral

    Good luck!


    Best wishes, Davin Mickelson


    Sunday, December 22, 2013 10:27 PM
  • Hello,

    Please forgive my poor understanding, could you please clarify the concrete questions here?

    Then I would know what I can do for you.

    Here are some related links below:

    list Class

    STL101 Part B - List and Iterators

    Thanks for your understanding.

    Best Regards,

    Jane.


    We are trying to better understand customer views on social support experience, so your participation in this interview project would be greatly appreciated if you have time. Thanks for helping make community forums a great place.
    Click HERE to participate the survey.

    Monday, December 23, 2013 6:31 AM
    Moderator
  • You obviously know how to create loops.  You should have no trouble seeding and using the random number generator to select nodes.  (You can use the modulus operator, %, to convert the random number into a valid index into myList.)

    Your comment about restoring the selected values without creating duplicates implies that the random selection process can select the same node multiple times.  But this is inconsistent with the requirement that the node be deleted after it is selected.  Please clarify.

    One method of restoring myList after the selection process is done would be to encapsulate the process in a function which takes myList (not a reference, not a pointer, the actual list) as an argument.  In this way, whatever the function does to the local copy of the list, such as deleting nodes, would not affect the "real" list in main.  When the function returns, myList will appear as restored.

    Just as your input loop was able to determine when the user had finished entering numbers, the selection/display/restore process in main (even if it is just a statement to call the function described above) should be embedded in a loop that asks the user if he want to select another set of random nodes or not.

    As an aside, your duplicate removal process removes all nodes which have a duplicate value.  Normally when removing duplicates is required, the intent is to remove all but one and leave that one unduplicated copy in the list.

    Monday, December 23, 2013 6:30 PM
  • Ok, in simple terms i have created confusions. now let me clear everything up.


    The above posted code allows the user to enter numbers into a dynamic array (linked list).


    1. THe user has the liberty to enter any number mulitple times.

    2. The code removes all the duplicates and stores them into another list (myDups), so that the myList contains a single copy of each integer entered (1-60).

    3. Now the code should randomly select five nodes and output the data (ofstream or cout to the screen). However the case shouild be such that no one node is selected more than ONCE. In other words if a node is selected in a single run, it should not be available for a second pick unless all the required 5 nodes have been picked.

    4. Once the five nodes have been selected and the data revealed to the user, the five nodes should again be available for selection if the user wants to make another set of selection......this gives the user the liberty to make as many set of 5 selections as possible.

    5. When the user has done all the selection in sets of five (5). the application should provide the the statistics of the second list, myDups in a summary. The summary should have all the integers entered and the frequency of occurence of each integer.

    Logically i know whats to be done, but i really dont know how to code it.

    What i have in mind is that an iterator should start from the TAIL of the list and traverse back to the HEAD and select random nodes.....either in a loop or in a single run. but i dont know how to code this.

    Tuesday, December 24, 2013 10:39 PM
  • could the above be achived through C#?
    Tuesday, December 24, 2013 10:41 PM
  • Ok, in simple terms i have created confusions. now let me clear everything up.


    The above posted code allows the user to enter numbers into a dynamic array (linked list).


    1. THe user has the liberty to enter any number mulitple times.

    2. The code removes all the duplicates and stores them into another list (myDups), so that the myList contains a single copy of each integer entered (1-60).

    3. Now the code should randomly select five nodes and output the data (ofstream or cout to the screen). However the case shouild be such that no one node is selected more than ONCE. In other words if a node is selected in a single run, it should not be available for a second pick unless all the required 5 nodes have been picked.

    4. Once the five nodes have been selected and the data revealed to the user, the five nodes should again be available for selection if the user wants to make another set of selection......this gives the user the liberty to make as many set of 5 selections as possible.

    5. When the user has done all the selection in sets of five (5). the application should provide the the statistics of the second list, myDups in a summary. The summary should have all the integers entered and the frequency of occurence of each integer.

    Logically i know whats to be done, but i really dont know how to code it.

    What i have in mind is that an iterator should start from the TAIL of the list and traverse back to the HEAD and select random nodes.....either in a loop or in a single run. but i dont know how to code this.

    0 - A linked list is different than a dynamic array.  It may appear the same to the user but as the coder you should not confuse the two.

    2 - My original assessment was incorrect.  The code you posted removes only the first entry in myList that contains a duplicated value.  If that value was entered more than twice, myList will still contain duplicates.  Consider the input sequence 2 1 2 3 2 0.  myList contains nodes with 2, 1, 2, 3, and 2 in that order.  myMap contains the entries (2,3), (1,1), and (3,1) in whatever order.  When iterator it eventually points to the entry containing (2,3), find will return an iterator that points to myList node and erase will remove that node.  myList will now contain nodes with 1, 2, 3, 2 in that order.  At this point you increment iterator it and therefore will never attempt to process another node containing 2.

    3 - There seem to be two choices:

         a - You can change IntList so instead of a bare int each node contains a struct which an int and a bool as members.  When you randomly select a node, you test the bool.  If it is false, you set it and use the int.  If it is true, you pick another random node.  After processing all five random nodes, you reset all the bool members to false.

         b - You copy the selected node to a new list called myChosen and the delete the node from myList.  After processing all five random nodes, you copy the nodes back to myList and empty myChosen.  This has the undesired side effect of reordering myList.

    4 - See 3 above.

    5 - myDups has no information about any integer that was entered only once.  But myMap does have all the information you need.

    If you are selecting nodes at random, don't bother reading nodes sequentially.  Let the iterator handle it.  For random node R, IntList::iterator r = myList.begin()+R gets you where you want.

    Surely you can write a loop that iterates 5 times.  In each iteration, generate a random number.  Use that number to select a node from myList.

    Wednesday, December 25, 2013 6:05 AM
  • what can i do to my code so that a single copy of every integer entered gets stored in a List. Assuming taht the user entered some integers just once and the others multiple times.
    Thursday, December 26, 2013 2:00 AM
  • You had no trouble using myMap to keep track of how many times each integer was entered.  Why do you find it difficult to decrement that count as you remove a node?  Then all you need to do is change the test of it->second from an if to a while.
    Friday, December 27, 2013 10:52 AM
  • You had no trouble using myMap to keep track of how many times each integer was entered.  Why do you find it difficult to decrement that count as you remove a node?  Then all you need to do is change the test of it->second from an if to a while.

    when i change the test from if to while, the program crashes. I think this is due to the fact taht one integer is entered multiple times.

    • Edited by nairk007 Wednesday, January 01, 2014 8:32 PM
    Wednesday, January 01, 2014 8:23 PM
  • Show us your current version of the program.  It might even pay to start a new message thread.
    Wednesday, January 01, 2014 10:15 PM