数据结构与算法(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);
}
……