数据结构C#实现.docx
- 文档编号:13039060
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:16
- 大小:17.93KB
数据结构C#实现.docx
《数据结构C#实现.docx》由会员分享,可在线阅读,更多相关《数据结构C#实现.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构C#实现
//选择排序
classSelectionSorter
{
privateintmin;
publicvoidSort(int[]arr)
{
for(inti=0;i { min=i; for(intj=i+1;j { if(arr[j] min=j; } intt=arr[min]; arr[min]=arr[i]; arr[i]=t; } } staticvoidMain(string[]args) { int[]array=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; SelectionSorters=newSelectionSorter(); s.Sort(array); foreach(intminarray) Console.WriteLine("{0}",m); } } //冒泡排序 classEbullitionSorter { publicvoidSort(int[]arr) { inti,j,temp; booldone=false; j=1; while((j done))//判断长度 { done=true; for(i=0;i { if(arr[i]>arr[i+1]) { done=false; temp=arr[i]; arr[i]=arr[i+1];//交换数据 arr[i+1]=temp; } } j++; } } staticvoidMain(string[]args) { int[]array=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; EbullitionSortere=newEbullitionSorter(); e.Sort(array); foreach(intminarray) Console.WriteLine("{0}",m); } } //快速排序 classQuickSorter { privatevoidswap(refintl,refintr) { inttemp; temp=l; l=r; r=temp; } publicvoidSort(int[]list,intlow,inthigh) { intpivot;//存储分支点 intl,r; intmid; if(high<=low) return; elseif(high==low+1) { if(list[low]>list[high]) swap(reflist[low],reflist[high]); return; } mid=(low+high)>>1; pivot=list[mid]; swap(reflist[low],reflist[mid]); l=low+1; r=high; do { while(l<=r&&list[l] l++; while(list[r]>=pivot) r--; if(l swap(reflist[l],reflist[r]); }while(l list[low]=list[r]; list[r]=pivot; if(low+1 Sort(list,low,r-1); if(r+1 Sort(list,r+1,high); } staticvoidMain(string[]args) { int[]iArrary=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; QuickSorterq=newQuickSorter(); q.Sort(iArrary,0,13); for(intm=0;m<=13;m++) Console.WriteLine("{0}",iArrary[m]); } } //插入排序 publicclassInsertionSorter { publicvoidSort(int[]arr) { for(inti=1;i { intt=arr[i]; intj=i; while((j>0)&&(arr[j-1]>t)) { arr[j]=arr[j-1];//交换顺序 --j; } arr[j]=t; } } staticvoidMain(string[]args) { int[]array=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; InsertionSorteri=newInsertionSorter(); i.Sort(array); foreach(intminarray) Console.WriteLine("{0}",m); } } //希尔排序 publicclassShellSorter { publicvoidSort(int[]arr) { intinc; for(inc=1;inc<=arr.Length/9;inc=3*inc+1); for(;inc>0;inc/=3) { for(inti=inc+1;i<=arr.Length;i+=inc) { intt=arr[i-1]; intj=i; while((j>inc)&&(arr[j-inc-1]>t)) { arr[j-1]=arr[j-inc-1];//交换数据 j-=inc; } arr[j-1]=t; } } } staticvoidMain(string[]args) { int[]array=newint[]{1,5,3,6,10,55,9,2,87,12,34,75,33,47}; ShellSorters=newShellSorter(); s.Sort(array); foreach(intminarray) Console.WriteLine("{0}",m); } } 先我们给树下一个定义: 树是一个有限的、非空的结点集 首先我们给树下一个定义: 树是一个有限的、非空的结点集, T={r}orT1orT2or…orTn 它具有下列性质: 1.集合指定的结点r叫做树的根结点 2.其余的结点可以划分成n个子集,T1,T2,…Tn(n>=0),其中每一个子集都是一棵树。 树的其它定义如度,叶子,高等就请大家查阅别的资料吧,到处都有的。 树的主要性质一个就是遍历,分为深度遍历和广度遍历 在这里分别实现为DepthFirstTravesal()和WidthFirstTravesal() 其中深度遍历又分为前序遍历、中序遍历、和后序遍历 这是是采用适配器技术实现的。 usingSystem; usingSystem.Collections; namespaceDataStructure { /// ///Tree的摘要说明。 ///whentraverse,traversaltypecan'tbechanged,orthrowa exception ///支持枚举、比较、深度复制 /// publicabstractclassTree: IEnumerable,IComparable { publicTree() { // //TODO: 在此处添加构造函数逻辑 // } protectedQueuekeyqueue=newQueue();//仅仅用于枚举时存放数据,不参与Equals实现中的比较 protectedTraversalTypetraversaltype=TraversalType.Breadth;//chooseatraversal type,and DepthFirstisdefault //protecteduintdegree=0;//degreeofthetree,init itas0 //protecteduintheight=0;//heightofthetree,inititas0 //枚举不同的遍历类型 publicenumTraversalType { Breadth=1,//广度遍历 PreDepth=2,//前序遍历 InDepth=3,//中序遍历 PostDepth=4//后序遍历 }; //publicvirtualabstractobject Key{} publicabstractTreethis[uint_index]{get;set;}//ifIonlyuseget,canIchangeitlater? public abstractobjectKey{get;} public abstractuintDegree{get;} //public abstractuintHeight{get;} public voidSetTraversalType(TraversalType_type){traversaltype=_type;}//setatraversalatype,ifit'snotsetmanually,DepthFirstwillbechosenindefault public abstractboolIsEmpty();//propertytakestheplaceofIsEmpty() public abstractboolIsLeaf(); //OnlyVisit,needn'tqueue publicvirtualvoidDepthFirstTraversal(IPrePostVisitor_vis)//middledepthfirsttraversal { //通过_vis使用不同的访问者来进行前序、后序、中序遍历 if(! IsEmpty()) { _vis.PreVisit(this.Key); if(this.Degree>=1) { if(this.Degree>=2) { for(uinti=0;i<(this.Degree-1);i++)// { this[i].DepthFirstTraversal(_vis);//recursivecall //_vis.Visit(this.Key); } } this[this.Degree-1].DepthFirstTraversal(_vis); } _vis.PostVisit(this.Key); } } publicvirtualvoidBreadthFirstTraversal(IVisitor_vis)//breadthfirsttraversal { QueuetmpQueue=newQueue();//usedtohelpBreadthFirstTraversal //this.keyqueue=newQueue();//storekeys if(! this.IsEmpty()) tmpQueue.Enqueue(this);//enqueuetherootnodeatfirst while(tmpQueue.Count! =0)//untilthenumberofthequeueiszero { TreeheadTree=(Tree)tmpQueue.Dequeue(); //this.keyqueue.Enqueue(headTree.Key); _vis.Visit(headTree.Key); for(uinti=0;i { TreechildTree=headTree[i]; if(! childTree.IsEmpty()) tmpQueue.Enqueue(childTree); } } } //------------------------------------------------end------------------------------------ //内部成员类用于提供不同遍历类型的访问者 publicclassPreOrder: IPrePostVisitor { privateIVisitorvisitor; publicPreOrder(IVisitor_vis){visitor=_vis;} #regionIPrePostVisitor成员 publicvoidPreVisit(object_obj) { //TODO: 添加PreOrder.PreVisit实现 this.visitor.Visit(_obj); } publicvoidVisit(object_obj) { //TODO: 添加PreOrder.Visit实现 } publicvoidPostVisit(object_obj) { //TODO: 添加PreOrder.PostVisitor实现 } #endregion } 数据结构与算法(C#实现)系列---树 (二) publicclassInOrder: IPrePostVisitor { privateIVisitorvisitor; publicInOrder(IVisitor_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) { //TODO: 添加PostOrder.Pos
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C# 实现