上文對數據結構與算法，有了一個簡單的概述與介紹，這篇文章，我們介紹一中典型數據結構――線性結構。

什么是線性結構，線性結構是最簡單、最基本、最常用的數據結構。線性表是線性結構的抽象(Abstract)， 線性結構的特點是結構中的數據元素之間存在一對一的線性關系。 這

種一對一的關系指的是數據元素之間的位置關系，即： （1）除第一個位置的數據元素外，其它數據元素位置的前面都只有一個數據元素； （2）除最后一個位置的數據元素外，其它數據元素位置的后面都只有一個元素。也就是說，數據元素是一個接一個的排列。因此，可以把線性結構想象為一種數據元素序列的數據結構。

線性結構(List)是由 n(n≥0)個相同類型的數據元素構成的有限序列。對于這個定義應該注意兩個概念：一是“有限” ，指的是線性表中的數據元素的個數是有限的，線性表中的每一個數據元素都有自己的位置(Position)。本書不討論數據元素個數無限的線性表。二是“相同類型” ，指的是線性表中的數據元素都屬于同一種類型。這體現在我們常用的數據結構就是數組，泛型等等他們都是線性結構的。

他們之間的關系 是：線性表的形式化定義為：線性表(List)簡記為 L，是一個二元組， L = (D, R) 其中：D 是數據元素的有限集合。 R 是數據元素之間關系的有限集合。

線性結構的基本操作如下：

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); //按值查找
}

這里為什么是IListDS是與。net自帶IList相區別。對每個方法解釋如下：

1、求長度：GetLength()
初始條件：線性表存在；
操作結果：返回線性表中所有數據元素的個數。
2、清空操作：Clear()
初始條件：線性表存在且有數據元素；
操作結果：從線性表中清除所有數據元素，線性表為空。
3、判斷線性表是否為空：IsEmpty()
初始條件：線性表存在；
操作結果：如果線性表為空返回 true，否則返回 false。
4、附加操作：Append(T item)
初始條件：線性表存在且未滿；
操作結果：將值為 item 的新元素添加到表的末尾。
5、插入操作：Insert(T item, int i)
初始條件：線性表存在，插入位置正確()(1≤i≤n+1,n 為插入前的表長)。
操作結果：在線性表的第 i 個位置上插入一個值為 item 的新元素，這樣使得原序號為 i,i+1,…,n 的數據元素的序號變為 i+1,i+2,…,n+1，插入后表長=原表長+1。 
6、刪除操作：Delete(int i)
初始條件：線性表存在且不為空，刪除位置正確(1≤i≤n,n 為刪除前的表長)。
操作結果：在線性表中刪除序號為 i 的數據元素，返回刪除后的數據元素。刪除后使原序號為 i+1,i+2,…,n 的數據元素的序號變為 i,i+1,…,n-1，刪除后表長=原表長-1。
7、取表元：GetElem(int i)
初始條件：線性表存在，所取數據元素位置正確（1≤i≤n，n 為線性表的表長） ； 操作結果：返回線性表中第 i 個數據元素。
8、按值查找：Locate(T value)
初始條件：線性表存在。
操作結果：在線性表中查找值為 value 的數據元素，其結果返回在線性表中首次出現的值為 value 的數據元素的序號，稱為查找成功；否則，在線性表中未找到值為 value 的數據元素，返回一個特殊值表示查找失敗。

先看最簡單的線性結構――順序表

什么是順序表，線性結構的順序存儲是指在內存中用一塊地址連續的空間依次存放線性表的數據元素，用這種方式存儲的線性就叫順序表(Sequence List)。

順序表儲存結構如圖所示

假設順序表中的每個數據元素占w個存儲單元， 設第i個數據元素的存儲地址為Loc(ai)，則有： Loc(ai)= Loc(a1)+(i-1)*w 1≤i≤n 式中的Loc(a1)表示第一個數據元素a1的存儲地址，也是順序表的起始存儲地址，稱為順序表的基地址(Base Address). 這里我們舉個例子吧，比如你去酒店的時候，知道101號房間的基準的位置，你要去111號房間，你知道每個房間之間的距離是5，那里只需要前進50米。順序表的地址運算就這么簡單。

而順序表是繼承與線性結構，他的源代碼又是這個樣子的。

public class SeqList<T> : IListDS<T> {
private int maxsize; //順序表的容量   順序表的最大容量
private T[] data; //數組，用于存儲順序表中的數據元素 用于存儲順序表的結構 
private int last; //指示順序表最后一個元素的位置  

//索引器
public T this[int index]
{
get
{
return data[index];
}
set
{
data[index] = value;
}
}

//最后一個數據元素位置屬性
public int Last
{
get
{
return last;
}
}

//容量屬性
public int Maxsize
{
get
{
return maxsize;
}

set
{
maxsize = value;
}
}

//構造器 進行函數初始化工作

public SeqList(int size) 

{
data = new T[size];
maxsize = size;
last = -1;
}

//求順序表的長度
public int GetLength()
{
return last+1;
}

//清空順序表

//清除順序表中的數據元素是使順序表為空，此時，last 等于-1。

public void Clear()
{
last = -1;
}

//判斷順序表是否為空

//如果順序表的 last 為-1，則順序表為空，返回 true，否則返回 false。
public bool IsEmpty()
{
if (last == -1)
{
return true;
}
else
{
return false;
}
}


//判斷順序表是否為滿

//如果順序表為滿，last 等于 maxsize-1，則返回 true，否則返回 false。
public bool IsFull()
{
if (last == maxsize-1)
{
return true;
}
else
{
return false;
}
}
//附加操作是在順序表未滿的情況下，在表的末端添加一個新元素，然后使順序表的last加1。

//在順序表的末尾添加新元素
public void Append(T item)
{
if(IsFull())
{
Console.WriteLine("List is full");
return;
}

data[++last] = item;
}
//順序表的插入是指在順序表的第i個位置插入一個值為item的新元素， 插入后使 原 表 長 為 n 的 表 (a1,a2, … ,ai-1,ai,ai+1, … ,an) 成 為 表 長 為 n+1 的 表(a1,a2,…,ai-1,item,ai,ai+1,…,an)。i的取值范圍為 1≤i≤n+1，i為n+1 時，表示在順序表的末尾插入數據元素。 順序表上插入一個數據元素的步驟如下： 

//順序表的刪除操作是指將表中第i個數據元素從順序表中刪除， 刪除后使原表長 為 n 的 表 (a1,a2, … ,ai-1,ai, ai+1, … ,an) 變 為 表 長 為 n-1的 表(a1,a2,…,ai-1,ai+1,…,an)。i的取值范圍為 1≤i≤n，i為n時，表示刪除順序表末尾的數據元素。 

順序表上刪除一個數據元素的步驟如下：
（1）判斷順序表是否為空和刪除的位置是否正確，表空或刪除的位置不正
確不能刪除；
（2）如果表未空和刪除的位置正確，則將ai+1～an依次向前移動。在算法中
用循環來實現；
（3）修改 last（相當于修改表長） ，使它仍指向順序表的最后一個元素。

//取表元運算是返回順序表中第 i 個數據元素，i 的取值范圍是 1≤i≤last+1。由于表是隨機存取的，所以，如果 i 的取值正確，則取表元運算的時間復雜度為O（1） 。

//獲得順序表的第i個數據元素 
public T GetElem(int i)
{
if (IsEmpty() | | (i<1) | | (i>last+1))
{
Console.WriteLine("List is empty or Position is error!");
return default(T);
}

return data[i-1];
}
//順序表中的按值查找是指在表中查找滿足給定值的數據元素。

在順序表中完成該運算最簡單的方法是：從第一個元素起依次與給定值比較，如果找到，則返回在順序表中首次出現與給定值相等的數據元素的序號，稱為查找成功；否則，在順序表中沒有與給定值匹配的數據元素，返回一個特殊值表示查找失敗。

如：已知順序表 L，寫一算法將其倒置，即實現如圖 2.4 所示的操作，其中(a)為倒置前，(b)為倒置后。

我思考的思路就是以所在的中間數進行前后調換。相應的源代碼如下：

還譬如，我就我開發親身經歷而言  在俄羅斯方塊這個項目中，我的順序結構用的確實很多譬如初始化過程中。