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

我使用结构向量来保存每行的三个值。

主要步骤是：

  • 初始化索引并从输入中读取值
  • 按值对向量进行排序
  • 确定链接
  • 按索引对向量进行排序（返回）

这是代码的草图：

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 回答