线性表顺序存储插入和删除操作

线性表的操作：1、InitList(*L):初始化操作,建立一个空的线性表L

2、ListEmpty(L):判断线性表是否为空，如果为空，返回true，否则返回false

           3、ClearList(*L):将线性表清空

           4、GetElem(L,I,*e):将线性表中的第i个位置元素值返回给e

              5、LocateElem(L,e):在线性表中查找与定值e相等的元素，如果查找成功，返回钙元素在表中序号，返回0表示失败

              6、ListInsert(*L,i,e):在线性表中第i个位置插入新元素e

              7、ListDelete(*L,i,*e):删除线性表中第i个位置元素，并用e返回其值

              8、ListLength(L):返回线性表L的元素个数

一、插入操作举例：实现A=AUB;

代码：

Void unionL(List  *La, List Lb)

{

Int  La_len , Lb_len , i ;

ElemType  e;

La_len =ListLength(*La);

Lb_len= ListLength(Lb);

For( i = 1; I <=Lb_len; i++)

{

    GetElem(Lb,i,&e);

    If(!LocateElem(*La, e))

    {

        ListInsert(La, ++La_len, e);

}

}

}

二、删除操作

1、  删除操作的思路： —如果删除位置不合理，抛出异常

                 —取出删除元素

                    —从删除元素位置开始遍历到最后一个元素位置，分别将他们向前移

动一个位置

2、  删除操作代码：

int ListDelete(SqList  *L, int i, ElemType *e)

{

int  k;

if(L->length  ==  0)

{

    return  0;

}

if(i < 1 | i> L->length)

{

    return  0;

}

*e =L->data[i-1];

if( i < L->length)

{

    For( k = i; k < L->length; k++)

    {

    L->data[k-1] = L->data[k];

}

}

L->length--;

return  0;

}

三、分析插入操作和删除操作的时间复杂度：

最好的情况：插入和删除操作都刚好要求在最后一个位置操作，因此不需要移动任何位置，所以此时的时间复杂度为O(1);

最坏的情况:如果要插入和删除的位置是第一个元素，那就意味着所有的元素向后或者向前，所以时间复杂度为O(n);

在存、读数据时，不管是什么位置，时间复杂度都是O(1),而在插入或者删除时，时间复杂度都是O(n)。说明顺讯存储结构适合元素个数稳定，存取数据的应用

一、线性表顺序存储结构的优缺点

优点：

1、  无需为表中元素之间的逻辑关系二增加额外的存储空间

2、  可以快速的存取表中任意位置的元素

缺点：

1、  插入和删除操作需要移动大量元素

2、  当线性表长度变化较大时，难以准确确定存储空间的容量

3、  容易造成存储空间的碎片