PTA 7-2 jmu-ds-顺序表区间元素删除 (15 分)

若一个线性表L采用顺序存储结构存储，其中所有的元素为整数。设计一个算法，删除元素值在[x,y]之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。

输入格式:

三行数据，第一行是顺序表的元素个数，第二行是顺序表的元素，第三行是x和y。

输出格式:

删除元素值在[x,y]之间的所有元素后的顺序表。

输入样例:

10 5 1 9 10 67 12 8 33 6 2 3 10

输出样例:

1 67 12 33 2

#include <stdio.h> #define SIZE_MAX 100 typedef int ElemType; int a[100]; typedef struct{ ElemType data[SIZE_MAX]; int last; }SequenList; void InitList(SequenList *sl) { sl->last = 0; } void CreateList(SequenList *sl,int n) { int i; for(i = 0;i<n;i++) { sl->data[i] = a[i]; } sl->last = n; } int Delete(SequenList *sl,ElemType x,ElemType y) { int i,k = 0; if(x > y) { return 0; } for(i = 0;i < sl->last;i++) { if(sl->data[i] < x || sl->data[i] > y) { sl->data[k] = sl->data[i]; k++; } } sl->last = k; return 1; } void OutputList(SequenList *sl) { int i; //printf("%d\n",sl->last); for(i = 0;i<sl->last-1;i++) { printf("%d ",sl->data[i]); } printf("%d",sl->data[sl->last-1]); } int main() { SequenList Lp; int n,i; int x,y;//删除元素的区间 scanf("%d",&n); //输入线性表的长度n，n小于等于最大长度 for(i = 0;i<n;i++){ scanf("%d",&a[i]); } scanf("%d %d",&x,&y); InitList(&Lp); CreateList(&Lp,n); if(Delete(&Lp,x,y)) OutputList(&Lp); return 0; }