-
November 19th, 2013, 05:46 PM
#1
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');
}
-
November 19th, 2013, 05:58 PM
#2
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 06:03 PM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 19th, 2013, 06:26 PM
#3
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
-
November 19th, 2013, 06:30 PM
#4
Re: Linked List - Random Nodes
Originally Posted by rockx
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?
-
November 19th, 2013, 06:36 PM
#5
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 06:42 PM.
-
November 19th, 2013, 08:20 PM
#6
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?
-
November 19th, 2013, 09:50 PM
#7
Re: Linked List - Random Nodes
ive briefly stated the steps in my first post..... are you asking for the details?
-
November 20th, 2013, 06:24 AM
#8
Re: Linked List - Random Nodes
Originally Posted by rockx
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 11:57 AM.
-
November 20th, 2013, 06:41 AM
#9
Re: Linked List - Random Nodes
Originally Posted by rockx
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.
-
November 24th, 2013, 02:51 PM
#10
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.
-
November 24th, 2013, 03:34 PM
#11
Re: Linked List - Random Nodes
Originally Posted by rockx
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.
-
November 24th, 2013, 07:35 PM
#12
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)
-
November 25th, 2013, 08:17 AM
#13
Re: Linked List - Random Nodes
Originally Posted by rockx
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.
-
November 25th, 2013, 06:11 PM
#14
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.
-
November 29th, 2013, 08:44 PM
#15
Re: Linked List - Random Nodes
what can i do to randomly select 5 nodes from the following
and output it to the screen
Assuming there are more than 5 entries in the list
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|