在文章开头想再强调一个概念：线性表是一个逻辑结构，顺序表和链表属于存储结构。

目录

1、顺序表的定义

2、顺序表的特点

3、顺序表上基本操作的实现

3.1、插入操作

3.2、删除操作

3.3、按值查找（顺序查找）

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为：

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定好，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序奔溃甚至引起其他未知异常。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦存储空间占满，就另外开辟一块更大的存储区间，将原来的元素复制过去，从而达到扩充存储数组空间的目的，而不需要一次性分配很大的空间。

C语言的初始动态分配语句为：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);

C++语言的初始化动态分配语句为：L.data=new ElemType[InitSize];

注意：动态存储并不是练市存储，它同样属于顺序存储，物理结构没有变化，还是和逻辑结构一样保持相邻，只是分配的空间不再是编译器决定，而是运行时分配。

随机访问：可通过首地址和元素序号在单位时间O(1)内找到指定的元素。

存储密度高：存储密度高是因为每个结点存储空间指用来存储数据元素，没有别的额外开销。

物理位置相邻：物理位置和逻辑位置一样，保持相邻，因此插入和删除元素需要移动大量元素，比较耗时。这是物理结构相邻的所有数据结构的通病，虽然访问快，但是如果有频繁的增删移动操作，就会效率很低。

仅展示查、增、删三种操作，其余的在线性表中较为简单，在后续更复杂的链表中展示。

在顺序表L的第i（1= i; j--)  //将第i个元素以及之后的元素后移一位         L.data[j] = L.data[j - 1];     L.data[i - 1] = e;   //在第i位插入元素e     L.length++;     //顺序表长度加1     return true; }

最好情况：在表尾插入（即i=n+1）,原本的元素不移动，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），所有元素需要后移一位，元素后移语句执行n次，时间复杂度为O(n)。

平均情况：假设Pi(Pi=1/(n+1))是在第i个位置上插入一个结点的概率，则在长度为n的顺序表中插入一个结点时，所需要移动结点的平均次数为n/2，时间复杂度为O(n)。

删除顺序表L中第i（1