我试图从John R Hubbard的书Data Structures with Java (Example 3.2)中为Java语言中的有序数组实现某种插入方法,以便插入元素并对数组进行排序,比移位元素或使用冒泡排序更快。
谁能给我解释一下下面的代码是怎么回事?我应该如何初始化变量'k‘(作为'a’数组的索引数组),以及a的值应该是什么(因为在下图中数组'a‘的0和2索引中没有值)。

void insert(int x){
int i=0;
while (k[i] != 0 && a[k[i]] < x) {
i = k[i];
}
a[free] = x;
k[free] = k[i];
k[i] = free++;
}发布于 2017-02-16 04:48:32
问题#1:
有人能给我解释一下下面的代码片段中发生了什么吗?
答案#1:
让我们首先看看如何遍历这样的结构并按顺序打印出元素。我在你的问题中使用了书中的例子:

下面是它在Java中的样子:
int i = 0;
while (k[i] != 0) {
System.out.println(a[k[i]]);
i = k[i];
}如果你想在这样的结构中插入一个值,你必须知道如何迭代它。您必须知道等于或大于要插入的元素(x)的第一个元素(a[k[i]])的i:
Procedure insert(x)将x插入a[free]。
现在必须更新索引以适应有序链中的额外链接。也就是说,从这个开始:
| ... | a[k[i]] >= x | ... |要这样做:
| ... | x | a[k[i]] >= x | ... |紧跟在x之后的元素是a[k[i]]。我们必须暂时将其从链上分离,才能插入x。因此:k[free] = k[i]。
接下来,执行:k[i] = free。a[k[i]]现在将是x (记住,我们在a[free]中插入了x )。
现在神奇的事情发生了。a[k[i]] == x和紧跟其后的元素是a[k[free]] (以前是a[k[i]] )。
然后free加1,我们就完成了。
问题#2:
我应该如何初始化变量
k(作为a数组的索引数组),a的值应该是什么?
答案#2:
书中的示例看起来很好:
import java.util.Arrays;
class IndirectReference {
static final int Q = 0; // This value is irrelevant; added for clarity
static int a[] = {Q, 44, Q, 22, 55, 33, 66, Q};
static int k[] = {3, 4, Q, 5, 6, 1, 0, Q, Q, Q};
static int free = 7;
public static void main(String[] args) {
insert(50);
System.out.print("a = ");
System.out.println(Arrays.toString(a));
System.out.print("k = ");
System.out.println(Arrays.toString(k));
System.out.println("free = " + free);
}
static void insert(int x) {
int i = 0;
while (k[i] != 0 && a[k[i]] < x) {
i = k[i];
}
a[free] = x;
k[free] = k[i];
k[i] = free++;
}
}注意:此过程依赖于free在两个表中保存下一个空闲位置的索引这一事实。
在上面的示例中,在插入50之后将其错误地设置为8,因为该过程假设索引free、free+1、free+2、...在a和k中。
一旦用完可用空间,您可以调整两个数组的大小,也可以压缩它们(将非尾随的?放在两个表的末尾),尽管我不太清楚如何做到这一点。
发布于 2017-02-16 04:19:55
您可以将k和a初始化为空整数数组:
int[] a = new int[10];
int[] k = new int[10];
int free=0;a中的空格可能是为了说明如果有一些删除,它会是什么样子。如果您所做的只是插入,那么a[free]之前的所有a元素都将有一个插入值,尽管如果您插入了0,它仍然可以是0,但这似乎不是本例中发生的情况。
至于代码在做什么,这是一个有点长的解释。a中的数据值是我们插入的数据。k中的数据值是对a和k中索引元素的引用,我们可以遵循这些元素以升序遍历数据。k[0]的值将始终包含数据值最小的a的索引。因此,使用书中的示例,k[0]是3。a[3]是22,22是我们有序列表中最小的数据值。
k中的数据也用于遍历k的元素,我们总是从0开始。因此,下一个元素是k[3],它包含一个5。a[5]是33,是我们数据中倒数第二小的数字。
因此,如果我们想在列表中插入27,并遵循此算法,则k中的相关条目为k[0]==3、k[3]==5和k[5]==1。插入后,a[7]将为27,因为插入时free为7(插入后为8)。k[0]仍然是3,因为22仍然是我们的最低值数据。k[3]将是7,因为我们的第二低数据值现在是27,并且存储在a[7]中。k[7]将是5,因为a[5]是33,现在是我们的第三个最小的数据值,而k[5]仍然是1(没有变化)。
因此,在我们按照k索引0,3,5,1,4,6 (根据本书)遍历列表的地方,我们现在将遵循以下路径: 0,3,7,5,1,4,6,给出数据值: 22,27,33,44,55,66
https://stackoverflow.com/questions/42255751
复制相似问题