顺序表

1.删除

主要在于删除后，后面元素怎样前移。

1.删除一个值

bool ListDelete(SqList &L, ElemType &e){
    if(i < 1 || i > L.length)
        return false;
    
    e = data[i-1];
    for(int j = i; j < L.length; j++)
        L.data[j-1] = L.data[j];
    L.length--;
    
    return 0;
}

2.删除一定范围的值

模板（通法，不追求完美复杂度）：

①设置k值;记录符合要求的值（或者记录不符合要求的值，但通常时间复杂度要高，故不作讨论）

②如果符合要求，k++;

​ 如果不符合要求，前移k值；

int k = 0;	//记录要删去值的个数
int i = 0;

while(i < L.length){
    if(删除的条件)	//确定前移的个数
        k++;
    else	//前移操作
        L.data[i-k] = L.data[i];
    i++;
}

L.length -= k;	//更新顺序表

例题：

​ 1.在一个顺序表中删除值为x的元素，值为x的元素不唯一。

void del(SqList &L, ElemType x){
	int k = 0;	//记录要删去值的个数
    int i = 0;

    while(i < L.length){
        if(L.data[i] == x)	//确定前移的个数
            k++;
        else	//前移操作
            L.data[i-k] = L.data[i];
        i++;
    }

    L.length -= k;	//更新顺序表
}

2.在一顺序表（有序或无序）中删除所有s到t范围内的值。

void del(SqList &L, ElemType s, ElemType t){
	int k = 0;	//记录要删去值的个数
    int i = 0;

    while(i < L.length){
        if(L.data[i] >= s && L.data[i] <= t)	//确定前移的个数
            k++;
        else	//前移操作
            L.data[i-k] = L.data[i];
        i++;
    }

    L.length -= k;	//更新顺序表
}

针对有序数组，可利用s到t在同一区间进行操作

int Del(SqList &L, ElemType s, ElemType t){
    int i , j;
    
    if(s >= t || L.length == 0)
        return false;
    
    for(i = 0; i < L.length && L.data[i] < s; i++);
    
 	if(i >= L.length)
        return false;
    
    for(j = i; j < L.length && L.data[j] <= t; j++);
   	for(; j < L.lengthg; i++,j++)
        L.data[i] = L.data[j];
    
    L.length = i;
    
    return true;
}

3.对有序顺序表进行去重。

void del(SqList &L, ElemType s, ElemType t){
	int k = 0;	//记录要删去值的个数
    int i = 0;

    while(i < L.length){
        if(L.data[i] == L.data[i-1])	//确定前移的个数
            k++;
        else	//前移操作
            L.data[i-k] = L.data[i];
        i++;
    }

    L.length -= k;	//更新顺序表
}