c - 如何从链表/队列中删除所有具有相同值的节点

Question

我一直在努力解决这个问题，但没有成功，我有如下数据结构(实际上非​​常复杂，我只是为了讨论而简化):

typedef struct node{
 struct node* next;
  void* arg;
}node_t;

typedef struct queue{
node_t* head;
node_t* tail;
}queue_t;

addQ(queue_t*ptr , int data)
{
    queue_t* q = ptr;
    node_t * n = malloc(sizeof(*n));

    n->arg = data;
    n->next = NULL;

    if(NULL == q->head){
       q->head = q->tail = n;
       return ;
    }
    q->tail->next = n;
    q->tail = q->tail->next;
}

现在我想删除相同值的节点(我尝试了几种方法但没有成功)，只需考虑这个序列以供引用:

addQ(q, 12);
addQ(q, 12);
addQ(q,  4);
addQ(q, 12);
addQ(q, 12);
addQ(q, 14);
addQ(q, 12);
addQ(q, 12);

我想删除所有值为 12 的节点。

Answer 1

这个解决方案使用双指针有点麻烦，但我仍然喜欢它，因为它不必特殊情况下检查哪个节点(第一个与其余节点)。我试图添加足够多的评论来描述正在发生的事情，但即使是我，乍一看仍然很难理解。

伪代码..

Queue * q;
VALUE = 12;

// double pointer so we can treat the queue head and subsequent nodes the same.
//   because they are both pointers to Node.  
// Otherwise you'd have to have code that says if the one you're removing is the 
// first element of the queue, adjust q->head, otherwise adjust node->next.  
// This lets you not special case the deletion.
Node ** node_ptr = &(q->head)

while (*node_ptr != null) {
    if ((**node_ptr).arg == VALUE) {
        // store off the matching node to be freed because otherwise we'd orphan
        // it when we move the thing pointing to it and we'd never be able to free it
        Node * matched_node = *node_ptr;

        // when we find a match, don't move where node_ptr points, just change the value it
        // points to to skip the matched node and point to the one after it (or null)
        *node_ptr = matched_node->next; 
        free(matched_node);
    } else {
        // otherwise, nothing was deleted, so skip over that node to the next one.
        // remember, **node_ptr is a double dereference, so we're at the node
        // now, so then we grab the address of the non-matching node's next value so it can be
        // potentially changed in the next iteration
        node_ptr = &((**node_ptr).next);
    }
}