java - 拆分数组 - 我的实现正确吗？

Question

我正在为学校的混合数据结构编写代码，并正在调试代码。基本上，该结构是双链表和数组的组合，其中每个列表节点包含一个设定大小的数组。由于这是一个有序结构，因此必须采取措施来识别完整数组并将其平均分割为两个节点。

这是我的代码，用于将一个节点拆分为两个，然后将父节点的数组值的后半部分复制到子节点。

public Chunk<E> split(Chunk<E> node) {
  Chunk<E> newChunk= new Chunk<E>();
  newChunk.index= node.index++;

  //connect to previous node
  node.next= newChunk.next;
  newChunk.prev= node.prev;

  //connect to next node
  newChunk.next= node.next.next;
  node.next.prev= newChunk.prev;

  //adds the latter half of the array contents to the new node
  //and erases the same contents from the old node
  for (int i=chunkSize/2; i<node.numUsed; i++) {
   newChunk.items[i-chunkSize/2]= node.items[i];
   node.items[i]=null;
  }

  //update capacity counter for both chunks
  node.numUsed=chunkSize/2;
  newChunk.numUsed= chunkSize/2;

  return newChunk;

}

toArray() 方法从列表中返回空值，因此我认为此 split 方法出现了问题。

我的问题是:

新节点与列表其余部分的链接是否正确？

循环内的值清零是否导致了 null 打印输出？

Answer 1

要彻底回答这个问题，您应该编写一些单元测试。例如:

package so3898131;

import static org.junit.Assert.*;

import org.junit.Test;

public class ChunkTest {

  /** Ensure that the simplest possible case works as expected. */
  @Test
  public void testEmptySplit() {
    Chunk<Object> old = new Chunk<Object>();
    Chunk<Object> split = old.split(old);
    assertEquals(0, split.chunkSize);
    assertEquals(0, split.items.length);
    assertEquals(0, split.index);
    assertEquals(1, old.index);
  }

  @Test
  public void testSplitWithOneItem() {
    // TODO: make sure that after splitting one of the chunks contains
    // one element, the other none.
  }

  @Test
  public void testSplitWithTwoItems() {
    // TODO: make sure that after splitting a chunk with two elements
    // each of the new chunks contains exactly one of the elements.
    // Use assertSame(..., ...) to check it.
  }
}

这会向我抛出 NullPointerException，因为 node.next 可能为 null，在这种情况下，您无法访问 node.next .下一个。这可能意味着您的代码不起作用。至少它没有像我预期的那样工作。

更新:您的代码不正确。我写了一个这样的单元测试:

@Test
public void testSplitLinkage() {
  Chunk<Object> old = new Chunk<Object>();
  assertNull(old.prev);
  assertNull(old.next);

  Chunk<Object> split = old.split(old);

  assertNull(old.prev);
  assertSame(split, old.next);
  assertSame(old, split.prev);
  assertNull(split.next);
}

然后我修改了代码，以便该测试成功运行。我必须将一些行替换为:

// connect to previous and next node
Chunk<E> one = node, two = newChunk, three = node.next;
one.next = two;
two.prev = one;
two.next = three;
if (three != null)
  three.prev = two;