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

什么是線性結構，線性結構是最簡單、最基本、最常用的數據結構。線性表是線性結構的抽象(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 時，表示在順序表的末尾插入數據元素。 順序表上插入一個數據元素的步驟如下： 

//（1）判斷順序表是否已滿和插入的位置是否正確，表滿或插入的位置不正確不能插入；
//（2）如果表未滿和插入的位置正確，則將an～ai依次向后移動，為新的數據元素空出位置。在算法中用循環來實現；
//（3）將新的數據元素插入到空出的第 i 個位置上；
//（4）修改 last（相當于修改表長） ，使它仍指向順序表的最后一個數據元素。

//在順序表的第i個數據元素的位置插入一個數據元素
public void Insert(T item, int i)
{
if (IsFull())
{
Console.WriteLine("List is full");
return;
}

if(i<1 | i>last+2)
{
Console.WriteLine("Position is error!");
return;
}

if (i == last + 2)
{
data[last+1] = item; 
}
else
{
for (int j = last; j>= i-1; --j)
{
data[j + 1] = data[j];
}

data[i-1] = item;
}
++last;
}

算法的時間復雜度分析：順序表上的插入操作，時間主要消耗在數據的移動上， 在第i個位置插入一個元素， 從ai到an都要向后移動一個位置， 共需要移動n-i+1
個元素，而i的取值范圍為 1≤i≤n+1，當i等于 1 時，需要移動的元素個數最多，為n個；當i為n+1 時，不需要移動元素。設在第i個位置做插入的概率為pi，則平
均移動數據元素的次數為n/2。這說明：在順序表上做插入操作平均需要移動表中一半的數據元素，所以，插入操作的時間復雜度為O（n） 。

//順序表的刪除操作是指將表中第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個數據元素
public T Delete(int i)
{
T tmp = default(T);
if (IsEmpty())
{
Console.WriteLine("List is empty");
return tmp;
}

if (i < 1 | i > last+1)
{
Console.WriteLine("Position is error!");
return tmp;
}

if (i == last+1)
{
tmp = data[last--];
}
else
{
tmp = data[i-1];
for (int j = i; j <= last; ++j)
{
data[j] = data[j + 1];
}
}

--last;
return tmp;
}

算法的時間復雜度分析：順序表上的刪除操作與插入操作一樣，時間主要消耗在數據的移動上。在第i個位置刪除一個元素，從ai+1到an都要向前移動一個位置，共需要移動n-i個元素，而i的取值范圍為 1≤i≤n，當i等于 1 時，需要移動的元素個數最多，為n-1 個；當i為n時，不需要移動元素。設在第i個位置做刪除的概率為pi，則平均移動數據元素的次數為(n-1)/2。這說明在順序表上做刪除操作平均需要移動表中一半的數據元素，所以，刪除操作的時間復雜度為O（n） 。

//取表元運算是返回順序表中第 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];
}
//順序表中的按值查找是指在表中查找滿足給定值的數據元素。 在順序表中完成該運算最簡單的方法是：從第一個元素起依次與給定值比較，如果找到，則返回在順序表中首次出現與給定值相等的數據元素的序號，稱為查找成功；否則，在順序表中沒有與給定值匹配的數據元素，返回一個特殊值表示查找失敗。

//在順序表中查找值為value的數據元素
public int Locate(T value)
{
if(IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}

int i = 0;
for (i = 0; i <= last; ++i)
{
if (value.Equals(data[i]))
{
break;
}
}

if (i > last)
{
return -1;
}
return i;
}
}

算法的時間復雜度分析：順序表中的按值查找的主要運算是比較，比較的次數與給定值在表中的位置和表長有關。當給定值與第一個數據元素相等時，比較次數為 1；而當給定值與最后一個元素相等時，比較次數為 n。所以，平均比較次數為(n+1)/2，時間復雜度為 O（n） 。

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

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

public void ReversSeqList(SeqList<int> L)
{
int tmp = 0;
int len = L.GetLength();
for (int i = 0; i<= len/2; ++i)
{
tmp = L[i];
L[i] = L[len - i];
L[len - i] = tmp;
}
}

該算法只是對順序表中的數據元素順序掃描一遍即完成了倒置， 所以時間復雜度為 O(n)。其中運行效果如圖所示：

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

// 初始化形狀集合，共七種形狀
_pieces = new List<PieceBase> { new I(), new L(), new I2(), new L2(), new N(), new N2(), new O(), new T() };
// 初始化方塊容器（用 Block 對象填滿整個容器）
Container = new Block[_rows, _columns];
for (int i = 0; i < _rows; i++)
{
for (int j = 0; j < _columns; j++)
{
var block = new Block();
block.Top = i * block.rectangle.ActualHeight;
block.Left = j * block.rectangle.ActualWidth;
block.Color = null;
Container[i, j] = block;
}
}

// 初始化下一個形狀的容器（用 Block 對象將其填滿）
NextContainer = new Block[4, 4];
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
var block = new Block();
block.Top = i * block.rectangle.ActualHeight;
block.Left = j * block.rectangle.ActualWidth;
block.Color = null;
NextContainer[i, j] = block;
}
}

// 創建一個新的形狀
CreatePiece();
// 呈現當前創建出的形狀
AddPiece(0, 0);

// Timer 用于定時向下移動形狀
_timer = new DispatcherTimer();
_timer.Interval = TimeSpan.FromMilliseconds(_initSpeed);
_timer.Tick += _timer_Tick;
GameStatus = GameStatus.Ready;

你看看我用的初始化方塊容器，這個容器是二維數組，這就是一種明顯的順序表。將他top位置，left位置賦值，進行一系列初始化工作。這就等同于順序表初始化操作。這個算法的復雜度為O（n²）。

本文中，我們討論了什么是線性結構，線性結構有哪些特點，并且詳細介紹了一個最簡單線性結構順序表，并且通過源代碼對她進行一些列的分析，最后還舉了兩個例子，讓我們更好的理解順序表。