線性表是最簡單、最基本、最常用的數據結構。線性表是線性結構的抽象(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 }