heap.cs

使用C#写的数据结构库(从链表到图)

using System;

namespace DataTypeDemo
{
	/// <summary>
	/// heap 的摘要说明。
	/// </summary>
	public class heap : tree
	{
		private treeNode hcrrent;
		private treeNode hroot;
		private bool isBig;
		private object[] allData;
		private int count;

		public bool IsBig
		{
			get{return isBig;}
			set{isBig = value;}
		}
		public treeNode HCrrent
		{
			get{return hcrrent;}
		}
		public treeNode HRoot
		{
			get{ return hroot;}
		}
	
		public heap()
		{
			//
			// TODO: 在此处添加构造函数逻辑
			//
			this.hcrrent = null;
			this.hroot = null;
		}

		/**
		*CreateHeap
		* 
		* <PARAM> 
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void CreateHeap()
		{
		}

		/**
		*CreateHeap
		* 
		* <PARAM> object[], bool
		* <RETURN> _
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void CreateHeap(object[] data,bool b)
		{
			bool isint = false;
			double[] idata = new double[data.Length];

			//get changed int type,if return true
			isint = this.changeArrayType(ref idata, data, b);
			//create int type heap
			if(isint == true)
			{
				string[] sdata = new string[data.Length];
				int i =0;
				foreach(double d in idata)
				{
					sdata[i] = d.ToString();
					i++;
				}
				base.CreateTree(sdata);
			}
			//create other type heap
			else
			{
				base.CreateTree(data);
			}
			this.hroot = base.root; //get base.root
			this.isBig = b;	//get The bigRoot heap or small
		}

		/**
		*changeArrayType
		* changed object[] type to int type		
		* <PARAM>ref int[] idata,object[] data,bool big
		* <RETURN>bool
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private bool changeArrayType(ref double[] idata,object[] data,bool big)
		{
			int i=0;
			foreach(object d in data)
			{
				if(this.changeType(ref idata[i],d) == false)
				{
					return false;
				}
				i++;
			}
			idata = this.taxis(idata,big); // taxis big heap or small heap
			return true;
		}

		/**
		*changeType
		* changed object type to int type		
		* <PARAM>ref double d, object data
		* <RETURN>bool
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private bool changeType(ref double d, object data)
		{
			bool isdouble = false;
			try
			{
				d = Convert.ToDouble(data); //change int type
				isdouble = true;
			}
			catch{}
			return isdouble;
		}

		/**
		*Taxis
		* Taxis from small to big,or ...
		* <PARAM>int[] ,bool 
		* <RETURN> int[]
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private double[] taxis(double[] data, bool b)
		{
			int size = data.Length;
			double[] ndata = new double[size];
			//go on the taxis for big or smallRoot heap
			for(int i=1;i<size;i++)
			{
 
				for(int j=0;j<size-i;j++)
 
					if(data[j]>data[j+1])
					{
 
						double temp;
 
						temp=data[j];
 
						data[j]=data[j+1];
 
						data[j+1]=temp;
 
					}
			}
			//is big root heap
			if(b == false)
			{
				ndata = data;
			}
			// else small root heap
			else
			{
				for(int i=0,j=(size-1); i<size; i++,j--)
				{
					ndata[i] = data[j];
				}
			}
			return ndata;	//return 
		}

		/**
		*getAllData
		* 
		* <PARAM> 
		* <RETURN> treeNode
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private void getAllData(treeNode r)
		{
			if(r != null)
			{
				
				getAllData(r.Left);
				getAllData(r.Right);
				this.allData[this.count++] = r.Data;
			}
		}

		/**
		*getLeafNode
		* 
		* <PARAM> 
		* <RETURN> treeNode
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private treeNode getLeafNode()
		{
			treeNode temp = this.hroot;
			while(temp != null && temp.Left != null)
			{
				temp = temp.Left;
			}
			return temp;
		}

		/**
		*InsertHeapNode
		* 
		* <PARAM> tree pardata,object data, bool isright
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private void InsertHeapNode(treeNode parNode,object data, bool isright)
		{
			double indata = 0;
			//auto add node
			if(this.changeType(ref indata,data) != false)
			{
				this.count = 0;
				this.allData = new object[base.length+1];
				this.getAllData(this.hroot);
				this.allData[allData.Length-1] = (object)indata;
				this.CreateHeap(this.allData,this.isBig);
			}
			//have choose add node
			else
			{
				if(isright == true)
				{
					base.InsertRight(parNode,data);
				}
				else
				{
					base.InsertLeft(parNode,data);
				}
			}
		}
		
		/**
		*InsertHeapNode
		* 
		* <PARAM> object pardata,object data, bool isright
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		private void InsertHeapNode(object pardata,object data, bool isright)
		{
			this.InsertHeapNode(base.getNode(pardata),data,isright);
		}

		/**
		*InsertHeapRight
		* 
		* <PARAM> object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapRight(object data)
		{
			this.InsertHeapNode(this.getLeafNode().Data,data,true);
		}
	
		/**
		*InsertHeapLeft
		* 
		* <PARAM> object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapLeft(object data)
		{
			treeNode tn = this.getLeafNode();	
			this.InsertHeapNode(tn.Data,data,false);
		}

		/**
		*InsertHeapRight
		* 
		* <PARAM> object, object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapRight(object rdata,object pardata)
		{
			this.InsertHeapNode(pardata,rdata,true);
		}

		/**
		*InsertHeapRight
		* 
		* <PARAM> object, treeNode
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapRight(object rdata,treeNode parNode)
		{
			this.InsertHeapNode(parNode,rdata,true);
		}

		/**
		*InsertHeapLeft
		* 
		* <PARAM> object ,object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapLeft(object ldata,object pardata)
		{
			this.InsertHeapNode(pardata,ldata,true);
		}

		/**
		*InsertHeapLeft
		* 
		* <PARAM> object ,treeNode
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void InsertHeapLeft(object ldata,treeNode parNode)
		{
			this.InsertHeapNode(parNode,ldata,true);
		}

		/**
		*DeleteHeapRight
		* 
		* <PARAM> object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void DeleteHeapRight(object pardata)
		{
			base.DeleteRight(pardata);
		}

		/**
		*DeleteHeapLeft
		* 
		* <PARAM> object
		* <RETURN> -
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public void DeleteHeapLeft(object pardata)
		{
			base.DeleteLeft(pardata);
		}

		/**
		*GetHeapLeft
		* 
		* <PARAM> object
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public object GetHeapLeft(object pardata)
		{
			return base.GetLeft(pardata);
		}

		/**
		*GetHeapRight
		* 
		* <PARAM> object
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public object GetHeapRight(object pardata)
		{
			return base.GetRight(pardata.ToString());
		}

		/**
		*GetHeapParent
		* 
		* <PARAM> object data
		* <RETURN> object
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public object GetHeapParent(object data)
		{
			return base.GetParent(data.ToString());
		}
		
		/**
		*GetHeapCurrent
		* 
		* <PARAM> object data
		* <RETURN>treeNode
		* <NOTES> 
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public treeNode GetHeapCurrent(object data)
		{
			return base.GetCurrentNode(data.ToString());
		}

		/**
		*GetFindData
		* 
		* <PARAM> int index
		* <RETURN>object
		* <NOTES> is override base
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public override object GetFindData(int index)
		{
			return null;
		}

		/**
		*SetEmpty
		* 
		* <PARAM> 
		* <RETURN> -
		* <NOTES> the override base
		* <HISTORY> 2004/6/30 by LiJun
		*/
		public override void SetEmpty()
		{
			base.SetEmpty();
			this.hroot = null;
			this.length = 0;
		}
	}
}