Dziwnie przepinające się wskaźniki w kopcu dwumianowym

Odpowiedz Nowy wątek
2015-02-09 19:48
0

Hej,

Zabrałem się za implementację kopców dwumianowych w C++, i mam następujący problem ze wskaźnikami:

Gdy w mian wykonuje się

H = bHeap.Insert(&b);

w funkcji Insert po wykonaniu linii

X.n = x;

Wszystkie wskaźniki w następnej linii zaczynają wskazywać na X, przez co później tworzy się nieskończona pętla i program wisi.
Czemu tak się dzieje?

apex.h

#ifndef APEX_H
#define APEX_H
#include <vector>
#include "edge.h"

using namespace std;

class Apex
{
public:
    vector<Edge> Edges;
    Apex* Connection;
    int Value;
    int Distance;
    bool Visited;
    Apex();
    ~Apex();
};

#endif // APEX_H

apex.cpp


#include "apex.h"

Apex::Apex()
{
    Connection = NULL;
    Distance = Value = INT_MAX;
    Visited = false;
}

Apex::~Apex()
{}

node.h

#ifndef NODE_H
#define NODE_H
#include "apex.h"

struct Node
{
public:
    Apex* n;
    int degree;
    Node* parent;
    Node* child;
    Node* sibling;
};

#endif // NODE_H

node.cpp

#include "node.h" 

binomialHeap.h

#ifndef BINOMIALHEAP_H
#define BINOMIALHEAP_H
#include "node.h"
#include <cstdlib>

class BinomialHeap
{
private:
    Node* H;
    Node* Hr;
public:
    //Node* H;
    BinomialHeap();
    ~BinomialHeap();
    Node* Initializeheap();
    Node* Minimum();
    Node* Merge(Node* H1, Node* H2);
    Node* Union(Node* H1, Node* H2);
    Node* ExtractMin(Node* H1);
    void Link(Node *y, Node* z);
    Node* Insert(Apex* X);
    void Revert(Node* y);
};

#endif // BINOMIALHEAP_H 

binomialHeap.cpp - ograniczony do koniecznych funkcji

#include "binomialHeap.h"
using namespace std;

BinomialHeap::BinomialHeap()
{
    H = Initializeheap();
    Hr = Initializeheap();
}
BinomialHeap::~BinomialHeap()
{}
Node* BinomialHeap::Initializeheap()
{
    Node* np;
    np = NULL;
    return np;
}

void BinomialHeap::Link(Node* y, Node* z)
{
    y->parent = z;
    y->sibling = z->child;
    z->child = y;
    z->degree = z->degree + 1;
}

Node* BinomialHeap::Insert(Apex* x)
{
    Node X;
    X.parent = NULL;
    X.child = NULL;
    X.sibling = NULL;
    X.degree = 0;
    X.n = x;
    H = Union(H, &X);
    return H;
}

Node* BinomialHeap::Union(Node* H1, Node* H2)
{
    Node *H = Initializeheap();
    H = Merge(H1, H2);
    if (H == NULL)
        return H;
    Node* prev_x;
    Node* next_x;
    Node* x;
    prev_x = NULL;
    x = H;
    next_x = x->sibling;
    while (next_x != NULL)
    {
        if ((x->degree != next_x->degree) || ((next_x->sibling != NULL)
            && (next_x->sibling)->degree == x->degree))
        {
            prev_x = x;
            x = next_x;
        }
        else
        {
            if (x->n <= next_x->n)
            {
                x->sibling = next_x->sibling;
                Link(next_x, x);
            }
            else
            {
                if (prev_x == NULL)
                    H = next_x;
                else
                    prev_x->sibling = next_x;
                Link(x, next_x);
                x = next_x;
            }
        }
        next_x = x->sibling;
    }
    return H;
}

Node* BinomialHeap::Merge(Node* H1, Node* H2)
{
    Node* H = Initializeheap();
    Node* y;
    Node* z;
    Node* a;
    Node* b;
    y = H1;
    z = H2;
    if (y != NULL)
    {
        if (z != NULL)
        {
            if (y->degree <= z->degree)
                H = y;
            else if (y->degree > z->degree)
                H = z;
        }
        else
            H = y;
    }
    else
        H = z;
    while (y != NULL && z != NULL)
    {
        if (y->degree < z->degree)
        {
            y = y->sibling;
        }
        else if (y->degree == z->degree)
        {
            a = y->sibling;
            y->sibling = z;
            y = a;
        }
        else
        {
            b = z->sibling;
            z->sibling = y;
            z = b;
        }
    }
    return H;
}

main.cpp

#include "binomialHeap.h"

int main()
{
    BinomialHeap bHeap;
    Node *H;
    Apex a,b,c;
    a.Distance = 1;
    b.Distance = 2;
    c.Distance = 3;
    H = bHeap.Insert(&a);
    H = bHeap.Insert(&b);
    return 0;
}

Pozostało 580 znaków

2015-02-09 20:17

Za dużo kodu z jednoliterowymi zmiennymi, żeby się dało to ogarnąć wzrokiem. Ale widać, że
Initializeheap() można wywalić, bo jedyne co robi to zwraca nulla, więc zamiast

H = Initializeheap();

wystarczy

H = nullptr;  // ew. H = NULL jak nie masz C++11

Tak samo zamiast:

Node *H = Initializeheap();  
H = Merge(H1, H2);

wystarczy:

Node *tmpHead = Merge(H1, H2);

Używanie tej samej nazwy zmiennej i przesłonięcie zmiennej z klasy to zły pomysł. W dodatku nazwa jest totalnie bezużyteczna.

X.parent = NULL;
X.child = NULL;
X.sibling = NULL;
X.degree = 0;

Niech bezargumentowy konstruktor Node się tym zajmuje.

Poza tym odnoszę wrażenie, że

Node* BinomialHeap::Insert(Apex* x)
{
    Node X;
    ...
}

skoro tworzysz tymczasowy obiekt na stosie, to po wyjściu z funkcji obiekt zniknie i masz dziurawy kopiec. Chyba że gdzieś robisz kopię tego węzła, ale nie wczytałem się w ten kod.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0