线性表的概念及运算
定义:线性表是由n个类型相同的数据元素a1,a2……an组成的有限序列
记作(a1,a2……ai,ai+1……an)
数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继
逻辑结构图

线性表的特点:
1.同一性:线性表由同类数据元素组成,每一个ai必须属于同一数据对象
2.有穷性:线性表由有限个数据元素组成,表长度就是表中数据元素的个数
3.有序性:线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>
线性表的顺序存储
定义:是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。
采用顺序存储结构的线性表通常称为顺序表。
假设线性表中每个元素占k个单元,第一个元素的地址为loc(a1),则第i个元素的地址为:loc(ai)=loc(ai)+(i-1)*k
基本运算:1.查找操作 2.插入操作 3.删除操作
1.查找操作:按序号查找GetData(L,i): 要求查找线性表L中第i个数据元素,其结果是L.elem[i]。
(1).按内容查找Locate(L,x): 要求查找线性表L中给定值x相等的数据元素,其结果是:若在表L中找到与x相等的元素,则返回该元素在表中的序号;若找不到,则返回一个“空序号”,如-1.
int Locate(SeqList L,ElemType x){
int i;
while(i<=L.length)&&(L.elem[i]!=x)
i++;
if(i<=L.length) return(i);
else return(-1);
}
2.插入操作:是指在表的第i(1<=i<=n+1)个位置,插入一个新元素e,使长度为n的线性表(e1,……ei-1,ei……en)变成长度为n+1的线性表(e1,……ei-1,X,ei……en)

3.删除操作:是指将表的第i(1<=i<=n)个元素删去,是长度为n的线性表 (e1,……ei-1,ei,ei+1……en) ,变成长度为n-1的线性表 (e1,……ei-1,ei+1……en)

线性表的顺序存储优缺点
优点
1.用数据存储元素,操作方法简单,容易实现
2.无须为表示节点间的逻辑关系而增加额外的存储开销。
3.存储密度高。
4.顺序表可按元素位序随机存取节点。
缺点
1.插入或删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作都必须移动大量的节点,其效率较低;
2.由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配。因此当表长变化较大时,难以确定合适的存储规模。