-
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.
-
December 25th, 2013, 08:57 PM
#9
Re: Linked List - Random Nodes
Originally Posted by Paul McKenzie
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
-
December 26th, 2013, 12:14 AM
#10
Re: Linked List - Random Nodes
Originally Posted by rockx
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
-
December 28th, 2013, 02:40 AM
#11
Re: Linked List - Random Nodes
Originally Posted by Paul McKenzie
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 03:43 PM.
-
December 26th, 2013, 12:27 AM
#12
Re: Linked List - Random Nodes
Originally Posted by rockx
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
-
December 26th, 2013, 01:09 AM
#13
Re: Linked List - Random Nodes
Originally Posted by rockx
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.
-
January 1st, 2014, 05:33 PM
#14
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
-
November 20th, 2013, 06:41 AM
#15
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.
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
|