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

  1. #1
    Join Date
    May 2004
    Posts
    207

    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,277

    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
    207

    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 offline Moderator / MS MVP Power Poster
    Join Date
    Aug 2004
    Posts
    11,202

    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
    207

    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,057

    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
    207

    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,423

    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
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,057

    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.

  10. #10
    Join Date
    May 2004
    Posts
    207

    Re: Linked List - Random Nodes

    well the best i can think of is that

    if the nData of a particular NODE == x then all the x's to be removed and added to a second list.

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

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    well the best i can think of is that

    if the nData of a particular NODE == x then all the x's to be removed and added to a second list.
    That's just restating the problem, not coming up with the steps you need to solve it.

    As I said, forget code. Given a list of numbers, your brain, and a pencil and paper, what would you do? Be specific.

  12. #12
    Join Date
    May 2004
    Posts
    207

    Re: Linked List - Random Nodes

    1. re-write the numbers in ascending order
    2. cancel out all the numbers that have been repeated and noting them into another piece of paper. keeping in mind that one of the repeated numbers is left on the first piece of paper. re-write the numbers that have not been cancelled
    3. Tally all the numbers and build up a stat table for all the numbers on the second piece of paper (*with the repeated numbers)

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

    Re: Linked List - Random Nodes

    Quote Originally Posted by rockx View Post
    1. re-write the numbers in ascending order
    2. cancel out all the numbers that have been repeated and noting them into another piece of paper. keeping in mind that one of the repeated numbers is left on the first piece of paper. re-write the numbers that have not been cancelled
    3. Tally all the numbers and build up a stat table for all the numbers on the second piece of paper (*with the repeated numbers)
    Okay, that's one approach. Another that you may find easier is just to visit the first node, then read the rest of the list removing any nodes that have the same value and putting them in the second list. Repeat for the next node.

    Whichever approach you go with, once you have a plan, then you can think about how you need to implement it in code. Going with your approach, step one is to sort the list.

  14. #14
    Join Date
    May 2004
    Posts
    207

    Re: Linked List - Random Nodes

    well i would like to sort the data (Maybe later il dump the data in a DB or Excel Worksheet). and do whatever needs to be done.

    however i want to keep in mind that minimum memory is used, thus if using a weaker PC (PII o PII) should work just fine.

  15. #15
    Join Date
    May 2004
    Posts
    207

    Re: Linked List - Random Nodes

    what can i do to randomly select 5 nodes from the following

    Code:
    IntList myList;
    and output it to the screen

    Assuming there are more than 5 entries in the list

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