目录
1 线性表的概念及运算
1.1线性表的逻辑结构
线性表的定义
线性表(Linear List)是由n (n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1， …，an）。
数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。
线性表的逻辑结构图为：
线性表的特点
同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。
有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。
有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。
1.2线性表的抽象数据类型定义
抽象数据类型定义 ：
2 线性表的顺序存储
2.1 线性表的顺序存储结构
顺序存储结构的定义
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。
假设线性表中每个元素占k个单元，第一个元素的地址为loc(a1)，则第k个元素的地址为： loc(ai) =loc(a1)+(i-1)×k
顺序存储结构示意图：
顺序存储结构的C语言定义：
2.2 线性表顺序存储结构上的基本运算
线性表的基本运算：
查找操作
插入操作
删除操作
顺序表合并算法
线性表的两种基本
查找
运算
1.按序号查找GetData(L,i)：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。
2.按内容查找Locate（L,e）: 要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空序号”，
如-1。 线性表的查找运算算法描述为：
int Locate(SeqList L，ElemType e)
{ i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
while ((i<=L.last)&&(L.elem[i]!=e) ) i++;
/*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/
if (i<=L.last)
return(i); /*若找到值为e的元素，则返回其序号*/
else
return(-1); /*若没找到，则返回空序号*/
}
插入操作
线性表的插入运算是指在表的第i (1≤i≤n+1)个位置，插入一个新元素e，使长度为n的线性表 (e1，…，ei-1，ei，…，en) 变成长度为n+1的线性表（e1，…,ei-1，e，ei，…，en）。
插入算法示意图
插入运算：
int InsList(SeqList *L,int i,ElemType e)
{ int k;
if( (i<1) || (i>L->last+2) ) /*首先判断插入位置是否合法*/
{ printf(“插入位置i值不合法”)；return(ERROR); }
if(L->last>=maxsize-1)
{ printf(“表已满无法插入”)； return(ERROR); }
for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e; /*在C语言中数组第i个元素的下标为i-1*/
L->last++;
return(OK);
}
删除操作
线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表 (e1，…,ei-1，ei，ei+1，…，en)，变成长度为n-1的线性表(e1，…,ei-1， ei+1，…，en)。
删除算法示意：
删除算法：
int DelList(SeqList *L,int i,ElemType *e)
/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/
{ int k;
if((i<1)||(i>L->last+1))
{ printf(“删除位置不合法！”)； return(ERROR)； }
*e= L->elem[i-1]; /* 将删除的元素存放到e所指向的变量中*/
for(k=i;i<=L->last;k++)
L->elem[k-1]= L->elem[k]; /*将后面的元素依次前移*/
L->last--;
return(OK);
}
合并算法
已知 ：有两个顺序表LA和LB，其元素均为非递减有序排列，编写一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。
算法思想
：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、j分别指向表LA和LB中的元素，若LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，若LA.elem[i]≤LB.elem[j] ，当前先将LA.elem[i]插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。
顺序表合并算法实现
：
void merge(SeqList *LA, SeqList *LB, SeqList *LC)
{ i=0;j=0;k=0;
while(i<=LA->last&&j<=LB->last)
if(LA->elem[i]<=LB->elem[j])
{ LC->elem[k]= LA->elem[i]; i++; k++; }
else
{ LC->elem[k]=LB->elem[j]; j++; k++; }
while(i<=LA->last) /*当表LA长则将表LA余下的元素赋给表LC*/
{ LC->elem[k]= LA->elem[i]; i++; k++; }
while(j<=LB->last) /*当表LB长则将表LB余下的元素赋给表LC*/
{ LC->elem[k]= LB->elem[j]; j++; k++; }
LC->last=LA->last+LB->last;
}
3 顺序存储结构的优点和缺点：
优点
：
1.无需为表示结点间的逻辑关系而增加额外的存储空间；
2.可方便地随机存取表中的任一元素。
缺点
：
1.插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须 移动大量的结点，其效率较低；
2.由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化 较大时，难以确定合适的存储规模。