常用数据结构及算法C#实现
1.冒泡排序、选择排序、插入排序（三种简单非递归排序）
1 int[] waitSort = { 1,0, 12, 13, 14, 5, 6, 7, 8, 9, 10 }; 2 3 //冒泡排序 4 int length = waitSort.Length; 5 6 for (int i = 0; i < length; i++) 7 { 8 for (int j = i + 1; j < length; j++) 9 {10 if (waitSort[j] > waitSort[i])11 {12 int temp = waitSort[j];13 waitSort[j] = waitSort[i];14 waitSort[i] = temp;15 }16 }17 }18 19 //选择排序20 int pos1;21 for (int i = 0; i < length; i++)22 {23 pos1 = i;24 for (int j = i + 1; j < length; j++)25 {26 if (waitSort[pos1] < waitSort[j])27 {28 pos1 = j;29 }30 }31 if (pos1 != i)32 {33 int temp = waitSort[pos1];34 waitSort[pos1] = waitSort[i];35 waitSort[i] = temp;36 }37 }38 39 //插入排序40 for (int i = 1; i < length; i++)41 {42 for (int k = i; k > 0; k--)43 {44 if (waitSort[k] > waitSort[k - 1])45 {46 int temp = waitSort[k];47 waitSort[k] = waitSort[k - 1];48 waitSort[k - 1] = temp;49 }50 }51 }52 53 foreach (var i in waitSort)54 {55 Console.WriteLine(i);56 }57 Console.ReadKey();
2.快速排序
1 static int[] a = { 2, 5, 8, 6, 3, 4, 7, 9, 1,20,12,15,7,20,2 }; 2 static void Main(string[] args) 3 { 4 QuickSort(0, a.Length - 1); 5 foreach (var t in a) 6 { 7 Console.WriteLine(t); 8 } 9 Console.ReadKey();10 }11 12 static void QuickSort(int low,int high)13 {14 if (low < high)15 {16 int partition=Partition(low,high);17 QuickSort(low, partition-1);18 QuickSort(partition+1, high);19 }20 }21 22 static int Partition(int low, int high)23 {24 int point = a[low];25 while (low < high)26 {27 while (a[high] <= point && low<high)28 {29 high--;30 }31 Swap(high, low);32 while (a[low] >= point && low<high)33 {34 low++;35 }36 Swap(high, low);37 }38 return low;39 }40 41 static void Swap(int x, int y)42 {43 int temp = a[x];44 a[x] = a[y];45 a[y] = temp;46 }
3.二叉排序树
1 namespace BinarySortTree 2 { 3 class Node 4 { 5 public int Num { get; set; } 6 public Node LChild { get; set; } 7 public Node RChild { get; set; } 8 } 9 10 class BinarySortTree11 {12 public Node Root { get; set; }13 public BinarySortTree()14 {15 Root = new Node();16 }17 }18 19 class Program20 {21 static void Main(string[] args)22 {23 int[] sort = { 2, 5, 8, 3, 9, 6, 1, 7, 4,2,2,2 };24 BinarySortTree bst = new BinarySortTree();25 bst.Root.Num = 2;26 for (int i = 1; i < sort.Length; i++)27 {28 InsertBst(bst.Root, sort[i]);29 } 30 DFS(bst.Root);31 Console.ReadKey();32 }33 34 static void InsertBst(Node parent,int num)35 {36 if (num <= parent.Num)37 {38 if (parent.LChild == null)39 {40 parent.LChild = new Node();41 parent.LChild.Num = num;42 return;43 }44 else45 {46 InsertBst(parent.LChild, num);47 } 48 }49 else50 {51 if (parent.RChild == null)52 {53 parent.RChild = new Node();54 parent.RChild.Num = num;55 return;56 }57 else58 {59 InsertBst(parent.RChild, num);60 } 61 }62 }63 64 static void DFS(Node parent)65 {66 67 if (parent.LChild != null)68 {69 DFS(parent.LChild);70 71 }72 Console.WriteLine(parent.Num);73 74 if (parent.RChild != null)75 {76 DFS(parent.RChild); 77 }78 }79 }80 }
4.堆排
1 namespace HeapSort 2 { 3 class Program 4 { 5 static int[] a = new int[] { -1,1, 5, 9, 3, 7, 6, 4, 2, 8 }; 6 static void Main(string[] args) 7 { 8 HeapSort(a.Length-1); 9 }10 11 static void HeapSort(int len)12 {13 //第一次调整得到最小堆，即k>2k+1 && k>2k14 for (int i = len/2; i >= 1; i--)15 {16 Adjust(i, len);17 }18 19 //第二次先交换第一个节点和最后一个节点，使堆顶元素最小，然后调整20 for (int i = len; i >= 2; i--)21 {22 Swap(1, i);23 Adjust(1, i-1);24 }25 }26 27 static void Swap(int m,int n)28 {29 int temp = a[m];30 a[m] = a[n];31 a[n] = temp;32 }33 34 static void Adjust(int parent,int len)35 {36 int l = 2 * parent;37 int r = 2 * parent + 1;38 int largest = parent;39 //选出最大的节点，用于与父节点交换位置40 if (l <=len && a[l] > a[largest])41 {42 largest = l;43 }44 if (r<=len && a[r]>a[largest])45 {46 largest = r;47 }48 //如果需要调整父节点，先交换然后调整交换节点与其孩子节点49 if (largest != parent)50 {51 Swap(parent, largest);52 Adjust(largest, len);53 }54 }55 }56 }
5.栈的实现
1 namespace 栈 2 { 3 public class MyStack 4 { 5 private int index = -1; 6 private int[] a = new int[100]; 7 8 public void Push(int num) 9 {10 a[++index] = num;11 }12 13 public int? Pop()14 {15 if (index == -1)16 {17 return null;18 }19 return a[index--];20 }21 }22 }23 24 namespace 栈25 {26 class Program27 {28 static void Main(string[] args)29 {30 MyStack stack = new MyStack();31 stack.Push(1);32 stack.Push(2);33 stack.Push(3);34 stack.Push(4);35 int? temp;36 while ((temp = stack.Pop()) != null)37 {38 Console.WriteLine(temp);39 }40 41 stack.Push(4);42 stack.Push(3);43 stack.Push(2);44 stack.Push(1);45 while ((temp = stack.Pop()) != null)46 {47 Console.WriteLine(temp);48 }49 Console.ReadKey();50 }51 }52 }
6.List实现
namespace MyList{ public class Node { public int Num{get;set;} public Node Next{get;set;} } public class MyList { public Node Head { get; set; } public int Length { get; set; } public MyList() { Head = new Node(); Head.Next = null; Length = 1; } public void Add(int num) { Node n = new Node(); n.Num = num; Node node = Head; while (node.Next != null) { node = node.Next; } node.Next = n; Length++; } public void Delete(int index) { Node n = Head; if (index == 0) { Head = n.Next; } else if(Length-1==index) { for (int i = 0; i < index - 1; i++) { n = n.Next; } n.Next = null; } else { for (int i = 0; i < index - 1; i++) { n = n.Next; } n.Next = n.Next.Next; } Length--; } public int this[int index] { get { Node n = Head; for (int i = 0; i < index; i++) { n = n.Next; } return n.Num; } set { Node n = Head; for (int i = 0; i < index; i++) { n = n.Next; } n.Num = value; } } }}namespace MyList{ class Program { static void Main(string[] args) { MyList list = new MyList(); list.Head.Num = 1; list.Add(2); list.Add(3); list.Add(4); list.Add(5); list.Add(6); Console.WriteLine("链表长度："+list.Length); Node n = list.Head; Console.WriteLine(n.Num); while (n.Next != null) { n = n.Next; Console.WriteLine(n.Num); } Console.ReadKey(); } }}
7.DFS(深搜)/BFS(宽搜)
1 private static void DFS(XmlNode parent) 2 { 3 if (!parent.HasChildNodes) 4 { 5 return; 6 } 7 else if (parent.HasChildNodes) 8 { 9 for (int j = 0; j < parent.ChildNodes.Count; j++)10 {11 if (parent.ChildNodes[j].Name == "span")12 {13 list.Add(parent.ChildNodes[j]);14 }15 DFS(parent.ChildNodes[j]);16 }17 }18 }19 20 21 public static void BFS(XmlNode root)22 {23 queue.Enqueue(root);24 while (queue.Count != 0)25 {26 XmlNode n = queue.Dequeue();27 if (n.Name == "span")28 {29 list.Add(n);30 }31 for (int i = 0; i < n.ChildNodes.Count; i++)32 {33 queue.Enqueue(n.ChildNodes[i]);34 }35 }36 }