次の定義を持つクラスがあります。
class BinomialNode
{
public int key; // The key value
public int x_point; // x co-ordinate for drawing
public int y_point; // y co-ordinate for drawing
public int degree; // number of siblings/children for current node
public BinomialNode parent;
public BinomialNode child;
public BinomialNode sibling;
...
}
私たちは大学で二項ヒープを学んでおり、マージと挿入のアルゴリズムをコードに実装しました。少なくとも、Visual Studio を一時停止して "Locals" に移動すると (マウスを変数の上に置いて)、期待どおりにデータが表示されます。
実験として、標準の「二項ノード」に 2 つの変数を追加しました。それらは x_point と y_point です。プログラムの実行中に、これが表示されます。
上で示した領域に注意してください。同じノードを表すはずですが、ご覧のとおり、x_point の値が異なります。(それ以外の場合は y_point が異なります)
なぜこれが起こっているのか、誰にも手がかりがありますか？私が理解しているように、それが同じノードを表す場合、データは同一である必要があります。しかし、そうではありません。つまり、同じノードではありません。どうすればそれが可能になりますか？「余分な」x_point 変数と y_point 変数を無視すると、コードは完全に実行されます。実際、私はこれが問題であることさえ知りませんでした。
私のスニペットからは見えませんが、クラス定義の外で編集する値は x_point と y_point だけです。他のものは公開されていますが、読み取り専用です。
編集：ここに私が作ったコードがあります、
class BinomialNode
{
public int key; // The key value
public int x_point; // x co-ordinate for drawing
public int y_point; // y co-ordinate for drawing
public int degree; // number of siblings/children for current node
public BinomialNode parent;
public BinomialNode child;
public BinomialNode sibling;
// Binomial Link takes the tree rooted at y and makes it a child of z
private static void Binomial_Link(ref BinomialNode y,ref BinomialNode z)
{
y.parent = z;
y.sibling = z.child;
z.child = y;
z.degree++;
}
// This merges the root lists of H1 and H2 into a single linked list that is sorted
// by degree in increasing order
private static BinomialNode Binomial_Heap_Merge(BinomialNode H1, BinomialNode H2)
{
BinomialNode H = new BinomialNode();
BinomialNode temp = H;
if (H1 == null) // if it's the first insert
{
return H2;
}
while (H1 != null && H2 != null)
{
if (H1.degree < H2.degree)
{
// insert H1 into position
temp.key = H1.key;
temp.x_point = H1.x_point;
temp.y_point = H1.y_point;
temp.child = H1.child;
temp.degree = H1.degree;
temp.sibling = new BinomialNode();
temp = temp.sibling;
// move H1 to the next sibling
H1 = H1.sibling;
}
else
{
// insert H2 into position
temp.key = H2.key;
temp.x_point = H2.x_point;
temp.y_point = H2.y_point;
temp.child = H2.child;
temp.degree = H2.degree;
temp.sibling = new BinomialNode();
temp = temp.sibling;
// move H2 to next sibling
H2 = H2.sibling;
}
}
// one of them hit null, so fill in the rest
while (H1 != null)
{
// insert H1 into position
temp.key = H1.key;
temp.x_point = H1.x_point;
temp.y_point = H1.y_point;
temp.child = H1.child;
temp.degree = H1.degree;
temp.sibling = new BinomialNode();
temp = temp.sibling;
// move H1 to the next sibling
H1 = H1.sibling;
}
while (H2 != null)
{
// insert H2 into position
temp.key = H2.key;
temp.x_point = H2.x_point;
temp.y_point = H2.y_point;
temp.child = H2.child;
temp.degree = H2.degree;
temp.sibling = new BinomialNode();
temp = temp.sibling;
// move H2 to the next sibling
H2 = H2.sibling;
}
// To remove the extra node added,
temp = H;
while (temp != null)
{
if (temp.sibling.key == 0 && temp.sibling.sibling == null && temp.sibling.child == null)
{
// found the extra, now to get rid of it!
temp.sibling = null;
}
temp = temp.sibling;
}
return H; // send back the merged heap
}
// Unites the binomial heaps H1 & H2 and returns resulting heap
public static BinomialNode Binomial_Heap_Union(BinomialNode H1, BinomialNode H2)
{
BinomialNode prev_x, x, next_x;
BinomialNode H = new BinomialNode();
H = Binomial_Heap_Merge(H1, H2);
// simple checks
if (H == null)
{
return H;
}
else
{
prev_x = null;
x = H;
next_x = x.sibling;
}
// now, for the actual merging
while (next_x != null)
{
if ((x.degree != next_x.degree) || (next_x.sibling != null && x.degree == next_x.sibling.degree))
{
prev_x = x;
x = next_x;
}
else if (x.key <= next_x.key)
{
x.sibling = next_x.sibling;
Binomial_Link(ref next_x, ref x);
}
else
{
if (prev_x == null)
{
H = next_x;
}
else
{
prev_x.sibling = x.sibling;
}
Binomial_Link(ref x, ref next_x);
x = next_x;
}
next_x = x.sibling;
}
// now, to return the merged heap
return H;
}
// inserting a key into a heap
public static void Binomial_Heap_Insert(ref BinomialNode H, int x)
{
BinomialNode H_temp = new BinomialNode();
H_temp.key = x;
H_temp.parent = null;
H_temp.degree = 0;
H_temp.sibling = null;
H_temp.child = null;
H = Binomial_Heap_Union(H, H_temp);
}
}
フォーム ウィンドウを使用してユーザーからデータを取得し、ヒープに入力します。入力はこちら、
private void button1_Click(object sender, EventArgs e)
{
BinomialNode.Binomial_Heap_Insert(ref B_HEAP1, Int32.Parse(numericUpDown1.Value.ToString()));
// drawing the heap
pictureBox1.Refresh();
int x = 0;
DrawNodeValue(pictureBox1, ref B_HEAP1, ref x, 0);
}
コードがあまり悪くないことを願っていますか？