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"

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 laserlight

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!

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.

Quote:

---

Originally Posted by laserlight

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!!!

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 laserlight

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?

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 laserlight

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.

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.