【循环移动数组元素

• • 问题描述
  • • 左移一个元素
    • 右移一个元素
    • 左移 K 个元素
    • 右移 K 个元素
  • 上面是采用元素一个个移动，下面采取逆置实现
  • • 左移 K 个元素
    • 右移 K 个元素

设计一个算法，将数组A[1:n]中的元素循环左、右移k位。

void Left_Move_Array(int* br, int n)	//左移一个元素
{
	if (NULL == br || n < 2) return;
	int tmp = br[0];
	for (int i = 0; i < n - 1; i++)
	{
		br[i] = br[i + 1];
	}
	br[n - 1] = tmp;
}

void Right_Move_Array(int* br, int n)	//右移一个元素
{
	if (NULL == br || n < 2) return;
	int tmp = br[n - 1];
	for (int i = n - 1; i > 0; i--)
	{
		br[i] = br[i - 1];
	}
	br[0] = tmp;
}

void Left_Move_Array_K(int* br, int n, int k)	//左移 k 个元素
{
	if (NULL == br || n < 2) return;
	k = k % n;
	if (k >= 0)
	{
		while (k--)
		{
			Left_Move_Array(br, n);
		}
	}
	else
	{
		while (k++)
		{
			Right_Move_Array(br, n);
		}
	}
}

void Right_Move_Array_K(int* br, int n, int k)  //右移 k 个元素
{
	if (NULL == br || n < 2) return;
	Left_Move_Array_K(br, n, -k);
}

———————————————————————————————————————————————————————————————

假如原数组： 1 2 3 4 5 6 7 8 9 10需要左移 3 次，那么我们想要的结果是： 4 5 6 7 8 9 10 1 2 3。
1.将1 2 3逆置 变成 3 2 1
2.将4 5 6 7 8 9 10 逆置 变成 10 9 8 7 6 5 4
3.将两个逆置数组拼接： 4 5 6 7 8 9 10 1 2 3
4.将这个已拼接的数组逆置： 4 5 6 7 8 9 10 1 2 3 就成了我们想要的结果了。

void Swap_Int(int* ap, int* bp)
{
	assert(ap != NULL && bp != NULL);
	int tmp = *ap;
	*ap = *bp;
	*bp = tmp;
}
void Reverse_Ar(int* br, int left, int right)
{
	if (NULL == br || left >= right) return;
	while (left < right)
	{
		Swap_Int(&br[left], &br[right]);
		left++;
		right--;
	}
}
void Left_Move_Ar_K(int* br, int n, int k)	//左移 k 个元素
{
	if (NULL == br || n < 2 || k < 1) return;
	k = k % n;
	Reverse_Ar(br, 0, k - 1);
	Reverse_Ar(br, k, n - 1);
	Reverse_Ar(br, 0, n - 1);
}

void Swap_Int(int* ap, int* bp)
{
	assert(ap != NULL && bp != NULL);
	int tmp = *ap;
	*ap = *bp;
	*bp = tmp;
}
void Reverse_Ar(int* br, int left, int right)
{
	if (NULL == br || left >= right) return;
	while (left < right)
	{
		Swap_Int(&br[left], &br[right]);
		left++;
		right--;
	}
}
void Right_Move_Ar_K(int* br, int n, int k)	//右移 k 个元素
{
	if (NULL == br || n < 2 || k < 1) return;
	k = k % n;
	k = n - k;
	Reverse_Ar(br, k, n - 1);
	Reverse_Ar(br, 0, k - 1);
	Reverse_Ar(br, 0, n - 1);
}

OK ~