Ссылки не совпадают - PullRequest
       19

Ссылки не совпадают

0 голосов
/ 24 февраля 2012

У меня есть класс со следующим определением:

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 и перебираю «Локальные объекты» (при наведении мыши на переменную), я вижу данные, как и ожидал.

В качестве эксперимента я добавил 2 дополнительные переменныек стандартному «биномиальному узлу».Это x_point и y_point.Теперь во время выполнения программы я вижу это enter image description here

Обратите внимание на область, которую я указал выше.Предполагается, что он представляет один и тот же узел, но, как мы видим, значение x_point отличается.(В других случаях y_point отличается)

Кто-нибудь знает, почему это происходит?Как я понимаю, если он представляет один и тот же узел, данные должны быть идентичными.Но это не так - это означает, что это не тот же самый узел.Как это может быть возможно?Если я проигнорирую свои «лишние» переменные x_point и y_point, код работает отлично!На самом деле, я бы даже не знал, что это проблема.

Это не видно из моего фрагмента, но x_point & y_point - единственные значения, которые я РЕДАКТИРУЮ вне определения класса.Другие, в то время как public читаются только из.

РЕДАКТИРОВАТЬ: Вот код, который я сделал,

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

Надеюсь, код сделан не так уж плохо?

1 Ответ

1 голос
/ 24 февраля 2012

Вы создаете новый узел, а затем копируете все значения.Это то, что вы хотите сделать?Если вы планируете использовать те же узлы, то используйте те же узлы.

Вместо:

Node H = new Node();
Node temp = H;
if(node1 > node2)
  temp.values = node1.values
else
  temp.values = node2.values

Просто используйте фактические объекты ...

Node temp;
if(node1 > node2)
  temp = node1;
else
  temp = node2;

Я не уверен, где значения разделяются, но именно поэтому они на самом деле не один и тот же узел.

...