当前位置：首页 > article >正文

顺序表逆置相关的算法题|整体逆置|两个顺序表互换位置|轮转数组(C)

article 2024/10/22 4:56:40

整体逆置

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

算法思想

扫描顺序表L的前半部分元素，对于元素L.data[i](0<=i<L.length/2)，将其与后半部分的对应元素L.data[L.length-i-1]进行交换

从两边往中间遍历
当length是偶数时

左右半部分的数据个数相同
因为下标是从0开始，所以length指向的是最后一个数据的下一个位置
因为length是偶数，所以length/2指向的是前半部分的最后一个数据的下一个位置
所以i的范围是0到length/2-1闭区间，正好遍历前半部分
后半部分是length-1开始到length/2，也就是length-1-i

当length是奇数时

length/2指向中间的数据
顺序表分为三部分，前半部分，中间和后半部分
前半部分时，i从0到length/2-1闭区间，后半部分从length-1到length/2+1，也就是length-1-i
中间时，不符合循环条件，不参与循环，不需要逆置

void Reverse(SqList &L)
{
	ElemType temp;
	for (int i = 0; i < L.length/2; i++)
	{
		temp = L.data[i];
		L.data[i] = L.data[L.length-i-1];
		L.data[L.length-i-1] = temp;
	}
}

新建一个中间变量tmp进行交换

两个顺序表互换

已知在一维数组 A[m+n]中依次存放两个线性表 $a_{1},a_{2},a_{3},…,a_{m})$ 和 $(b_{1},b_{2},b_{3},\dots,b_{n},)$ 。编写一个函数,将数组中两个顺序表的位置互换,即将 $(b_{1},b_{2},b_{3},\dots,b_{n},)$ 放在 $a_{1},a_{2},a_{3},…,a_{m})$ 的前面。

算法思想

首先将数组A[m+n]中的全部元素整体原地逆置，然后对前n个元素和后m个元素分别使用逆置算法，从而实现顺序表的位置互换

typedef int ElemType;
void Reverse(ElemType A[], int left, int right, int arraySize)
{
	if (left >= right || right >= arraySize)
		return;
	
	int mid = (left + right)/2;
	for (int i = 0; i <= mid - left; i++)
	{
		ElemType temp = A[left + i];
		A[left + i] = A[right - i];
		A[right - i] = temp;
	}
}

void Exchange(ElemType A[], int m, int n, int arraySize)
{
	Reverse(A, 0, m + n - 1, arraySize);
	Reverse(A, 0, n - 1, arraySize);
	Reverse(A, n, m + n - 1, arraySize);
}

通过mid算逆置区间的中间位置
两个指针走，left + i和right - i
当区间内的数据个数是偶数，mid指的是前半区间的最后一个数
mid-left=1
mid-left是左半部分的数据个数
第一次left和right交换
第二次left+1和right-1交换
当区间内的数据个数是奇数时，mid指的是正中间的数
![[Pasted image 20241021213745.png]]
mid-left=2
第一次left和right交换
第二次left+1和right-1交换

轮转数组

设将n个整数存放到一维数组R中，将R中保存的序列循环左移p个位置

算法思想

先逆置前p个元素，再逆转其余的元素，最后整体逆置
![[Pasted image 20241012204054.png]]

void Reverse(int R[], int left, int right)
{	
	for (int i = 0; i < (right-left+1)/2; i++)
	{
		int temp = R[left + i];
		A[left + i] = A[right - i];
		A[right - i] = temp;
	}
}

void Converse(int R[], int n, int p)
{
	Reverse(R, 0, p-1);
	Reverse(R, p, n-1);
	Reverse(R, 0, n-1);
}