3

0、1、または 2 を含むリンク リストを並べ替えたいと思っていました。さて、これは明らかにオランダ国旗問題の変種です。 http://en.wikipedia.org/wiki/Dutch_national_flag_problem

リンクに示されているのと同じアルゴリズムは次のとおりです。

「上のグループを配列の上から下に、下のグループを下から上に成長させ、中央のグループを下のすぐ上に保持します。アルゴリズムは、上のグループのすぐ下、下のすぐ上、および3 つのインデックスの真ん中のすぐ上. 各ステップで, 真ん中のすぐ上の要素を調べます. 上のグループに属している場合は, 一番上の要素と交換します. 下のグループに属している場合は, 上の要素と交換します.底のすぐ上にある場合はそのままにしておきます。適切なインデックスを更新します。複雑さは Θ(n) 回の移動と検査です。"

そして、同じために与えられた C++ 実装は次のとおりです。

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] == low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }

}

私の唯一の質問は、ここで配列で行っているように、リンクされたリストをどのようにトラバースするかということです。

4

5 に答える 5

4

標準の単一リンク リストでは、リンク リスト セルを指定して後方に移動することはできません。ただし、各セルが次と前のポインターを格納する二重リンク リストを使用することもできます。これにより、リストを前後にナビゲートできます。

ただし、解決しようとしている特定の問題については、これは必要ないと思います。配列のアルゴリズムとリンク リストのアルゴリズムの主な違いの 1 つは、リンク リストを操作するときに、リスト内のセルを並べ替えて、リスト内の要素を並べ替えることができることです。したがって、上記で詳しく説明したアルゴリズム (配列の内容を変更することによって機能する) は、実際には、リンクされたリストで最も洗練されたアルゴリズムではない可能性があります。

実際にリンクされたリストを使用している場合、この問題を解決する 1 つの方法は次のとおりです。

  • 0、1、または 2 のすべての値を保持するリストを作成します。
  • リンクされたリストからすべてのセルを削除し、それらを 0、1、または 2 に等しい要素のリストに分配します。
  • これら 3 つのリストを連結します。

これはメモリの割り当てを行わず、リンクされたリストのセルを再配置することによって純粋に機能します。それはまだ時間 Θ(n) で実行されます。これは別のプラスです。さらに、逆方向に歩く必要なくこれを行うことができます (つまり、これは単一リンクのリストで機能します)。

完全な実装はあなたにお任せしますが、例として、連結リスト セルをゼロ、1、2 リストに分配する簡単な C++ コードを次に示します。

struct Cell {
    int value;
    Cell* next;
}

/* Pointers to the heads of the three lists. */
Cell* lists[3] = { NULL, NULL, NULL };

/* Distribute the cells across the lists. */
while (list != NULL) {
    /* Cache a pointer to the next cell in the list, since we will be
     * rewiring this linked list.
     */
    Cell* next = list->next;

    /* Prepend this cell to the list it belongs to. */
    list->next = lists[list->value];
    lists[list->value] = list;

    /* Advance to the next cell in the list. */
    list = next;
}

お役に立てれば！

于 2013-06-20T01:33:41.470 に答える
1

双方向リンク リストの使用。リンクされたリスト オブジェクトと関連するリンク リスト ノード オブジェクトを既に実装していて、それを順方向にトラバースできる場合、逆方向にトラバースするのにそれほど多くの作業は必要ありません。

次のような Node オブジェクトがあるとします。

public class Node
{
    public Node Next;
    public Object Value;
}

次に、実際に行う必要があるのは、Node クラスを変更し、Insert メソッドを少し上に置いて、以前の Node を追跡することだけです。

public class Node
{
    public Node Next;
    public Node Previous;
    public Object Value;
}

public void Insert(Node currentNode, Node insertedNode)
{
    Node siblingNode = currentNode.Next;

    insertedNode.Previous = currentNode;
    insertedNode.Next = siblingNode;

    if(siblingNode!= null)
        siblingNode.previous = insertedNode;

    currentNode.next = insertedNode;
}

PS 申し訳ありませんが、C++ のものを含む編集に気付かなかったので、より C# です。

于 2013-06-20T01:35:05.027 に答える
0

アイデアは、わずかな変更を加えたオランダのフラグの並べ替えアルゴリズムを使用することです。
オランダのフラグの方法に従って0と1を並べ替えますが
、2の場合はリストの最後に追加するのではなく、別のリンクリストに保持します。
最後に、2 のリストを 0 と 1 のソート済みリストに追加します。

Node * sort012_linked_list(Node * head) {

  if (!head || !head->next)
    return head;

  Node * head_of_2s = NULL;

  Node * prev = NULL;
  Node * curr = head;

  while (curr) {
    if (curr->data == 0) {
      if (prev == NULL || prev->data == 0) {
        prev = curr;
        curr = curr->next;
      }
      else {
        prev->next = curr->next;
        curr->next = head;
        head = curr;
        curr = prev->next;
      }
    }
    else if (curr->data == 1) {
      prev = curr;
      curr = curr->next;
    }
    else { // curr->data == 2
      if (prev == NULL) {
        head = curr->next;
        curr->next = head_of_2s;
        head_of_2s = curr;
        curr = head;
      }
      else {
        prev->next = curr->next;
        curr->next = head_of_2s;
        head_of_2s = curr;
        curr = prev->next;
      }
    }
  }

  if (prev)
    prev->next = head_of_2s;

  return head;
}
于 2015-06-29T19:22:06.753 に答える