线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，而且可以进行插入和删除等操作。
顺序表的存储结构如下：
//-----顺序表的存储结构-----
#define MAXSIZE 100
typedef struct{
ElemType *elem; //存储空间的基地址
int length; //当前长度
}SqList; //顺序表的结构类型为SqList
(1)顺序表的初始化
即为顺序表L动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址，同时将表的当前长度设为0.
Status InitList(SqList &L){
//构造一个空的顺序表L
L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
if(!L.elem){
exit(OVERFLOW); //存储分配失败退出
}
L.length = 0; //空表长度为0
return OK;
}
（2）顺序表的取值
首先判断制定的位置序号i值是否合理（1≤i≤L.length），若不合理，则返回ERROR。若i值合理，则将第i个元素L.elem[i-1]赋给参数e，通过e返回第i个数据元素的传值。
Status GetElem(SqList L, int i, ElemType &e){
if(i < 1 || i > L.length){
return ERROR; //判断i值是否合理，若不合理，返回ERRROR
}
e = L.elem[i-1]; //elem[i-1]单元存储第i个数据元素
return OK;
}
（3）顺序表的查找
从第一个元素起，依次和e相比较，若找到与e相等的元素L.elem[i]，则查找成功，返回该元素的序号i+1，若查遍整个顺序表都没有找到，则查找失败，返回0.
int LocateElem(SqList L, ElemType e){
//在顺序表L中查找值为e的数据元素，返回其序号
for(i = 0;i < L.length;i++){
if(L.elem[i] == e){
return i+1; //查找成功，返回序号i+1
}
}
return 0; //查找失败，返回0
}
(4)顺序表的插入
1.判断插入位置i是否合法（i值的合法范围为1≤i≤n+1），若不合法则返回ERROR。
2.判断顺序表的存储空间是否已满，若满则返回ERROR。
3.将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置（i=n+1时无需移动）
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 = e; //将新元素e放入第i个位置
++L.length; //表长加1
return OK;
}
（5）顺序表的删除
1.判断删除位置i是否合法（合法值为1≤i≤n），若不合法则返回ERROR。
2.将第i+1个至第n个的元素依次向前移动一个位置（i=n时无需移动）。
3.表长减1.
Status ListDelete(SqList &L,int i){
//在顺序表L中删除第i个元素，i值的合法范围是 1≤i≤L.length
if((i < 1)||(i > L.length)){
return ERROR; //i值不合法
}
for(j = i;j<=L.length-1;j++){
L.elem[j-1] == L.elem[j]; //被删除的元素之后的元素前移
}
--L.length; //表长减1
return OK;
}
总结：
顺序表可以随机存取表中的任一元素，其存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的缺点：在做插入或删除操作时，需移动大量元素。另外由于数组有长度相对固定的静态特性。当表中数据元素个数较多且变化较大时，操作过程相对复杂，必然导致存储空间的浪费。
网友评论