数据结构与算法(C#实现).doc

数据结构与算法(C#实现)系列-前言 Heavenkiller (原创) 搞计算机的人都应该很清楚，语言只是一种工具，算法才是灵魂。现在的开发语言有很多，如C+,VB,Perl,java,c#,还有如脚本语言js,vbs等，在如此多的选择面前，很多人不知道该选择哪一种好。其实不管哪一种语言，既然他存在，就一定有他的价值，有它的特定用途，而这往往是其它语言所无法比拟的。譬如C+就适合于系统底层的编程，而java一般就用于对稳定性，兼容性要求较高的场合，正所谓各有所长。像我一般用C+编写网络基层和与操作系统相关的程序，用C#写ASP.NET等程序，必要的时候再辅以Rose, Rational XDE等建模工具。但无论选择哪一种语言，算法才是根本，掌握了算法，就掌握了所有语言的根本，以不变应万变。 微软的C#是一种全新的语言，利用它能快捷、高效地布署程序。现在关于C#的资料也已经有很多了，各个方面的资料都能找得到，但用C#做数据结构的似乎还没有什么，在CSDN上我只找到了三四篇，而且仅仅是讲了一下链表之类简单的数据结构。于是我利用空闲的时间用C#写了一些数据结构与算法的实现，希望对大家学习数据结构能够有所帮助。另外，由于时间仓促，难免出现一些纰漏，希望大家不吝赐教给予指正,我的email是.欢迎大家和我一起交流学习。 本系列包括树，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 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); 数据结构与算法(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 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(); 数据结构与算法(C#实现)系列-演示篇(三) Heavenkiller(原创) public static void ShowSortedList_Polynomial() /100+10*x+x2 + 1+10*x+100x2 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=tmpListAobjC; if(tmpListA.ContainsKey(objC) objB=tmpListBobjC; /objC=objA+objB; /tmpKeyListobjC=(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); 数据结构与算法(C#实现)系列-树(一) Heavenkiller(原创)首先我们给树下一个定义：树是一个有限的、非空的结点集，T=r or T1 or T2 oror Tn它具有下列性质：1集合指定的结点r叫做树的根结点2其余的结点可以划分成n个子集，T1,T2,Tn(n=0),其中每一个子集都是一棵树。树的其它定义如度，叶子，高等就请大家查阅别的资料吧，到处都有的。树的主要性质一个就是遍历，分为深度遍历和广度遍历在这里分别实现为DepthFirstTravesal()和WidthFirstTravesal()其中深度遍历又分为前序遍历、中序遍历、和后序遍历这是是采用适配器技术实现的。using System;using System.Collections;namespace DataStructure / / Tree 的摘要说明。 / when traverse, traversaltype cant be changed,or throw a exception / 支持枚举、比较、深度复制 / public abstract class Tree:IEnumerable,IComparable public Tree() / / TODO: 在此处添加构造函数逻辑 / protected Queue keyqueue=new Queue();/仅仅用于枚举时存放数据，不参与Equals实现中的比较 protected TraversalType traversaltype=TraversalType.Breadth;/ choose a traversal type,and DepthFirst is default /protected uint degree=0;/degree of the tree, init it as 0 /protected uint height=0;/height of the tree, init it as 0 /枚举不同的遍历类型 public enum TraversalType Breadth=1,/广度遍历 PreDepth=2,/前序遍历 InDepth=3,/中序遍历 PostDepth=4/后序遍历 ; /public virtual abstract object Key public abstract Tree thisuint _indexget;set;/if I only use get, can I change it later? public abstract object Keyget; public abstract uint Degreeget; /public abstract uint Heightget; public void SetTraversalType(TraversalType _type)traversaltype=_type;/set a traversal a type, if its not set manually, DepthFirst will be chosen in default public abstract bool IsEmpty();/ property takes the place of IsEmpty() public abstract bool IsLeaf(); /Only Visit, neednt queue public virtual void DepthFirstTraversal(IPrePostVisitor _vis)/middle depthfirst traversal /通过_vis使用不同的访问者来进行前序、后序、中序遍历 if(!IsEmpty() _vis.PreVisit(this.Key); if( this.Degree=1 ) if( this.Degree=2) for(uint i=0;i(this.Degree-1);i+)/ thisi.DepthFirstTraversal(_vis);/recursive call /_vis.Visit(this.Key); thisthis.Degree-1.DepthFirstTraversal(_vis); _vis.PostVisit(this.Key); public virtual void BreadthFirstTraversal(IVisitor _vis)/breadth first traversal Queue tmpQueue=new Queue();/used to help BreadthFirstTraversal /this.keyqueue=new Queue();/store keys if(!this.IsEmpty() tmpQueue.Enqueue(this);/enqueue the root node at first while(tmpQueue.Count!=0)/until the number of the queue is zero Tree headTree=(Tree)tmpQueue.Dequeue(); /this.keyqueue.Enqueue(headTree.Key); _vis.Visit(headTree.Key); for(uint i=0;iheadTree.Degree;i+) Tree childTree=headTreei; if(!childTree.IsEmpty() tmpQueue.Enqueue(childTree); /-end- /内部成员类 用于提供不同遍历类型的访问者 public class PreOrder:IPrePostVisitor private IVisitor visitor; public PreOrder(IVisitor _vis)visitor=_vis; #region IPrePostVisitor 成员 public void PreVisit(object _obj) / TODO: 添加 PreOrder.PreVisit 实现 this.visitor.Visit(_obj); public void Visit(object _obj) / TODO: 添加 PreOrder.Visit 实现 public void PostVisit(object _obj) / TODO: 添加 PreOrder.PostVisitor 实现 #endregion 数据结构与算法(C#实现)系列-树(二) Heavenkiller(原创) public class InOrder:IPrePostVisitor private IVisitor visitor; public InOrder(IVisitor _vis)visitor=_vis; #region IPrePostVisitor 成员 pu