-1

我正在编写优先级队列的抽象数据类型作为大学的任务，其他人将使用它。我的类 dequeue 中有一个函数，它删除队列中的第一个元素并返回该元素的数据。但是，当我尝试从空队列中删除一个元素时，程序崩溃了。我应该在这里做什么？

如果有帮助，这是代码：

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H

#include <iostream>

using namespace std;

const int max_queue_items = 1000;

template<class T>
struct node{
    T data;
    int priority;
    node *next;
};

template<class T>
class PriorityQueue
{
    public:
        /*
            Constructor that creates an empty queue.
        */
        PriorityQueue(){
            head = NULL;
            size = 0;
        }

        /*
            Adds an element to the queue.

            Params:
            data - data of the element
            priority - priority of the element
        */
        bool is_empty(){
            if (size == 0){
                return true;
            }

            return false;
        }

        bool is_full(){
            if (size == max_queue_items){
                return true;
            }

            return false;
        }

        /*
            Adds an element to thq queue.
            It gets inserted before the first element with
            lower priority.
        */
        void enqueue(T data, int priority){
            node<T> * previous = NULL;
            node<T> * now = head;

            while (now != NULL && now->priority >= priority){
                previous = now;
                now = now->next;
            }

            node<T> * new_element = new node<T>;
            new_element->data = data;
            new_element->priority = priority;
            new_element->next = now;

            if (previous == NULL){
                head = new_element;
            } else {
                previous->next = new_element;
            }

            size++;
        }

        /*
            Removes the first element in the queue
        */
        T dequeue(){
            T data;

            if (!is_empty()){
                node<T> * now = head;
                data = now->data;
                head = head->next;
                delete now;

                size--;
            }

            return data;
        }

        /*
            Returns the priority of the first element.
            It's always the highest priority in the queue.
        */
        int get_first_priority(){
            return head->priority;
        }

        /*
            Returns the data of the first element in the queue.
        */
        T get_first_value(){
            if (is_empty())
                throw 0;

            return head->data;
        }

        /*
            Returns the number of elements in the queue.
        */
        int get_size(){
            return size;
        }

        /*
            Deletes the whole queue from the memory.
        */
        void flush(){
            node<T> * now;

            while (head != NULL){
                now = head;
                head = head->next;
                delete now;
                size--;
            }
        }

        /*
            Prints the whole queue following this format:
            data(priority)
        */
        void print(){
            node<T> * now = head;

            while (now != NULL){
                cout << now->data << "(" << now->priority << ")" << endl;
                now = now->next;
            }
        }

    private:
        node<T> * head; // Pointer to the head of the queue
        int size; // Number of elements in the queue
};

#endif // PRIORITYQUEUE_H
4

3 回答 3

1

这可能是也可能不是您的问题的根源，但我肯定会认为这是一个问题。在函数dequeue()中，您可能会在返回时返回一个未初始化的变量（如果不是T类类型）：is_empty()true

    T dequeue()
    {
        T data; // Uninitialized if T is not a class type

        if (!is_empty())
        {
            node<T> * now = head;

            //--------------------------------------------------------------
            // This initialization is skipped when `is_empty()` returns true
            data = now->data;
            //--------------------------------------------------------------

            head = head->next;
            delete now;

            size--;
        }

        return data;
    }

根据您对该函数返回的值和 的类型所做的操作T，您的程序可能具有未定义的行为（我可以想象T是您稍后取消引用的指针类型）。

您可能希望将函数的第一行更改为：

T data = T();

这会强制您的data对象进行值初始化。如果T是类类型，将调用默认构造函数。否则，data将被零初始化。

然后调用的函数dequeue()应该在使用它之前检查返回的值（或者更好的是，is_empty()在尝试从中弹出一个值之前调用队列以检查它是否为空）。

dequeue()您甚至可以考虑在被调用且队列为空时抛出异常：

T dequeue()
{
    if (is_empty())
    {
        // Requires including the <stdexcept> standard header
        throw std::logic_error("Queue is empty"); 
    }

    node<T> * now = head;
    T data = now->data;
    head = head->next;
    delete now;

    size--;

    return data;
}

客户端现在负责确保dequeue()永远不会在空队列上调用它（或者他们应该将调用包装dequeue()到一个try/catch块中以处理可能抛出的异常。

另一种可能性是将 a 返回bool给您的客户端，指示该值是否已成功弹出，可能会将弹出的元素分配给通过引用传递的参数：

bool dequeue(T& data)
{
    if (is_empty())
    {
        return false;
    }

    node<T> * now = head;
    data = now->data;
    head = head->next;
    delete now;

    size--;

    return true;
}

这样，客户端负责检查函数的结果。如果函数返回false，则该data变量将被初始化为客户端将其初始化为的任何值。处理错误情况的责任再次转移给客户。

于 2013-02-19T23:56:28.177 回答
1

我认为有一些问题。

首先也是最重要的，类没有析构函数。如果您的程序中并非所有元素都出队，则会出现内存泄漏。编写析构函数或使用智能指针而不是原始指针。

其次，正如@Andy Prowl（顺便说一句，谁知道如何@ twitter 等帖子中的人？）说，应该考虑未初始化的局部变量。并且T data = T()适用于内置和自定义类型。

第三，我认为队列有容量限制max_queue_items但入队部分没有对应的代码。

尽管如此，我认为所有这些缺陷在正常情况下都不会导致严重的崩溃。也许问题发生在您的代码调用类并且对未初始化的返回值的错误处理导致崩溃。

于 2013-02-20T02:59:00.547 回答
0

我在你的出队中看到的唯一潜在问题是你正在创建一个未知类型 T 的临时变量。如果你在优先级队列中存储没有默认构造函数的类型的数据，那么当你的出队时你会遇到问题调用并尝试默认构造该变量。

如果是这种情况，我建议您重新处理优先级队列以保存指向模板类型而不是数据本身的指针。

于 2013-02-21T15:11:38.013 回答