首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >是否在有序数组中插入值?

问是否在有序数组中插入值?
EN

Stack Overflow用户
提问于 2017-02-16 01:02:43
回答 2查看 1.1K关注 0票数 0

我试图从John R Hubbard的书Data Structures with Java (Example 3.2)中为Java语言中的有序数组实现某种插入方法,以便插入元素并对数组进行排序,比移位元素或使用冒泡排序更快。

谁能给我解释一下下面的代码是怎么回事?我应该如何初始化变量'k‘(作为'a’数组的索引数组),以及a的值应该是什么(因为在下图中数组'a‘的0和2索引中没有值)。

​

​

代码语言:javascript
复制
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++;
}
EN

回答 2

Stack Overflow用户

发布于 2017-02-16 04:48:32

问题#1:

有人能给我解释一下下面的代码片段中发生了什么吗?

答案#1:

让我们首先看看如何遍历这样的结构并按顺序打印出元素。我在你的问题中使用了书中的例子:

​

​

下面是它在Java中的样子:

代码语言:javascript
复制
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]。

现在必须更新索引以适应有序链中的额外链接。也就是说,从这个开始:

代码语言:javascript
复制
| ... | a[k[i]] >= x | ... |

要这样做:

代码语言:javascript
复制
| ... | 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:

书中的示例看起来很好:

代码语言:javascript
复制
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中。

一旦用完可用空间,您可以调整两个数组的大小,也可以压缩它们(将非尾随的?放在两个表的末尾),尽管我不太清楚如何做到这一点。

票数 1
EN

Stack Overflow用户

发布于 2017-02-16 04:19:55

您可以将k和a初始化为空整数数组:

代码语言:javascript
复制
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

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/42255751

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档