0

単純な構造体を考えてみましょう:

struct Node{
 int val;
 Node *next;
 Node *freeNode;
};

ここで、指定されたリンク リストを freeNode のみを使用してソートする必要があり、メソッドは効率的でなければなりません。別のリストを作成して、そこである種のソート挿入を使用することはできません。ゲノムやバブルソートも使えません。リスト内の任意の要素のポインターfreeNodeは、リスト内の任意の要素を指すことができます。

今、私は2つのアイデアを思いつきました:

  1. 二重リンク リストを作成するには、freeNode を使用します。

    そして、ペア比較を行います。つまり、i 番目の要素と (i+1) 番目の要素を比較します。2 つの要素を交換する必要があることがわかった場合は、それらを交換してから、リストの先頭から開始します。

    このアルゴリズムは O(n) 以上になります (推測だけではわかりません)。時間がかかります。

  2. もう 1 つの方法は、freeNode がそれより小さい elem を指すようにすることです。

    たとえば、私が持っている30->6->14->56>Tail場合、

    56->freeNode->14
30->freeNode->14
14->freeNode->6
6->freeNode->NULL.

    しかし、繰り返しますが、これはあまり役に立ちません。なぜなら、挿入するときにポインター45 or 20を再配置する必要があるからです。freeNode繰り返しますが、これはあまり効率的な方法ではありません。

これに関する提案はありますか？freeNodeソートのためのより優れた効率的な方法を実装するために使用する方法。疑似コードも機能しますが、私は実際のコードよりもその方が好きです。

編集:配列、ベクトルなどは使用できません。freeNodeポインタだけ。好きなように使用してください。NULL のままにするか、選択した要素を指すようにします。

4

1 に答える 1

2

二分木を作ることができます。next を右の子ポインターとして使用し、freeNode を左の子ポインターとして使用します。ルートをソートする最初のノードを作成します。次に、残りのノードを取得して、新しいバイナリ ツリーに「挿入」します。

編集：このように：

あなたの型定義:

typedef struct Node{
 int val;
 struct Node *next;
 struct Node *freeNode;
} NodeT;

このコードを読みやすくするためのいくつかの定義:

// Conversions to make this code easier to read.
#define pRight freeNode
#define pLeft  next

再帰的な二分木挿入:

static void BinTreeInsert( NodeT *pRootNode, NodeT *pChildNode );

編集2：これが宿題であることが明らかになったときに解決策が削除されました。おいを理解してください！

この解決策は、O(n log n) の最良/平均的なケースですが、O(n2) の最悪のケースです...着信リストが既にソートされている場合。

http://en.m.wikipedia.org/wiki/Tree_sort#section_1

于 2013-02-27T07:10:29.950 に答える