數據結構與算法(C#實現)系列---演示篇(一)

                                 Heavenkiller(原創)

     這一篇主要是針對以后各篇的數據類型進行一個實質性的演示。因此希望大家具體看了各種數據結構的分析之后再看這篇。

     主要包括如下幾個方面的演示：

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

         }