1

私は、ヘッダー ノードとテール ノードを持つ単一リンク リストがあると仮定するように指示している割り当てに取り組んでいます。位置 p の前に項目 y を挿入する必要があります。誰でも私のコードを見て、私が正しい軌道に乗っているかどうか教えてもらえますか? そうでない場合は、ヒントや指針を教えていただけますか (しゃれは意図していません)。 

tmp = new Node();
tmp.element = p.element;
tmp.next = p.next;
p.element = y;
p.next = tmp;

問題の説明で具体的に言及されているにもかかわらず、ヘッダーノードとテールノードをまったく使用していないため、間違っている可能性があると思います。p が見つかるまでリストをたどってそのように問題に取り組む while ループを作成することを考えていましたが、それは一定時間ではありませんね。

4

7 に答える 7

5

アルゴリズムに行き詰まった場合は、書き留めてください。

// First we have a pointer to a node containing element (elm) 
// with possible a next element.
// Graphically drawn as:
// p -> [elm] -> ???

tmp = new Node();
// A new node is created. Variable tmp points to the new node which 
// currently has no value.
// p   -> [elm] -> ???
// tmp -> [?]

tmp.element = p.element;

// The new node now has the same element as the original.
// p   -> [elm] -> ???
// tmp -> [elm]

tmp.next = p.next;

// The new node now has the same next node as the original.
// p   -> [elm] -> ???
// tmp -> [elm] -> ???

p.element = y;

// The original node now contains the element y.
// p   -> [y] -> ???
// tmp -> [elm] -> ???

p.next = tmp;

// The new node is now the next node from the following.
// p   -> [y] -> [elm] -> ???
// tmp -> [elm] -> ???

あなたは必要な効果を持っていますが、それはより効率的であり、あなた自身を見つけることができると思います.

次のように書くとより明確になります。

tmp = new Node();
tmp.element = y;
tmp.next = p;
p = tmp;

もちろん、 p が可変でない場合は機能しません。ただし、p == NULL の場合、アルゴリズムは失敗します。

しかし、私が言いたかったのは、アルゴリズムに問題がある場合は、その効果を書き出すだけだということです. 特にツリーとリンクされたリストでは、すべてのポインターが正しい方向を指していることを確認する必要があります。そうしないと、大きな混乱が生じます。

于 2008-11-16T19:10:54.227 に答える
4

ヒント: リンクされたリストへの挿入は、位置n = 0、またはリストの先頭の場合にのみ一定です。それ以外の場合、最悪の場合の複雑さはO(n)です。合理的に効率的なアルゴリズムを作成できないと言っているわけではありませんが、少なくとも線形の複雑さは常に存在します。

于 2008-11-16T19:15:21.473 に答える
1

質問でヘッダーとテール ノードが指定されている理由は、作成した置換ノードがたまたまヘッダーまたはテールになった場合に、ヘッダーとテールの参照を更新するためです。つまり、指定された前のノードはヘッダーまたはテールのいずれかです。

于 2010-07-17T23:53:48.260 に答える
0

既存のコードを使用するのはどうですか? LinkedHashMap、LinkedList、LinkedHashSet。コードをチェックアウトして、そこから学ぶこともできます。

于 2008-11-17T04:17:22.423 に答える
0

あなたがしていないのは、y を y に挿入する前に p の前にあった要素をリンクすることです。したがって、y が p の前に挿入されている間、誰も y を指していません (少なくとも、あなたが示したコードではありません)。

y を挿入する必要がある要素の位置がわかっている場合にのみ、一定時間で挿入できます。その位置を検索する必要がある場合は、単一のリンク リストに一定時間挿入することはできません。

于 2008-11-16T19:25:03.870 に答える
0 
create a node ptr
ptr->info = item //item is the element to be inserted...
ptr->next = NULL
if (start == NULL) //insertion at the end...
    start = ptr
else
    temp = ptr
    while (temp->next != NULL)
        temp = temp->next
    end while 
end if
if (start == NULL) //insertion at the beginning...
    start = ptr
else
    temp = start
    ptr->info = item
    ptr->next = start
    start = ptr
end if
temp = start //insertion at specified location...
for (i = 1; i < pos-1; i++)
    if (start == NULL)
        start = ptr
    else
        t = temp
        temp = temp->next
    end if
end for
t->next = ptr->next
t->next = ptr
于 2010-03-31T17:09:36.237 に答える
0

単独の LinkedList では、ノードをリストの先頭に追加するか、ノードが 1 つだけのリストを作成するだけで O(1) かかります。または、TailNode も提供しているため、リストの最後にノードを挿入すると O(1) かかります。

他のすべての挿入操作には O(n) がかかります。

于 2012-12-11T18:58:36.173 に答える