2

私は C で線形連結リスト構成を頻繁に使用してきました。

typedef struct _node {
    ...node guts...
    struct _node *next
} node;

そして、列挙イディオム

for (node *each = headNode; each != NULL; each = each->next)

私は現在、循環リストが魅力的な状況にあります (たとえば、最後のノードの次が headNode に設定されています)。素朴にそこの表現に似たものを使っていると思っていたのforですが、見れば見るほど、循環リンクリストではそのようなことはできないと確信したようです。

終了条件にどのような式を思いついたとしても、同じノードに遭遇したときに最初に true を評価し、2 回目に false を評価するという基本的な問題があるようです。私はループの副作用で何かをすることができました:

for (BOOL traversed = FALSE, node *each = headNode;
    traversed && each != headNode;
    traversed = TRUE, each = each->next)

しかし、それはヌル終了リストアプローチの優雅さ/単純さを確実に失います。一日の終わりに私を逃れている論理のトリックはありますか?

明らかに、while() コンストラクトを使用できますが、おそらくそれが唯一の方法です。

4

5 に答える 5

3

以下を仮定します。

  • 空のリストは、開始点が NULL であることを意味します。
  • 最後のノードは、ポインターの自己参照nextである単一ノードのリストを含む、ポインターの開始点を参照するノードになります。next
  • NOnextポインタは NULL です。

次に、インクリメンタル ステップとして 3 次式を使用して、次のようにします。

// node* start comes from "somewhere'
for (node *p=start; p; p = (p->next==start ? NULL : p->next))
{
    // do something with p
}

注:pこれが何らかの形で終了すると NULL になります。単一の自己参照ノードと同様にstart、NULLは許容されます。start

そうは言っても、while ループでこれを行いますが、特に for ループを要求したため、=P が得られます。

于 2012-12-12T04:00:34.087 に答える
1

すでに指摘したように、「現在の」ポインターはリスト全体を循環するだけで、2 回目は最初のポインターと同じです。

したがって、他の情報を使用する必要があります。最も単純/最小の追加変数であるブール値は、あなたの承認により複雑すぎるか洗練されていないため、これを行うことはできないと推測できます。

...すでに追加のデータを使用している場合を除き、最初は null である「前の」ポインターを使用します (この場合、traversed例と非常によく似たものを使用できます)。

記録のために、do...while を使用します。

struct _node *node = head;
do {
    ...
    node = node->next;
} while (node != head);
于 2012-12-12T01:34:28.653 に答える
0 
p = (pointer to some node)
pfirst = p
while true:
    do whatever with node (p)...
    p = p->next
    if (p==pfirst)  break

これは1つの要素リストで機能することに注意してください。

于 2012-12-12T01:11:19.473 に答える
0

次の再配置されたループはそれほどひどく見えません：

for (node * n = head; ; )
{
    // process n

    if ((n = n->next) == head) { break; }
}

ちなみに、これは空でないリストに対してのみ機能します。空の概念が何であれ、初期チェックとして追加する必要があります—ダミーのヘッドノードを使用してその問題を回避しない限り（空のリストにが含まれるノードが1つ含まnれるn == head == n.nextように、その場合、実際にはダミーを印刷したくない）まったく、本物のforループを使用できます（上記の条件をループステートメントに戻すだけです）。

于 2012-12-12T01:11:28.730 に答える
0

チェーンをループするだけではないことをお勧めします。それ自体は美しいものではありません。チェーンの 2 番目の要素などでループしていないことをどのように確認しますか?

a の概念がある場合、各ノードでheada へのポインターを保持するか、静的にする必要があります。headまた、先頭にループする代わりに、特別なフラグが必要です。

于 2012-12-12T01:15:12.457 に答える