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

Thread: Linked List - Random Nodes

Hybrid View

  1. #1
    Join Date
    May 2004
    Posts
    209

    Question Linked List - Random Nodes

    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.

    below is my code.

    Code:
    #include <iostream>
    #include <stdlib.h>
    #include <string>
    #include <fstream>
    
    using namespace std;
    
    struct NODE {
       NODE *pNext;
       NODE *pPrev;
       int nData;
    };
    
    //declare head and tail of list
    //originally the list is empty
    NODE *pHead=NULL, *pTail=NULL;
    
    void AppendNode(NODE *pNode);
    void InsertNode(NODE *pNode, NODE *pAfter);
    void RemoveNode(NODE *pNode);
    void DeleteAllNodes( );
    void discard_line(ifstream &in);
    
    int main()
    {
        int i = 0;
        NODE * pNode;
        NODE * pNode1;
    
        //Add items to linked list
        do
        {
            pNode = new NODE;    //allocate
    	                        // memory for each node and make
                                // pointer point to the
            cin >> i;                    //dynamically allocated memory
        	pNode->nData = i;  //put some data in the node
            AppendNode(pNode); //add node to list
        }while((i >= 1 )&&(i <= 60));
    
    /*
    
        for(int i = 0; i < = 3; i++){	
    
        	for(int j = 0; j < 5; j++)
        	{
              pNode1 = pNode1 % (pNode->nData);
              
        	}
    	}  */
        // Now display each item in list
        for(pNode = pHead; pNode != NULL; pNode = pNode->pNext)
            cout<<pNode->nData<<endl;
    
       // DeleteAllNodes();
    
        
        for(pNode = pHead; pNode != NULL; pNode = pNode->pNext)
        {
            cout<<pNode->nData<< "\t";
        }
    
        system ("pause");
        return 0;
    }
    
    //function Implementations
    
    void AppendNode(NODE *pNode)
    {
       if (pHead == NULL) {     //if list is empty
          pHead = pNode;        //make head point to pNode
          pNode->pPrev = NULL;
       }
       else {
          pTail->pNext = pNode;  //make tail point to pNode
          pNode->pPrev = pTail;
       }
       pTail = pNode;        //tail is now pNode
       pNode->pNext = NULL;  //pNode next now points to NULL
    }
    
    /* Inserts a node into the list after pAfter
    void InsertNode(NODE *pNode, NODE *pAfter)
    {
       pNode->pNext = pAfter->pNext; //make next of new node point to "next" node
       pNode->pPrev = pAfter;               //make prev of new node point the "after" node
    
       if (pAfter->pNext != NULL)       // if we are NOT inserting at the end
          pAfter->pNext->pPrev = pNode;    //make prev of  "next" node point to the new node
       else
          pTail = pNode;                      //if we are inserting at the end, make new node the tail
    
       pAfter->pNext = pNode;   //make next of  "after" node point to new node
    }
    */
    // Removes the specified node from the list
    void RemoveNode(NODE *pNode)
    {
       if (pNode->pPrev == NULL)  //if removing the head
           pHead = pNode->pNext;
    
       else
          pNode->pPrev->pNext = pNode->pNext;  //if removing a middle node
    
       if (pNode->pNext == NULL)  //if removing the tail
          pTail = pNode->pPrev;
           
       else
          pNode->pNext->pPrev = pNode->pPrev;
    
       delete pNode;  //*free the memory
    }
    
    //****** Deletes the entire list******
    void DeleteAllNodes( )
    {
       while (pHead != NULL)   //keep on removing until the 
                               //head points to NULL
          RemoveNode(pHead);
    }
    
    void discard_line(ifstream &in)
    {
        char c;
    
        do
       	    in.get(c);
        while (c!='\n');
    }

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,319

    Re: Linked List - Random Nodes

    So what's the c++ question? Is this a homework assigment?

    For adding/removing temporary nodes and moving between 2 lists, why not just have one list with a flag stored in the node which indicates whether temporarily removed or not?
    Last edited by 2kaud; November 19th, 2013 at 05:03 PM.
    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. #3
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    This is not a homework/assignment question. it is something that ive come up with for my personal needs.

    I want something such that, later i can use a DB to store the information entered

  4. #4
    Arjay's Avatar
    Arjay is online now Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,220

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    This is not a homework/assignment question. it is something that ive come up with for my personal needs.

    I want something such that, later i can use a DB to store the information entered
    Okay, since it isn't homework, why not use std::list? Why roll your own list?

  5. #5
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    i have done what i m aware of. and i m still in the process of learning. so i havent put up things i dont know of....anyone is free to even modify my functions
    Last edited by rockx; November 19th, 2013 at 05:42 PM.

  6. #6
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,068

    Re: Linked List - Random Nodes

    There's a bug in this code
    Code:
        do
        {
            pNode = new NODE;    //allocate
    	                        // memory for each node and make
                                // pointer point to the
            cin >> i;                    //dynamically allocated memory
        	pNode->nData = i;  //put some data in the node
            AppendNode(pNode); //add node to list
        }while((i >= 1 )&&(i <= 60));
    If the user enters a number outside of the range, you're still putting it in the list.

    Looks like you need to implement step 2. Forgetting about coding for now, you need to work out what steps you need to do that. Any ideas yet?

  7. #7
    Join Date
    May 2004
    Posts
    209

    Re: Linked List - Random Nodes

    ive briefly stated the steps in my first post..... are you asking for the details?

  8. #8
    Join Date
    Apr 1999
    Posts
    27,424

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    ive briefly stated the steps in my first post..... are you asking for the details?
    Since this is not homework, then it is advantageous to use (and learn) the C++ standard library -- this is what it was designed for:
    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
    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;
    
        // Requirement #1
        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);
        
       // Requirement #2 -- go through map and remove dups from list (adding to new list)
       IntMap::iterator it = myMap.begin();
       while ( it != myMap.end() )
       {
           // check if map entry has a count > 1
           if ( it->second > 1 )
          {
               // add this entry to duplicate linked list  
               myDups.push_back(it->first);
    
              // find and erase this entry from the original linked list
               myList.erase( find(myList.begin(), myList.end(), it->first));
           }
           // go to next item in map
           ++it;
       }
    }
    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
    Last edited by Paul McKenzie; November 20th, 2013 at 10:57 AM.

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

  10. #10
    Join Date
    Apr 1999
    Posts
    27,424

    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

  11. #11
    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 02:43 PM.

  12. #12
    Join Date
    Apr 1999
    Posts
    27,424

    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

  13. #13
    Join Date
    Jul 2013
    Posts
    247

    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.

  14. #14
    Join Date
    Apr 1999
    Posts
    27,424

    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

  15. #15
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,068

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    ive briefly stated the steps in my first post..... are you asking for the details?
    I'm asking if you have an approach for solving step 2 of your problem. Don't think of it in terms of code yet, just explain what steps you need to take to implement it.

Page 1 of 3 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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center