[算法] C#实现的数据结构与算法演示

萧闫子

这一篇主要是针对以后各篇的数据类型进行一个实质性的演示。因此希望大家具体看了各种数据结构的分析之后再看这篇。
     主要包括如下几个方面的演示：
1.      堆栈。 演示了一个利用堆栈作的RPN计算器
2.      排序表。演示了一个利用排序表做的多项式表达式的加法运算
3.      广义树。演示了深度遍历和广度遍历
4.      N叉树。演示了N叉树的生成插入删除等基本操作
5.      表达式树。演示了一个用二叉树和堆栈做的可以将一个后缀表达式翻译为日常中熟悉的中缀表达式的例子
6.      AVL树。演示了基本操作


using System;
using System.Collections;

namespace DataStructure
{
     /// <summary>
     /// Class1 的摘要说明。
     /// </summary>
     class Show
     {
         /// <summary>
         /// 应用程序的主入口点。
         /// </summary>
         [STAThread]
         static void Main(string[] args)
         {
              //
              // TODO: 在此处添加代码以启动应用程序
              //
              while(true)
              {
                   Console.WriteLine("please choose a the No. of a item you want to perform:");
                   Console.WriteLine("1.Stack----- RPNCalCulator");
                   Console.WriteLine("2.SortedList-----the addition of polynomial realized by sortedlist ");
                   Console.WriteLine("3.GeneralTree----depthtravesal and breathtraval");
                   Console.WriteLine("4.NaryTree");
                   Console.WriteLine("5.ExpressionTree");
                   Console.WriteLine("6.AVLTree");
                   Console.WriteLine("7.BinaryHeap");
                   Console.WriteLine("exit--Exit this programme");
                   //Test();

                   switch(Console.ReadLine())
                   {
                       case "1"://Show Stack
                            ShowStack_RPNCalCulator();
                            break;
                       case "2"://SortedList
                            ShowSortedList_Polynomial();
                            break;
                       case "3":                  
                            ShowGeneralTree_travel();
                            break;
                       case "4":
                            ShowNaryTree();//演示一个三叉树的Attach和Detach
                            break;
                       case "5":
                            ShowExpressionTree();
                            break;
                       case "6":
                            ShowAVLTree();
                            break;
                       case "7":
                            ShowBinaryHeap();
                            break;
                       case "exit":
                            return;      
                       default:
                            break;
                   }
              }

         }
         public static void ShowBinaryHeap()
         {
              //构造一个二叉堆， 包含2,4,6,8,10,12
              BinaryHeap bHeap=new BinaryHeap(10);
              bHeap.Enqueue(12);
              bHeap.Enqueue(10);
              bHeap.Enqueue(8);
              bHeap.Enqueue(6);
              bHeap.Enqueue(4);
              bHeap.Enqueue(2);

              //测试Dequeue();
              while(bHeap.Count!=0)
              {
                   Console.WriteLine(bHeap.DequeueMin().ToString());
              }
         }
         public static void ShowAVLTree()
         {
              AVLTree testAVL=new AVLTree(5);
              testAVL.Insert(1);
              testAVL.Insert(3);
              testAVL.Insert(7);
              testAVL.Insert(8);
              testAVL.Insert(9);
              testAVL.Insert(10);
              testAVL.Insert(11);

              PrintVisitor vis=new PrintVisitor();
              Tree.InOrder inVis=new DataStructure.Tree.InOrder(vis);
              testAVL.DepthFirstTraversal(inVis);
         }
         public static void ShowExpressionTree()
         {
              ExpressionTree.PostfixToInfix();
         }
         public static void ShowNaryTree()
         {
              //构造一个三叉树，具体见图1-2
              NaryTree A=new NaryTree(3,"A");
              NaryTree B=new NaryTree(3,"B");
              NaryTree C=new NaryTree(3,"C");
              NaryTree D=new NaryTree(3,"D");
              NaryTree E=new NaryTree(3,"E");

              B.AttachSubtree(1,D);
              B.AttachSubtree(2,E);
               A.AttachSubtree(1,B);
              A.AttachSubtree(3,C);
                //---------------------------
              Console.WriteLine("广度遍历");
              PrintVisitor vis=new PrintVisitor();
               A.BreadthFirstTraversal(vis);//广度遍历
               Console.WriteLine("前序遍历");
              Tree.PreOrder preVisit=new DataStructure.Tree.PreOrder(vis);
              A.DepthFirstTraversal(preVisit);

              Console.WriteLine("后序遍历");
              Tree.PostOrder postVisit=new DataStructure.Tree.PostOrder(vis);
              A.DepthFirstTraversal(postVisit);

              Console.WriteLine("中序遍历");
              Tree.InOrder inVisit=new DataStructure.Tree.InOrder(vis);
              A.DepthFirstTraversal(inVisit);               
         }
         public static void ShowGeneralTree_travel()
         {
              IEnumerator tmpIEnum;
              Tree.TraversalType travelType=0;

              //---------------------提示----------------------------
              Console.WriteLine("please choose a the No. of a item you want to travel:");
              Console.WriteLine("1.BreadthFirst----- 广度遍历");
              Console.WriteLine("2.PreDepthFirst-----前序遍历");
              Console.WriteLine("3.InDepthFirst----中序遍历");
              Console.WriteLine("4.PostDepthFirst----后序遍历");
              switch(Console.ReadLine())
              {
                   case "1"://Show Stack
                       travelType=Tree.TraversalType.Breadth;
                       Console.WriteLine("广度遍历");
                       break;
                   case "2"://SortedList
                       travelType=Tree.TraversalType.PreDepth;
                       Console.WriteLine("前序遍历");
                       break;
                   case "3":
                       travelType=Tree.TraversalType.InDepth;
                       Console.WriteLine("中序遍历");
                       break;
                   case "4":

travelType=Tree.TraversalType.PostDepth;
                       Console.WriteLine("后序遍历");
                       break;

                   default:
                       break;
              }
              //构造一棵广义树 generaltree
              GeneralTree A=new GeneralTree("A");
              GeneralTree B=new GeneralTree("B");
              GeneralTree C=new GeneralTree("C");
              GeneralTree D=new GeneralTree("D");
              GeneralTree E=new GeneralTree("E");
              GeneralTree F=new GeneralTree("F");
                       A.AttackSubtree(B);
              A.AttackSubtree(C);
              B.AttackSubtree(D);
              B.AttackSubtree(E);
              A.AttackSubtree(F);
              //show the operation
              Console.WriteLine("A.AttackSubtree(B)");
              Console.WriteLine("A.AttackSubtree(C)");
              Console.WriteLine("B.AttackSubtree(D)");
              Console.WriteLine("B.AttackSubtree(E)");
              Console.WriteLine("A.AttackSubtree(F)");
//--------------------------------------------------------

              A.SetTraversalType(travelType);//设置遍历类型
              tmpIEnum=A.GetEnumerator();

              //Console.WriteLine("begin to depthfist travel:");

              while(tmpIEnum.MoveNext())
              {
                   Console.WriteLine(tmpIEnum.Current.ToString());
              }
    }

         public static void ShowStack_RPNCalCulator()
         {
              //read a expression string and push every character into the stack in queue.
              Console.WriteLine("this is performance for stack,you can input a string like this '123*+',then this subprogramme can compute it and get the result '7',this is RPN calculator. ");
              Console.WriteLine("please input a expression string:");
              string strExpression=Console.ReadLine();
              char [] tmpChars=strExpression.ToCharArray(0,strExpression.Length);
              Stack stackRPN=new Stack();

              int numA,numB;
              foreach(char tmp in tmpChars)
              {
                   switch (tmp)
                   {
                        case '*':
                            numA=(int)stackRPN.Pop();
                            numB=(int)stackRPN.Pop();
                            stackRPN.Push(numA*numB);
                            break;
                       case '+':
                            numA=(int)stackRPN.Pop();
                            numB=(int)stackRPN.Pop();
                            stackRPN.Push(numA+numB);
                            break;
                       default:
                            stackRPN.Push(Int32.Parse(tmp.ToString()));
                            break;

                   }

              }
              Console.WriteLine("the result is:{0}",stackRPN.Pop().ToString());
           }
public static void ShowSortedList_Polynomial()
         {
              //100+10*x+x^2  + 1+10*x+100x^2
              SortedList tmpListA=new SortedList();
              SortedList tmpListB=new SortedList();
              SortedList tmpListC=new SortedList();//used to store the result
              SortedList tmpKeyList=new SortedList();//used to store all keys of two polynomials

               //init polynomial A and show it
              tmpListA.Add(0,100);
              tmpListA.Add(1,10);
              tmpListA.Add(2,1);
              ShowSortedList_ShowPolynomial("tmpListA",tmpListA.GetEnumerator());

              //init polynomial B and show it
              tmpListB.Add(0,1);
              tmpListB.Add(1,10);
              tmpListB.Add(2,100);
              ShowSortedList_ShowPolynomial("tmpListB",tmpListB.GetEnumerator());

              //init the key list which contains all keys of A and B but everyone once
              IDictionaryEnumerator tmpIDic=tmpListA.GetEnumerator();
              while(tmpIDic.MoveNext()!=false)
              {
                   if(!tmpKeyList.ContainsKey(tmpIDic.Key))
                   {
                       tmpKeyList.Add(tmpIDic.Key,null);
                   }
              }

              tmpIDic=tmpListB.GetEnumerator();
              while(tmpIDic.MoveNext()!=false)
              {
                   if(!tmpKeyList.ContainsKey(tmpIDic.Key))
                   {
                       tmpKeyList.Add(tmpIDic.Key,null);
                   }
              }

              //Add A and B and show the result
              tmpIDic=tmpKeyList.GetEnumerator();
              while(tmpIDic.MoveNext()!=false)
              {
                   object objA=null,objB=null,objC=null;
                   objC=tmpIDic.Key;
                   if(tmpListA.ContainsKey(objC))
                       objA=tmpListA[objC];
                   if(tmpListA.ContainsKey(objC))
                       objB=tmpListB[objC];
                   //objC=objA+objB;
                   //tmpKeyList[objC]=(int)objA+(int)objC;
                   tmpListC.Add(objC,(int)objA+(int)objB);
               }
              ShowSortedList_ShowPolynomial("the addition result of A and B",tmpListC.GetEnumerator());
           }
         public static void ShowSortedList_ShowPolynomial(string tip,IDictionaryEnumerator iDic)
         {
              string strExpress=null;
              iDic.Reset();
              while(iDic.MoveNext()!=false)
              {
                   strExpress+=iDic.Value.ToString()+"*X^"+iDic.Key.ToString()+"+";
              }
              Console.WriteLine(tip+":"+strExpress);
          }
}

二叉树
using System;
using System.Collections;
namespace DataStructure
{
    /// <summary>
    /// BinaryTree 的摘要说明。
    /// </summary>
    public class BinaryTree:NaryTree
    {
         //构造二叉空树
         public BinaryTree():base(2)
         {
             //
             // TODO: 在此处添加构造函数逻辑
             //
         }
         
  public BinaryTree(object _obj):base(2,_obj)
         {
  
  }
         //------------------------------------------------------
         protected override object GetEmptyInstance(uint _degree)
         {
      return new BinaryTree(_degree);
  }
         //------------------------------------------------------

         //重写深度遍历
         public override void DepthFirstTraversal(IPrePostVisitor _vis)
         {
              if ( !IsEmpty() )
              {
                  _vis.PreVisit(this.Key);
                  this[0].DepthFirstTraversal(_vis);
                  _vis.Visit(this.Key);
                  this[1].DepthFirstTraversal(_vis);
                  _vis.PostVisit(this.Key);
              }
          }

          //二叉树大小的比较
          //先比较关键字，如果相等，再比较左子树，如果再相等，则比较右子树----如此递归
          #region IComparable 成员
          public override int CompareTo(object obj)
          {
               // TODO: 添加 BinaryTree.CompareTo 实现
               //因为Comare()中已经进行了类型断定，故不会出现转型错误
               BinaryTree tmpTree=(BinaryTree)obj;

               if( this.IsEmpty() )
                   return tmpTree.IsEmpty()?0:-1;
               if( tmpTree.IsEmpty() )
                   return 1;
               int result=Comparer.Default.Compare(this,tmpTree);
               if(result==0)
                   result=this[0].CompareTo(tmpTree[0]);
               if(result==0)
                   result=this[1].CompareTo(tmpTree[1]);

               return result;
           }
           #endregion
      }
}
二叉堆
using System;
using System.Collections;

namespace DataStructure
{
    /// <summary>
    /// BinaryHeap 的摘要说明。-------二叉堆(基于数组的实现)
    /// </summary>
    public class BinaryHeap:IPriorityQueue
    {
         protected ArrayList array;
         //建立一个最多容纳_length个对象的空二叉堆
         public BinaryHeap(uint _length)
         {
              //
              // TODO: 在此处添加构造函数逻辑
              //
              array=new ArrayList((int)_length);
              array.Capacity=(int)_length;
         }
         //堆中对象个数
         public virtual int Count{get{return this.array.Count;}
    }
    //将成员数组变成用1为基数表达的形式
    public virtual object Item(int _i)
    {
         if(_i&gt;=this.array.Capacity)
         throw new Exception("Myundefinedut of index");//不能出界
         return this.array[_i-1];
    }

    #region IPriorityQueue 成员
    //先将空洞放在数组的下一个位置上，也就是i(注：基数是1),然后和[i/2]位置上的数比较，如果小于则将空洞上移到[i/2]位置，而原先[i/2]位置上的对象则移到上，否则就将空洞变为_obj----如此递归
    public void Enqueue(Object _obj)
    {
       // TODO: 添加 BinaryHeap.Enqueue 实现
       if( this.array.Count==this.array.Capacity )
           throw new Exception("My:priority queue is full");//如果优先队列已满，则抛出异常
       this.array.Add(new object());
       int i=this.array.Count;
       while(i&gt;1&amp;&amp;Comparer.Default.Compare(this.array[i/2-1],_obj )&gt;0)
       {
           //this.Item(i)=this.Item(i/2);
           this.array[i-1]=this.array[i/2-1];
           i/=2;
       }
       this.array[i-1]=_obj;
    }
    public object FindMin()
    {
         // TODO: 添加 BinaryHeap.FindMin 实现
         if( this.array.Count==0 )
             throw new Exception("My:priority queue is empty");//如果队列是空的，则抛出异常
         return this.array[0];
    }
    public object DequeueMin()
    {
         // TODO: 添加 BinaryHeap.DequeueMin 实现
         object tmpObj=this.FindMin();
         int i=1;
         while( (2*i+1)&lt;=this.array.Count)
         {
             if( Comparer.Default.Compare(this.array[2*i-1],this.array[2*i])&lt;=0 )
             {
                 this.array[i-1]=this.array[2*i-1];
                 this.array[2*i-1]=tmpObj;
                 i=2*i;
             }
             else
             {
                 this.array[i-1]=this.array[2*i];
                 this.array[2*i]=tmpObj;
                 i=2*i+1;
             }
         }
         object delObj=this.array[i-1];//暂时储存要删去的元素
         if(i!=this.array.Count)//如果搜索到的对象就是数组的最后一个对象，则什么都不要做
         {
             this.array[i-1]=this.array[this.array.Count-1];//添补空洞
         }
         this.array.RemoveAt(this.array.Count-1);//将最后一个对象删除
         return delObj;
     }
     #endregion
}
}
AVLTree
using System;
using System.Collections;
namespace DataStructure
{
    /// <summary>
    /// AVLTree 的摘要说明。-----平衡二叉查找树
    /// </summary>
    public class AVLTree:BST
    {
        protected int height;//空树的高定义为-1;
        
//构造一棵空的二叉查找树
        public AVLTree():base()
        {
            //
            // TODO: 在此处添加构造函数逻辑
            //
            height=-1;
         }
         public AVLTree(object _obj):base(_obj)
         {
             height=0;
         }
         //------------------------------------------------------
         protected override object GetEmptyInstance(uint _degree)
         {
      return new AVLTree();
  }
         //------------------------------------------------------
         protected int BalanceFactor()
         {
             if (this.IsEmpty() )
                 return 0;
             return ((AVLTree)this.Left).height-((AVLTree)this.Right).height;
          }
          //调整高度
         protected void AdjustHeight()
  {
      this.height=Math.Max( ((AVLTree)this.Left).height, ((AVLTree)this.Right).height)+1;
  }
         //平衡时的四种旋转方式
         protected void LLRotation()
         {
             if( this.IsEmpty() )
                 throw new Exception("My:invalid operation!");
             AVLTree avlB=new AVLTree(this.key);
             avlB.AttachSubtree(1,(AVLTree)this[0][1]);
             avlB.AttachSubtree(2,(AVLTree)this[1]);
             this.key=this[0].Key;
             this[0]=this[0][0];
             this[1]=avlB;
             //调整两个节点的高度
             ((AVLTree)this.Right).AdjustHeight();
             this.AdjustHeight();
          }
          protected void LRRotation()
          {
              if( this.IsEmpty() )
              throw new Exception("My:invalid operation!");
              ((AVLTree)this.Left).RRRotation();
              this.LLRotation();
          }

          protected void RRRotation()
          {
              if( this.IsEmpty() )
                  throw new Exception("My:invalid operation!");
              AVLTree avlB=new AVLTree(this.key);

              avlB.AttachSubtree(1,(AVLTree)this[0]);
              avlB.AttachSubtree(2,(AVLTree)this[1][0]);
              //avlA.AttachSubtree(1,avlB);

              //this=avlA;
              this.key=this[1].Key;
              this[0]=avlB;
              this[1]=this[1][1];
              //调整两个节点的高度
              ((AVLTree)this.Left).AdjustHeight();
              this.AdjustHeight();
           }
           protected void RLRotation()
           {
               if( this.IsEmpty() )
                  throw new Exception("My:invalid operation!");
               ((AVLTree)this.Right).LLRotation();
               this.RRRotation();
           }
//---------------override--------------------
public override void AttachKey(object _obj)
{
     if(!IsEmpty())
         throw new Exception("My:this node must be a empty tree node!");
     this.key=_obj;
     //产生一个degree长的数组,并将其初始化为空树
     this.treeList=new ArrayList();
     this.treeList.Capacity=(int)this.degree;
     for(int i=0;i<this.degree;i++)
     {
         treeList.Add(new AVLTree());
     }
     //
     this.height=0;
}
//在改动树的结构后平衡树
public override void Balance()
{
     this.AdjustHeight();
     //大于1则说明不平衡
     if( Math.Abs(this.BalanceFactor())>1)
     {
         if(this.BalanceFactor()>0)
         {
             if (((AVLTree)this.Left).BalanceFactor()>0)
                 this.LLRotation();
             else
                 this.LRRotation();
         }
         else
         {
              if (((AVLTree)this.Right).BalanceFactor()<0)
                  this.RRRotation();
              else
                  this.RLRotation();
         }
     }
}
public int Height
{
     get{return this.height;}
}

国产008

顶!!!!!!!!!!