CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9
  1. #1
    Join Date
    Apr 2006
    Posts
    15

    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;		
    		}		
    					
    	}		
     }

  2. #2
    Join Date
    Apr 1999
    Posts
    27,449

    Re: Linked List Problem

    Quote Originally Posted by MarcJ View Post
    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

  3. #3
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    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.

  4. #4
    Join Date
    Apr 2006
    Posts
    15

    Re: Linked List Problem

    Quote Originally Posted by Paul McKenzie View Post
    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 ?

  5. #5
    Join Date
    Apr 2006
    Posts
    15

    Re: Linked List Problem

    Quote Originally Posted by monarch_dodra View Post
    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...

  6. #6
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    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.

  7. #7
    Join Date
    Apr 2006
    Posts
    15

    Re: Linked List Problem

    Quote Originally Posted by monarch_dodra View Post
    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.

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

    Re: Linked List Problem

    Quote Originally Posted by MarcJ View Post
    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.

  9. #9
    Join Date
    Apr 2008
    Posts
    5

    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
  •  





Click Here to Expand Forum to Full Width

Featured