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

寻寻寻寻

已于 2024-09-12 14:36:58 修改

阅读量525

点赞数

分类专栏：原创编程题AC代码文章标签：数据结构算法

于 2020-11-30 20:05:02 首次发布

本文链接：https://blog.csdn.net/SDU_st/article/details/110403972

版权

原创编程题AC代码专栏收录该内容

14 篇文章

订阅专栏

设计一个O(n)时间复杂度、O(1)空间复杂度的算法，用于顺序表中删除[x,y]区间内的整数元素。输入包括顺序表长度、元素及区间[x,y]，输出是删除指定区间元素后的顺序表。" 112820288,10541874,Python VideoCapture 模块详解,"['Python开发', '视频处理', '图像处理', 'DirectX', '模块使用']

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

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<iostream>
#define MAX_DATE 100
using namespace std;
typedef int Elemtype;
typedef struct {
	Elemtype *date;
	int Lenlist;
} List;
void InitList(List &l,Elemtype &n1) {
	l.Lenlist=0;
	l.date= new Elemtype[n1+1];
}

void CreatList(List &l,int len){
	for(int i=0;i<len;i++){
		cin>>l.date[i];
		l.Lenlist++;
	}
	
}
void ChangeList(List &l,int m,int n){
	for(int i=0;i<l.Lenlist;i++){
		if(m<=l.date[i]&&l.date[i]<=n ){
			l.Lenlist--;
			for(int j=i;j<l.Lenlist;j++)
			l.date[j]=l.date[j+1];	
			i--;		
		}
	}
}
void OutPut(List &l){	int p=0;
	for(int i=0;i<l.Lenlist;i++){
	
		if(p==1){
			cout<<" ";
		}
		else {
			p=1;
		}
		cout<<l.date[i];
		
	}
}
void DesList(List &l) {
	delete[] l.date;
	l.date=NULL;
}
int main() {
//	freopen ("in.txt","r",stdin);
	
	List l1;
	int n;
	cin>>n;
	InitList(l1,n);
	CreatList(l1,n);
	int M,N;
	cin>>M>>N;
	ChangeList(l1,M,N);
	OutPut(l1);
	DesList(l1);
}