-
March 25th, 2012, 07:19 PM
#1
Linked List Problem
Hello. I am supposed to write a program that process a linked list and creates distinct pairs.
For example. a list containing 5 becomes 5 5
5 2 4 5 4 becomes 5 5 2 2 4 4
1 2 3 3 1 3 2 becomes 1 1 2 2 3 3
1 3 1 1 0 4 3 2 0 3 2 2 2 2 3 4 1 1 2 becomes 1 1 3 3 0 0 4 4 2 2
3 0 2 2 2 0 1 5 1 0 0 4 4 1 0 5 becomes 3 3 0 0 2 2 1 1 5 5 4 4
5 5 5 5 2 3 1 3 3 2 3 0 2 4 1 4 becomes 5 5 2 2 3 3 1 1 0 0 4 4
If I pass a list with 5 2 4 5 4 it becomes 5 5 2 2 4 4 but when I pass a list without duplicates like
say 3 4 it will return 33 4. In other words it only creates one duplicate, everything else seems to be working. I would greatly appreciate if anyone could point me in the right direction.
Thank you in advance.
Code:
void CreateDistinctPairs()
{
Node* ourHead = head;
Node* first = head;
Node* prev = head;
bool duplicateFound = false;
while (first->next)
{
while (first)
{
prev = first;
first = first->next;
if ((!duplicateFound) && (first) &&
first->info == ourHead->info) // did we find a duplicate
{
duplicateFound = true;
if (ourHead->next != first) // duplicate not adjacent to ourHead
{
if (first->next != 0) // there is an adjacent node next to duplicate ?
{ // rearrange
prev->next = first->next; // rearrange them
first->next = ourHead->next; // to make duplicates
ourHead->next = first;
if (first->next)
{
prev = first;
first = first->next;
}
}
else
{
prev->next = first->next; // rearrange them
first->next = ourHead->next; // to make duplicates
ourHead->next = first;
first = 0;
}
}
}
if (duplicateFound && ourHead->next != first) // remove remaining duplicates
{
if ((first) && first->info == ourHead->info) // next duplicate found
{ // remove it
Node* nodeToRemove = prev->next;
first = first->next;
prev->next = first;
delete nodeToRemove;
}
}
if(first->next == 0 && (!duplicateFound))
{
Node* duplicate = new Node;
duplicate->info= ourHead->info;
duplicate->next = ourHead->next;
ourHead->next = duplicate;
first = 0;
}
}
duplicateFound = false;
if(ourHead->next->next == 0) break;
else
{
ourHead = ourHead->next->next;
first = ourHead;
}
}
}
-
March 25th, 2012, 11:26 PM
#2
Re: Linked List Problem
Originally Posted by MarcJ
If I pass a list with 5 2 4 5 4 it becomes 5 5 2 2 4 4 but when I pass a list without duplicates like
say 3 4 it will return 33 4. In other words it only creates one duplicate, everything else seems to be working. I would greatly appreciate if anyone could point me in the right direction.
Did you write this code? If you did, did you debug your code? If not, please do so. Posting a program (or bits and pieces of a program) and just saying "it doesn't work when I do 'x'" doesn't convey that you did enough to debug your program.
Debugging is a mandatory process in learning how to write programs. If the program doesn't behave as expected, then you're supposed to debug your code and find out what's wrong.
Use your compiler's debugger to single step through your program and determine where things go wrong. If you don't know how to use the debugger, then this is an excellent time to learn how to use it. You can't write programs unless you know how to debug them.
So when you debug your code, where does the code break down with the data you say doesn't produce the right results?
Regards,
Paul McKenzie
-
March 26th, 2012, 04:13 AM
#3
Re: Linked List Problem
Does the assignment require you to write your own list? If not, then don't write one! No one in their mind would. use an std::list instead
Even if you were required to write your own list, what you should do is first write your program using std::list, and then, replace std::list with your own list.
This is smart on many levels, but primarily, at allows you to cut into two separate blocks your container, and your algorithm. Given the state of your code, both are tightly interlocked, and the bugs could be anywhere: It could be your list, your algorithm, or potentially something dependent on both...
Last but not least, if your instructor gives you a new assignment next week, you'll have your list clean and prepared for re-use in another project.
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
March 26th, 2012, 10:18 AM
#4
Re: Linked List Problem
Originally Posted by Paul McKenzie
Did you write this code? If you did, did you debug your code? If not, please do so. Posting a program (or bits and pieces of a program) and just saying "it doesn't work when I do 'x'" doesn't convey that you did enough to debug your program.
Debugging is a mandatory process in learning how to write programs. If the program doesn't behave as expected, then you're supposed to debug your code and find out what's wrong.
Use your compiler's debugger to single step through your program and determine where things go wrong. If you don't know how to use the debugger, then this is an excellent time to learn how to use it. You can't write programs unless you know how to debug them.
So when you debug your code, where does the code break down with the data you say doesn't produce the right results?
Regards,
Paul McKenzie
I have written and debugged the code.
For the cases of rearranging and eliminating additional duplicates the program works.
For the case where there are no duplicates say, the list is 3, 4 and should turn into 3,3,4,4 the program only processes the first non duplicate producing 3,3,4.
I have run with the debugger through the program and this piece of code...
Code:
if(first->next == 0 && (!duplicateFound))
{
Node* duplicate = new Node;
duplicate->info= ourHead->info;
duplicate->next = ourHead->next;
ourHead->next = duplicate;
first = 0;
}
..that's responsible for creating duplicates is only executed once.
To be more precise I have a hard time figuring out to what condition I should change the inner while loop to have subsequent non-duplicates to be processed.
Does that make sense ?
-
March 26th, 2012, 11:29 AM
#5
Re: Linked List Problem
Originally Posted by monarch_dodra
Does the assignment require you to write your own list? If not, then don't write one! No one in their mind would. use an std::list instead
Even if you were required to write your own list, what you should do is first write your program using std::list, and then, replace std::list with your own list.
This is smart on many levels, but primarily, at allows you to cut into two separate blocks your container, and your algorithm. Given the state of your code, both are tightly interlocked, and the bugs could be anywhere: It could be your list, your algorithm, or potentially something dependent on both...
Last but not least, if your instructor gives you a new assignment next week, you'll have your list clean and prepared for re-use in another project.
Thanks for your advise. I am thinking on starting from scratch ...it just seems I get always lost in the middle of a moderate complex problem. I probably use the wrong approach...
-
March 26th, 2012, 11:38 AM
#6
Re: Linked List Problem
Does your assignment require that you modify your input list "in place"? Wouldn't it be simpler to create a second "result" list, that you would fill as you process the input?
Also, IMO, the "pairs" thing is just designed to confuse you. Why don't you just create a list with all the unique digits, and then "double them" once you have them all?
Code:
input: 5 5 5 5 2 3 1 3 3 2 3 0 2 4 1 4
output1: 5 2 3 1 0 4
output2: 5 5 2 2 3 3 1 1 0 0 4 4
The algorithm is pretty simple:
Code:
For every item in input: Is it inside output?
Yes - Process next item
No - Place inside output
Is your question related to IO?
Read this C++ FAQ article at parashift by Marshall Cline. In particular points 1-6.
It will explain how to correctly deal with IO, how to validate input, and why you shouldn't count on "while(!in.eof())". And it always makes for excellent reading.
-
March 26th, 2012, 12:39 PM
#7
Re: Linked List Problem
Originally Posted by monarch_dodra
Does your assignment require that you modify your input list "in place"? Wouldn't it be simpler to create a second "result" list, that you would fill as you process the input?
Also, IMO, the "pairs" thing is just designed to confuse you. Why don't you just create a list with all the unique digits, and then "double them" once you have them all?
Code:
input: 5 5 5 5 2 3 1 3 3 2 3 0 2 4 1 4
output1: 5 2 3 1 0 4
output2: 5 5 2 2 3 3 1 1 0 0 4 4
The algorithm is pretty simple:
Code:
For every item in input: Is it inside output?
Yes - Process next item
No - Place inside output
One of the requirements is that I have to detach and insert the first found duplicate. Of course if these nodes are adjacent then all I must do is delete subsequent duplicates. But I am only allowed to use ONE list.
-
March 26th, 2012, 03:18 PM
#8
Re: Linked List Problem
Originally Posted by MarcJ
One of the requirements is that I have to detach and insert the first found duplicate. Of course if these nodes are adjacent then all I must do is delete subsequent duplicates. But I am only allowed to use ONE list.
1) Write a function that deletes a node at a certain position
.
2) Write a function that inserts a node at a certain position.
3) Write a function that finds a node starting at a certain position and returns its pointer, NULL if not found.
There is no talk of duplicates in what I stated above. Maybe that's the problem -- you were fixated in finding duplicates, and all you really needed to do from the start was to write basic functions to do these tasks above, regardless of whether the nodes are duplicates or not.
The problem with your code is it is one monolithic function, with this function trying to stuff everything in one glob that is too difficult to manage. If you broke down your list in a functional manner, then the problem will become clearer for you to diagnose and debug. In other words, where is your InsertNode() function? Your FindNode() function? Your DeleteNode() function?
Once you have that, then the problem becomes manageable:
Code:
For each node i:
Step 1:
Get the number for node i.
Starting from node i+1, search for node with the same number.
If found, record this node's position (j)
insert the node at position i+1.
Starting at position j+1 remove all nodes that have the same node number as node i.
Go to next node after node i+1.
Go back to step1 if more nodes left.
So it's basically find, insert, delete, with keeping track of the position of the elements you've found.
Regards,
Paul McKenzie
Last edited by Paul McKenzie; March 26th, 2012 at 03:21 PM.
-
March 27th, 2012, 03:39 PM
#9
Re: Linked List Problem
Were you able to find solution to your problem. I am having a similar issue
Tags for this Thread
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
|