Thread: List exercise: Given two lists, write a function which delete common elements.....

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    33

    List exercise: Given two lists, write a function which delete common elements.....

    Hi everyone! I have a little problem with the solution of this exercise:

    List exercise: Given two lists, A and B, write a function which delete common elements in the list named "B".

    Here there is what I written:

    Code:
    
    
    void delete_commons (int m, struct node *B, struct node *A){
    
    
    
    
    
    
      int i;
      for (i=0;i<m;i++){
    
    
             if ((B->value)==(A->value)){
    
                 struct node *temp;
                 temp=B;
                 B= &(*(B->next));
                 free (temp);
                A=&(*A->next);
                delete_commons (m-1,B,A);
    
    
        }
    
        else{
    
                A=&(*A->next);
               delete_commons (m-1,B,A);
    
    
        }
    
    
        B=&(*(B->next));
    
      }
    }
    There is a bug, but I can't fix that.

    NOTE:
    1)Struct node is the structured data formed by the float value and the pointer to another node;
    2) "m" is the number of nodes of the list named "B"

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,082
    I suggest that you declare the function like this:
    Code:
    void delete_common_elements(struct node *A, struct node **B) {
    You need B to be a pointer to a pointer because the head node of B might have a value in common with some node in A.

    For the actual implementation, use iteration, not recursion (although you could implement a recursive solution after you have a working iterative solution, I guess).
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post
    You need B to be a pointer to a pointer because the head node of B might have a value in common with some node in A.

    For the actual implementation, use iteration, not recursion (although you could implement a recursive solution after you have a working iterative solution, I guess).
    Hello Laserlight!

    Thanks again for your answer.

    Here there is what I changed:

    Code:
    void delete_commons (struct list **B, struct list **A){
    	while ((*A)!=NULL && (*B)!=NULL){
    		if (((*B)->value)==((*A)->value)){
    			delete(B);
    
    
    		}
    		else if(((*B)->value)!=((*A)->value)){
    			nexta(A);
    		}
    		nexta(B);
    
    
    	}
    }
    
    
    
    
    void nexta (struct list **C){
    	if (((*C)->next)!=NULL)
    		(*C)=((*C)->next);
    }
    
    
    void delete(struct list **C){
    	struct list *temp;
    	temp=(*C);
    	nexta (C);
    	free (temp);
    
    
    
    
    }
    Still not working.
    I keep on working on it. If you have any advice, it would be very helpful!

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,082
    Your algorithm is just wrong. You need to work it out say on paper first.

    You also need to work out how to delete a node from a linked list. You don't seem able to do that, and if you can't do that, this exercise is beyond you, so practice that first.

    The nexta function just obscures your logic. I wouldn't use it.

    A shouldn't be a pointer to a pointer.

    I have no idea why you reverted to calling your node type struct list. Also, you should show the struct declaration.
    Last edited by laserlight; 07-23-2019 at 11:36 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post

    You also need to work out how to delete a node from a linked list. You don't seem able to do that, and if you can't do that, this exercise is beyond you, so practice that first.
    I'm sorry for the name of structured data.

    This is the one:
    Code:
    struct node {
      float value;
      struct node *next;
    };
    Here there is the function which deletes an element from a linked list:

    Code:
    void delete(struct node*C){
    	struct node *temp;
    	temp=C;
            C=(C->next);
    	free (temp);
    
    
    }

    Note: this function I wrote is very simple because, in this case, I don't need the function which removes a node of a list which contains a specific value.
    May I ask you if, in your opinion, that one is wrong?



    A shouldn't be a pointer to a pointer because in this case there isn't the possibility that I will have to delete the head of that list. You're right.
    Thank you for your advices laserlight!!!

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,082
    I recommend that you change the value member to be an int rather than a float. It's easier that way. When you have something that's working well, you can then change the member back to float and make the code adjustments required to compare for "equal" floating point values. Otherwise, you currently have the problem in which a simple some_node->value == other_node-> value might not give you the result you expect.

    Quote Originally Posted by letthem
    Note: this function I wrote is very simple because, in this case, I don't need the function which removes a node of a list which contains a specific value.
    May I ask you if, in your opinion, that one is wrong?
    It's wrong. Test the delete function as a unit and it will be obvious. That is, write a main function that creates a linked list with three nodes. Use your delete function to delete the middle node. Now print the entire linked list starting fron the head.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post

    It's wrong. Test the delete function as a unit and it will be obvious. That is, write a main function that creates a linked list with three nodes. Use your delete function to delete the middle node. Now print the entire linked list starting fron the head.

    My opinion is that:
    In the function I wrote, the input always changeds(because of the function nexta), so, theorically, it should be able to remove nodes "in the middle".
    This is just my opinion, but it doesn't have much importance because the program is not working.

    However, this is how I would write a function to remove nodes which contains a specific value from a linked list (assuming that now all values are int):

    Code:
     void remove_node(struct node **dptr, int n) {
    
             while (*dptr != NULL){
    Code:
                 if ((*dptr)->value != n)
                      *dptr = (*dptr)->next;
    
                 else{
                     struct node *temp;
                     temp = *dptr;
                    *dptr = (*dptr)->next;
                    free (temp);
                 }
         }
    }


    Is that correct in your opinion?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,082
    Quote Originally Posted by letthem
    Is that correct in your opinion?
    In my opinion, you should stop asking me for my opinion on whether something is correct until you have tested it and found that it appears to be correct. At that point, asking me for my opinion on its correctness makes sense because I might be able to say, spot undefined behaviour that makes it seem like your code works when actually it doesn't. But if you haven't tested your code, don't ask for opinions on whether your code is correct. Test your code, otherwise I'm just going to tell you that in my opinion, your untested code is wrong (even if it is correct)... it's wrong because you haven't tested it.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post
    In my opinion, you should stop asking me for my opinion on whether something is correct until you have tested it and found that it appears to be correct. At that point, asking me for my opinion on its correctness makes sense because I might be able to say, spot undefined behaviour that makes it seem like your code works when actually it doesn't. But if you haven't tested your code, don't ask for opinions on whether your code is correct. Test your code, otherwise I'm just going to tell you that in my opinion, your untested code is wrong (even if it is correct)... it's wrong because you haven't tested it.
    It's not correct dear Laserlight.
    I hope that I'm not bothering you.
    Actually it isn't correct.
    The function deletes the float element given in input, but it doesn't link correctly the list after the removal.

    I keep on working on it.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,082
    Quote Originally Posted by letthem
    The function deletes the float element given in input, but it doesn't link correctly the list after the removal.
    Now you're getting somewhere! Here's a hint: to remove an element from a linked list, you must link the previous element to the next element of the element that is to be removed. This excludes the element from the rest of the linked list, thereby allow you to free its memory safely. If the element to be removed is the head, its next element becomes the new head.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 07-23-2019, 12:38 PM
  2. Replies: 1
    Last Post: 06-24-2018, 10:41 AM
  3. Replies: 1
    Last Post: 06-18-2018, 11:28 AM
  4. Replies: 3
    Last Post: 06-16-2018, 08:30 AM
  5. List - Why my delete function doesn't delete?
    By juanjuanjuan in forum C Programming
    Replies: 7
    Last Post: 12-09-2014, 10:10 PM

Tags for this Thread