线性表顺序存储

#define MaxSize 50
typedef struct
{
	ElemType data[MaxSize];
	int length;
}SqList;
           

设计一个高效的算法，将顺序表的所有元素逆置，要求算法的空间复杂度为o(1)

void reverse(SqList *p)
{
	ElemType a;
	int i=0,j=p->length-1;
	while(i<j)
	{
		a=p->data[i];
		p->data[i]=p->data[j];
		p->data[j]=a;
		i++;
		j--;
	}
}
           

长度为n的顺序表L，编写一个时间复杂度为o(n)，空间复杂度为o(1)的算法，该算法删除线性表中所有值为x的数据元素

//长度为n的顺序表L，编写一个时间复杂度为o(n)，空间复杂度为o(1)的算法，该算法删除线性表中所有值为x的数据元素
void delete_x_l(SqList *p,ElemType x)
{
	int k=0;    //记录值不等于x的元素个数
	for(int i=0;i<p->length;i++)
		if(x!=p->data[i])
		{
			p->data[k]=p->data[i];
			k++;
		}
	p->length = k;
}
           

从有序顺序表中删除在给定值s与t之间（s<t）的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并退出运行

//从有序顺序表中删除在给定值s与t之间（s<t）的所有元素，如果s或t不合理或者顺序表为空则显示出错信息并退出运行
int Del_s_t(SqList *p, ElemType s, ElemType t)
{
	
	if(p==NULL)
		return 1;
	else if(s>=p->data[p->length-1]||t<=p->data[0])
		return 2;
	else
	{
		if(s<p->data[0]&&t>p->data[p->length-1])
			p->length=0;
		else if(s<p->data[0]&&t<=p->data[p->length-1])
		{
			int a,b,j=0;
			for(int i=0;i<p->length-1;i++)
				if(t>=p->data[i]&&t<p->data[i+1])
				{
					a=i;
					break;
				}
				else
					a=p->length-1;
			for(int i=a;i<p->length;i++)
				p->data[j++]=p->data[i];
			p->length=p->length-a;
		}
		else if(s>=p->data[0]&&t<=p->data[p->length-1])
		{
			int a,b;
			for(int i=0;i<p->length-1;i++)
				if(t>=p->data[i]&&t<p->data[i+1])
				{
					a=i;
					break;
				}
			else
				a=p->length-1;
			for(int i=0;i<p->length-1;i++)
				if(s>=p->data[i]&&s<p->data[i+1])
				{
					b=i;
					break;
				}
				else
					b=p->length-1;
			 int  j=b;
			 for(int i=a;i<p->length;i++)
				 p->data[++j]=p->data[i];
			  p->length=p->length-a+b+1;
		}
		else
		{
			int len;
			for(int i=0;i<p->length-1;i++)
				if(s>=p->data[i]&&s<p->data[i+1])
				{
					len=i;
					break;
				}
				else
					len=p->length-1;
			p->length = len+1;
		}
		return 0;
	}

}
           

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

//从头到尾扫描顺序表，k记录不在s与t之间的元素个数，边扫描边统计k，并将不在s与t之间的元素向前放置在k位置上，最后修改L的长度
bool delete_s_t2(SqList *p, ElemType s, ElemType t)
{
	if(p==NULL||s>=t)
		return false;
	int k=0;
	for(int i=0;i<p->length;i++)
	{
		if(p->data[i]>=s&&p->data[i]<=t)
		{
		}
		else
		{
		   p->data[k]=p->data[i];
		   k++;
		}
	}
	p->length=k;
	return true;
}
           

合并两个有序的顺序表

//合并两个有序的顺序表
void Merge_List(SqList *p1,SqList *p2,SqList *p)
{
	int i=0,j=0,k=0;
	while(i!=p1->length&&j!=p2->length)
	{
		if(p1->data[i]<=p2->data[j])
		{
			p->data[k]=p1->data[i];
            i++;
		}
		else
		{
            p->data[k]=p2->data[j];
			j++;
		}
		k++;
	}
	if(i==p1->length)
		while(j!=p2->length)
		  p->data[k++]=p2->data[j++];
	else
		while(i!=p1->length)
		  p->data[k++]=p1->data[i++];
	p->length=p1->length+p2->length;
}