-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

いくつか問題があると思います。

まず、最も重要なのは、クラスにデストラクタがないことです。また、プログラム内のすべての要素がデキューされていない場合、メモリリークが発生します。デストラクタを作成するか、生のポインタの代わりにスマートポインタを使用します。

次に、@ Andy Prowl（Twitterのような投稿で@人を@する方法を知っている人はいますか？）が言ったように、初期化されていないローカル変数を考慮する必要があります。またT data = T()、組み込みタイプとカスタムタイプの両方でうまく機能します。

max_queue_items第三に、キューには容量制限があると思いますが、エンキュー部分に対応するコードはありません。

とはいえ、これらすべての欠陥が通常の場合に深刻なクラッシュを引き起こす可能性があるとは思いません。コードがクラスを呼び出すときに問題が発生し、初期化されていない戻り値の処理が正しくないとクラッシュする可能性があります。

于 2013-02-20T02:59:00.547 に答える
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

もう1つの可能性は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 に答える
0

デキューで発生する可能性のある唯一の問題は、不明なタイプTの一時変数を作成していることです。優先度キューにデフォルトのコンストラクターがないタイプのデータを格納している場合、デキュー時に問題が発生します。呼び出して、その変数をデフォルトで構築しようとします。

この場合、データ自体ではなくテンプレートタイプへのポインタを保持するように優先キューを作り直すことをお勧めします。

于 2013-02-21T15:11:38.013 に答える