顺序表
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; //更新顺序表
}
标签:int,ElemType,王道,++,length,课后,习题,data,前移
From: https://www.cnblogs.com/sinowind/p/16749598.html