一维数组中序列循环左移p个位置形成新的一维数组

水深无声 2021-12-11 03:37 213阅读 0赞

问题描述:设将n(n>1)个整数存放到一维数组arr中，设计一个在时间和空间两方面都尽可能高效的算法，将arr中保存的序列循环左移p(0<p<n)个位置，即将arr中的数据由(X0,X1,...,Xn-1)变换为(Xp,Xp+1,...,Xn-1,X0,X1,...,Xp-1)。

设计思想：本题是在一维数组中进行元素位置变换，对数组内元素位置进行逆置来满足题目要求。

本题进行数组元素位置逆置共需要进行三次：

(1)对arr中的数据(X0,...,Xn-1)整体进行逆置，变为(Xn-1,...,X0)

(2)将arr中已经逆置的数据(Xn-1,...,X0)分两次逆置，分别逆置(Xn-1,...,Xp)和(Xp-1,...,X0)

(3)将(2)中两次逆置完成后，新的arr中的数据就变成(Xp,...,Xn-1,X0,...,Xp-1)

代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    void reverse(int arr[], int left, int right){
    	int temp;
    	if (left > right) //输入有错不符合条件
    		return;
    	while (left<right)
    	{
    		temp = arr[left];
    		arr[left] = arr[right];
    		arr[right] = temp;
    		left++;
    		right--;
    	}
    }
    void exchangeEle(int arr[], int n, int p){
    	if (p>n){
    		cout << "输入p值有错，大于数组的大小";
    		return;
    	}
    	reverse(arr, 0,n - 1); //第一次整体逆置
    	reverse(arr, 0, p-1);
    	reverse(arr, p, n - 1);
    }
    int main(){
    	int *arr,n,p;
    	cout << "输入一维数组的大小：";
    	cin >> n;
    	arr = (int *)malloc(sizeof(int)*n);
    	cout << "\n" << "输入数组的元素：";
    	for (int i = 0; i < n; i++)
    		cin >> arr[i];
    	cout << "\n" << "输入左移的元素个数p：";
    	cin >> p;
    	exchangeEle(arr,n,p);
    
    	//输出
    	cout << "\n" << "左移p个后的新数组：";
    	for (int i = 0; i < n; i++)
    		cout << arr[i] << "\t";
    	system("pause");
    	return 0;
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20211211/63fb7d04b0a144a7af2f507eebbc7b6b.png