数据结构与算法2016-06-03

1.递归

一个算法调用自己来完成它的部分工作，在解决某些问题时，一个算法需要调用自身。如果一个算法直接调用自己或间接调用自己，就称这个算法是递归的。根据调用方式的不同，它分为直接递归和间接递归。

一个递归算法必须由两个部分：初始部分和递归部分。初始部分只处理可以直接解决而不需要再次递归调用的简单输入。递归部分包含对算法的一次或多次递归调用，每一次的调用参数都在某种程度上比原始调用参数更接近初始情况。

2. 接口

通用语言运行时（clr）支持单实现继承和多接口继承。

单实现继承是指一个类型只能有一个基类型。多接口继承是指一个类型可以继承多个接口，而接口是类之间相互交互的一个抽象，把类之间需要交互的内容抽象出来定义成接口，可以更好地控制类之间的逻辑交互。可见，接口内容的抽象的好坏关系到整个程序逻辑质量。另外可以在任何时候通过开发附加接口和实现来添加新的功能。

关于接口的很重要的概念是接口只包含成员定义，不包含成员的实现。接口仅仅是一个包含着一组虚方法的抽象类型。成员的实现需要在继承的类或者结构中实现。接口的成员包括静态方法、索引器、常数、事件以及静态构造器等，不包含任何实例资源或实例构造器，所以，不能实例化一个接口。

3.常用的接口

（1）IComparable接口

IComparable接口定义通用的比较方法。由类型使用的IComparable接口提供了一种比较多个对象的标准方式。如果一个类要实现与其他对象的比较，则必须实现IComparable接口。由可以排序的类型，例如值类型实现以创建适合排序等目的类型特定的比较方法。

（2）IEnumerable接口

IEnumerable接口公开枚举数，该枚举数支持再集合上进行简单迭代。

IEnumerable接口可由支持迭代内容对象的类实现。

（3）IEnumerator接口

IEnumerator接口支持在集合上进行简单迭代。是所有枚举数的基接口。枚举数只允许读取集合中的数据，枚举数无法用于修改基础集合。

（4）ICollection接口

ICollection接口定义所有集合的大小、枚举数和同步方法。ICollection接口是System.Collections命名空间中类的基接口。

（5）IDictionary接口

IDictionary接口是基于ICollection接口的更专用的接口。IDictionary接口实现是键值对的集合，如Hashtable类。

（6）IList接口

IList接口实现是可被排序且可按照索引访问其成员的值的结合，如ArrayList类。

4.接口与抽象类

抽象类与接口在定义与功能上有很多相似的地方，在程序中选择使用抽象类还是接口需要比较抽象类和接口之间的具体差别。

抽象类是一种不能实例化而必须从中继承的类，抽象类可以提供实现，也可以不提供实现。子类只能从一个抽象类继承。抽象类应主要用于关系密切的对象。如果要设计大的功能单元或创建组件的多个版本，则使用抽象类。

接口是完全抽象的成员集合，不提供实现，类或者结构可以继承多个接口。接口最适合为不相关的类提供通用功能。如果要设计小而简练的功能块，则使用接口。接口一旦创建就不能更改，如果需要接口的新版本，必须创建一个全新的接口。

5.接口的实现

接口的实现分为隐式实现和显式实现。如果类或结构要实现的是单个接口，可以使用隐式实现，如果类或者结构继承了多个接口，那么接口中相同名称成员就要显式实现。显示实现是通过使用接口的完全限定名来实现接口成员的。