第1章第1节练习题3 删除指定元素
最后更新于：2022-04-01 19:50:13
## 问题描述
> 长度为n的顺序表L，编写一个时间复杂度为O(n)，空间复杂度为O(1)的算法，该算法删除线性表中所有值为e的数据元素
## 算法思想1
> 用k记录顺序表L中不等于e的元素个数（即需要保存的元素个数），边扫描边统计k，并将不等于e的元素向前放置到k的位置上，最后修改顺序表的长度。
## 算法描述
~~~
void DelX(SqList *L, ElemType e)
{
int k=0, i;
for(i=0;ilength;i++){
if(L->data[i]!=e){
L->data[k++]=L->data[i];
}
}
L->length=k;
}
~~~
具体代码见附件1
## 算法思想2
> 用k记录顺序表L中等于e的元素个数，边扫描边统计k，并将不等于e的元素向前移k个位置，最后修改L的长度。
## 算法描述
~~~
void DelX(SqList *L, ElemType e)
{
int k=0, i=0;
while(ilength){
if(L->data[i]==e){
k++;
}else{
L->data[i-k]=L->data[i];
}
i++;
}
L->length=L->length-k;
}
~~~
具体代码见附件2
## 附件1
~~~
#include
#define MaxSize 100
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
int DelX(SqList *, ElemType);
void print(SqList *);
int main(int argc, char* argv[])
{
SqList SL;
SL.length=10;
for(int i=0;ilength;i++){
if(L->data[i]!=e){
L->data[k++]=L->data[i];
}
}
if(L->length==k){
return -1;
}else{
L->length=k;
return 0;
}
}
void print(SqList *L)
{
for(int i=0;ilength;i++){
printf("%d\t",L->data[i]);
}
printf("\n");
}
~~~
## 附件2
~~~
#include
#define MaxSize 100
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
void DelX(SqList *, ElemType);
void Print(SqList *);
int main(int argc, char* argv[])
{
SqList SL;
SL.length=10;
for(int i=0;ilength){
if(L->data[i]==e){
k++;
}else{
L->data[i-k]=L->data[i];
}
i++;
}
L->length=L->length-k;
}
void Print(SqList *L)
{
for(int i=0;ilength;i++){
printf("%d\t",L->data[i]);
}
printf("\n");
}
~~~
';