C语言从有序顺序表中删除其值在给定值s与t之间的所有元素

这里涉及到数据结构中顺序表的实现、删除、插入、查找等知识，请查看：数据结构 -> 线性表

问题描述：

问题1)：从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，如果s或t 不合理或者顺序表为空则显示出错信息并退出运行。

问题2)：从顺序表中删除其值在给定值s与t之间（包含s和t，要求s<t）的所有元素，如果 s或t不合理或者顺序表为空则显示出错信息并退出运行。

问题解答：

注意，因为是有序表，所以删除的元素必然是相连的整体。

问题1)：

算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素)，然后寻找值>t 的第一个元素（最后一个删除的元素的下一个元素)，要将这段元素删除，则只需直接将后面的元素前移即可。

bool Del_s_t2(sqList &L, ElemType s, ElemType t){
    //删除有序顺序表L中值在给定值s与t之间的所有元素
    int i,j;
    if(s>=t) || L.length==0)
        return false;
    for (i=0; i<L.length && L.data[i] <s; i++) ;    //寻找值>=s 的第一个元素
    if(i>=L.length)
        return false;  //所有元素值均小于s，则返回
    for(j=i; j<L.length && L.data[j] <=t; j++) ;    //寻找值>t 的第一个元素
    for(;j<L.length;i++, j++)
        L.data[i]=L.data[j];  //前移，填补被删元素位置
    L.length=i;
    return true;
}

问题2)：

算法思想：从前向后扫描顺序表L，用k记录下元素值在s到t之间元素的个数（初始时k=0）。对于当前扫描的元素，若其值不在s到t之间，则前移k个位置；否则，删除该元素，并执行k++。由于这样每个不在s到t之间的元素仅移动一次，所以算法效率高。

本题代码如下：

bool Del_s_t (sqList &Lf ElemType s, ElemType t) {
    //删除顺序表L中值在给定值s与t之间（要求s<t）的所有元素
    int i,k=0;
    if (L.length==0 || s>=t)
        return false;  //线性表为空或s、t不合法，返回
    for(i=0;i<L.length;i++){
        if (L.data[i] >= s && L.data[i] <= t)
            k++;
        else
            L.data [i-k] = L.data[i];  //当前元素前移 k 个置
    } //for
    L.length-=k;  // 长度减小
    return true;
}

注意：本题也可以从后向前扫描顺序表，每遇到一个值在S到t之间的元素，则删除该元素，其后的所有元素全部前移。但移动次数远大于前者，效率不够高。