1.线性表的顺序存储结构

线性表的顺序存储是最常用的存储方式，它直接将线性表的逻辑结构映射到存储结构上，所以既便于理解，又容易实现。

2.线性表的顺序存储结构——顺序表

2.1顺序表的定义

顺序表是一种存储结构，是线性表在内存中的一种直接映射方式。在顺序表中，采用以下字段存放数据：

string[ ] data; //存放顺序表中的元素

int length; //存放顺序表的长度

说明：顺序表的data数组可以是任意合法的数据类型，这可以通过C#泛型编程来实现。为了简便，这里假设顺序表元素为string类型。

顺序表存储结构如图所示，它具有随机存取特性。所谓随机存取特性，是指通过首地址和元素序号可以在O(1)时间内找到指定的元素。

顺序表存储结构

顺序表的特点如下：

（1)顺序表属直接映射（逻辑上相邻的元素其物理位置也相邻），具有随机存取特性。

（2)顺序表存储密度高。存储密度 = 结点数据本身占用的存储量 / 结点结构占用存储量，顺序表的存储密度为1，链表的存储密度小于1（需用指针来表示逻辑关系）。

（3)顺序表中插入和删除元素需大量移动元素。

说明：线性表中元素ai（1≤i≤n)的逻辑序号为i，在对应顺序表中该元素的物理序号为i-1。算法形参中的序号i通常指的是逻辑序号。

2.2顺序表中插入元素操作

在顺序表中位置i（i为逻辑序号，1≤i≤n+1)插入元素x的操作是：

将原顺序表中ai元素及之后的所有元素后移一个位置（即将ai...n所有元素后移一个位置，共移动n-i+1个元素)，再将插入的元素放在该位置上，如图[在顺序表中插入原素x]所示，所以移动的次数与表长n有关；插入一个元素时所需移动元素的平均次数为

所以插入元素算法的时间复杂度为O(n)

在顺序表中插入元素x

2.3顺序表中删除元素操作

删除顺序表中ai（i为逻辑序号，1≤i≤n）

元素的操作是：

将ai元素之后的所有元素前移一个位置覆盖该元素（即将ai+1...n所有元素后移一个位置，共移动了n-(i+1)+1=n-i个元素），如图所示，所以移动的次数与表长n有关。删除一个元素时所需移动元素的平均次数为

所以删除元素算法的时间复杂度为O(n)。

在顺序表中删除元素ai

<下一节：顺序表实践项目及其设计> 结合以上所讲述的内容，使用编程语言实现顺序表的操作