数据结构C#实现.docx

/选择排序class SelectionSorterprivate int min;public void Sort(int arr)for (int i = 0; i arr.Length - 1; +i)min = i;for (int j = i + 1; j arr.Length; +j)if (arrj arrmin)min = j;int t = arrmin;arrmin = arri;arri = t;static void Main(string args)int array = new int 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 ;SelectionSorter s = new SelectionSorter();s.Sort(array);foreach (int m in array)Console.WriteLine(0, m);/冒泡排序class EbullitionSorterpublic void Sort(int arr)int i, j, temp;bool done = false;j = 1;while (j arr.Length) & (!done)/判断长度done = true;for (i = 0; i arri + 1)done = false;temp = arri;arri = arri + 1;/交换数据arri + 1 = temp;j+;static void Main(string args)int array = new int 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 ;EbullitionSorter e = new EbullitionSorter ();e.Sort(array);foreach (int m in array)Console.WriteLine(0, m);/快速排序class QuickSorterprivate void swap(ref int l, ref int r)int temp;temp = l;l = r;r = temp;public void Sort(int list, int low, int high)int pivot;/存储分支点int l, r;int mid;if (high listhigh)swap(ref listlow, ref listhigh);return;mid = (low + high) 1;pivot = listmid;swap(ref listlow, ref listmid);l = low + 1;r = high;dowhile (l = r & listl = pivot)r-;if (l r)swap(ref listl, ref listr); while (l r);listlow = listr;listr = pivot;if (low + 1 r)Sort(list, low, r - 1);if (r + 1 high)Sort(list, r + 1, high);static void Main(string args)int iArrary = new int 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 ;QuickSorter q = new QuickSorter();q.Sort(iArrary, 0, 13);for (int m = 0; m = 13; m+)Console.WriteLine(0, iArrarym);/插入排序public class InsertionSorterpublic void Sort(int arr)for (int i = 1; i 0) & (arrj - 1 t)arrj = arrj - 1;/交换顺序-j;arrj = t;static void Main(string args)int array = new int 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 ;InsertionSorter i = new InsertionSorter();i.Sort(array);foreach (int m in array)Console.WriteLine(0, m);/希尔排序public class ShellSorterpublic void Sort(int arr)int inc;for (inc = 1; inc 0; inc /= 3)for (int i = inc + 1; i inc) & (arrj - inc - 1 t)arrj - 1 = arrj - inc - 1;/交换数据j -= inc;arrj - 1 = t;static void Main(string args)int array = new int 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 ;ShellSorter s = new ShellSorter();s.Sort(array);foreach (int m in array)Console.WriteLine(0, m);先我们给树下一个定义：树是一个有限的、非空的结点集 首先我们给树下一个定义： 树是一个有限的、非空的结点集，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#实现)系列-树(二)public class InOrder:IPrePostVisitor private IVisitor visitor; public InOrder(IVisitor _vis)visitor=_vis; #region IPrePostVisitor 成员 public void PreVisit(object _obj) / TODO: 添加 InOrder.PreVisit 实现 public void Visit(object _obj) / TODO: 添加 InOrder.Visit 实现 this.visitor.Visit(_obj); public void PostVisit(object _obj) / TODO: 添加 InOrder.PostVisitor 实现 #endregion public class PostOrder:IPrePostVisitor private IVisitor visitor; public PostOrder(IVisitor _vis)visitor=_vis; #region IPrePostVisitor 成员 public void PreVisit(object _obj) / TODO: 添加 PostOrder.PreVisit 实现 public void Visit(object _obj) / TODO: 添加 PostOrder.Visit 实现 public void PostVisit(object _obj) / TODO: 添加 PostOrder.PostVisitor 实现 this.visitor.Visit(_obj); #endregion protected class EnumVisitor:IVisitor Queue thisQueue; public EnumVisitor(Queue _que) this.thisQueue=_que; #region IVisitor 成员 public void Visit(object _obj) / TODO: 添加 EnumVisitor.Visit 实现 this.thisQueue.Enqueue(_obj); #endregion #region IEnumerable 成员 public IEnumerator GetEnumerator() / TODO: 添加 Tree.GetEnumerator 实现 EnumVisitor vis=new EnumVisitor(this.keyqueue); switch (this.traversaltype) case TraversalType.Breadth: BreadthFirstTraversal(vis); break; case TraversalType.PreDepth: PreOrder preVis=new PreOrder(vis); DepthFirstTraversal(preVis); break; case TraversalType.InDepth: InOrder inVis=new InOrder(vis); DepthFirstTraversal(inVis); break; case TraversalType.PostDepth: PostOrder postVis=new PostOrder(vis); DepthFirstTraversal(postVis); break; default: Console.WriteLine(WARNING:please set a travel type first!-void SetTraversalType(TraversalType _type) ); /throw new Exception(WARNING:please set a travel type first!);/if not set a type, a exception will happen break; return this.keyqueue.GetEnumerator(); #endregion数据结