倒置顺序表

c/c++

浏览数:332

2019-6-29

已知数组中存放了两个线性表(a1,a2,a3….am)和(b1,b2,b3……bn),设计一个算法,用尽可能少的辅助空间将两个线性表的位置互换。

(1)、线性表位置互换一:

从b1开始的把b表的所有元素都插入到a表之前,首先将b表的元素bi存储到一个临时变量temp中,然后将a表的所有元素后移一位,其次将temp插入到腾出来的位置上,此时只需要一个临时的辅助空间。

void Exchange1(SeqList L,int m,int n)
{
	int i,j;
	ElemType temp;
	for(i=0;i<n;i++)
	{
		temp=L.elem[m+i+1];	//第二个表的第一个位置,加1是因为要跳过设置的间隔符0
		for(j=m+i-1;j>=i;j--)	//注意,这里并不是把所有的元素后移,而是在拷贝的数字这里结束
			L.elem[j+1]=L.elem[j];
		L.elem[i]=temp;
	}
}

 此时时间复杂度为:O(m*n),空间复杂度为O(1);

(2)、第二种交换方法:  将整个线性表的元素倒置,如a1a2a3….an b1b2b3…bn,变为b1b2b3…bn a1a2…an,然后再分别将第一个表和第二个表倒置即可,即执行三次倒置。

//元素倒置
void invert(SeqList *s,int m,int n)
{
	ElemType temp;
	int i;
	for(i=m;i<(m+n+1)/2;i++)
	{
		temp=s->elem[i];
		s->elem[i]=s->elem[m+n-i];
		s->elem[m+n-i]=temp;
	}
}

 其中倒置算法的时间复杂度为O((m+1-n)/2)。

开始倒置顺序表

void Exchange2(SeqList *s,int m,int n)
{
	int i;
	//将全表倒置
	invert(s,0,m+n);
	//将第一个表倒置
	invert(s,0,n-1);
	//第二个表倒置
	invert(s,n+1,m+n);
}

 整个算法的时间复杂度为O((m+n+1)/2+(n-1+1)/2+[(m+n)+1-n]/2)=O(m+n),空间复杂度为O(1)。

源程序如下:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

#define MAXSIZE 100
#define ElemType int

//定义结构体
typedef struct
{
	ElemType elem[100];
	int length;
}SeqList;

//顺序表的初始化
SeqList Init_Seq(){
	SeqList L;
	L.length=0;
	return L;
}

//顺序表的建立
SeqList Create_Seq(SeqList L)
{
	ElemType x;
	scanf("%d",&x);
	while(x!=-1)
	{
		L.elem[L.length]=x;
		L.length++;
		scanf("%x",&x);
	}
	return L;
}

/*线性表位置互换一:从b1开始的把b表的所有元素都插入到a表之前,
  首先将b表的元素bi存储到一个临时变量temp中,然后将a表的所有元素后移一位,
  其次将temp插入到腾出来的位置上,此时只需要一个临时的辅助空间
 */

void Exchange1(SeqList L,int m,int n)
{
	int i,j;
	ElemType temp;
	for(i=0;i<n;i++)
	{
		temp=L.elem[m+i+1];	//第二个表的第一个位置,加1是因为要跳过设置的间隔符0
		for(j=m+i-1;j>=i;j--)	//注意,这里并不是把所有的元素后移,而是在拷贝的数字这里结束
			L.elem[j+1]=L.elem[j];
		L.elem[i]=temp;
	}
	printf("交换之后线性表的元素为:\n");
	for(i=0;i<n;i++)
		printf("%d ",L.elem[i]);
	for(i=n;i<L.length-1;i++)
		printf("%d ",L.elem[i]);
	printf("\n********************\n");
}

/*
	第二种交换方法:
	将整个线性表的元素倒置,如a1a2a3....anb1b2b3...bn,变为b1b2b3...bna1a2...an
	然后分别将第一个表和第二个表倒置即可
*/
//元素倒置
void invert(SeqList *s,int m,int n)
{
	ElemType temp;
	int i;
	for(i=m;i<(m+n+1)/2;i++)
	{
		temp=s->elem[i];
		s->elem[i]=s->elem[m+n-i];
		s->elem[m+n-i]=temp;
	}
}
void Exchange2(SeqList *s,int m,int n)
{
	int i;
	//将全表倒置
	invert(s,0,m+n);
	//将第一个表倒置
	invert(s,0,n-1);
	//第二个表倒置
	invert(s,n+1,m+n);
	printf("第二种倒置方法交换后如下:\n");
	for(i=0;i<n;i++)
		printf("%d ",s->elem[i]);
	for(i=n+1;i<s->length;i++)
		printf("%d ",s->elem[i]);
	printf("\n********************\n");
}

void main()
{
	SeqList seqlist,*p;
	int i,middle;
	//ElemType x;
	seqlist=Init_Seq();
	printf("创建一个顺序表的顺序,其中两个顺序表表以0作为间隔符,以-1作为结束符:\n");
	seqlist=Create_Seq(seqlist);
	p=&seqlist;
	for(i=0;i<p->length;i++)
		if(p->elem[i]==0)
			middle=i;
	printf("您所创建的顺序表如下:\n");
	for(i=0;i<middle;i++)
		printf("%d ",seqlist.elem[i]);
	for(i=middle+1;i<seqlist.length;i++)
		printf("%d ",seqlist.elem[i]);
	printf("\n执行第一种倒置后的变为:\n");
	Exchange1(seqlist,middle,seqlist.length-middle-1);
	Exchange2(p,middle,seqlist.length-middle-1);

}

 效果如图:

 

作者:一盏淡酒、醉了夕阳