上文对数据结构与算法，有了一个简单的概述与介绍，这篇文章，我们介绍一中典型数据结构——线性结构。

什么是线性结构，线性结构是最简单、最基本、最常用的数据结构。线性表是线性结构的抽象(Abstract)， 线性结构的特点是结构中的数据元素之间存在一对一的线性关系。 这

种一对一的关系指的是数据元素之间的位置关系，即： （1）除第一个位置的数据元素外，其它数据元素位置的前面都只有一个数据元素； （2）除最后一个位置的数据元素外，其它数据元素位置的后面都只有一个元素。也就是说，数据元素是一个接一个的排列。因此，可以把线性结构想象为一种数据元素序列的数据结构。

线性结构(List)是由 n(n≥0)个相同类型的数据元素构成的有限序列。对于这个定义应该注意两个概念：一是“有限” ，指的是线性表中的数据元素的个数是有限的，线性表中的每一个数据元素都有自己的位置(Position)。本书不讨论数据元素个数无限的线性表。二是“相同类型” ，指的是线性表中的数据元素都属于同一种类型。这体现在我们常用的数据结构就是数组，泛型等等他们都是线性结构的。

他们之间的关系 是：线性表的形式化定义为：线性表(List)简记为 L，是一个二元组， L = (D, R) 其中：D 是数据元素的有限集合。 R 是数据元素之间关系的有限集合。

线性结构的基本操作如下：

public interface IListDS {
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 : IListDS {
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(ilast+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