【算法】将一维数组arr中的元素循环左移p个位置

ゝ一纸荒年。 2022-06-16 03:17 155阅读 0赞

要准备考研了，现在也开始看专业课了。传统的数据结构和算法啊！现在也在看书，看一些做一些记录吧，也算是积累，不仅仅是考研，说不定以后也用的上~

今天要谈的是【将一维数组中的元素循环左移P个元素】

题目是这样的：设将n(n>1)个整数存放到一维数组R中，设计一个算法，将R中的序列循环左移P(0<P<n)个位置，即将R中的数据由\{X0，X1，...，Xn-1\}变换为\{Xp，Xp+1，...，Xn-1，X0，X1，...，Xp-1\}

分析一下：

这题要的是如下的这种效果

例如数组元素为

元素  1    2    3    4    5

下标  0    1    2    3    4

假如循环左移3个位置，变为

元素   4    5   1    2    3

下标   0    1   2    3    4

显然，题目中所说的循环左移，就是指将数组中的每一个元素向左移动P个位置

设计的算法如下：

S1：将数组元素1~P进行逆置

S2：将数组元素P+1~n进行逆置(假设数组元素总数为n)

S3：将数组元素1~n进行逆置(假设数组元素总数为n)

需要指出的是：这里我们思考的时候，数组元素下标是从1开始的

但是在实际编程当中，下标是从0开始，也就是说，上面算法中【P】要变为【P-1】；【P+1】变为【P】

核心代码如下：

1、逆置代码

void reverse(int *arr , int begin , int end)
    {
    	int i , j;
    	for(i = begin , j = end ; i < j ; i++ , j--)
    	{
    		int t;
    		t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
    	}
    }

说明：在参数中 arr是一个一维数组，begin表示逆置的起始位置，end表示逆置的结束位置

函数实现逻辑是：定义两个整型变量i，j；i指向逆置的起始位，j指向逆置的结束位，然后头尾互相交换元素。接着i++ j--，前后夹击。循环退出的条件为，当i大于等于j时。也就是说，变量i负责数组arr的前半部分，j负责数组arr的后半部分，不能越权。

2、循环左移代码

void function(int *arr , int n , int p)
    {
    	reverse(arr,0,p-1);
    	reverse(arr,p,n-1);
    	reverse(arr,0,n-1);
    }

说明：这个部分就是根据上面所提及的算法进行编写。 注意，数组下标从0开始，一些临界值要减一

3、完整代码

#include <iostream>
    using namespace std;
    
    void reverse(int *arr , int begin , int end)
    {
    	int i , j;
    	for(i = begin , j = end ; i < j ; i++ , j--)
    	{
    		int t;
    		t = arr[i];
    		arr[i] = arr[j];
    		arr[j] = t;
    	}
    }
    
    void function(int *arr , int n , int p)
    {
    	reverse(arr,0,p-1);
    	reverse(arr,p,n-1);
    	reverse(arr,0,n-1);
    }
    
    
    void display(int *arr , int n)
    {
    	int i;
    	for(i = 0 ; i < n ; i++)
    	{
    		cout<<arr[i]<<" ";
    	}
    	cout<<endl;
    }
    
    int main()
    {
    	int arr[5] = {1,2,3,4,5};
    	function(arr,5,3);
    	display(arr,5);
    	return 0;
    }

说明：我初始化了一个长度为5的一维数组，让数组中的每一个元素循环左移3个位置

运行效果如下：

![20170503233343496][]

[20170503233343496]: /images/20220616/1018274e75cf4986917d7d96c9efc992.png