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. head pointer(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これは、リストの先頭を指していない副作用で機能すると思います。したがって、ヘッドノードは他の変数に格納する必要があります。

ところで、あなたはそれを試しましたか？あなたは何を手に入れますか？

于 2012-08-25T10:30:51.717 に答える
0

After for ループを想定parameter p as pArg
:-

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

*i=pArg [リンクされたリストにノード pArg が存在する場合](ケース 1) または *i=NULL(ケース 2)

最初の場合:-

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

p=pArg->next (ケース 1) で操作なし (ケース 2)

2 番目以降の場合:-

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

free(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 に答える