连载4：《用C#实现数据结构与算法》--翻译Michael McMillan写的《Data Structures and Algorithms Using C#》
第一章：介绍集合，泛型和计时器类-04请访问
http://blog.csdn.net/abatei/archive/2007/12/25/1967116.aspx
正文：
CollectionBase 类
.NET Framework类库并不包含用于存储数据的泛型集合类，但可以使用抽象类CollectionBase去创建您自己的集合类。CollectionBash类使得开发人员可以定制集合类。它实现了创建一个集合类所必须实现的接口：ICollection and IEnumerable，做为集合类的一部份，开发人员不得不去实现它们。
用ArrayLists实现集合类
这一节，我们将演示如何使用C#实现我们自己的集合类。这人几个目的。首先，如果你不是很熟悉使用面向对象（OOP）的方式编程，这个程序将向您展示C#中简单的OOP技术。我们也可以通过这一节来讨论一些性能问题，从而引入C#中不同的数据结构进行讨论。最后，我想你会象喜欢本书的其他程序一样喜欢本节，因为使用代码去重新实现已经存在的数据结构是一件非常有趣的事情。正如Don Knuth（译者注：中文名：高德纳(1938-)算法和程序设计技术的先驱者。经典著作《计算机程序设计艺术》更是被誉为算法中“真正”的圣经，像KMP和LR(K)这样令人不可思议的算法，在此书比比皆是。难怪连BillGates 都说：“如果能做对书里所有的习题，就直接来微软上班吧！”对于DonE.Knuth本人，一生中获得的奖项和荣誉不计其数，包括图灵奖，美国国家科学金奖，美国数学学会斯蒂尔将（AMS SteelPrize），以及发明先进技术荣获的极受尊重的京都奖（KyotoPrize）等等）所说的，you haven’t really learned something well until you’ve taught it to a computer.(译者著：这里实在不懂如何翻译，妄加推论，大意应该是：在没有教会电脑如何使用它之前，都不能算真正地掌握了它。------用程序实现了它就代表着电脑会使用它了)。对于C#的教学来说，自己实现不同的数据结构比你日复一日地调用现成类库能学到更多的关于数据结构的知识。
定义一个集合类
在C#中定义一个集合类的最简单的方法是基于系统的System.Collections类库里的CollectionBash抽象类进行定义。这个类提供了一系列的抽象方法让你去实现并创建自己的集合类。CollectionBase类本身在内部实现了一个数据结构：InnerList（一个ArrayList），可以把字作为你所实现的类的基础。本节我们着眼于怎样使用CollectionBase去创建一个集合类。
实现集合类
在集合类中应该创建包含了常用的跟底层数据结构类InnerList进行交互的方法。我们首先实现Add，Remove，Count和Clear方法。这些方法对于这个类来说是最基本的，尽管其它方法使得这个类更加有用。
让我们开始实现Add方法。这个方法有一个Object类型的参数，它在集合中添加一个项。代码如下：
public void Add(Object item)
{
InnerList.Add(item);
}
ArrayList把数据存储为object（Object数据类型），这也是为什么我们把item声明为一个Object类型的原因。你将在第2章学到更多的关于ArrayList的知识。
Remove方法也是同样的道理：
public void Remove(Object item)
{
InnerList.Remove(item);
}
下一个方法是Count。Count经常被做为属性，但我宁愿把它实现为方法。在祖先类CollectionBase中Count方法已经被实现，所以我们不得不使用new关键字去隐藏CollectionBase类中的Count方法：
public new int Count()
{
return InnerList.Count;
}
Clear方法用于清除InnerList中的所有项目。在定义这个方法也也需要使用new关键字：
public new void Clear()
{
InnerList.Clear();
}
在最初阶段，这些已经足够了。让我们着眼于如何在程序中使用这个类，下面代码包含了类的完整代码：
using System;
using System.Collections;
public class Collection : CollectionBase<T>
{ //译者注：并不存在CollectionBase<T>类，上面应该改为CollectionBase。
public void Add(Object item)
{
InnerList.Add(item);
}
public void Remove(Object item)
{
InnerList.Remove(item);
}
public new void Clear()
{
InnerList.Clear();
}
public new int Count()
{
return InnerList.Count;
}
}
class chapter1
{
static void Main()
{
Collection names = new Collection();
names.Add("David");
names.Add("Bernica");
names.Add("Raymond");
names.Add("Clayton");
foreach (Object name in names)
Console.WriteLine(name);
Console.WriteLine("Number of names: " + names.Count());
names.Remove("Raymond");
Console.WriteLine("Number of names: " + names.Count());
names.Clear();
Console.WriteLine("Number of names: " + names.Count());
}
}
为了使得这个集合类更加有用，你可以实现其他几个方法。在本章的练习中你将有机会实现这几个方法。
泛型编程
OOP（面向对象）的问题之一是代码膨胀问题，有一种类型的代码膨胀是由于你考虑在方法中可以使用各种可能的数据类型做为参数而不得不重载一个或一系列方法。解决它的方法之一是使用一个可以接纳所有数据类型的值，这个值只需要定义一次。这种技术叫泛型编程。
泛型在编译时提供了一种叫占位符的数据类型，用于填充需要指定某种数据类型的地方。占位符为用中括号括住的一个标识符。让我们看一个例子。
泛型编程的一个标准的例子是Swap方法。下面是C#中的Swap方法泛型版本的定义：
static void Swap<T>(ref T val1, ref T val2)
{
T temp;
temp = val1;
val1 = val2;
val2 = temp;
}
代表数据类型的占位符紧跟在方法名称的后面。当任何时候需要使用一个泛型数据类型时，就可以使用中括号之间的标识符来代替。每个参数都被声明为泛型类型，temp变量用于实现交换。下面是测试程序的代码：
using System;
class chapter1
{
static void Main()
{
int num1 = 100;
int num2 = 200;
Console.WriteLine("num1: " + num1);
Console.WriteLine("num2: " + num2);
Swap<int>(ref num1, ref num2);
Console.WriteLine("num1: " + num1);
Console.WriteLine("num2: " + num2);
string str1 = "Sam";
string str2 = "Tom";
Console.WriteLine("String 1: " + str1);
Console.WriteLine("String 2: " + str2);
Swap<string>(ref str1, ref str2);
Console.WriteLine("String 1: " + str1);
Console.WriteLine("String 2: " + str2);
}
static void Swap<T>(ref T val1, ref T val2)
{
T temp;
temp = val1;
val1 = val2;
val2 = temp;
}
}
运行结果为
泛型并非只能在方法中声明，你也可以创建一个泛型类。声明一个泛型类需要在类名后面包含泛型占位符。任何时候在程序中引用类名都必须包含占位符。下面代码演示了如何创建一个泛型类：
public class Node<T> //译者注：C#中的泛型链表的实现
{
T data;
Node<T> link;
public Node(T data, Node<T> link)
{
this.data = data;
this.link = link;
}
}
这个类的使用方法如下：
Node<string> node1 = new Node<string>("Mike", null);
Node<string> node2 = new Node<string>("Raymond", node1);
我们将在本书所讨论的几个数据结构中使用Node类。
使用泛型进行编程非常有用，C#已经提供了用泛型实现的数据结构的类库。这些数据结构可以在System.Collection.Generics命名空间之下找到，并且当我们讨论这个命名空间下的某个数据结构时，将会研究如何使用它。一般情况下，尽管这个类具有和非泛型数据结构类相同的功能，我们还是尽量使用泛型类做为实例，因为使用它们并没有什么区别。
--------------------编程问答-------------------- it's goog --------------------编程问答--------------------
补充：.NET技术 , C#
