0

マージ、挿入、およびフェッチ機能を備えたプライオリティ キューを作成しています。テスト プログラムは、データと優先順位を指定してノードを挿入します。ノードを作成し、Leftist Tree Heap Priority Queue 内に配置しようとします。

これはクラス ノードのコードです。

template <class DATA>
class Node {
    public :
    DATA data ;
    double priority ;
    unsigned distance ;
    Node<DATA> * left , * right ;

    Node ( DATA & d , double prio ) : data (d) , priority(prio) ,
    distance(0) , left(NULL) , right(NULL) {} ;
} ;

これは、マージとスワップを使用してノードを挿入する私のコードです:

template<class DATA> 
Node<DATA> *
PQueue<DATA> :: merge ( Node<DATA> * p , Node<DATA> * q )
{
    unsigned d1, d2;

    if ( p == NULL ) return q ;
    if ( q == NULL ) return p ;

    if ( (p->priority) < (q->priority) ) // p is final root.
        swap(p,q) ;

    p->right = merge ( p->right , q );

    d1 = p->left->distance;
    d2 = p->right->distance;

    if ( d1 < d2 ) 
        swap(p->left,p->right) ; // leftist tree.

    p->distance = 1 + p->right->distance ;

    return p ;
}

template<class DATA>
void
PQueue<DATA> :: swap (Node<DATA> * p, Node<DATA> * q )
{
    Node<DATA> * temp;
    temp = p;
    p = q;
    q = temp;
    delete temp;
}

template < class DATA >
bool 
PQueue<DATA> :: insertPQ ( DATA & data , double priority )
{
    root = merge(root, new Node<DATA>(data, priority));
    return true;
}

挿入のテスト コードは次のとおりです。

pq.insertPQ( data[i] , data[i] )

最初の挿入は正常に機能します。2 番目の挿入はマージ関数に到達し、最初の再帰ループに入り、p->right = merge ( p->right , q );if でセグ フォールトを与えます。( p == NULL ) return q ;いくつかのチェックを行った後、p はこの時点で = NULL を実行しますが、if をチェックするとエラーが発生しますp == NULL。どんな助けでも大歓迎です。

4

1 に答える 1

1

あなたが思っている場所で実際にクラッシュしているとは思いません。

ただし、いくつかのバグがあります。まず、swap 関数は指定されたポインターを交換しますが、ツリーにはまったく影響を与えないことに注意してください。これらの引数を参照するつもりだったと思います：swap (Node<DATA> *&p, Node<DATA> *&q)

次に、そこでノードを削除しますが、ノードを割り当てていないことに注意してください。p ノードを解放しています。これにより、セグメンテーション違反が発生する可能性があります。

于 2012-06-29T06:42:04.473 に答える