线性表的顺序存储结构

标签（空格分隔）： DS 线性表 顺序存储

1.线性表的顺序存储结构

#define MAXSIZE 20//数组最大长度
typedef struct
{
ElemeType data[MAXSIZE];//数组顺序存储元素，data即为存储空间的起始位置
int length;//线性表当前长度:表中元素的个数length<=MAXSIZE
}SqList，*SqList;

2.获得第i个元素操作

注意：	
1.出错判断
    1.1线性表是否空表
    1.2.i是否合法，合法的i应在[1,length],若不合法，即i<1||i>length
2.线性表如果有第i个元素，用指针e返回data[i-1].

Status GetElem(SqList L, int i, ElemType *e)
{
    //出错判断
    If(L.length==0||i<1||i>L.length)
    return ERROR;
    //没有错误，用指针e返回第i个元素
    *e=L.data[i-1];
    return OK;
}

3.插入第i个元素

插入算法的思路:
1.判断错误
    1.1判断线性表是否已满，还能否插入，若已满，则不能插入；
    1.2判断i是否合法,合法应在[1,length+1],即可以在第i个位置插入;不合法为i<1||i>length+1
2.插入元素
    2.1若插入位置不在表尾，即i!=length+1，则从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置;
    2.2将要插入的元素e填入位置i处;
    2.3表长加1。

Status ListInsert(SqList *L, int i, Elemtype e)
{
//判断错误
If(L->length==MAXSIZE)
return ERROR;
If(i<1||i>L->length+1)
Return ERROR;

//插入元素
if(i<=L->length)//或者i!=L->length+1
{
    Int k;//k为数组下标
    for(k=L->length-1;k>=i-1;k--)
         L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
L->length++;
return OK;
}

4.删除第i个元素

思路：
1.判断错误
    1.1线性表若为空，则无元素可删
    1.2删除的位置不正确，正确的位置i为[1,length],即可以删除第1到第length（最后）个元素，不正确的i为i<1||i>length
2.删除元素
    2.1用指针e存储返回被删除的元素
    2.2若删除的元素不在最后一个，即i!=length,则从元素位置到最后一个元素前移
    2.3表长减一

Status ListDelete(SqList *L, int i,ElemType *e)
{
    //判断错误
    if(L->length==0||i<1||i>L->length)
        return ERROR;
    
    //删除元素
    *e=L->data[i-1];
    if(i!=L->length)//或者i<L->length
    {
        int k;//数组下标
        for(k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}