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

数据结构与算法（C#实现）系列——前言Heavenkiller（原创）搞计算机的人都应该很清楚，语言只是一种工具，算法才是灵魂。现在的开发语言有很多，如C++,VB,Perl,java,c«,还有如脚本语言js,vbs等，在如此多的选择面前，很多人不知道该选择哪一种好。其实不管哪一种语言，既然他存在，就一定有他的价值，有它的特定用途，而这往往是其它语言所无法比拟的。譬如C++就适合于系统底层的编程，而java一般就用于对稳定性，兼容性要求较高的场合，正所谓各有所长。像我一般用C++编写网络基层和与操作系统相关的程序，用C#写ASP.NET等程序，必要的时候再辅以Rose,RationalXDE等建模工具。但无论选择哪一种语言，算法才是根本，掌握了算法，就掌握了所有语言的根本，以不变应万变。微软的C#是一种全新的语言，利用它能快捷、高效地布署程序。现在关于C#的资料也已经有很多了，各个方面的资料都能找得到，但用C#做数据结构的似乎还没有什么，在CSDN上我只找到了三四篇，而且仅仅是讲了一下链表之类简单的数据结构。于是我利用空闲的时间用C#写了一些数据结构与算法的实现，希望对大家学习数据结构能够有所帮助。另外，由于时间仓促，难免出现一些纸漏，希望大家不吝赐教给予指正，我的email是heavenkiller2002@.欢迎大家和我一起交流学习。本系列包括树，N叉树，广义树，二叉树，BST二叉查找树，AVL平衡树，堆，二叉堆，以及图。还有一些如哈希表，散列，左翼树，二项树，Haffman编码树等因时间关系，暂时未能奉上，以后有时间再补上吧。首先给大家展示一幅用RationalXDEfor.NET生成的类模型图，让大家对所有的类有一个大概的了解。数据结构与算法（C#实现）系列--演示篇（-）Heavenkiller（原创）这一篇主要是针对以后各篇的数据类型进行一个实质性的演示。因此希望大家具体看了各种数据结构的分析之后再看这篇。主要包括如下几个方面的演示：堆栈。演示了一个利用堆栈作的RPN计算器排序表。演示了一个利用排序表做的多项式表达式的加法运算广义树。演示了深度遍历和广度遍历N叉树。演示了N叉树的生成插入删除等基本操作表达式树。演示了一个用二叉树和堆栈做的可以将一个后缀表达式翻译为日常中熟悉的中缀表达式的例子AVL树。演示了基本操作usingSystem;usingSystem.Collections;namespaceDataStructureIII<summary>IIIClassi的摘要说明。III</summary>classShow(III<summary>III应用程序的主入口点。III</summary>[STAThread]staticvoidMain(string[]args){////TODO:在此处添加代码以启动应用程序//while(true)(Console.WriteLine(*pleasechooseatheNo.ofaitemyouwanttoperform;Console.WriteLine(*l.Stack RPNCalCulator^);Console.WriteLine(zz2.SortedList theadditionofpolynomialrealizedbysortedlist");Console.WriteLineC/S.GeneralTree depthtravesalandbreathtraval*);Console.WriteLine(*4.NaryTree*);Console.WriteLine("5・ExpressionTreezz);Console.WriteLineC"6.AVLTree");Console.WriteLine(*7.BinaryHeap");Console.WriteLineC'exit-Exitthisprogramme");//TestO;switch(Console.ReadLine())(case*1*://ShowStackShowStackRPNCalCulator();break;case*2*://SortedListShowSortedList_Polynomial();break;case'3":ShowGeneralTree_trave1();break;case'4":ShowNaryTreeO;〃演示一个三叉树的Attach和Detachbreak;case5:ShowExpressionTree();break;caseb：ShowAVLTreeO;break;case(:ShowBinarylleap();break;case"exit”:return;default:break;))}publicstaticvoidShowBinaryHeap(){〃构造•个二叉堆，包含2,4,6,8,10,12Binarylleapblleap=newBinaryHeap(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.DequeueMinO.ToString());iipublicstaticvoidShowAVLTreeO(AVLTreetestAVL=newAVLTree(5);testAVL.Insert(1);testAVL.Insert(3);testAVL.Insert(7);testAVL.Insert(8);testAVL.Insert(9);testAVL.Insert(10);testAVL.Insert(11);PrintVisitorvis=newPrintvisitor();Tree.InOrderinVis=newDataStructure.Tree.InOrder(vis);testAVL.DepthFirstTraversal(inVis);publicstaticvoidShowExpressionTree()(ExpressionTree.PostfixToInfix();}publicstaticvoidShowNaryTree0{〃构造一个三叉树，具体见图1-2NaryTreeA=newNaryTree(3,*A*);NaryTreeB=newNaryTree(3,"B");NaryTreeC=newNaryTree(3,"C");NaryTreeD=newNaryTree(3,*D*);NaryTreeE=newNaryTree(3,"E");B.AttachSubtreed,D);B.AttachSubtree(2,E);A.AttachSubtreed,B);A.AttachSubtree(3,C);// Console.WriteLine("广度遍历")；PrintVisitorvis=newPrintVisitor();A.BreadthFirstTraversal(vis);〃广度遍历Console.WriteLine("前序遍历")；Tree.PreOrderpreVisit=newDataStructure.Tree.PreOrder(vis);A.DepthFirstTraversal(preVisit);Console.WriteLine("后序遍历”)；Tree.PostOrderpostVisit=newDataStructure.Tree.PostOrder(vis);A.DepthFirstTraversal(postVisit);Console.WriteLine("中序遍历”)；Tree.InOrderinVisit=newDataStructure.Tree.InOrder(vis);A.DepthFirstTraversal(inVisit);数据结构与算法(C#实现)系列…演示篇(二)Heavenkiller(原创)publicstaticvoidShowGeneralTree_travel()(lEnumeratortmpIEnum;Tree.TraversalTypetravelType=O;// 提示 Console.WriteLine("pleasechooseatheNo.ofaitemyouwanttotravel:H);Console.WriteLine(nl.BreadthFirst--…广度遍历)Console.WriteLine("2.PreDepthFirst 前序遍历");Console.WriteLine（u3.InDepthFirst--中序遍历"）;Console.WriteLine（u4.PostDepthFirst--一后序遍历”）；switch（Console.ReadLine（））{case,,r,://ShowStacktravelType=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;）〃构造一棵广义树generaltreeGeneralTreeA=newGeneralTreeC^A'1）;GeneralTreeB=newGeneralTreeC^");GeneralTreeC=newGeneralTree("C");GeneralTreeD=newGeneralTreeC'D");GeneralTreeE=newGeneralTree(,,EH);GeneralTreeF=newGeneralTree(HFM);A.Attacksubtree(B);A.AttackSubtree(C);B.AttackSubtree(D);B.AttackSubtree(E);A.Attacksubtree(F);//showtheoperationConsole.WriteLineC'A.AttackSubtreeCB)");Console.WriteLine(',A.AttackSubtree(C)M);Console.WriteLine(nB.Attacksubtree(D)");Console.WriteLine(HB.AttackSubtree(E)n);Console.WriteLine(,,A.AttackSubtree(F)n);小 A.SelTraversalType(travelType);〃设置遍历类型tmpIEnum=A.GetEnumerator();//Console.WriteLine("begintodepthfisttravel:H);while(tmplEnum.MoveNext())Console.WriteLine(tmpIEnum.Current.ToStringO);)publicstaticvoidShowStack_RPNCalCulator()(//readaexpressionstringandpusheverycharacterintothestackinqueue.Console.WriteLine(nthisisperformanceforstack,youcaninputastringlikethis'123*+\thenthissubprogrammecancomputeitandgettheresult7',thisisRPNcalculator.n);Console.WriteLine(''pleaseinputaexpressionstring:M);stringstrExpression=Console.ReadLine();char[]tmpChars=strExpression.ToCharArray(0,strExpression.Length);StackstackRPN=newStack();intnumA,numB;fbreach(chartmpintmpChars){switch(tmp)(casenumA=(int)stackRPN.Pop();numB=(int)stackRPN.Pop();stackRPN.Push(numA*numB);break;casenumA=(int)stackRPN.Pop();numB=(int)stackRPN.Pop();stackRPN.Push(numA+numB);break;default:stackRPN.Push(Int32.Parse(tmp.ToString()));break;})Console.WriteLine("theresultis:{0}M,stackRPN.Pop().ToString());)数据结构与算法(C#实现)系列…演示篇(三)HeavenkiHer(原创)publicstaticvoidShowSortedList_Polynomial(){//100+10*x+x八2+l+10*x+l00xA2SortedListtmpListA=newSortedList();SortedListtmpListB=newSortedList();SortedListtmpListC=newSortedList();//usedtostoretheresultSortedListtmpKeyList=newSortedList();//usedtostoreallkeysoftwopolynomials//initpolynomialAandshowittmpListA.Add(0,100);tmpListA.Add(1,10);tmpListA.Add(2,1);ShowSortedList_ShowPolynomial(,'tmpListA,,,tmpListA.GetEnumerator());//initpolynomialBandshowittmpListB.Add(OJ);tmpListB.Add(l,10);tmpListB.Add(2,100);ShowSortedList_ShowPolynomial(,'tmpListB,,,tmpListB.GetEnumerator());//initthekeylistwhichcontainsallkeysofAandBbuteveryoneonceIDictionaryEnumeratortmpIDic=tmpListA.GetEnumerator();while(tmpIDic.MoveNext()!=false){if(!tmpKeyList.ContainsKey(tmpIDic.Key))(tmpKeyList.Add(tmpIDic.Key,null);)ItmpIDic=tmpListB.GetEnumerator();while(tmpIDic.MoveNext()!=false)(if(!tmpKeyList.ContainsKey(tmpIDic.Key))(tmpKeyList.Add(tmpIDic.Key,null);}}//AddAandBandshowtheresulttmplDic=tmpKeyList.GetEnumerator();while(tmpIDic.MoveNext()!=false)objectobjA=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(,,theadditionresultofAandBmpListC.GetEnumerator());)publicstaticvoidShowSortedList_ShowPolynomiaI(stringtipJDictionaryEnumeratoriDic)(stringstrExpress=null;iDic.Reset();whi!e(iDic.MoveNext()!=false){strExpress+=iDic.Value.ToString()+"*XA"+iDic.Key.ToString()+"+”；)Console.WriteLineCtip+^^'+strExpress);数据结构与算法（C#实现）系列一树（一）Heavenkiller（原创）首先我们给树下一个定义：树是一个有限的、非空的结点集，T={r}orTlorT2or...orTn它具有下列性质：.集合指定的结点r叫做树的根结点.其余的结点可以划分成n个子集，T1,T2,…Tn（n>=0）,其中每一个子集都是一棵树。树的其它定义如度，叶子，高等就请大家查阅别的资料吧，到处都有的。树的主要性质一个就是遍历，分为深度遍历和广度遍历在这里分别实现为DepthFirstTravesal。和WidthFirstTravesaR）其中深度遍历又分为前序遍历、中序遍历、和后序遍历这是是采用适配器技术实现的。usingSystem;usingSystem.Collections;namespaceDataStructure（///<summary>///Tree的摘要说明。///whentraverse,traversaltypecan'tbechanged,orthrowaexception///支持枚举、比较、深度复制III</summary>publicabstractclassTree:IEnumerableJComparablepublicTree()////TODO:在此处添加构造函数逻辑//}protectedQueuekeyqueue=newQueue。;〃仅仅Hl于枚举时存放数据，不参与Equals实现中的比较protectedTraversalTypetraversaltype=TraversalType.Breadth;//chooseatraversaltype,andDepthFirstisdefault//protecteduintdegree=O;//degreeofthetree,inititas0//protecteduintheight=O;//heightofthetree,inititas0〃枚举不同的遍历类型publicenumTraversalType{Breadth=1,/〃度遍历PreDepth=2〃前序遍历InDepth=3,〃中序遍历PostDeplh=4〃后序遍历}；//publicvirtualabstractobjectKey{}publicabstractTreethis[uint_index]{get;set;}//ifIonlyuseget,canIchangeitlater?publicabstractobjectKey{get;}publicabstractuintDegree{get;}//publicabstractuintHeight{get;}publicvoidSetTraversalType(TraversalType_type){traversaltype=_type;}//setatraversalatype,ifit*snotsetmanually,DepthFirstwillbechosenindefaultpublicabstractboolIsEmptyO;//propertytakestheplaceofIsEmptyOpublicabstractboolIsLeaf();//OnlyVisit,needn'tqueuepublicvirtualvoidDepthFirstTraversal(IPrePostVisitor_vis)//middledepthfirsttraversal(〃通过_vis使用不同的访问者来进行前序、后序、中序遍历if(!IsEmpty())|_vis.PreVisit(this.Key);if(this.Degree>=l)(if(this.Degree>=2)(for(uinti=O;i<(this.Degree-1);i++)//{this[i].DepthFirstTraversal(_vis);//recursivecall//_vis.Visit(this.Key);1)this[this.Degree-l].DepthFirstTraversal(_vis);)_vis.PostVisit(this.Key);})publicvirtualvoidBreadthFirstTraversal(IVisitor_vis)//breadthfirsttraversalQueuetmpQueue=newQueue()^/usedtohelpBreadthFirstTraversal//this.keyqueue=newQueue();//storekeysif(!this.IsEmpty())tmpQueue.Enqueue(this);//enqueuetherootnodeatfirstwhile(tmpQueue.Count!=0)//untilthenumberofthequeueiszero(TreeheadTree=(Tree)tmpQueue.Dequeue();//this.keyqueue.Enqueue(headTree.Key);_vis.Visit(headTree.Key);for(uinti=O;i<headTree.Degree;i++)(TreechildTree=headTree|i];if(!childTree.IsEmpty())tmpQueue.Enqueue(childTree);))J// end 〃内部成员类用于提供不同遍历类型的访问者publicclassPreOrder:IPrePostVisitor(privateIVisitorvisitor;publicPreOrder(IVisitor_vis){visitor=_vis;}#regionIPrePostVisitor成员//TODO:添加PreOrder.PreVisit实现this,visitor.Visit(_obj);}publicvoidVisit(object_obj)(//TODO:添加PreOrder.Visit实现}publicvoidPostVisit(object_obj)(//TODO:添加PreOrder.PostVisitor实现)#endregion}数据结构与算法(C#实现)系列一树(二)

Heavenkiller(原创)publicclass1nOrder:lPrePostVisitor(privateIVisitorvisitor;publicInOrder(lVisitor_vis){visitor=_vis;}#regionIPrePostVisitor成员publicvoidPreVisit(object_obj)//TODO:添加InOrder.PreVisit实现publicvoidVisit(object_obj){//TODO:添加InOrder.Visit实现this,visitor.Visit(_obj);}publicvoidPostVisit(object_obj)(//TODO:添加InOrder.PostVisitor实现}#endregion}publicclassPostOrder:IPrePostVisitor(privateIVisitorvisitor;publicPostOrder(IVisitor_vis){visitor=_vis;}#regionIPrePostVisitor成员publicvoidPreVisit(object_obj){//TODO:添加PostOrder.PreVisit实现)publicvoidVisit(object_obj)//TODO:添加PostOrder.Visit实现publicvoidPostVisit(object_obj)Z/TODO:添加PostOrder.PostVisitor实现this,visitor.Visit(_obj);)#endregion)protectedclassEnumVisitor:!Visitor(QueuethisQueue;publicEnumVisitor(Queue_que){this.thisQueue=_que;)#regionIVisitor成员publicvoidVisit(object_obj){//TODO:添加EnumVisitor.Visit实现this.thisQueue.Enqueue(_obj);}#endregionI#region1Enumerable成员

IITODO:添加Tree.GetEnumerator实现EnumVisitorvis=newEnumVisitor(this.keyqueue);switch(this.traversaltype){caseTraversalType.Breadth:BreadthFirstTraversal(vis);break;caseTraversalType.PreDepth:PreOrderpreVis=newPreOrder(vis);DepthFirstTraversal(preVis);break;caseTraversalType.InDepth:InOrderinVis=newInOrder(vis);DepthFirstTraversal(inVis);break;caseTraversalType.PostDepth:PostOrderpostVis=newPostOrder(vis);DepthFirstTraversal(postVis);break;default:-type)M);Console.WriteLine(nWARNING:pleasesetatraveltype-type)M);//thrownewException(uWARNING:pleasesetatraveltypefirst!M);//ifnotsetatype,aexceptionwillhappenbreak;returnthis.keyqueue.GetEnumerator();)#endregion数据结构与算法(C#实现)系列一树(三)

Heavenkiller(原仓ij)//overwriteObject.Equals()-referencetyperealizationpublicoverrideboolEquals(object_obj){if(_obj==null)returnfalse;〃因为this不可能为nullif(!(this.GetType()=_obj.GetType()))returnfalse;〃类型不相等也不相等TreetmpObj=(Tree)_obj;〃比较引用成员if(!Object.Equals(this.Key,tmpObj.Key))returnfalse;〃比较值类型成员if(!this.Degree.Equals(tmpObj.Degree))returnfalse;Z/if(!this.Height.Equals(tmpObj.Height))//returnfalse;returntrue;〃在此重载==,!=后，在以后继承的类中不必实现了publicstaticbooloperator==(Tree_treeA,Tree_treeB)(returnObject.Equals(_treeA,_treeB);)publicstaticbooloperator!=(Tree_treeA,Tree_treeB)return!(_treeA==_treeB);)#regionIComparable成员publicvirtualintCompareTo(objectobj)(//TODO:添力口Tree.CompareTo实现return0;)#endregion数据结构与算法（C#实现）系列…广义树（一）Heavenkiller（原创）广义树和基本树的主要区别就是有任意的度usingSystem;usingSystem.Collections;namespaceDataSlructure(///<summary>IIIGeneralTree的摘要说明。///generaltreeisatreewhichhasaarbitrarydegreeandnoemptytree///useArrayListtoreplaceListAsLinkedList///</summary>publicclassGeneralTree:Tree(protectedobjectkey=null;protecteduintdegree=0;//protecteduintheight=0;protectedArrayListtreeList=newArrayList();publicGeneralTree(object_objKey)(////TODO:在此处添加构造函数逻辑//key=_objKey;degree=0;//height=0;ArrayListtreeList=newArrayList();)this.treeList.Add(_gTree);++degree;}publicvirtualGeneralTreeDetachSubtree(GeneralTree_gTree)(this.treeList.Remove(_gTree);degree—;return_gTree;//?????howtoremovereferenceorobject????)publicoverrideTreethis[uint_index](get{if(_index>=this.degree)thrownewException(Hmy:outofindexM);return(Tree)treeList[(int)_index];)set{treeList[(int)_index]=value;))数据结构与算法（C#实现）系列…广义树（二）HeavenkiHer(原创)publicoverrideobjectKey{get{returnthis.key;}}publicoverrideuintDegree{get{returnthis.degree;}}//publicoverrideuintHeight{get{returnthis.height;}}publicoverrideboolIsEmpty()//propertytakestheplaceofIsEmptyO(returnfalse;//generaltreewon'tbeemptyforever)publicoverrideboolIsLeaf(){returnthis.degree==0;//ifthistree'sdegreeiszero,itmeansthetreehasnosubtrees,soitisleafcertainly)//overwriteObject.Equals()--referencetyperealizationpublicoverrideboolEquals(object_obj){if(!base.Equals(_obj))returnfalse;〃基类比较不相等，则不相等〃基类中的一些条目在此可免去〃在基类中已判定其为GeneralTree类型，故转型不会失败GeneralTreetmpTree=(GeneralTree)_obj;〃比较引用成员if(!Object.Equals(this.treeList,tmpTree.treeList))returnfalse;〃比较值类型成员returntme;数据结构与算法(C#实现)系列…N叉树(一)HeavenkiHer(原创)N叉树的每一节点度数都相同，为NusingSystem;usingSystem.Collections;namespaceDataStructure(///<summary>///NaryTree的摘要说明。--N叉树///</summary>publicclassNaryTree:Tree(//membervariablesprotectedobjectkey;protecteduintdegree;protectedArrayListtreeList=newArrayList();//protecteduintheight=0;〃暂时默认为0//createanemptytreewhoseattributeofdegreeis..degree////TODO:在此处添加构造函数逻辑//this.key=null;this.degree=_degree;this.treeList=null;)〃构造一棵叶子结点的N叉树publicNaryTree(uint_degree,object_key)(this.key=_key;this.degree=_degree;this.treeList=newArrayList();this.treeList.Capacity=(int)_degree;for(inti=0;i<this.treeList.Capacity;i+4-)(this,treeList.Add(this.GetEmptylnstanceQdegree));}}// protectedvirtualobjectGetEmptyInstance(uint_degree){returnnewNaryTree(_degree);}// //judgewhetherthetreeisanemptytreepublicoverrideboolIsEmptyO{returnthis.key==null;}〃判定是否是叶子结点。如果即不是空树且每一棵子树均为空树，则为叶子结点publicoverrideboollsLeaf()(if(IsEmpty())returnfalse;fbr(uinti=O;i<this.degree;i++){if(!(this[i].IsEmpty()))returnfalse;)returntrue;)// InheritedAttributes publicoverrideobjectKey(get{returnthis.key;))〃索引器publicoverrideTreethis[uint_index]getif(_index>=this.degree)thrownewException(HMy:outofindex!”);〃如果出界，则抛出异常if(this.IsEmptyO)returnnull;〃如果是空树，则索引器返回一个nullreturn(Tree)this.treeList[(int)_index];}set{this.treeList[(int)_index]=value;))数据结构与算法(C#实现)系列一N叉树(二)

Heavenkiller(原创)publicoverrideuintDegree(get(returnthis.degree;})//-- -……-……- - 〃只用于空树结点publicvirtualvoidAttachKey(object_obj)(if(!IsEmpty())thrownewException(HMy:thisnodemustbeaemptytreenode!**);this.key=_obj;this.treeList=newArrayList。，产生一个degree长的数组,并将其初始化为空树this.treeList.Capacity=(int)this.degree;fbr(inti=O;i<this.degree;i++){treeList.Add(newNaryTree(this.degree));}foreach(objecttmpObjinthis.treeList)(tmpObj=newNaryTree(this.degree);)*/}〃只用于叶子结点，将叶子结点变为一个空结点，并返回叶子结点关键字的引用publicvirtualobjectDetachKey()(if(!IsLeaf())thrownewException(°My:thisnodemustbealeafnode!**);objectresult=this.key;//storethisleafnodetemporarythis.key=null;this.treeList=null;returnresult;)〃将子树连接到指定树的第num个结点上，前提是这个结点必须是空结点，并且度数相同，否则抛出异常publicvirtualvoidAttachSubtree(uintnum,NaryTree_naryTree)if(this.IsEmpty())thrownewException('rMy:itcan'tbeaemptytree!**);if(!(this|num-l].IsEmpty())Ithis.degree!=_naryTree.degree)thrownewException(nMy:this[i-i]mustbeemptyandtheyshouldhavethesamedegree!M);this[num-l]=_naryTree;)〃仅为非空树定义，从给定树中删去它的第i棵子树并连上一个空树，度数相同，并且返回删除的子树引用publicvirtualNaryTreeDetachSubtree(uintnum)(if(IsEmptyO)thrownewException(nMy:itcan'tbeempty!");NaryTreetmpTree=this;((NaryTree)this[num-1]).key=null;((NaryTree)this(num-l]).treeList=null;returnthis;)//.数据结构与算法(C#实现)系列…AVLTree(-)usingSystem;usingSystem.Collections;namespaceDataStructure{///<summary>///AVCTree的摘要说明。••一平衡二叉查找树III</summary>publicclassAVLTree:BST(protectedintheight;〃空树的高定义为〃构造一棵空的二叉查找树publicAVETree():base()(////TODO:在此处添加构造函数逻辑Hheight=1;}publicAVLTree(object_obj):base(_obj)height=O;}// protectedoverrideobjectGetEmptylnstance(uint_degree){returnnewAVLTree();}// protectedintBalanceFactor()(if(this.IsEmptyO)return0;return((AVLTree)this.Left).height-((AVLTree)this.Right).height;)〃调整高度protectedvoidAdjustHeight(){ this.height=Math.Max(((>WLTree)this.Left).height,((AVETree)this.Right).height)+l;}〃平衡时的四种旋转方式protectedvoidLLRotation()(if(this.IsEmptyO)thrownewException(MMy:invalidoperation!H);AVLTreeavlB=newAVLTree(this.key);avlB.AttachSubtree(l,(AVLTree)this[O][l]);avlB.AttachSubtree(2,(AVI_Tree)this|1]);this.key=this|0|.Key;this[O]=this[O][O];this|l]=avlB;〃调整两个节点的高度((AVLTree)this.Right).AdjustHeight();this.AdjustHeight();)protectedvoidLRRotation()(if(this.IsEmptyO)thrownewException("My:invalidoperation!");((AVLTree)this.Left).RRRotation();this.LLRotation();)protectedvoidRRRotation()(if(this.IsEmptyO)thrownewException('rMy:invalidoperation!'*);AVLTreeavlB=newAVLTree(this.key);avlB.AttachSubtree(l,(AVLTree)this[O]);avlB.AttachSubtree(2,(AVLTree)this[l][0]);Z/avlA.AttachSubtree(1,avlB);//this=avlA;this.key=this[1].Key;this[l]=this[l][l|;〃调整两个节点的高度((AVLTree)this.Left).AdjustHeight();this.AdjustHeight();)protectedvoidRLRotation()if(this.lsEmptyO)thrownewException(uMy:invalidoperation!M);((AVLTree)this.Right).LLRotation();this.RRRotation();)数据结构与算法(C#实现)系列一AVLTree(二)// override publicoverridevoidAttachKey(object_obj)(if(!IsEmpty())thrownewException(HMy:thisnodemustbeaemptytreenode!**);this.key=_obj;〃产生一个degree长的数组,并将其初始化为空树this.treeList=newArrayList();this.treeList.Capacity=(int)this.degree;for(inti=O;i<this.degree;i++)treeList.Add(newAVLTreeO);}//this.height=O;)〃在改动树的结构后平衡树publicoverridevoidBalance()(this.AdjustHeight();〃大于1则说明不平衡if(Math.Abs(this.BalanceFactor())>l){if(this.BalanceFactor()>0)(if(((AVLTree)this.Left).BalanceFactor()>0)this.LLRotation();elsethis.LRRotation();)else(if(((AVLTree)this.Right).BalanceFactor()<0)this.RRRotation();else)I)publicintHeight{get{returnthis.height;}}数据结构与算法(C#实现)系列一二叉树usingSystem;usingSystem.Collections;namespaceDataStructure(///<summary>IIIBinaryTree的摘要说明。///</summary>publicclassBinaryTree:NaryTree(〃构造二叉空树publicBinaryTree():base(2)(////TODO:在此处添加构造函数逻辑//)publicBinaryTree(object_obj):base(2,_obj)()//- protectedoverrideobjectGetEmptyInstance(uint_degree){returnnewBinaryTreeQdegree);)//- 〃重写深度遍历publicoverridevoidDepthFirstTraversal(IPrePostVisitor_vis)(if(!IsEmpty())(_vis.PreVisit(this.Key);this[O].DepthFirstTraversal(_vis);_vis.Visit(this.Key);this[l].DepthFirstTraversal(_vis);_vis.PostVisit(this.Key);})〃二叉树大小的比较〃先比较关健字，如果相等，再比较左子树，如果再相等，则比较右子树--如此递归#regionIComparable成员publicoverrideintCompareTo(objectobj)//TODO:添加BinaryTree.CompareTo实现〃因为Comare。中已经进行了类型断定，故不会出现转型错误BinaryTreetmpTree=(BinaryTree)obj;if(this.IsEmptyO)returntmpTree.IsEmpty()?O:-l;if(tmpTree.IsEmptyO)return1;intresult=Comparer.Default.Compare(this,tmpTree);if(result==O)result=this[0].CompareTo(tmpTree[0]);if(result==O)result=this[l].CompareTo(tmpTree[1]);returnresult;)#endregion数据结构与算法（C#实现）系列一二叉堆（数组实现）usingSystem;usingSystem.Collections;namespaceDataStructureIll<summary>///BinaryHeap的摘要说明。 二叉堆(基于数组的实现)III</summary>publicclassBinaryHeap:IPriorityQueue(protectedArrayListarray;〃建立一个最多容纳」ength个对象的空二叉堆publicBinaryHeap(uint_length)(////TODO:在此处添加构造函数逻辑//array=newArrayList((int)_length);array.Capacity=(int)_length;)〃堆中对象个数publicvirtualintCount{get{returnthis.array.Count;}}〃将成员数组变成用1为基数表达的形式publicvirtualobjectItem(int_i)(if(_i>=this.array.Capacity)thrownewException(MMy:outofindex");〃不能出界returnthis.array[_i-l];}#regionIPriorityQueue成员〃先将空洞放在数组的下一个位置匕也就是i（注：基数是1）,然后和「/2］位置上的数比较，如果小于则将空洞上移到[i/2]位置，而原先[i/2]位置上的对象则移到国上，否则就将空洞变为一obj---如此递归publicvoidEnqueue(Object_obj)!//TODO:添加BinaryHeap.Enqueue实现if(this.array.Count==this.array.Capacity)thrownewException(nMy:priorityqueueisfull");〃如果优先队列已满，则抛出异常this.array.Add(newobject。)；inti=this.array.Count;while(i>l&&Comparer.Default.Compare(this.array|i/2-l],_obj)>0){//this.Item(i)=this.Item(i/2);this.array[i-1|=this.array[i/2-1];i/=2;Ithis.array[i-l]=_obj;}publicobjectFindMin()(//TODO:添加BinaryHeap.FindMin实现if(this.array.Count==0)thrownewException(HMy:priorityqueueisemply");〃如果队歹!J是空的，则抛出异常returnthis.array[O];publicobjectDequeueMin()IITODO:添加BinaryHeap.DequeueMin实现objecttmpObj=this.FindMin();inti=l;while((2*i+l)<=this.array.Count){if(Comparer.Default.Compare(this.airay[2*i-1],this.array[2*i])<=0)(this.array[i-1]=this.array[2*i-1];this.array[2*i-l]=tmpObj;i=2*i;)else(this.array[i-l]=this.array[2*i];this.array[2*i]=tmpObj;i=2*i+l;))objectdelObj=this.array[i-1];〃暂时储存要删去的元素if(i!=this.array.Count)〃如果搜索到的对象就是数组的最后一个对象，则什么都不要做{this.array[i・l]=this.array[this.array.Count・l];〃添补空洞}this.array.RemoveAt(this.airay.Count・l);〃将最后一个对象删除returndelObj;#endregionC#算法(一)选择排序嗨!朋友们,C#将是未来网络开发的首选语言。本人用了C#开发出选择排序算法。希望能为C#语言的学习者带来一些益处。不要忘了，学语言要花大力气学数据结构和算法。usingSystem;publicclassSelectionSorter(//publicenumcomp{COMP_LESS,COMP_EQUAL,COMP_GRTR);privateintmin;//privateintm=0;publicvoidSort(int[]list)(for(inti=O;i<list.Length-l;-H-i){min=i;for(intj=i+l;j<list.Length;++j)(intt=list|min|;list[min]=list[i];list[i]=t;//Console.WriteLineC^OJMistfil);))}publicclassMainClass(publicstaticvoidMain(){int[]iArrary=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47);SelectionSorterss=newSelectionSorter();ss.Sort(iArrary);for(intm=0;m<=13;m++)Console.WriteLine(,,{0},',iArrary|m]);))已经成功的编译。C#算法(二)插入排序朋友们，我最近加紧写C#的一些算法。选择排序已经推出的。现推出插入算法。对想提高C#语言编程能力的朋友，我们可以互相探讨一下。如：下面的程序，并没有实现多态，来，帮它实现一下。usingSystem;publicclassInsertionSorterpublicvoidSort(int[]list){for(inti=1;i<list.Length;++i)(intt=list|i];intj=i;while((j>O)&&(list[j-l]>t)){list[j]=list[j-l];T}list[j]=t;I))publicclassMainClass{publicstaticvoidMain()(int[]iArrary=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47);InsertionSorterii=newInsertionSorter();ii.Sort(iArrary);for(intm=0;m<=13;m++)Console.WriteLine("{0}",iArrary[m]);已经编译运行通过.这太简单了，我不做详细介绍了.C#算法(三)希尔排序朋友们，我最近加紧写C#的一些算法。选择排序,插入算法是我已经推出的。现推出希尔排序.今后，如有时间我将依次推出其它的算法编写。希尔排序是将组分段，进行插入排序.对想提高C#语言编程能力的朋友，我们可以互相探讨一下。如：下面的程序，并没有实现多态，来，帮它实现一下。usingSystem;publicclassShellSorter(publicvoidSort(int[]list)|intinc;for(inc=l;inc<=list.Length/9;inc=3*inc+l);for(;inc>0;inc/=3){for(inti=inc+1;i<=list.Length;i+=inc){intt=list|i-l];intj=i;while((j>inc)&&(list[j-inc-1]>t))list|j-1]=list(j-inc-1];j-=inc;)list[j-l]=t;)}}}publicclassMainClass(publicstaticvoidMain()(int|)iArrary=newint|]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}；ShellSortersh=newShel!Sorter();sh.Sort(iArrary);for(intm=0;m<=13;m++)Console.WriteLine(',{0},\iArrary[m]);))已经编译通过.C#算法(四)快速排序前面我已经推出了三种排序的算法，比较简单。今天我又写了快速排序的算法。希望多多指教。具体的思想，我不做答了。前人的经验。usingSystem;publicclassQuickSorter(privatevoidSwap(refintl,refintr)|ints;s=l;l=r;r=s;)publicvoidSort(int[]list,intlow,inthigh){intpivot;intl,r;intmid;if(high<=iow)return;elseif(high==low+l)(if(list[low]>list[high])Swap(reflist[low],reflist[high]);return;mid=(low+high)»l;pivot=list[mid];Swap(reflist[low],reflist[mid]);|=low+l;r=high;do(while(l<=r&&list(l]<pivot)1++;while(list[r]>=pivot)r-；if(l<r)Swap(reflist[l],reflist[r]);}while(l<r);list[low]=list[r];list[r]=pivot;if(low+l<r)Sort(list,low,r-1);if(r+l<high)Sort(list,r+l,high);}}publicclassMainClass(publicstaticvoidMain()int[]iArrary=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47);QuickSorterq=newQuickSorter();q.Sort(iArrary,0J3);for(intm=0;m<=13;m++)Console.WriteLine(u{0}M,iArrary[m]);))}已经编译通过，运行环境：windowsxpVC#.net7.0C#排序算法大全冒泡排序本人用了C#开发出冒泡排序算法。希望能为C#语言的学习者带来一些益处。不要忘了，学语言要花大力气学数据结构和算法。usingSystem；namespaceBubbleSorter{publicclassBubbleSorter(publicvoidSort(int[]list)(inti,j,temp；booldone=false；j=l:while((j<list.Length)&&(!done))done=true；for(i=0；i<list.Length-j；i++)(if(Ust[i]>list[i+1])(done=false；temp=list[i]；list[i]=list[i+l]；list[i+l]=temp；))j++；publicclassMainClass{publicstaticvoidMain(){int[]iArrary=newint[]{l,5,13,6,10,55,99,2,87,12,34,75,33,47)；BubbleSortersh=newBubbleSorter0；sh.Sort(iArrary)；for(intm=0；m<iArrary.Length；m++)Console.WriteLine0；选择排序本人用了C#开发出选择排序算法。希望能为C#语言的学习者带来一些益处。不要忘了，学语言要花大力气学数据结构和算法。usingSystem；namespaceSelectionSorter{publicclassSelectionSorter(privateintmin；publicvoidSort(int[]list)(for(inti=0：i<list.Length-1；i++)(min=i；for(intj=i+l；j<list.Length；j++){if(list[j]<list[min])min=j；publicclassMainClass(publicstaticvoidMain()(int|]iArrary=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}；SelectionSorterss=newSelectionSorter()；ss.Sort(iArrary)；for(intm=0；m<iArrary.Length；m++)Console.Write(',{0}H,iArrary[m])；Console.WriteLine0；插入排序插入排序算法。对想提高C#语言编程能力的朋友，我们可以互相探讨一下。如：下面的程序，并没有实现多态，来,帮它实现一下。usingSystem：namespaceInsertionSorter(publicclassInsertionSorter(publicvoidSort(int[]list)(for(inti=l；i<list.Length；i++){intt=list[i]；intj=i；while((j>0)&&(list[j-l]>t))(-j:)list[j]=t；publicclassMainClassint[]iArrary=newint[]{1,13,3,6,10,55,98,2,87,12,34,75,33,4