顺序表的基本操作：插入元素、删除元素和按值查找(顺序查找)[C语言实现]

我们在这里仅给出顺序表的插入操作、删除操作和按值查找的算法，其他基本操作的算法相对都比较简单，请读者自行思考。

1) 插入操作

在顺序表L的第i (1<=L.length+1)个位置插入新元素e。如果i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素以及其后的元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

bool ListInsert(SqList &L, int i, ElemType e){
    //本算法实现将元素e插入到顺序表L中第i个位置
    if ( i<1 || i>L.length+1 )
        return false;  // 判断i的范围是否有效
    if(L.length>=MaxSize)
        return false;  // 当前存储空间已满，不能插入
    for (int j =L.length; j >=i; j--)  // 将第i个位置及之后的元素后移
        L.data[j]=L.data[j-l];
    L.data[i-1]=e; //在位置i处放入e
    L.length++; //线性表长度加1
    return true;
}

注意：区别顺序表的位序和数组下标。理解为什么判断插入位置是否合法时if语句中用 length+1，而移动元素的for语句中只用length？

最好情况：在表尾插入（即i=n+1），元素后移语句将不执行，时间复杂度为O(1)。

最坏情况：在表头插入（即i=1），元素后移语句将执行n次，时间复杂度为O(n)。

平均情况：假设p_i(p_i=1/(n+1))是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为：

因此，线性表插入算法的平均时间复杂度为O(n)。

2) 删除操作

删除顺序表L中第i (1<=i<=L.length)个位置的元素，成功则返回true,否则返回false，并将被删除的元素用引用变量e返回。

bool ListDelete(SqList &L,int i, int &e){
    //本算法实现删除顺序表L中第i个位置的元素
    if(i<1 || i>L.length)
        return false;  // 判断i的范围是否有效
    e=L.data[i-1] ;  // 将被删除的元素赋值给e
    for (int j=i; j<L.length; j++)  //将第i个位置之后的元素前移
        L.data[j-1]=L.data[j];
    L.length--;  //线性表长度减1
    return true;
}

最好情况：删除表尾元素（即i=n），无须移动元素，时间复杂度为O(1)。

最坏情况：删除表头元素（即i=1），需要移动除第一个元素外的所有元素，时间复杂度为O(n)。

平均情况：假设Pi(Pi=1/n)是删除第i个位置上结点的概率，则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为：

因此，线性表删除算法的平均时间复杂度为O(n)。

如图2-2所示为一个顺序表在进行插入和删除操作的前、后状态，其数据元素在存储空间中的位置变化以及表长的变化。在图2-2 (a)中，元素移动是从后往前依次后移一个元素，在图2-2b中，元素移动是从前往后依次前移一个元素。

图2-2  顺序表的插入和删除

3) 按值查找（顺序查找）

在顺序表L中查找第一个元素值等于e的元素，并返回其下标。

int LocateElem(SqList L, ElemType e){
    //本算法实现查找顺序表中值为e的元素，如果查找成功，返回元素位序，否则返回0
    int i;
    for(i=0;i<L.length;i++)
        if(L.data[i]==e)
            return i+1;  // 下标为i的元素值等于e，返回其位号i+1
    return 0;  //退出循环，说明查找失败
}

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)。

最坏情况：查找的元素在表尾（或不存在时），需要比较n次，时间复杂度为O(n)。

平均情况：假设p_i(p_i=1/n)是查找的元素在第i个位置上的概率，则在长度为n的线性表中查找值为e的元素所需比较的平均次数为：

因此，线性表按值查找算法的平均时间复杂度为O(n)。