2

节点删除的这种实现是否有效，还是我失败了？

void remove_node(node *p)
{
    node **i = &node_list;

    for (;(*i) != NULL && ((*i) != p); *i = ((*i)->next)) ;

    if (*i != NULL) 
    {
      (*i) = (*i)->next;
    }

    if (p != NULL) 
    {
      free(p);
    }
}

顺便说一句，据我所知，在我看到的每个从列表中删除节点的算法中，都有一个变量应该保留前一个指针。这个实现缺少这个......

4

4 回答 4

2

不，它不起作用。（是的，我知道，我作弊了——最初我说是作弊的）。

作为面试问题的答案，我首先列出假设：

  • node_list 开始有效（并且正确地以 NULL 终止）
  • 它是一个单链表
  • 节点是动态分配的

问题是：循环将在*i == p. 它需要在何时停止*i->next == p- 然后它几乎可以工作，但如果 p 是列表中的第一个节点，仍然会出现问题。

于 2012-08-25T10:30:34.913 回答
1

您的程序中的错误是

  1. 头指针（node_list）不会指向第一个元素，它会指向旁边的元素p
  2. (*i) = (*i)->next- 这是错误的。应该更新前一个节点的下一个指针。

下面更新的逻辑可以正常工作

void remove_node(node *p) 
{     
    node *i = node_list;      
    node *previous_node = NULL;

    if((NULL == p) || (NULL == node_list))
    {
        return;
    }

    for (; (i != NULL) && (i != p); i = i->next) 
    {
        previous_node = i;
    }

    if (i != NULL)      
    {       
        if(NULL == previous_node) // `p` is the first node
        {
            node_list = i->next;
            free(i);
        }
        else //`p` is not the first node
        {
            previous_node->next = i->next;     
            free(i);
        }
    }      
}
于 2012-08-25T10:34:45.810 回答
0

node_list我认为这将与不会指向列表开头的副作用一起工作。所以头节点需要存储在其他一些变量中。

BTW，你试过吗？你得到了什么？

于 2012-08-25T10:30:51.717 回答
0

假设parameter p as pArg
After for 循环：-

for (;(*i) != NULL && ((*i) != p); *i = ((*i)->next)) ;

*i=pArg [如果节点 pArg 存在于链表中](case 1) or *i=NULL(case 2)

首先如果：-

 if (*i != NULL) 
    {
      (*i) = (*i)->next;
    }

p=pArg->next（案例 1）并且在（案例 2）中没有操作

第二个如果：-

if (p != NULL) 
    {
      free(p);
    }

免费（pArg->next）；（案例1）；并且在（情况 2）中没有操作（如果 pArg 确实是 LL 中的一个节点）

您删除了 pArg 指向的节点，而不是 pArg本身。

做一点改变：-

node *prevp=NULL;

for (;(*i) != NULL && ((*i) != p); *i = ((*i)->next))
{prevp=*i;} 

if (*i != NULL) 
    {
      prevp->next = (*i)->next;
    }
于 2012-08-25T10:51:49.647 回答