线性表练习题4

题目描述：

从顺序表中，删除其值在s与t之间（包含s和t，要求s<t)的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并推出运行。

分析：

这个题目的解决方法和线性表练习题2的解题思路基本一样，可以解决方法有两个，都很容易理解，并且时间复杂度和空间复杂度都不大。

“线性表练习题2”是要求删除值等于x的元素，而该题目要求的是删除介于s和t之间的元素，所以只是判断条件不同而已，其他的完全一样。

思路一：

从头到尾扫描顺序表，我们用i表示扫描的元素的个数，用k记录满足判断条件的元素的个数；

则对于扫描到的每一个元素data[i]，进行判断：

如果data[i]满足判断条件，说明该元素是应该被删除的元素，k的值加1（删除该元素的操作是通过后面的元素向前覆盖的过程完成的），

如果data[i]不满足判断条件，说明该元素不应该被删除，则需要将该元素向前移动k个元素，进而实现覆盖前面的应该被删除的元素。

程序代码：

#include<iostream>
using namespace std;
struct Node
{
	int *data;
	int length;	
};
void Show(Node *L)
{
	for(int i=0;i<L->length;i++)
	cout<<L->data[i]<<" ";
	cout<<endl;
}
void Del_s_t(Node *L,int s,int t)
{
	int k	=	0;
	int i	=	0;
	while(i<L->length)
	{
		if(L->data[i]>=s&&L->data[i]<=t)
			k++;
		else
			L->data[i-k]	=	L->data[i];
			i++;		
	} 
	L->length -=	k;
	Show(L);
}
int main()
{
	Node nde;
	int a[10]	=	{1,2,5,3,4,5,6,7,8,9};
	nde.data 	=	 a;
	nde.length 	= 	10;
	int s,t;
	cin>>s>>t;
	Del_s_t(&nde,s,t); 
	return 0;
} 

4 7
1 2 3 8 9

程序运行过程分析：

思路二：

从头到尾扫描顺序表，我们用i表示扫描的元素的个数，用k记录满足不符合判断条件的元素的个数；

则对于扫描到的每一个元素data[i]，进行判断：

如果data[i]不满足判断条件，说明该元素不应该被删除，则k的值加1，并将i对应的数据赋值给k对应的元素

程序代码：

#include<iostream>
using namespace std;
struct Node
{
	int *data;
	int length;	
};
void Show(Node *L)
{
	for(int i=0;i<L->length;i++)
	cout<<L->data[i]<<" ";
	cout<<endl;
}
void Del_s_t(Node *L,int s,int t)
{
	int k	=	0;
	int i	=	0;
	while(i<L->length)
	{
		if(L->data[i]<s||L->data[i]>t)
			L->data[k++] = L->data[i];	
		i++;
	} 
	L->length =	k;
	Show(L);
}
int main()
{
	Node nde;
	int a[10]	=	{1,2,5,3,4,5,6,7,8,9};
	nde.data 	=	 a;
	nde.length 	= 	10;
	int s,t;
	cin>>s>>t;
	Del_s_t(&nde,s,t); 
	return 0;
} 

程序运行过程分析：

线性表练习题4,布布扣,bubuko.com

线性表练习题4

原文：http://blog.csdn.net/qsyzb/article/details/22779455