文章

58

粉丝

253

获赞

1

访问

22.0k

头像
2010年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年12月5日 15:45
阅读数 11

### (1)算法基本设计思想  
采用**三次反转法**,该方法在时间和空间效率上均最优,核心思路如下:  
1. **分割序列**:将数组 `R` 按左移位数 `P` 分为两部分——左段 `A = [X0, X1, ..., Xp-1]`(长度 `P`)和右段 `B = [Xp, Xp+1, ..., Xn-1]`(长度 `n-P`);  
2. **三次反转**:  
   - 反转左段 `A`,得到 `A' = [Xp-1, ..., X1, X0]`;  
   - 反转右段 `B`,得到 `B' = [Xn-1, ..., Xp+1, Xp]`;  
   - 反转整个数组(`A' + B'`),最终得到目标序列 `[Xp, ..., Xn-1, X0, ..., Xp-1]`。  

本质是通过“局部反转+整体反转”的组合,避免额外存储空间消耗,同时保证线性时间复杂度。


### (2)C语言实现(关键注释)  
```c
#include <stdio.h>

// 辅助函数:反转数组从下标left到right的元素(闭区间)
void reverse(int R[], int left, int right) {
    while (left < right) {
        // 交换left和right位置的元素
        int temp = R[left];
        R[left] = R[right];
        R[right] = temp;
        // 向中间靠拢
        left++;
        right--;
    }
}

// 主函数:循环左移P个位置
void leftRotate(int R[], int n, int P) {
    // 处理P≥n的情况(左移n位等价于不移动,故取模简化)
    P = P % n;
    if (P == 0) return; // 移动0位,直接返回
    
    // 1. 反转左段:[0, P-1]
    reverse(R, 0, P-1);
    // 2. 反转右段:[P, n-1]
    reve...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发