日期:2014-05-20  浏览次数:20783 次

求助,关于类的克隆
本帖最后由 jollwish 于 2013-02-18 17:37:20 编辑
我想在堆内实现一个按顺序输出堆中元素的方法,所以克隆了一个用于不断删除堆顶,实现如下:

public class StaticHeap implements Cloneable{

/*
This heap has a root at the INDEX_1, which refers to the minimum.
And this heap is STATIC, as means that its volume is limited.
*/

private final int MAX_VOLUME = 250000;

private int heapSize = 0;

private int[] heap = new int[MAX_VOLUME];

public StaticHeap(){
heap[0] = Integer.MIN_VALUE;
}

public StaticHeap(int[] input){

heap[0] = Integer.MIN_VALUE;
for (int i = 0; i < input.length; i++)
this.insert(input[i]);

}

private int parent(int i){
return i/2;
}

private int leftSon(int i){
return i*2;
}
private int rightSon(int i){
return i*2+1;
}

private void swap(int i, int j){

int tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;

}

private void update(int i){

while (heap[i] < heap[parent(i)]){
swap(i, parent(i));
i = parent(i);
}

}

private void heapify(int i){

int l = leftSon(i);
int r = rightSon(i);

if (l <= heapSize && heap[l] < heap[i] && heap[l] <= heap[r]){
swap(i, l);
heapify(l);
}
if (r <= heapSize && heap[r] < heap[i] && heap[l] > heap[r]){
swap(i, r);
heapify(r);
}

}

public void insert(int x){

heap[++heapSize] = x;
update(heapSize);

}

public boolean deleteMin(){

if (heapSize == 0) return false;

heap[1] = heap[heapSize--];
if (heapSize > 0) heapify(1);
return true;

}

public int getSize(){
return heapSize;
}

public int getMin(){
return heap[1];
}

public Object clone() throws CloneNotSupportedException{
return super.clone();
}

public int[] sortedArray() throws CloneNotSupportedException{

StaticHeap newHeap = (StaticHeap)this.clone();
int[] result = new int[newHeap.heapSize];
int n = 0;

while (newHeap.heapSize > 0){
result[n++] = newHeap.getMin();
newHeap.deleteMin();
}

return result;

}

}


但是实际运行时newHeap.deleteMin()的作用却相当于this.deleteMin(),也就是把原来的那个堆给毁了,这是为什么?是java不支持在类中对自己克隆吗?这个应该如何实现?谢谢各位了
class clone

------解决方案--------------------
Object的clone方法实现shallow copy而不是deep copy,
如果没错你的heap引用指向的数组对象并没有被clone,以至于在新的克隆出来的StaticHeap操作时操作的还是同一个数组对象,以至于造成上面的情况