数组A[m+n]中存放了两个线性表（a1,a2,.....am）和（b1,b2.....bn)，将数组中的两个线性表的位置互换，要求空间复杂度为1

要求空间复杂度为O(1)，那么不可以借助辅助数组来完成此操作

算法思路：可先将此数组逆置变成bn,......b1,am,....,a1，然后分别逆转两个线性表的数据元素

算法实现

1、定义一个函数，该函数的功能是可以对一个数组的任意连续的部分进行逆置

//该函数用于将一个数组的任意部分逆序
void Reverse(int a[], int left, int right)
{
	int temp;
	for (int i = left, j = right; j > i; i++, j--)
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

?2、交换两个线性表的顺序

//交换顺序
void Exchange(int a[], int m, int n)
{
	//先将整个数组逆序
	Reverse(a, 0, m + n-1);
	//分别逆序两个线性表
	Reverse(a, 0, n - 1);
	Reverse(a, n, m + n - 1);
}

3、测试函数

int main()
{
	int m = 5;
	int n = 10;
	int A[max];
	printf("互换顺序前：\n");
	for (int i = 0; i < m + n; i++)
	{
		A[i] = i;
		printf("%d\t", A[i]);
	}

	Exchange(A, m, n);
	//Reverse(A, 0, m + n - 1);
	printf("\n互换顺序后：\n");
	for (int i = 0; i < m + n; i++)
	{
		printf("%d\t", A[i]);
	}
	return 0;
}

4、测试结果

完整代码?

//数组A[m+n]中存放了两个线性表（a1,a2,.....am）和（b1,b2.....bn)，将数组中的两个线性表的位置互换，要求空间复杂度为1

#include<stdio.h>
#include<stdlib.h>
#define max 20
using namespace std;

//该函数用于将一个数组的任意部分逆序
void Reverse(int a[], int left, int right)
{
	int temp;
	for (int i = left, j = right; j > i; i++, j--)
	{
		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

//交换顺序
void Exchange(int a[], int m, int n)
{
	//先将整个数组逆序
	Reverse(a, 0, m + n-1);
	//分别逆序两个线性表
	Reverse(a, 0, n - 1);
	Reverse(a, n, m + n - 1);
}

int main()
{
	int m = 5;
	int n = 10;
	int A[max];
	printf("互换顺序前：\n");
	for (int i = 0; i < m + n; i++)
	{
		A[i] = i;
		printf("%d\t", A[i]);
	}

	Exchange(A, m, n);
	//Reverse(A, 0, m + n - 1);
	printf("\n互换顺序后：\n");
	for (int i = 0; i < m + n; i++)
	{
		printf("%d\t", A[i]);
	}
	return 0;
}