java - 如何在 Java 中合并两个排序的数组？

Question

我正在尝试从之前创建的两个数组 a 和 b 创建第三个排序数组 c；但是，我在合并方法中遇到了几个错误，提示“表达式的类型必须是数组类型，但它已解析为 OrdArray”。我已经做了好几个小时了，现在感觉我的大脑已经糊了。有人可以帮我吗？

class OrdArray
{
    private long[] a;                 // ref to array a 
    private int nElems;               // number of data items
    //-----------------------------------------------------------
    public OrdArray(int max)          // constructor
    {
        a = new long[max];             // create array a  
        nElems = 0;
    }
    //-----------------------------------------------------------
    public int size()
    { return nElems; }
    //-----------------------------------------------------------
    public int find(long searchKey)
    {
        int lowerBound = 0;
        int upperBound = nElems-1;
        int curIn;

        while (true)
        {
            curIn = (lowerBound + upperBound ) / 2;
            if (a[curIn] == searchKey)
                return curIn;              // found it
            else if (lowerBound > upperBound)
                return nElems;             // can't find it
            else                          // divide range
            {
                if (a[curIn] < searchKey)
                    lowerBound = curIn + 1; // it's in upper half
                else
                    upperBound = curIn - 1; // it's in lower half
            }  // end else divide range
        }  // end while

    }  // end find()
    //-----------------------------------------------------------
    public void insert(long value)    // put element into array
    {
    int j;
    for (j = 0; j < nElems; j++)        // find where it goes
        if (a[j] > value)            // (linear search)
            break;
        for (int k = nElems; k > j; k--)    // move bigger ones up
            a[k] = a[k-1];
        a[j] = value;                  // insert it
        nElems++;                      // increment size
    }  // end insert()
    //-----------------------------------------------------------
    public boolean delete(long value)
    {
        int j = find(value);
        if (j == nElems)                  // can't find it
            return false;
        else                           // found it
        {
            for (int k = j; k < nElems; k++) // move bigger ones down
                a[k] = a[k+1];
            nElems--;                   // decrement size
            return true;
        }
    }  // end delete()
    //-----------------------------------------------------------
    public void display()             // displays array contents
    {
        for (int j = 0; j < nElems; j++)       // for each element,
            System.out.print(a[j] + " ");  // display it
        System.out.println("");
    }
    //-----------------------------------------------------------
    public static long[] merge(OrdArray a, OrdArray b) 
    {

    long[] c = new long[a.nElems + b.nElems];
    int i = 0, j = 0, k = 0;

    while (i < a.nElems && j < b.nElems)
    {
        if (a.data[i] < b.data[j])     
            c[k++] = a.data[i++]; 
        else        
            c[k++] = b.data[j++];              
    }

    while (i < a.nElems)  
        c[k++] = a.data[i++];      

    while (j < b.nElems)    
        c[k++] = b.data[j++]; 
    return c;
    }
    }  // end class OrdArray
    ////////////////////////////////////////////////////////////////
  class OrderedApp
  {
      public static void main(String[] args)
      {
      int maxSize = 100;             // array size
      OrdArray a, b, c;                  // reference to array
      a = new OrdArray(maxSize);   // create the array
      b = new OrdArray(maxSize);
      c = new OrdArray(maxSize);

      a.insert(11);
      a.insert(13);
      a.insert(15);
      a.insert(17);
      a.insert(19);
      a.insert(21);
      a.insert(23);
      a.insert(25);
      a.insert(27);
      a.insert(29);

      b.insert(12);
      b.insert(14);
      b.insert(16);
      b.insert(18);
      b.insert(20);
      b.insert(32);
      b.insert(24);
      b.insert(26);
      b.insert(28);
      b.insert(30);

      OrdArray.merge(a,b);

      System.out.print("Array a: ");
      a.display();
      System.out.println();
      System.out.print("Array b: ");
      b.display();
      System.out.println();
      System.out.print("Array c: ");
      c.display();
      System.out.println();
      }  // end main()
  }// end class OrderedApp

Answer 1

OrdArray 不是数组类型(尽管名称如此)；因此，您不能像数组一样对其进行索引。这个表达式

a[i++]

其中 a 是一个 OrdArray，将没有任何意义。 Java 没有为您提供为类定义自己的 [] 运算符的方法(与 C++ 不同)。因此，您必须向 OrdArray 添加一个方法以返回给定索引处的元素，例如

public long get(int index) { ...write the code... }

a.get(i++) // will then get the element at that index

尽管我不确定这是否是您想要的，因为您已将 c 声明为 int[] 并且 OrdArray< 中的数组 成为 long[]，所以我不确定您要做什么。

编辑: 阅读您的评论后，我意识到 merge 方法位于 OrdArray 类中。我以前错过了。既然如此，就不需要添加get方法了；您可以直接访问 OrdArray 参数的私有(private)字段。在你的方法中:

public void merge(OrdArray a, OrdArray b) 

您想获取为每个 OrdArray 声明的私有(private)数组 a。如果您只使用 a，变量将引用 OrdArray，它不是数组(如上所述)；要获取属于 OrdArray a 的 long[] a，您需要说

a.a[i++]

同样，对于b，

b.a[i++]

这可能会让读者感到困惑，所以我建议想出一个更好的名称，这样您就不会将两个东西称为 a。也许数据？

其他一些事情:你像这样使用 merge:c.merge(a,b)，这意味着 merge 是一个实例方法和 c 是您正在操作的实例。但是您的方法对当前实例没有任何作用。 (你在merge中声明的c是一个局部变量，与调用merge时使用的c无关code>。)现在，您的方法在构造局部数组 c 时会遇到很多麻烦，但随后它就将其丢弃。您要么需要 (1) 修复该方法，以便它在当前实例中设置 a(或 data)数组；或者 (2) 使它成为一个 static 方法并使该方法返回新数组作为函数结果。我不确定你的导师希望你做哪一个。