
本文共 26056 字,大约阅读时间需要 86 分钟。
1、泛型的概念
对于泛型的概念通过程序进行讲解。 最快的一般用途的排序算法之一是Quicksort,这个算法利用分治法划分数据,然后递归调用自身来执行排序任务。 实现quickSort算法的代码:(效率很高的程序代码)using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks;class clsSort{ int[] data; public clsSort(int[] number) { data = number; } public void swap(int pos1, int pos2) { int temp; temp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = temp; } public void quickSort(int first, int last) { int start; int end; start = first; end = last; if (last - first >= 1) { int pivot = data[first]; while (end > start) { while (data[start] <= pivot && start <= last & start < end) { start++; } while (data[end] > pivot && end >= first && end >= start) { end--; } if (end > start) { swap(start, end); } } swap(first, end); quickSort(first, end - 1); quickSort(end + 1, last); } else { return; } }}
代码分析:
data = number;
上述语句将进行一个正常的rvalue到rvalue的赋值:引用变量rvalue是一个指向数据驻留的内存位置的内存地址指针,因此最终结果是data和number指向同一个数据。(这也意味着排序之后随机值的原始序列将会丢失。)可以通过如下语句解决 :
public clsSort(int[] vals){int[] data=new int [vals.Length];Array.Copy(number,data,vals.Length);}
关于quickSort算法,背后的理论是将一组数字围绕数据中的支点划分为两部分。代码围绕这两部分查看数据并且调用swap()方法交换值,从而重新对数据进行排序。然后代码从它自身中调用相同的quickSort方法。方法调用自身的过程被称为递归。
int start; int end; start = first; end = last; if (last - first >= 1) { int pivot = data[first]; while (end > start) { while (data[start] <= pivot && start <= last & start < end) { start++; } while (data[end] > pivot && end >= first && end >= start) { end--; } if (end > start) { swap(start, end); } } swap(first, end); quickSort(first, end - 1); quickSort(end + 1, last); } else { return; }
如上是quickSort代码,非常重要。
排序方法有性能因子:大O表示法指示。
EXE:O(N^2)这种表示法,意味着排序数目增加10倍,就要花费100倍时间来排序数据。 QuickSort由关系O(NxLogN)约束,这使得排序时间更线性。frmMain代码:
#define DEBUG#undef DEBUGusing System;using System.Windows.Forms;public class frmMain : Form{ private const int MAXVAL = 1000; private int[] data; private int number; private Label label1; private TextBox txtNumber; private Button btnGen; private Button btnSort; private Button btnClose; private ListBox lstOutput; private ListBox lstSort; #region Windows code private void InitializeComponent() { this.label1 = new System.Windows.Forms.Label(); this.txtNumber = new System.Windows.Forms.TextBox(); this.btnGen = new System.Windows.Forms.Button(); this.btnSort = new System.Windows.Forms.Button(); this.btnClose = new System.Windows.Forms.Button(); this.lstOutput = new System.Windows.Forms.ListBox(); this.lstSort = new System.Windows.Forms.ListBox(); this.SuspendLayout(); // // label1 // this.label1.BorderStyle = System.Windows.Forms.BorderStyle.Fixed3D; this.label1.Location = new System.Drawing.Point(29, 30); this.label1.Name = "label1"; this.label1.Size = new System.Drawing.Size(127, 23); this.label1.TabIndex = 0; this.label1.Text = "Number of items"; this.label1.TextAlign = System.Drawing.ContentAlignment.TopRight; // // txtNumber // this.txtNumber.Location = new System.Drawing.Point(162, 30); this.txtNumber.Name = "txtNumber"; this.txtNumber.Size = new System.Drawing.Size(113, 21); this.txtNumber.TabIndex = 1; // // btnGen // this.btnGen.Location = new System.Drawing.Point(29, 79); this.btnGen.Name = "btnGen"; this.btnGen.Size = new System.Drawing.Size(75, 23); this.btnGen.TabIndex = 2; this.btnGen.Text = "Generate"; this.btnGen.UseVisualStyleBackColor = true; this.btnGen.Click += new System.EventHandler(this.btnGen_Click); // // btnSort // this.btnSort.Location = new System.Drawing.Point(176, 79); this.btnSort.Name = "btnSort"; this.btnSort.Size = new System.Drawing.Size(75, 23); this.btnSort.TabIndex = 3; this.btnSort.Text = "Sort"; this.btnSort.UseVisualStyleBackColor = true; this.btnSort.Click += new System.EventHandler(this.btnSort_Click); // // btnClose // this.btnClose.Location = new System.Drawing.Point(341, 79); this.btnClose.Name = "btnClose"; this.btnClose.Size = new System.Drawing.Size(75, 23); this.btnClose.TabIndex = 4; this.btnClose.Text = "Close"; this.btnClose.UseVisualStyleBackColor = true; this.btnClose.Click += new System.EventHandler(this.btnClose_Click); // // lstOutput // this.lstOutput.FormattingEnabled = true; this.lstOutput.ItemHeight = 12; this.lstOutput.Location = new System.Drawing.Point(29, 160); this.lstOutput.Name = "lstOutput"; this.lstOutput.Size = new System.Drawing.Size(164, 220); this.lstOutput.TabIndex = 5; // // lstSort // this.lstSort.FormattingEnabled = true; this.lstSort.ItemHeight = 12; this.lstSort.Location = new System.Drawing.Point(239, 160); this.lstSort.Name = "lstSort"; this.lstSort.Size = new System.Drawing.Size(177, 220); this.lstSort.TabIndex = 7; // // frmMain // this.ClientSize = new System.Drawing.Size(445, 460); this.Controls.Add(this.lstSort); this.Controls.Add(this.lstOutput); this.Controls.Add(this.btnClose); this.Controls.Add(this.btnSort); this.Controls.Add(this.btnGen); this.Controls.Add(this.txtNumber); this.Controls.Add(this.label1); this.Name = "frmMain"; this.Load += new System.EventHandler(this.frmMain_Load); this.ResumeLayout(false); this.PerformLayout(); } #endregion //#region是C# 预处理器指令。 //#region 使您可以在使用 Visual Studio //代码编辑器的大纲显示功能时指定可展开或折叠的代码块。 public frmMain() { InitializeComponent(); } public static void Main() { frmMain main = new frmMain(); Application.Run(main); } private void btnGen_Click(object sender, EventArgs e) { bool flag; int i; flag = int.TryParse(txtNumber.Text, out number); if (flag == false) { MessageBox.Show("Enter whole digit only", "Input Error", MessageBoxButtons.OK, MessageBoxIcon.Error); txtNumber.Focus(); return; }#if DEBUG Random rnd = new Random(number);#else Random rnd = new Random();#endif data = new int[number]; lstOutput.Items.Clear(); lstSort.Items.Clear(); for (i = 0; i < data.Length; i++) { data[i] = rnd.Next(MAXVAL); lstOutput.Items.Add(data[i].ToString()); } } private void btnSort_Click(object sender, EventArgs e) { int i; clsSort mySort = new clsSort(data); mySort.quickSort(0, data.Length - 1); for (i = 0; i < data.Length; i++) { lstSort.Items.Add(data[i].ToString()); } } private void frmMain_Load(object sender, EventArgs e) { } private void btnClose_Click(object sender, EventArgs e) { Close(); }}
代码分析:
#if DEBUG Random rnd = new Random(number);#else Random rnd = new Random();#endif
上述代码为上一章叙述的脚手架代码。开发代码的时候,产生一系列可重复的数字通常是有益的,这样在调试和测试时就有一个稳定的测试数据集。为了建立这种测试环境,简单地钉入Random类的参数化构造函数的#undef DEBUG行为以注释的形式存在。测试的时候去掉注释,就可以进行相关的测试。
2、泛型的定义
泛型能够在C#中创建”无类型”数据结构。 未使用泛型:clsSort mySort = new clsSort(data);
使用泛型:
clsSortmySort = new clsSort (data);
优点:同样的代码可以处理不同的数据类型。而不需要修改每个数据类型的源代码。
包装和接触包装:(关于ArrayList) C#几乎一切都是从System.Object派生出来的。几乎允许所有对象存储在ArrayList中。每当用值类型作为对象时,C#都必须在处理时将该值类型转换为对象,称之为包装。将包装的对象转换回他的值类型的过程被称为解除包装。(但是包装和解除包装要产生100%的性能损失)示例程序:
设置选择数据类型的按钮,然后通过程序生成相应数据类型的随机值,并且排序。 使用泛类型的QuickSort类:using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading.Tasks; public class clsQuicksortwhere T: IComparable { T[] data; public clsQuicksort(T[] value) { data = value; } public void swap(int pos1,int pos2) { T temp; temp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = temp; } private int getPivotPoint(int first, int last) { int pivot = first; int start = first; int end = last; if (last - first >= 1) { while (end > start) { while (data[pivot].CompareTo(data[start]) >= 0 && start <= last && end > start) start++; while (data[pivot].CompareTo(data[end]) <= 0 && end >= first && end >= start) end--; if (end > start) swap(start, end); } swap(first,end); doSort(first, end - 1); } return end; } private void doSort(int first,int last) { if (first == last) { return; } else { int pivot = getPivotPoint(first,last); if (pivot > first) doSort(first,pivot-1); if (pivot < last) doSort(pivot +1,last); } } public void Sort() { int len = data.Length; if (len < 2) return; doSort(0,data.Length-1); } }
注意,程序中第二个using语句是的泛型成为可能。Generic名称空间包含支持泛型字典,列表,队列和堆栈的泛型类,结构和接口。
使用泛型尖括号表示啊,括起类的数据类型T由该类的对象使用:public class clsQuicksortwhere T: IComparable
实例化泛型类的语法:
clsQuicksort iSort = new clsQuicksort (iData);
与其它支持类似结构的语言(C++模板)不同,C#不喜欢对泛型类型T使用关系运算符。
while (data[pivot].CompareTo(data[start]) >= 0 && start <= last && end > start)
所以对相关的比较进行相应的修改。
关于frmMain函数,调用泛类的方法代码:
using System;using System.Windows.Forms;public class frmMain : Form{ const int INTEGER = 1; const int LONG = 2; const int DOUBLE = 3; const int STRING = 4; const int UNSORTED = 1; const int SORTED = 2; const int MAXVALUE = 1000; int items; int choice; int whichListBox; int[] iData; long[] lData; double[] dData; string[] sData; Random rnd = new Random(); private GroupBox groupBox1; private RadioButton rbString; private RadioButton rbLong; private RadioButton rbDouble; private RadioButton rbInt; private Label label1; private TextBox txtItems; private TextBox txtString; private Button btnRaw; private Button btnSort; private Button btnClose; private ListBox lstUnsorted; private ListBox lstSorted; #region Windows code private void InitializeComponent() { this.groupBox1 = new System.Windows.Forms.GroupBox(); this.rbInt = new System.Windows.Forms.RadioButton(); this.rbDouble = new System.Windows.Forms.RadioButton(); this.rbLong = new System.Windows.Forms.RadioButton(); this.rbString = new System.Windows.Forms.RadioButton(); this.label1 = new System.Windows.Forms.Label(); this.txtItems = new System.Windows.Forms.TextBox(); this.txtString = new System.Windows.Forms.TextBox(); this.btnRaw = new System.Windows.Forms.Button(); this.btnSort = new System.Windows.Forms.Button(); this.btnClose = new System.Windows.Forms.Button(); this.lstUnsorted = new System.Windows.Forms.ListBox(); this.lstSorted = new System.Windows.Forms.ListBox(); this.groupBox1.SuspendLayout(); this.SuspendLayout(); // // groupBox1 // this.groupBox1.Controls.Add(this.rbString); this.groupBox1.Controls.Add(this.rbLong); this.groupBox1.Controls.Add(this.rbDouble); this.groupBox1.Controls.Add(this.rbInt); this.groupBox1.Location = new System.Drawing.Point(29, 31); this.groupBox1.Name = "groupBox1"; this.groupBox1.Size = new System.Drawing.Size(244, 121); this.groupBox1.TabIndex = 0; this.groupBox1.TabStop = false; this.groupBox1.Text = "Data Type to Sort"; this.groupBox1.Enter += new System.EventHandler(this.groupBox1_Enter); // // rbInt // this.rbInt.AutoSize = true; this.rbInt.Location = new System.Drawing.Point(17, 35); this.rbInt.Name = "rbInt"; this.rbInt.Size = new System.Drawing.Size(65, 16); this.rbInt.TabIndex = 0; this.rbInt.TabStop = true; this.rbInt.Text = "Integer"; this.rbInt.TextAlign = System.Drawing.ContentAlignment.TopLeft; this.rbInt.UseVisualStyleBackColor = true; this.rbInt.CheckedChanged += new System.EventHandler(this.rbInt_CheckedChanged); // // rbDouble // this.rbDouble.AutoSize = true; this.rbDouble.Location = new System.Drawing.Point(135, 35); this.rbDouble.Name = "rbDouble"; this.rbDouble.Size = new System.Drawing.Size(59, 16); this.rbDouble.TabIndex = 1; this.rbDouble.TabStop = true; this.rbDouble.Text = "Double"; this.rbDouble.UseVisualStyleBackColor = true; this.rbDouble.CheckedChanged += new System.EventHandler(this.rbDouble_CheckedChanged); // // rbLong // this.rbLong.AutoSize = true; this.rbLong.Location = new System.Drawing.Point(17, 78); this.rbLong.Name = "rbLong"; this.rbLong.Size = new System.Drawing.Size(47, 16); this.rbLong.TabIndex = 2; this.rbLong.TabStop = true; this.rbLong.Text = "Long"; this.rbLong.UseVisualStyleBackColor = true; this.rbLong.CheckedChanged += new System.EventHandler(this.rbLong_CheckedChanged); // // rbString // this.rbString.AutoSize = true; this.rbString.Location = new System.Drawing.Point(135, 77); this.rbString.Name = "rbString"; this.rbString.Size = new System.Drawing.Size(59, 16); this.rbString.TabIndex = 3; this.rbString.TabStop = true; this.rbString.Text = "String"; this.rbString.UseVisualStyleBackColor = true; this.rbString.CheckedChanged += new System.EventHandler(this.rbString_CheckedChanged); // // label1 // this.label1.BorderStyle = System.Windows.Forms.BorderStyle.Fixed3D; this.label1.Location = new System.Drawing.Point(279, 59); this.label1.Name = "label1"; this.label1.Size = new System.Drawing.Size(78, 23); this.label1.TabIndex = 1; this.label1.Text = "Items:"; this.label1.TextAlign = System.Drawing.ContentAlignment.TopRight; // // txtItems // this.txtItems.Location = new System.Drawing.Point(363, 59); this.txtItems.Name = "txtItems"; this.txtItems.Size = new System.Drawing.Size(100, 21); this.txtItems.TabIndex = 2; // // txtString // this.txtString.Location = new System.Drawing.Point(29, 169); this.txtString.Name = "txtString"; this.txtString.Size = new System.Drawing.Size(432, 21); this.txtString.TabIndex = 3; // // btnRaw // this.btnRaw.Location = new System.Drawing.Point(29, 214); this.btnRaw.Name = "btnRaw"; this.btnRaw.Size = new System.Drawing.Size(91, 23); this.btnRaw.TabIndex = 4; this.btnRaw.Text = "Show Unsorted"; this.btnRaw.TextAlign = System.Drawing.ContentAlignment.TopLeft; this.btnRaw.UseVisualStyleBackColor = true; this.btnRaw.Click += new System.EventHandler(this.btnRaw_Click); // // btnSort // this.btnSort.Location = new System.Drawing.Point(198, 213); this.btnSort.Name = "btnSort"; this.btnSort.Size = new System.Drawing.Size(88, 23); this.btnSort.TabIndex = 5; this.btnSort.Text = "Show Sorted"; this.btnSort.UseVisualStyleBackColor = true; this.btnSort.Click += new System.EventHandler(this.btnSort_Click); // // btnClose // this.btnClose.Location = new System.Drawing.Point(386, 213); this.btnClose.Name = "btnClose"; this.btnClose.Size = new System.Drawing.Size(75, 23); this.btnClose.TabIndex = 6; this.btnClose.Text = "Close"; this.btnClose.UseVisualStyleBackColor = true; this.btnClose.Click += new System.EventHandler(this.btnClose_Click); // // lstUnsorted // this.lstUnsorted.FormattingEnabled = true; this.lstUnsorted.ItemHeight = 12; this.lstUnsorted.Location = new System.Drawing.Point(29, 254); this.lstUnsorted.Name = "lstUnsorted"; this.lstUnsorted.Size = new System.Drawing.Size(174, 172); this.lstUnsorted.TabIndex = 7; // // lstSorted // this.lstSorted.FormattingEnabled = true; this.lstSorted.ItemHeight = 12; this.lstSorted.Location = new System.Drawing.Point(283, 254); this.lstSorted.Name = "lstSorted"; this.lstSorted.Size = new System.Drawing.Size(178, 172); this.lstSorted.TabIndex = 8; // // frmMain // this.ClientSize = new System.Drawing.Size(473, 461); this.Controls.Add(this.lstSorted); this.Controls.Add(this.lstUnsorted); this.Controls.Add(this.btnClose); this.Controls.Add(this.btnSort); this.Controls.Add(this.btnRaw); this.Controls.Add(this.txtString); this.Controls.Add(this.txtItems); this.Controls.Add(this.label1); this.Controls.Add(this.groupBox1); this.Name = "frmMain"; this.groupBox1.ResumeLayout(false); this.groupBox1.PerformLayout(); this.ResumeLayout(false); this.PerformLayout(); } #endregion //#region是C# 预处理器指令。 //#region 使您可以在使用 Visual Studio //代码编辑器的大纲显示功能时指定可展开或折叠的代码块。 public frmMain() { InitializeComponent(); } public static void Main() { frmMain main = new frmMain(); Application.Run(main); } private void ShowData() { int i; switch (choice) { case INTEGER: for (i = 0; i < items; i++) { if (whichListBox == SORTED) lstSorted.Items.Add(iData[i].ToString()); else lstUnsorted.Items.Add(iData[i].ToString()); } break; case LONG: for (i = 0; i < items; i++) { if (whichListBox == SORTED) lstSorted.Items.Add(lData[i].ToString()); else lstUnsorted.Items.Add(lData[i].ToString()); } break; case DOUBLE: for (i = 0; i < items; i++) { if (whichListBox == SORTED) lstSorted.Items.Add(dData[i].ToString()); else lstUnsorted.Items.Add(dData[i].ToString()); } break; case STRING: for (i = 0; i < sData.Length; i++) { if (whichListBox == SORTED) lstSorted.Items.Add(sData[i].ToString()); else lstUnsorted.Items.Add(sData[i].ToString()); } break; } } private void btnClose_Click(object sender, EventArgs e) { Close(); } private void rbInt_CheckedChanged(object sender, EventArgs e) { choice = INTEGER; } private void btnRaw_Click(object sender, EventArgs e) { bool flag; int i; flag = int.TryParse(txtItems.Text,out items); if (flag == false) { MessageBox.Show("Numeric only,Re-enter","Input Error",MessageBoxButtons.OK,MessageBoxIcon.Error); txtItems.Focus(); return; } lstUnsorted.Items.Clear(); lstSorted.Items.Clear(); whichListBox = UNSORTED; switch (choice) { case INTEGER: iData=new int[items]; for (i = 0; i < items; i++) { iData[i] = rnd.Next(MAXVALUE); } break; case LONG: lData=new long[items]; for (i = 0; i < items; i++) { lData[i] = (long) rnd.Next(MAXVALUE); } break; case DOUBLE: dData=new double[items]; for (i = 0; i < items; i++) { dData[i] = rnd.NextDouble()*MAXVALUE; } break; case STRING: sData = txtString.Text.Split(','); break; } ShowData(); } private void btnSort_Click(object sender, EventArgs e) { whichListBox = SORTED; switch (choice) { case INTEGER: clsQuicksort iSort = new clsQuicksort (iData); iSort.Sort(); break; case DOUBLE: clsQuicksortdSort=new clsQuicksort (dData) ; dSort.Sort(); break; case LONG: clsQuicksort lSort = new clsQuicksort (lData); lSort.Sort(); break; case STRING: clsQuicksort sSort = new clsQuicksort (sData); sSort.Sort(); break; } ShowData(); } private void rbDouble_CheckedChanged(object sender, EventArgs e) { choice = DOUBLE; } private void rbLong_CheckedChanged(object sender, EventArgs e) { choice = LONG; } private void rbString_CheckedChanged(object sender, EventArgs e) { choice = STRING; } private void groupBox1_Enter(object sender, EventArgs e) { }}
关于对字符串进行的排序工作:
Splite方法:选择字符串数据类型时,数量由在txtString的文本框对象中创建的逗号分隔字符串条目个数设置。如下为代码:sData = txtString.Text.Split(',');
Splite()方法分析txtString来查找逗号,每发现一个逗号就为该逗号前面的字符创建一个新字符串。当读完所有子串之后,字符串的数组就会被赋予sData。
注意关于数据生成的部分:
switch (choice) { case INTEGER: iData=new int[items]; for (i = 0; i < items; i++) { iData[i] = rnd.Next(MAXVALUE); } break; case LONG: lData=new long[items]; for (i = 0; i < items; i++) { lData[i] = (long) rnd.Next(MAXVALUE); } break; case DOUBLE: dData=new double[items]; for (i = 0; i < items; i++) { dData[i] = rnd.NextDouble()*MAXVALUE; } break; case STRING: sData = txtString.Text.Split(','); break; }
参数化方法Next()在for循环内部生成了一个伪随机值。通过循环的次数由用户输入的items变量确定。传递值MAXVALUE意味生成的值落在0~MAXVALUE范围内。对于double类型,方法NextDouble()方法返回一个0~1的值。
综上为泛型的使用实例。
(1)使用带约束和接口的泛型
如果该类的第一行写成:public class clsQuickSort;
这个类可以使用能够想到的任何数据类型。这样的泛型类称之为无界泛型类。无界泛型类没有被限制或约束为任何特定数据类型。
将类的使用限制为支持IComparable接口的那些数据类型。下面的表达式使用where关键字引入该类的约束:public class clsQuicksortwhere T: IComparable
翻译:clsQuickSort可以用于任何数据类型T,只是要将该数据类型T约束为实现IComparable接口。
(2)接口
接口:没有实现或没有代码与之关联的引用对象。 前文已经叙述过数据定义和声明的区别。数据定义必须为数据分配内存,意味着该数据的lvalue必须存在于符号表中。数据声明不会导致为该数据分配内存。 接口可以包括方法签名,属性和事件的声明。然而,他们没有提供实现那些方法属性或事件的代码。接口正好就是声明。(没有代码与接口相关) 注意,使用的IComparable接口仅仅支持该接口中的一个方法,所以将该接口编写成: 定义接口的方法:public interface IComparable{int CompareTo(Object obj);}
这意味着围绕每个值类型的包装器类有一个CompareTo()方法,可以用它来将该类型的一个数据项同一个类型的另一个数据项作比较。如果返回的int值小于0那么当前实例小于obj。如果返回值为0,那么两值相等。如果大于0,那么当前实例大于obj。
obj.CompareTo(obj2);
接口实际上是作为程序员向使用实现ICompareable接口的类中的代码的任何人做的一个承诺。包括C#编译器。
(3)使用接口的原因
接口真正长处:如果正确执行,那么接口就会将用户界面从底层代码中解耦。
不会破坏之前版本的代码。(4)使用接口
如何知道接口是为了一个数据类型实现的: I.亲自实现接口。 II.使用C#文档。 III.使用is运算符。 is运算符的语法:TypeInQuestion is InterfaceInQuestion
泛型目前不直接支持关系运算符。
IV.as运算符
as运算符来判断一个对象是否支持特定的接口。as运算符的语法形式如下:expression as type
as运算符实际上用来执行兼容的两个引用数据类型之间的转换。如果不能执行转换,那么会产生null作为表达式的输出。
例如:ArrayList数据类型仅支持IList接口,可以用如下代码进行检验:ArrayList val=new ArrayList();IComparable vall =val as IComparable;if(val==null){Console.WriteLine("Vall doesnt support IComparable");}
实现泛型可以得到更加健壮的类。
发表评论
最新留言
关于作者
