0

extractMin()当我多次调用时，此代码会崩溃。我认为对你们中的一些人来说，问题出在函数上应该是显而易见的，因为我是指针新手，可能是一个明显的错误。所以你知道它是一个链表就足够了，除了函数应该使用<运算符检索字典最小值，然后从链表中删除该值之外，无需详细说明。

string LinkedListPQueue::extractMin() {
    if (this->isEmpty()) throw ErrorException("Empty queue.");
    string front = LEX_HIGH;
    cell *old;

    for (int i = 0; i < this->size(); i++) {
        if (this->head->value < front) {
            front = this->head->value;
            old = this->head;
        }

        old = this->head;
        this->head = this->head->next;
    }

    logSize--;
    delete old;
    return front;
}



void LinkedListPQueue::enqueue(const string& elem) {
    cell *newCell = new cell;
    newCell->value = elem;
    newCell->next = NULL;
    if(this->isEmpty()) {
        this->head = this->tail = newCell;
        logSize++;

    } else {
        recurSort(newCell);
        this->tail->next = newCell;
        this->tail = newCell;
        logSize++;
    }
}
4

3 回答 3

1

您head被修改但在运行后从未重置

您应该简单地使用iterators或简单地添加一个从开始的指针head并移动该指针，而不是“破坏”您的列表head

于 2013-01-12T19:32:35.540 回答
1

您正在修改 中的头成员extractMin()，这会使列表损坏。

于 2013-01-12T19:32:42.990 回答
1

问题在于这个循环：

for (int i = 0; i < this->size(); i++) {
    if (this->head->value < front) {
        front = this->head->value;
        old = this->head;
    }

    old = this->head;
    this->head = this->head->next;
}

它对我来说似乎已经过时了，但它也会导致内存泄漏以及导致列表在执行后具有单个元素。

在我看来这两行：

old = this->head;
this->head = this->head->next;

不应该在循环中。函数逻辑应该更复杂一些——你找到一个指向最小元素的指针，然后将它的值与头部交换，然后移除头部。

于 2013-01-12T19:34:02.593 回答