## 問題描述 > 長度為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"); } ~~~