已知数组中存放了两个线性表（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("交换之后线性表的元素为：
");
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("
********************
");
}
/*
第二种交换方法：
将整个线性表的元素倒置，如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("第二种倒置方法交换后如下：
");
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("
********************
");
}
void main()
{
SeqList seqlist,*p;
int i,middle;
//ElemType x;
seqlist=Init_Seq();
printf("创建一个顺序表的顺序，其中两个顺序表表以0作为间隔符，以-1作为结束符：
");
seqlist=Create_Seq(seqlist);
p=&seqlist;
for(i=0;i<p->length;i++)
if(p->elem[i]==0)
middle=i;
printf("您所创建的顺序表如下：
");
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("
执行第一种倒置后的变为：
");
Exchange1(seqlist,middle,seqlist.length-middle-1);
Exchange2(p,middle,seqlist.length-middle-1);
}
效果如图：
