从数组复制元素

Question

我是计算机科学的新手。我被告知在以下Java类型伪代码中只有1个bug，但我无法弄清楚。不是不止一个吗?首先，if语句意味着它不会循环，因为大小不等于最大大小，但我认为循环也是不正确的，而不是i<=大小，不应该是i<=maxsize吗?

private int size = 0;
private int maxsize = 16;
private int[] arr = new int[maxsize];
public void append(val, list)
{
if (size == maxsize)
{
int[] newArr = new int[maxsize * 2];
for (i = 0; i <= size ; i++)
newArr[i] = arr[i];
arr = newArr;
maxsize = maxsize*2;
}
arr[size++] = val;
}

在这些选项中，哪个是正确的?

• 第一行应该是:private int size = 16;
• 第7行应该是:if (size > maxsize)
• 第10行应该是:for (i = 0 ; i <= maxsize ; i++)
• 第13行应该放在第10行之前
• 第15行应该是:arr[++size] = val;

Answer 1

好，让我们稍微分析一下伪代码。鉴于这是伪代码，我们将不关注语法错误，而是关注逻辑错误(或设计问题)。

首先，这看起来像是一个数组列表的实现，也就是说，它在内部保留一个数组，如果需要更多的空间，它会将其加倍。它还保持列表的当前大小为size。

//this is ok since at tehe beginning there are no elements in the array
private int size = 0; 
//initial capacity of the array, ok too
private int maxsize = 16; 
//an array of elements with value 0, ok too
private int[] arr = new int[maxsize]; 
//ok but a potential bug: what is list used for?
public void append(val, list) 
{
//if the size of the list hits the capacity, we need to increase space, so this is ok
if (size == maxsize)
{
//we create a new array with 2x the previous size, ok as well
int[] newArr = new int[maxsize * 2]; 
//we're looping and copying the elements from the old array to the new one
//bug: for i == size it would try to access arr[size] which is out of bounds
//fix: use i < size or even i < maxsize if you have to
for (i = 0; i <= size ; i++) 
newArr[i] = arr[i];
//move the references to "point" to the new array - ok
arr = newArr;
//double capacity - could have been better but ok here
maxsize = maxsize*2;
}
//add a new element at the index right after the last (i.e. size) and increase size by 1
arr[size++] = val;
}

现在选项:

第一行应该是:private int size = 16;

这将导致数组在添加第一个元素时被翻倍，并导致前16个元素为"空";(0).并且它不会修复错误。

第7行应该是:if (size > maxsize)

不应该是真的，因为arr[size++]会在size == maxsize。它也不会修复这个错误。

第10行应该是:for (i = 0 ; i <= maxsize ; i++)

本质上与for (i = 0 ; i <= size ; i++)相同，因为它只在size == maxsize时执行。它包含相同的错误，但没有修复它。

第13行应该放在第10行之前

如果我正确地识别行，这不会改变太多，代码将是:

int[] newArr = new int[maxsize * 2];
maxsize = maxsize*2;
for (i = 0; i <= size ; i++)
newArr[i] = arr[i];
arr = newArr;

如果你改变代码，你可以摆脱一个计算:

maxsize = maxsize*2;
int[] newArr = new int[maxsize];

为了提高可理解性，最好这样写:

int newMaxSize = maxsize * 2;
int[] newArr = new int[newMaxSize];
for (i = 0; i <= size ; i++)
newArr[i] = arr[i];
arr = newArr;
//could be before the loop as well but it's safer to set it here, e.g. someone could change the loop to "for (i = 0; i < maxsize ; i++)" ;)
maxsize = newMaxSize;

第15行应该是:arr[++size] = val;

这将使第一个元素(索引0处)"为空"(0)和将打破size == maxsize-1。不能修复错误。