pgm11_18.txt

来自「c#版本 算法大全 几乎所有常见的算法 This file contain」· 文本 代码 · 共 56 行

//
//   This file contains the C# code from Program 11.18 of
//   "Data Structures and Algorithms
//    with Object-Oriented Design Patterns in C#"
//   by Bruno R. Preiss.
//
//   Copyright (c) 2001--2002 by Bruno R. Preiss, P.Eng.  All rights reserved.
//
//   http://www.brpreiss.com/books/opus6/programs/pgm11_18.txt
//
public class BinomialQueue :
    AbstractContainer, MergeablePriorityQueue
{
    protected LinkedList treeList;

    public virtual void Merge(MergeablePriorityQueue queue)
    {
	BinomialQueue arg = (BinomialQueue)queue;
	LinkedList oldList = treeList;
	treeList = new LinkedList();
	count = 0;
	LinkedList.Element p = oldList.Head;
	LinkedList.Element q = arg.treeList.Head;
	BinomialTree carry = null;
	for (int i = 0; p!=null || q!=null || carry!=null; ++i)
	{
	    BinomialTree a = null;
	    if (p != null)
	    {
		BinomialTree tree = (BinomialTree)p.Datum;
		if (tree.Degree == i)
		{
		    a = tree;
		    p = p.Next;
		}
	    }
	    BinomialTree b = null;
	    if (q != null)
	    {
		BinomialTree tree = (BinomialTree)q.Datum;
		if (tree.Degree == i)
		{
		    b = tree;
		    q = q.Next;
		}
	    }
	    BinomialTree sum = Sum(a, b, carry);
	    if (sum != null)
		AddTree(sum);
	    carry = Carry(a, b, carry);
	}
	arg.Purge();
    }
    // ...
}