2

作业协助

描述一个向量的基于数组的实现，以便在向量的开头和结尾插入和删除可以在恒定时间内完成。有说服力地争论。

显然，这对于直列阵列是不可能的。如果从前面移除，将会有一个需要填充的孔，以保持矢量属性。当然，如果我们抓取下一个元素，我们将需要这样做 n 次，因此运行时间将是线性的，而不是恒定的。

另一种方法是抓住最后一个元素并将其粘贴在前面，但是打乱数据的数据结构有什么好处呢？

到目前为止我所做的是创建一个数组。奇数索引在数组中的某个点之后（出于大小目的，最好是中间，但它可以在任何地方），然后偶数索引在该点之前。如果那个特殊点不是中心点，那会占用一大堆内存并且有很多开放的插槽。最坏的情况是 2n。但是，它就像没有孔一样，因为它总是会填充下一个元素。

插入：

private int front = 0;
private int back = 0;
public void insertAtFront(int element)
{
    (front+1));
        dataArray[2*(front + 1) + 1] =  element;
        front++;
}

public void insertAtBack(int element)
{
    dataArray[2*(back+1)] = element;
    back++;
}

要移除，只需减少正面或背面。然后在访问数组时，只允许显示前后的值。

首先，这是否符合向量的要求？其次，在移除时，我在弄清楚如何越过那个特殊的中心点时遇到了一些重大问题。假设您想从前面删除整个数组，而从后面添加所有内容。

感谢您提供任何帮助。

4

3 回答 3

1

The secret is to use two arrays. The end of the first array is the "front". The end of the second array is the "back".

于 2013-06-13T16:13:38.083 回答
0

我不明白您要对偶数和奇数索引做什么。但是有一个开始索引和一个结束索引基本上是要走的路——在前面留空，这样你就可以在那里添加元素，如果你删除一个元素，就再次增加开始索引。

于 2013-06-13T16:09:46.100 回答
0

另一种选择是使用圆形数组，让您可以有效地在前面和结尾添加/删除。

还有其他可以应用的变体：您是否还可以找到一种实现，使得在开头、结尾和（恰好）中间插入/删除是有效的并且有 O(1) 时间？

于 2016-04-17T13:37:18.983 回答