## 问题描述 > 长度为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;i<L->length;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(i<L->length){ if(L->data[i]==e){ k++; }else{ L->data[i-k]=L->data[i]; } i++; } L->length=L->length-k; } ~~~ 具体代码见附件2 ## 附件1 ~~~ #include<stdio.h> #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;i<SL.length;i++){ SL.data[i]=2*i+1; } ElemType e=5; int flag; print(&SL); flag=DelX(&SL, e); print(&SL); if(flag==0){ printf("Delete Success!\n"); }else{ printf("Find not the number!\n"); } return 0; } int DelX(SqList *L, ElemType e) { int k=0, i; for(i=0;i<L->length;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;i<L->length;i++){ printf("%d\t",L->data[i]); } printf("\n"); } ~~~ ## 附件2 ~~~ #include<stdio.h> #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;i<SL.length;i++){ SL.data[i]=2*i+1; } ElemType e=5; Print(&SL); DelX(&SL, e); Print(&SL); return 0; } void DelX(SqList *L, ElemType e) { int k=0, i=0; while(i<L->length){ 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;i<L->length;i++){ printf("%d\t",L->data[i]); } printf("\n"); } ~~~