Linked List - Random Nodes

[rockx]

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

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

[Paul McKenzie]

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

[Paul McKenzie]

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:

#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:

#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

[razzle]

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.

[rockx]

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

#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

[rockx]

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

if ( it->second > 1 )

to

while ( it->second > 1 )

[Paul McKenzie]

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

if ( it->second > 1 )

to

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

[2kaud]

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

#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

2 3 4 1 27 22 25 22 16 22 5 34 22

This gives the required sorted output of

1 2 3 4 5 16 22 25 27 34

and with your data

1 2 3 4 22 25 26 27 22 22 22 23 22

the output is the expected

1 2 3 4 22 23 25 26 27

[Paul McKenzie]

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

[rockx]

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.

[Paul McKenzie]

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

[rockx]

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.

[GCDEF]

2kaud's code has already solved the problem.

Yeah, he's good at doing homework for people. Do you understand what he did?

[Paul McKenzie]

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.

#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

[rockx]

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