C# 數據結構 線性表（順序表 鏈表 IList 數組）

線性表

線性表是最簡單、最基本、最常用的數據結構。數據元素 1 對 1的關系，這種關系是位置關系。

特點

（1）第一個元素和最后一個元素前后是沒有數據元素，線性表中剩下的元素是近鄰的，前后都有元素。

（2）線性表中的元素是有限的（List），線性表中的數據類型一致。

（3）線性表表示方法 L={a1,a2,a3,a4…….an},L=(D,R)

（4）每一個元素都有前驅和后繼，第一個元素只有后繼，最后一個元素只有前驅。

實例

例如：1～100的整數是一個線性表

{“zhangsan”, “lisi”, “wangwu”}

……

A.順序表

所有的操作都是根據建立在線性結構的基礎之上進行的,線性表接口表示如下：

public interface IListDS<T>

{

int GetLength(); //求長度

void Clear();//清空線性表

bool IsEmpty();//判斷是否為空

void Append(T item);//追加元素

void Insert(T item,int i);//插入元素

T Delete(int i);//刪除元素

T GetElem(int i);//獲取元素

int Locate(T value);//查找元素

void Reverse();//倒置

}

操作

1.插入操作：

30在插入之前數據表沒有什么變化，當30數據出入到第i個位置后，后面的數據需要向后移動，那么插入的

數據越靠前，所需要移動的次數越多，如果i=0 那么需要向后移動 n 個位置，如果插入到最后一個，那么

順序表就不需要移動，如果插入的數據的位置i的概率為Pi，那么需要移動的位置次數為n/2,在順序表中移動

其中一半的數據，那么插入操作的時間復雜度為0(n)。

2.刪除操作：順序表刪除操作和插入操作一致，時間都是浪費在移動數據上，時間復雜度也為0（n）

3.讀取操作：直接讀取到順序表中的數值 比如 IListDS[i]元素,那么時間復雜度為 0(1) 只需要取一次即可。

4.查找操作：查找需要找到數據位置i，然后判斷數值是否一致，這個類似于插入和刪除，時間復雜度：0（n）

5.倒置操作：倒置操作只需要把前后對比 把第i個元素和第n-i個元素交換即可，時間復雜度也為:0(n)

B.單鏈表

對比順序表，邏輯相同的數據在物理地址上也相同，在順序表上查找一個位置上的數據非常方便，這是順序表的

優勢所在，那么問題來了，在順序表插入或者刪除一個數據時候往往需要移動剩下的數據，那么這樣會影響效率

，接下來學習一下線性表的另外一個存儲結構----鏈式存儲（Linked Strorage）,這樣的線性表叫做（Linked

List），對單鏈表的操作也不需要移動其他數據元素，但也失去順序表可隨機存儲的優點。

從兩張圖我們可以看到單鏈表的結構和順序表的一個差異

單鏈表實現的方法：

pulic class LinkedList<T>:IListDS<T>

{

Pulic Node<T> Head;//屬性

pulic LinkedList();//構造器

pulic GetLength();//獲取長度

pulic Clear();//清空

pulic bool IsEmpty();//判斷是否為空

pulic void Append(T item);//追加

pulic void Insert(T item,int i);//i位置插入

pulic void Delete(T item);//刪除元素

pulic T GetElem(int i);//獲取單鏈表第i個元素

pulic int i Location(T item);//查找位置

pulic void Reserver();//倒置

}

操作

1.獲取長度

單鏈表和順序表的長度過去方法不一致，因為單鏈表是連續的順序空間，而單鏈表

從頭引用頭開始，一個節點一個節點的便利，直到表的末尾。那么問題來了：剛剛介紹單鏈表物理空間不也是

連續的嗎？這個筆者個人理解，初始化數據是物理連續，而新插入的數據不會按照物理地址排列，所以所單鏈

表還是要便利整個內容來計算長度,時間復雜度為 0(n)。

2.清空操作

清空操作是指將單鏈表所有的節點使得單鏈表為空，此時頭引用head為null.清空單鏈表的算法實現如下：

pulic void Clear()

{

head=null;

}

需要注意的是，單鏈表清空后，原來節點所占用的空間不會一直保留，而由垃圾回收器進行回收和順序表不一樣

的是，順序表是連續的空間，數組分配的空間仍然保留。

3.附加操作

附加操作，是要便利單鏈表中所有的元素，然后在鏈表的尾部添加元素，時間復雜度為：0(n);

線性表的順序存儲和鏈式存儲各有優缺點，線性表如何存儲取決于使 用的場合。如果不需要經常在線性表中進行

插入和刪除，只是進行查找，那么， 線性表應該順序存儲；如果線性表需要經常插入和刪除，而不經常進行查找

，則 線性表應該鏈式存儲。

C 結合單向鏈表，肯定也有有雙向鏈表，雙向鏈表也是有上面的基本操作，然后思考相關的問題：時間復雜度問題。

D 循環列表：循環鏈表是在單鏈表和雙向鏈表的基礎上頭尾相連Last.Next=>Header.Head

C#中的線性表

說道C# 線性表那就是List，在1.1中提供了非泛型接口 IList,接口中的項是object，非泛型IList是從ICollection

接口繼承而來,是所有線性表的接口，用了這么長時間的List才發現IList是線性結構，IList分為三類：只讀的，大

小不可變，大小可變的。

只讀的IList：不能被修改，插入或者刪除。

大小不變的IList：不能在表中插入或刪除，但是可以修改表中的項。

大小可變的ILIST: 可以操作，可以插入或者刪除

非泛型的IList接口聲明如下：

interface IList:ICollenciton,IEnumberable

{

//共有屬性

bool IsFiexedSize{get;} //只讀，如果IList有固定大小

bool IsReadOnly{get;} //只讀 ，如果ILIST是只讀的

object this[T index] {get;set;} //索引器 得到某個類型

int add(object value);

void clear();

int indexof(object value);

bool contains(ojbject value);

void insert(index,object value);

void remove();

void removeat();

}

.NET 框架中一些集合實現了IList接口，如ArrayList，ListDictionary,StringCollection,String Dictionary.

.NET 線性表中順序存儲采用的是數組，而鏈式的存儲方式則是：IList接口。

未完待續…….