第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"); } ~~~
';