3

我有一个创建 PriorityQueue 结构的任务,但我在处理这段代码时遇到了问题。当我在我的编译器上编译它时,一切都很好,但我尝试将它提交给 ideone,我收到以下错误:

“glibc 检测到 *** ./prog:双重释放或损坏”。

我能够跟踪给我这个错误的部分,我发现导致崩溃的原因是我试图在我的类的析构函数中删除一个指针。问题是我不知道为什么我不能删除它。我对指针不太了解,但我认为如果我使用 new 来分配内存,我必须在使用它后删除它,我认为这就是我想要做的。这是我的代码:

struct PriorityQueue
{
LinkedList queue; LinkNode *it,*node;
int sz;

PriorityQueue(){
    sz=0;
    queue.head=NULL;
    queue.tail=NULL;
    it = NULL;
    node=NULL;
}

~PriorityQueue(){

    if(node != NULL) //this is causing the error.
    delete [] node;


    if(it != NULL)
    delete [] it;
}


int size(){

    return sz;
}


void enqueue(int x){

    node = new LinkNode(x,NULL,NULL);

    if(sz==0){

        queue.insert_head(x);
        sz++;

    }

    else{

    if(x <= queue.head->value ){

        queue.insert_head(x);
        sz++;

    }

    else if( x>= queue.tail->value ){

        queue.insert_tail(x);
        sz++;

    }
    else{

        it = queue.head;


        for(int k=0;k<sz;k++){

                if( (x>= it->value)  && (x <= it->next->value) ){

                     node->next= it->next;
                     node->previous = it;

                     it->next->previous = node;
                     it->next = node;
                     sz++;
                     break;

                }

                    it=it->next;

        }

    }


    }

}

int dequeue_min(){

    int min = queue.remove_head();
    sz--;


    return min;
}

int dequeue_max(){

    int max= queue.remove_tail();
    sz--;

    return max;
}


};



int main()
{
PriorityQueue pq;
pq.enqueue(4);
pq.enqueue(2);
pq.enqueue(7);
pq.enqueue(-6);
pq.enqueue(0);
cout << pq.dequeue_min() << endl;   // debe imprimir -6
cout << pq.dequeue_min() << endl;   // debe imprimir 0
pq.enqueue(3);
cout << pq.dequeue_min() << endl;   // debe imprimir 2
cout << pq.dequeue_min() << endl;   // debe imprimir 3

return 0;
}

谢谢。

4

4 回答 4

3

itnode指向对象,而不是数组。
您不能delete[]在它们上使用数组形式。

于 2012-11-28T01:29:18.113 回答
1

正如 Slaks 指出的那样,似乎不仅指向对象itnode不是数组,而且它们似乎也可能指向同一事物。作为旁注,您不需要在调用delete[] p或之前检查 null delete p:如果指针p为 null,则此表达式将无效。

这与您的问题无关,但请注意您的优先级队列O(n)(具有n大小)复杂性。通常,在实现优先级队列时,您希望获得O(log(n))复杂性。实现这种优先级队列的最简单策略是d-heap,它方便地存在于一个数组中,并且实际上比您的链表更容易维护(我认为,至少)。

于 2012-11-28T01:36:00.073 回答
1

使用 delete[] 将尝试删除其对象是某种数组的指针。还有另一种删除类型,它允许删除指向单个对象的指针。(提示:非常直观)

于 2012-11-28T01:31:16.770 回答
1

您正在删除itnode使用delete []. 它们不是数组。您只能delete []对数组或对象数组使用语法。请记住对相同数据类型使用类似删除和新建命令的经验法则。如果您已分配内存new,请删除delete。如果您已分配内存new [],请删除它deete []

于 2012-11-28T01:31:27.617 回答