您现在的位置：程式碼之家 >> 編程語言 > >> 更多程式語言 >> 程式設計綜合問答

C++ 線性表合併：將 L2 尾部插入 L1 完整實作 (順序表/鏈表雙版本)

編輯：程式設計綜合問答

題目要求

C++ 實作
介面函數：`int MergeList(SqlList &L1, SqlList L2)`
將 L2 所有資料**直接合併到 L1 尾部** (不排序)
範例：L1={1,2,3,4,5}, L2={6,7,8,9,10} → L1={1,2,3,4,5,6,7,8,9,10}

資料結構定義 (順序表 SqlList)

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int length;
} SqlList;

順序表版本實作 (陣列)


/**
 * 合併兩個順序表：L2 追加到 L1 尾部
 * @param L1 目標表 (引用，會被修改)
 * @param L2 來源表 (傳值/引用均可，不修改)
 * @return 0 成功, -1 空間不足
 */
int MergeList(SqlList &L1, const SqlList &L2) {
    // 1. 檢查空間是否足夠
    if (L1.length + L2.length > MAXSIZE) {
        return -1; // 溢出
    }

    // 2. 複製 L2 元素到 L1 尾部
    for (int i = 0; i < L2.length; ++i) {
        L1.data[L1.length + i] = L2.data[i];
    }

    // 3. 更新 L1 長度
    L1.length += L2.length;

    return 0;
}

鏈表版本實作 (單向鏈表，更靈活無容量上限)


struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

typedef Node* LinkList; // 頭指標

/**
 * 合併兩個單向鏈表：L2 接在 L1 尾部
 * @param L1 目標表頭指標 (引用，可能修改頭指標)
 * @param L2 來源表頭指標
 * @return void
 */
void MergeList(LinkList &L1, LinkList L2) {
    if (L2 == nullptr) return; // L2 空，無操作
    if (L1 == nullptr) {       // L1 空，直接指向 L2
        L1 = L2;
        return;
    }

    // 找到 L1 尾節點
    Node* tail = L1;
    while (tail->next != nullptr) {
        tail = tail->next;
    }

    // 尾節點指向 L2 頭
    tail->next = L2;
    // L2 現在屬於 L1，調用者不應再使用 L2
}

測試主程式 (順序表版)


#include 
using namespace std;

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int length;
} SqlList;

int MergeList(SqlList &L1, const SqlList &L2) {
    if (L1.length + L2.length > MAXSIZE) return -1;
    for (int i = 0; i < L2.length; ++i) 
        L1.data[L1.length + i] = L2.data[i];
    L1.length += L2.length;
    return 0;
}

void PrintList(const SqlList &L) {
    for (int i = 0; i < L.length; ++i) cout << L.data[i] << " ";
    cout << endl;
}

int main() {
    SqlList L1 = {{1,2,3,4,5}, 5};
    SqlList L2 = {{6,7,8,9,10}, 5};

    cout << "合併前 L1: "; PrintList(L1);
    cout << "合併前 L2: "; PrintList(L2);

    if (MergeList(L1, L2) == 0) {
        cout << "合併後 L1: "; PrintList(L1);
    } else {
        cout << "合併失敗：空間不足\n";
    }
    return 0;
}

輸出結果

合併前 L1: 1 2 3 4 5 
合併前 L2: 6 7 8 9 10 
合併後 L1: 1 2 3 4 5 6 7 8 9 10

關鍵點總結

場景	核心邏輯	複雜度	注意事項
順序表 (陣列)	檢查容量 → `memcpy`/迴圈複製 → 更新長度	O(L2.length)	固定容量 `MAXSIZE`，需檢查溢出
鏈表	找尾節點 → `tail->next = L2_head`	O(L1.length) 找尾	無容量限制，L2 併入後不可再獨立使用
已排序合併	雙指針歸併 (如合併排序 merge 步驟)	O(n+m)	題目明確「不排序，直接合併」

現代 C++ 寫法 (vector / list)


// vector 版 (動態陣列，自動擴容)
void mergeVector(vector &v1, const vector &v2) {
    v1.insert(v1.end(), v2.begin(), v2.end());
}

// list 版 (雙向鏈表，拼接 O(1))
void mergeList(list &l1, list &l2) {
    l1.splice(l1.end(), l2); // l2 變空，元素移動到 l1
}