/* 实现整型数组的循环右移 cycleMoveR1:临时空间比较大,但是时间复杂度为O(1) cycleMoveR2:临时空间比较小,时间复杂度为O(n) */ #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> // 数组循环右移moveLen个 int cycleMoveR1(int arr[], int len, int moveLen) { assert(len > 0 && moveLen > 0); moveLen = moveLen % len; int *p = malloc(moveLen * sizeof(int)); if(NULL == p) return 0; memcpy(p, arr+len-moveLen, moveLen * sizeof(int)); // 保存将被右移出数组的元素 memmove(arr+moveLen, arr, (len - moveLen) * sizeof(int)); // 将数组最前的元素右移moveLen个 memmove(arr, p, moveLen * sizeof(int)); free(p); return 1; } // 数组循环右移moveLen个 int cycleMoveR2(int arr[], int len, int moveLen) { assert(len > 0 && moveLen > 0); moveLen = moveLen % len; int i, j, t, p0, p1 = 0; for(i = 0; i < moveLen - p1; i++) // 循环moveLen-p1次 { j = len - i - 1; p0 = j; // p0保存此轮最先空出来的元素的下标 t = arr[j]; while(1) { if(j - moveLen >= 0) { arr[j] = arr[j - moveLen]; j -= moveLen; } else { if(j - moveLen + len != p0) { arr[j] = arr[j - moveLen + len]; j = j - moveLen + len; p1++; } else { arr[j] = t; break; } } } } return 1; } void display(int arr[], int len) { int i = 0; for(; i < len; i++) printf("%d ", arr[i]); printf("\n"); } int main(int argc, char *argv[]) { int arr[] = {1, 2, 3, 4, 5, 6}; int len = sizeof(arr)/sizeof(int); int moveLen = 0; do { printf("请输入循环右移的个数:"); scanf("%d", &moveLen); if(moveLen <= 0) break; cycleMoveR2(arr, len, moveLen); display(arr, len); } while (1); return 0; }