順序表逆置算法：C++ 類封裝實現

問題描述

將順序表中的元素順序完全反轉，即 a[0] ↔ a[n-1], a[1] ↔ a[n-2] …。原地交換，空間 O(1)，時間 O(n)。

類設計

#include <iostream>
using namespace std;

typedef int ElemType;
const int MaxSize = 1000;

class SequenList {
    ElemType a[MaxSize];
    int len;
public:
    void input(int n) {
        len = n;
        for (int i = 0; i < n; ++i) cin >> a[i];
    }
    void print(int n) const {
        for (int i = 0; i < n; ++i) cout << a[i] << ' ';
        cout << endl;
    }
    void exchange(int n) {           // 核心：逆置前 n 個元素
        for (int i = 0; i <= n/2 - 1; ++i) {
            ElemType t = a[i];
            a[i] = a[n - i - 1];
            a[n - i - 1] = t;
        }
    }
    int size() const { return len; }
};

主程式

int main() {
    int n;
    cout << "元素個數: ";  cin >> n;
    SequenList L;
    cout << "輸入 " << n << " 個整數: ";  L.input(n);

    cout << "原序列: ";  L.print(n);
    L.exchange(n);
    cout << "逆置後: ";  L.print(n);
    return 0;
}

算法細節

• 循環條件 i <= n/2 - 1 等價於 i < n/2，避免中間元素自交換（奇數長度時）。
• 交換用臨時變量 t，標準三步驟。
• 若用 std::swap(a[i], a[n-i-1]) 更簡潔（C++11）。

擴展：STL 算法一行解決

#include <algorithm>
#include <vector>

vector<int> v = {1,2,3,4,5};
reverse(v.begin(), v.end());  // 原地逆置
// 或複製逆置
vector<int> vr(v.rbegin(), v.rend());

總結

逆置是經典原地演算法，掌握「雙指針向中間縮」模式，可舉一反三解決「判斷迴文」「旋轉陣列」「移動零」等問題。