c - 如何从队列中删除集合节点

Question

我希望从队列中删除一个集合节点。假设我按名称 I.D 搜索选择节点。我知道如何从队列前面删除某些内容，但对如何在用户设置点(例如中途)删除某些内容感到困惑。

我的功能:

void retrieveAndRemove(linkedPtr*hd, int size){
linkedPtr temp = *hd;


   if (hd == NULL){
    printf("List is empty!");

   }
    while( temp != NULL){
        if (temp->status == IN_RESTAURANT && temp->size == size){

            //HERE is where I am stuck, how do i now re-arrange the que
            //Such that the node gets removed and the next node is linked
            free(temp);
            return;

        }
        temp = temp->next;
    }

}

Answer 1

当您需要从链表中间删除一个节点时，您需要跟踪前一个节点。这将允许您重置链接列表中的链接。

起始状态:

                         Node to be removed
                            |
                            v
+-------+                +-------+             +-------+
| node1 |  -- next -->   | node2 | -- next --> | node3 |
+-------+                +-------+             +-------+

结束状态:

+-------+                                      +-------+
| node1 |                -- next -->           | node3 |
+-------+                                      +-------+

这是您的函数的修订版本，应该可以工作。

// This wont work for the case when the head needs to be removed.
// void retrieveAndRemove(linkedPtr*hd, int size) {

void retrieveAndRemove(linkedPtr** hd, int size) {

   linkedPtr prev = **hd;
   linkedPtr cur = prev;

   if (hd == NULL){
      printf("List is empty!");
      return;
   }

   // Take care of the case where the item to be removed is at the head.
   if ( cur->status == IN_RESTAURANT && cur->size == size) {
      *hd = cur->next;
      free(cur);
   }

   // Take care of the case where the item to be removed is in the middle.
   while( cur != NULL) {
      if (cur->status == IN_RESTAURANT && cur->size == size){

         // Fix the links.
         prev->next = cur->next;
         free(cur);
         return;
      }
      prev = cur;
      cur = cur->next;
   }
}