第二章 线性表 2.2 线性表的顺序表示和实现

2.4 线性表的顺序表示和实现 2.4.1线性表的的顺序存储结构表示

线性表的顺序存储结构：用一组地址连续的存储单元依次存储线性表的数据元素。
顺序表(Sequential List):== 具有顺序存储结构的线性表为顺序表。==

顺序表需要的三部分：
（1）存储空间的起始位置
（2）顺序表最大存储空间
（3）顺序表当前的长度
顺序表的静态建表：
#define maxsize 50 //定义线性表的最大长度
Typedef int Elemtype //假定表中元素类型是int
Typedef Structure{
Elem type data[maxsize]; //顺序表的元素（数组）
int lengh; //顺序表的当前长度
}Sqlist;
动态分配语句（C语言）
#define IntSize 100
Seqlist.L;
L.data=(Elem.Type*)malloc(sizeof(ElemType)* IntSize);

2.4.2顺序表的基本操作：
1.初始化
2.取值
3.查找
4.插入
线性表的插入操作是指在表的第i个位置插入一个新的数据元素e，使长度为n的线性表变
（a1,…,ai-1,ai,…,an）
成长度为n+1的线性表
（a1,…,ai-1,e,ai,…,an）
算法步骤：
（1）判断插入位置i是否合法
（2）判断顺序表的存储空间是否已满
（3）将第n个至第i个元素依次向后移动一个位置
（4）将e放入第i个位置
（5）表长加1
算法描述：
Status ListInsert (SqList &L, int i, ElemType e)
{//在顺序表L中第i个位置之前插入新的元素e，i值的合法范围是1=<i=<L.length+1
if ((i<1||i>L.length+1)) return ERROR; // i值不合法
if (L.length ==MAXSIZE) return ERROR; //当前存储空间已满
for(j=L.length-1;j>=i-1;j–)
L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移
L.elem[i-1]=e; //将新元素e放入第i个位置
++ L.length; //表长加1
Return OK;
}
顺序表插入算法的平均时间复杂度为O(n).

5.删除
线性表的删除操作是指将表的第i个元素删除，将长度为n的线性表
（a1,…,ai-1,ai,ai+1,…,an）
变成长度为n-1的线性表
（a1,…,ai-1,ai+1,…,an）

算法步骤：
（1）判断插入位置i是否合法
（2）将第i+1个至第n个元素依次向前移动一个位置（i=n时无需移动）
（3）表长减1

算法描述：
Status ListDelete (SqList &L, int i)
if ((i<1||i>L.length+1)) return ERROR; // i值不合法
for(j=i;j=< L.length-1;j++)
L.elem[j-1]=L.elem[j]; //将删除元素之后的元素前移
– L.length; //表长加1
Return OK;
}
顺序表删除算法的平均时间复杂度为O(n).

优点：
（1）存储密度大
（2）随机存取
缺点：
（1）插入和删除操作需要移动大量元素
（2）对存储空间要求高，会产生存储空间碎片