跳转至

AB33-将顺序表中的元素逆置（原地逆置）

代码实现

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * 将顺序表中的元素逆置（原地逆置）
 * @param L 指向顺序表的指针
 */
void Reverse_L(Sqlist *L) {
    // 初始化双指针：i指向第一个元素，j指向最后一个元素
    int i = 0;              // 前指针，从数组开头开始
    int j = L->length - 1;  // 后指针，从数组末尾开始

    // 双指针向中间移动，直到相遇
    for (; i < j; i++, j--) {
        // 交换两个指针所指向的元素
        int temp = L->data[i];    // 临时存储前指针元素
        L->data[i] = L->data[j];  // 将后指针元素赋值给前位置
        L->data[j] = temp;        // 将前指针元素赋值给后位置
    }
}

算法原理图解

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
初始状态：[1][2][3][4][5]
          ↑           ↑
          i           j

第一次交换后：[5][2][3][4][1]
                 ↑     ↑
                 i     j

第二次交换后：[5][4][3][2][1]
                    ↑
                 i=j(结束)

最终结果：[5][4][3][2][1]

复杂度分析

时间复杂度：O(n)

  • 分析过程：
  • 循环次数：n/2次（双指针从两端向中间移动）
  • 每次循环执行：3次赋值操作（常数时间）
  • 总执行次数：3 × (n/2) = 1.5n
  • 忽略常数系数，时间复杂度为 O(n)

空间复杂度：O(1)

  • 分析过程：
  • 只使用了3个额外变量：i、j、temp
  • 这些变量占用的空间不随输入规模n的变化而变化
  • 因此空间复杂度为 O(1)（原地算法）

算法特点

优点： - 原地逆置，空间效率高 - 实现简单，逻辑清晰 - 时间复杂度线性，效率较高

核心思想： 使用双指针技术，从数组两端开始，逐步向中间靠拢，每次交换对应位置的元素，实现整体逆置。