
数据结构与算法(C#实现) (2).doc
34页数据结构与算法(C#实现)系列-----前言Heavenkiller (原创)搞计算机的人都应该很清楚,语言只是一种工具,算法才是灵魂现在的开发语言有很多,如 C++,VB,Perl,java,c#,还有如脚本语言 js,vbs 等,在如此多的选择面前,很多人不知道该选择哪一种好其实不管哪一种语言,既然他存在,就一定有他的价值,有它的特定用途,而这往往是其它语言所无法比拟的譬如 C++就适合于系统底层的编程,而 java一般就用于对稳定性,兼容性要求较高的场合,正所谓各有所长像我一般用 C++编写网络基层和与操作系统相关的程序,用 C#写 ASP.NET 等程序,必要的时候再辅以 Rose, Rational XDE 等建模工具但无论选择哪一种语言,算法才是根本,掌握了算法,就掌握了所有语言的根本,以不变应万变微软的 C#是一种全新的语言,利用它能快捷、高效地布署程序现在关于 C#的资料也已经有很多了,各个方面的资料都能找得到,但用 C#做数据结构的似乎还没有什么,在 CSDN 上我只找到了三四篇,而且仅仅是讲了一下链表之类简单的数据结构于是我利用空闲的时间用 C#写了一些数据结构与算法的实现,希望对大家学习数据结构能够有所帮助。
另外,由于时间仓促,难免出现一些纰漏,希望大家不吝赐教给予指正,我的 email 是 heavenkiller2002@.欢迎大家和我一起交流学习本系列包括树,N 叉树,广义树,二叉树,BST 二叉查找树,AVL 平衡树,堆,二叉堆,以及图还有一些如哈希表,散列,左翼树,二项树,Haffman 编码树等因时间关系,暂时未能奉上,以后有时间再补上吧首先给大家展示一幅用 Rational XDE for .NET 生成的类模型图,让大家对所有的类有一个大概的了解数据结构与算法(C#实现)系列---演示篇(一)Heavenkiller(原创)这一篇主要是针对以后各篇的数据类型进行一个实质性的演示因此希望大家具体看了各种数据结构的分析之后再看这篇主要包括如下几个方面的演示:1. 堆栈 演示了一个利用堆栈作的 RPN 计算器2. 排序表演示了一个利用排序表做的多项式表达式的加法运算3. 广义树演示了深度遍历和广度遍历4. N 叉树演示了 N 叉树的生成插入删除等基本操作5. 表达式树演示了一个用二叉树和堆栈做的可以将一个后缀表达式翻译为日常中熟悉的中缀表达式的例子6. AVL 树。
演示了基本操作using System;using System.Collections;namespace DataStructure{/// /// Class1 的摘要说明/// class Show{/// /// 应用程序的主入口点/// [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 StackShowStack_RPNCalCulator();break;case "2"://SortedListShowSortedList_Polynomial();break;case "3": ShowGeneralTree_travel();break;case "4":ShowNaryTree();//演示一个三叉树的 Attach 和 Detachbreak;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-2NaryTree 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);}数据结构与算法(C#实现) 系列--- 演示篇( 二)Heavenkiller(原创)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 StacktravelType=Tree.TraversalType.Breadth;Console.WriteLine("广度遍历");break;case "2"://SortedListtravelType=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 operationConsole.WriteLine("A.AttackSubtree(B)");Console.WriteLine("A.AttackSubtree(C)");Console.WriteLine("B.AttackSubtree(D)");Console.WriteLine("B.。
