資料結構習題：集合交並補集運算

題目描述

給定兩個嚴格遞增排序的整數集合 A、B（元素數 1~30000，值為 32 位帶號整數），求：

1. A ∩ B（交集）
2. A ∪ B（並集）
3. A - B（屬於 A 不屬於 B）
4. B - A（屬於 B 不屬於 A）

輸出格式：每組測試資料 5 行，第 1 行案例編號，後 4 行依序輸出上述四集合，元素以空格分隔，空集輸出空行。

核心演算法：有序序列雙指標合併（O(n+m) 時間，O(n+m) 空間）

利用兩集合**已排序**特性，雙指標同步掃描：

• *pa == *pb → 屬於交集，雙指標後移。
• *pa < *pb → *pa 僅屬 A，併入並集與 A-B，pa++。
• *pa > *pb → *pb 僅屬 B，併入並集與 B-A，pb++。
• 任一序列掃描完，剩餘元素全屬於該集合獨有，併入並集與對應差集。

完整 C++ 實作（動態陣列模擬順序表）

#include <cstdio>
#include <cstdlib>
#include <vector>

using namespace std;

struct SqList {
    vector elem; // 用 vector 替代手動 malloc/realloc
    int length = 0;
};

void readList(SqList& L, int n) {
    L.elem.resize(n);
    for (int i = 0; i < n; ++i) scanf("%d", &L.elem[i]);
    L.length = n;
}

void merge(const SqList& A, const SqList& B,
           vector& inter, vector& uni,
           vector& aMinusB, vector& bMinusA) {
    int i = 0, j = 0;
    while (i < A.length && j < B.length) {
        if (A.elem[i] == B.elem[j]) {
            inter.push_back(A.elem[i]);
            uni.push_back(A.elem[i]);
            ++i; ++j;
        } else if (A.elem[i] < B.elem[j]) {
            uni.push_back(A.elem[i]);
            aMinusB.push_back(A.elem[i]);
            ++i;
        } else {
            uni.push_back(B.elem[j]);
            bMinusA.push_back(B.elem[j]);
            ++j;
        }
    }
    while (i < A.length) {
        uni.push_back(A.elem[i]);
        aMinusB.push_back(A.elem[i]);
        ++i;
    }
    while (j < B.length) {
        uni.push_back(B.elem[j]);
        bMinusA.push_back(B.elem[j]);
        ++j;
    }
}

void printVec(const vector& v) {
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) putchar(' ');
        printf("%d", v[i]);
    }
    putchar('\n');
}

int main() {
    int T; scanf("%d", &T);
    for (int tc = 1; tc <= T; ++tc) {
        SqList A, B;
        int na, nb;
        scanf("%d", &na); readList(A, na);
        scanf("%d", &nb); readList(B, nb);

        vector inter, uni, aMinusB, bMinusA;
        merge(A, B, inter, uni, aMinusB, bMinusA);

        printf("Case #%d:\n", tc);
        printVec(inter);
        printVec(uni);
        printVec(aMinusB);
        printVec(bMinusA);
    }
    return 0;
}

關鍵點總結

• **雙指標線性掃描**：單趟 O(n+m)，無需雙重迴圈 O(nm)。
• **vector 自動擴容**：替代手動 malloc/realloc，安全簡潔。
• **輸出格式嚴謹**：空集輸出空行，元素間單一空格，行尾無多餘空格。
• **邊界處理**：一序列提前耗盡時，正確處理剩餘元素。

擴展思考

• 若集合未排序 → 先排序 O(n log n) 或用 unordered_set O(n) 平均。
• 若元素型別為字串/自訂型別 → 提供比較函數/運算子重載。
• STL 算法 set_intersection、set_union、set_difference 直接對應四操作，生產碼優先使用。