C#数据结构－线性表

C#数据结构－线性表2011-02-13 博客园 Richet理论基础：

线性表是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象（Abstract），线性结构的特点是结构中的数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系，即：

（1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素；

（2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。

也就是说，数据元素是一个接一个的排列。因此，可以把线性表想象为一种数据元素序列的数据结构。

线性表（List）是由n（n≥0）个相同类型的数据元素构成的有限序列.

注意：“有限”，指的是线性表中的数据元素的个数是有限的，线性表中的每一个数据元素都有自己的位置（Position）。本书不讨论数据元素个数无限的线性表。

“相同类型”，指的是线性表中的数据元素都属于同一种类型。

C#实现：

1接口

由于现在只考虑线性表的基本操作，所以以C#接口的形式表示线性表，接口中的方法成员表示基本操作。并且，为了使线性表对任何数据类型都适用，数据元素的类型使用泛型的类型参数。在实际创建线性表时，元素的实际类型可以用应用程序中任何方便的数据类型来代替，比如用简单的整型或者用户自定义的更复杂的类型来代替。

线性表的接口如下所示。

Code

[copy to clipboard]

CODE:

1 public interface IListDS<T>
2  {
3    /**//// <summary>
4    /// 获取长度
5    /// </summary>
6    /// <returns></returns>
7    int GetLength（）;
8
9    /**//// <summary>
10    /// 清空操作
11    /// </summary>
12    void Clear（）;
13
14    /**//// <summary>
15    /// 判断线性表是否为空
16    /// </summary>
17    /// <returns></returns>
18    bool IsEmpay（）;
19
20    /**//// <summary>
21    /// 附加操作,线性表未满，将值为item的新元素添加到末尾
22    /// </summary>
23    /// <param name="item"></param>
24    void Append（T item）;
25
26    /**//// <summary>
27    /// 插入操作
28    /// </summary>
29    /// <param name="item"></param>
30    /// <param name="i"></param>
31    void Insert（T item,int i）;
32
33    /**//// <summary>
34    /// 删除操作
35    /// </summary>
36    /// <param name="i"></param>
37    /// <returns></returns>
38    T Delete（int i）;
39
40    /**//// <summary>
41    /// 去表元
42    /// </summary>
43    /// <param name="i"></param>
44    /// <returns></returns>
45    T GetElem（int i）;
46
47    /**//// <summary>
48    /// 按值查找
49    /// </summary>
50    /// <param name="value"></param>
51    /// <returns></returns>
52    int Locate（T value）;
53  }