1

最初に、これはハードウェアであるため、回答よりも多くのアドバイスを探していると言わせてください。入力シーケンスを読み取り、昇順で値を与えるリンクの配列を生成するプログラムを作成します。

入力ファイルの最初の行はシーケンスの長さ (n) で、残りの n 行はそれぞれ非負の整数です。出力の最初の行は、最小の入力値の添え字を示します。残りの各出力行は、添字と対応する入力シーケンスおよびリンク値で構成されるトリプルです。

(リンク値は、再帰ソートが開始される前に初期化されません。各リンクは、そのシーケンス値が再帰ツリーの下部にある単一の要素リストに配置されると、-1 に初期化されます)

出力は次のようになります。

0  3  5
1  5  2
2  6  3
3  7  -1
4  0  6
5  4  1
6  1  7
7  2  0

(私が思うに) 最後の列は添え字、中央はソートされていない配列、最後の列はリンク値です。私はmergeSortのコードをすでに持っており、それがどのように機能するかを理解しています。私はただ混乱しているだけで、リンクがどのように配置されるかを理解しています。

4

1 に答える 1

1

構造体のベクトルを使用して、各行の 3 つの値を保持しました。

主な手順は次のとおりです。

  • インデックスを初期化し、入力から値を読み取ります
  • ベクトルを値でソートする
  • リンクを決定する
  • ベクトルをインデックスで並べ替える (戻す)

コードのスケッチは次のとおりです。

struct Element {
    int index;
    int value;
    int nextIndex; // link
}

Element V[N + 1];
int StartIndex;

V[i].index = i;
V[i].value = read_from_input;

sort(V); // by value

startIndex = V[0].index;
V[i].nextIndex = V[i + 1].index;
V[N].nextIndex = -1;

sort(V); // by index
于 2013-02-10T15:06:44.613 に答える