C语言实现数组循环右移的四种方法

创作时间:

作者:

@小白创作中心

C语言实现数组循环右移的四种方法

引用

来源

https://docs.pingcode.com/baike/1230265

数组循环右移是C语言编程中常见的操作之一，特别是在处理数据结构和算法问题时。本文将详细介绍四种实现数组循环右移的方法：使用临时数组、逐个移动元素、利用环形数组的思想以及使用反转方法。每种方法都有其特点和适用场景，读者可以根据实际需求选择合适的方法。

一、使用临时数组

使用临时数组的方法是最直接的一种方式。这种方法的思路是先将需要移动的元素存储到一个临时数组中，然后再将临时数组中的元素插入到原数组的适当位置。

实现步骤

创建一个临时数组，用来存储需要右移的元素。
将原数组中最后k个元素复制到临时数组中。
将原数组中的元素向右移动k个位置。
将临时数组中的元素放回到原数组的前k个位置。

代码示例

#include <stdio.h>

void rotateArray(int arr[], int n, int k) {  
    int temp[k]; // 创建一个临时数组  
    k = k % n; // 防止k大于数组长度  
    // 将最后k个元素存储到临时数组中  
    for (int i = 0; i < k; i++) {  
        temp[i] = arr[n - k + i];  
    }  
    // 将原数组中的元素向右移动k个位置  
    for (int i = n - 1; i >= k; i--) {  
        arr[i] = arr[i - k];  
    }  
    // 将临时数组中的元素插入到原数组的前k个位置  
    for (int i = 0; i < k; i++) {  
        arr[i] = temp[i];  
    }  
}  

int main() {  
    int arr[] = {1, 2, 3, 4, 5, 6, 7};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int k = 3;  
    rotateArray(arr, n, k);  
    printf("Array after rotation: ");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

二、逐个移动元素

逐个移动元素的方法不需要额外的空间，适合在空间复杂度要求较高的情况下使用。这种方法的思路是依次将数组中的每个元素右移一个位置，重复k次即可。

实现步骤

循环k次，每次将数组中的元素右移一个位置。
每次右移时，将最后一个元素保存，然后从后往前依次移动元素。
最后将保存的元素放到数组的第一个位置。

代码示例

#include <stdio.h>

void rotateArray(int arr[], int n, int k) {  
    k = k % n; // 防止k大于数组长度  
    for (int i = 0; i < k; i++) {  
        int temp = arr[n - 1]; // 保存最后一个元素  
        for (int j = n - 1; j > 0; j--) {  
            arr[j] = arr[j - 1];  
        }  
        arr[0] = temp; // 将保存的元素放到第一个位置  
    }  
}  

int main() {  
    int arr[] = {1, 2, 3, 4, 5, 6, 7};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int k = 3;  
    rotateArray(arr, n, k);  
    printf("Array after rotation: ");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

三、利用环形数组的思想

环形数组的思想是将数组看成是环形的，通过索引的取模运算实现元素的移动。这样的方法时间复杂度较低，是一种比较高效的实现方式。

实现步骤

创建一个与原数组相同大小的新数组。
利用取模运算将原数组中的元素放到新数组的相应位置。
将新数组的内容复制回原数组。

代码示例

#include <stdio.h>

void rotateArray(int arr[], int n, int k) {  
    int newArr[n];  
    k = k % n; // 防止k大于数组长度  
    for (int i = 0; i < n; i++) {  
        newArr[(i + k) % n] = arr[i];  
    }  
    for (int i = 0; i < n; i++) {  
        arr[i] = newArr[i];  
    }  
}  

int main() {  
    int arr[] = {1, 2, 3, 4, 5, 6, 7};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int k = 3;  
    rotateArray(arr, n, k);  
    printf("Array after rotation: ");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

四、使用反转方法

使用反转方法是一种巧妙且高效的实现方式。这种方法的思路是将数组分成两部分，分别反转，然后将整个数组再反转一次。

实现步骤

反转整个数组。
反转前k个元素。
反转后n-k个元素。

代码示例

#include <stdio.h>

void reverse(int arr[], int start, int end) {  
    while (start < end) {  
        int temp = arr[start];  
        arr[start] = arr[end];  
        arr[end] = temp;  
        start++;  
        end--;  
    }  
}  

void rotateArray(int arr[], int n, int k) {  
    k = k % n; // 防止k大于数组长度  
    reverse(arr, 0, n - 1);  
    reverse(arr, 0, k - 1);  
    reverse(arr, k, n - 1);  
}  

int main() {  
    int arr[] = {1, 2, 3, 4, 5, 6, 7};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    int k = 3;  
    rotateArray(arr, n, k);  
    printf("Array after rotation: ");  
    for (int i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

五、总结

C语言实现数组循环右移的方法包括：使用临时数组、逐个移动元素、利用环形数组的思想和使用反转方法。其中，逐个移动元素的方法是比较常见且高效的一种实现方式，不需要额外的空间。使用临时数组的方法虽然简单直观，但空间复杂度较高。利用环形数组的思想和使用反转方法是两种比较高效的实现方式，适合在时间复杂度要求较高的情况下使用。

在实际应用中，可以根据具体的需求和限制选择合适的实现方式。对于需要频繁进行数组右移操作的场景，可以考虑使用环形数组的思想或反转方法，以提高程序的运行效率。