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;
}