数组元素循环移动

Myth丶恋晨 2021-09-26 15:24 391阅读 0赞

# 数组元素循环移动 #

--------------------

### 文章目录 ###

*  数组元素循环移动
 *   *  1. 目的
     *  2. 效果
     *  3. 示例
     *   *  3.1 算法Ⅰ：循环单次右移一位
         *  3.2 算法Ⅱ：下标关系交换元素
     *  4. 结论：

--------------------

数组元素循环移动分为循环左移和循环右移。  
由于两种情况类似。就以循环右移为例。

--------------------

## 1. 目的 ##

将数组中的元素循环向右移动。

## 2. 效果 ##

右移一位时，数组最后一个元素跑到了数组第一个位置，数组其余元素统一向后挪动一个位置。  
右移 m 位时，连续执行 m 次 “右移一位” 的操作。

## 3. 示例 ##

现有整型数组

>  A = \[ 1 ， 2 ， 3 ， 4 ， 5 ， 6 \] \\color\{DeepPink\}\{A = \[ 1，2，3，4，5，6 \]\} A=\[1，2，3，4，5，6\]

循环向右移动两次，得到的结果应该是

>  A = \[ 5 ， 6 ， 1 ， 2 ， 3 ， 4 \] \\color\{DeepPink\}\{A = \[ 5，6，1，2，3，4 \]\} A=\[5，6，1，2，3，4\]

### 3.1 算法Ⅰ：循环单次右移一位 ###

基本思想：将数组元素循环右移 m 次，每一次的操作如下图

一个整型变量 temp 保存最后一个位置的元素  t e m p = A \[ l e n g t h − 1 \] \\color\{DeepPink\}\{temp = A \[length-1\]\} temp=A\[length−1\]；  
然后将其余元素从下标 length-2 到下标 0 的元素右移一个位置；

将 temp中的值存放到数组下标 0 的位置；完成一次右移操作。

C代码如下：

/* 函数功能：从控制台读入n个整型数据，存入数组中，并将数组循环右移m位 */
    	// 这里假设n>0，m>=0，是合法的数字。
    	void cyclicShiftRight(int n, int m)
    	{ 
    		// input.
    		int *testArray = (int*)malloc(sizeof(int) * n);
    		for (int i = 0; i < n; ++i)
    		{ 
    			// 如果报错，请尝试 scanf("%d", testArray + i);
    			scanf_s("%d", testArray + i);
    		}
    
    		// process.
    		/* 循环右移的结果和右移的前n(数组长度）个结果一致，所以做取余操作。*/
    		m = m % n;
    		
    		// 如果取余操作之后的m等于0，则不需要移动
    		if (0 == m)
    		{ 
    			// empty
    		}
    		// 如果取余操作之后的m不等于0，则需要右移
    		else
    		{ 
    			// 循环右移m次
    			for (int j = 1; j <= m; ++j)
    			{ 
    				// 先将最后一个元素（下标值为n-1的元素）保存在临时变量temp中
    				int temp = testArray[n - 1];
    				// 从倒数第二个元素到第一个元素，向右移动一个位置
    				for (int k = n - 2; k >= 0; --k)
    				{ 
    					testArray[k + 1] = testArray[k];
    				}
    				// 将temp中保存的元素值放入第一个位置（下标值为0）。
    				testArray[0] = temp;
    			}
    		}
    
    		// output.
    		for (int i = 0; i < n; ++i)
    		{ 
    			printf("%d", *(testArray + i));
    			if (i != n - 1)
    			{ 
    				printf(" ");
    			}
    		}
    		printf("\n");
    		free(testArray);
    		testArray = NULL;
    	}
    
    	int main()
    	{ 
    		// N是数组的大小（数组元素的个数）
    		int N = 0;
    		// M是循环右移的位数
    		int M = 0;
    		// 如果报错，请尝试 scanf("%d %d", &N, &M);
    		scanf_s("%d %d", &N, &M);
    		cyclicShiftRight(N, M);
        	return 0;
    	}

--------------------

### 3.2 算法Ⅱ：下标关系交换元素 ###

假设循环右移 2 次（循环右移 8 次与其结果一致，因为 8%6 == 2），正确结果应该如下表

观察结果发现结果数组分为 2 个部分，一组有 2 个元素 “5” 和 “6” 保持有序，另一组 4 个元素 “1” 、“2”、“3” 和 “4” 保持有序。  
于是将原数组看作两个部分，一组有 2 个元素保持有序，另一组 4 个元素保持有序，结果如下

将两个数组中的元素，每个部分数组第一个元素和自身最后一个元素交换，第二元素和倒数第二个元素交换，以此类推… …

然后整个数组看作一个整体，执行以上操作

此时得到了正确的结果。  
C代码如下：

/* 函数功能：交换数组testArray中下标firstIndex和下标secondIndex的元素*/
    	/* 这里假设传入的参数都是正确的，即testArray不能为空，firstIndex和secondIndex下标值是合法的（不能越界）。*/
        void swap(int testArray[], int firstIndex, int secondIndex)
    	{ 
    		// 如果firstIndex和second指向的是同一个下标，则不做任何动作；
    		if (firstIndex == secondIndex)
    		{ 
    			// empty block.
    		}
    		else
    		{ 
    			// 交换两个元素
    			int temp = testArray[firstIndex];
    			testArray[firstIndex] = testArray[secondIndex];
    			testArray[secondIndex] = temp;
    		}
    	}
    
    
    	/* 函数功能：将数组testArray下标从leftIndex到rightIndex，包含leftIndex和rightIndex的元素进行反转（翻转）。*/
    	/* 这里假设传入的参数都是正确的，即testArray不能为空，leftIndex和rightIndex下标值是合法且合理的（不能越界并且leftIndex < rightIndex）。*/
    	void ReverseArray(int testArray[], int leftIndex, int rightIndex)
    	{ 
    		/* 双“指针”--i和j */
    		/* i从leftIndex开始，往下标值增大的方向移动 */
    		/* j从rightIndex开始，往下标值减小的方向移动 */
    		int i = leftIndex;
    		int j = rightIndex;
    		
    		// 当满足 i<j 时，循环执行“交换testArray[i]和testArray[j]”的操作
    		while (i < j)
    		{ 
    			swap(testArray, i, j);
    			++i;
    			--j;
    		}
    	}
    
    	/* 函数功能：从控制台读入n个整型数据，存入数组中，并将数组循环右移m位 */
    	// 这里假设n>0，m>=0，是合法的数字。
    	void cyclicShiftRight(int n, int m)
    	{ 
    		// input.
    		// 这里假设都能分配成功。
    		int *testArray = (int*)malloc(sizeof(int) * n);
    		for (int i = 0; i < n; ++i)
    		{ 
    			// 如果报错，请尝试 scanf("%d", testArray + i);
    			scanf_s("%d", testArray + i);
    		}
    
    		// process.
    		/* 循环右移的结果和右移的前n(数组长度）个结果一致，所以做取余操作。*/
    		m = m % n;
    		
    		// 如果取余操作之后的m等于0，则不需要移动
    		if (0 == m)
    		{ 
    			// empty
    		}
    		// 如果取余操作之后的m不等于0，则需要右移
    		else
    		{ 
    			/* 将原数组看作两部分 */
    			/* 一部分下标从0到n-m-1，进行数组元素的反转 */
    			ReverseArray(testArray, 0, n - m - 1);  
    
    			/* 另一部分下标从n-m到n-1，进行数组元素的反转 */
    			ReverseArray(testArray, n - m, n - 1);  
    
    			/* 整个数组所有元素进行一次数组元素的反转 */
    			ReverseArray(testArray, 0, n - 1);
    		}
    
    		// output.
    		for (int i = 0; i < n; ++i)
    		{ 
    			printf("%d", *(testArray + i));
    			if (i != n - 1)
    			{ 
    				printf(" ");
    			}
    		}
    		printf("\n");
    		free(testArray);
    		testArray = NULL;
    	}
    
    	int main()
    	{ 
    		// N是数组的大小（数组元素的个数）
    		int N = 0;
    		// M是循环右移的位数
    		int M = 0;
    		// 如果报错，请尝试 scanf("%d %d", &N, &M);
    		scanf_s("%d %d", &N, &M);
    		cyclicShiftRight(N, M);
        	return 0;
    	}

以上两种代码在Microsoft Visual Studio 2015 以及 Microsoft Visual Studio 2017上运行成功。

--------------------

## 4. 结论： ##

> 第一种算法由于要移动大量（数组很大的时候）的元素，效率不如第二种高。第二种算法更高效，时间复杂度低，优先考虑。

--------------------