Java 數據結構：線性表歸並算法實現詳解

Java 數據結構：線性表歸並算法實現詳解

在數據結構與算法的學習中，線性表的歸並操作是一個經典且實用的問題。當我們擁有兩個已按非遞減順序排列的線性表 LA 和 LB 時，如何高效地將它們合併為一個同樣有序的新線性表 LC，是考察指針操作與邏輯控制能力的良好練習。

問題描述與示例

已知線性表 LA 和 LB 中的數據元素均按值非遞減有序排列。目標是將這兩個表歸並為一個新的線性表 LC，使 LC 中的數據元素仍保持非遞減有序。例如：

• LA = (3, 5, 8, 11)
• LB = (2, 6, 8, 9, 11, 15, 20)
• 歸並後 LC = (2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20)

本文採用線性表的順序存儲結構（即動態數組）來實現該算法。

核心算法思路

歸並過程類似於合併排序中的合併步驟：

1. 設置兩個指針 i 和 j 分別指向 LA 和 LB 的起始位置。
2. 比較 LA[i] 與 LB[j] 的值，將較小者插入 LC，並移動相應指針。
3. 重複上述步驟，直到其中一個表被遍歷完畢。
4. 將另一個表中剩餘的所有元素依次追加到 LC 末尾。

時間複雜度為 O(La_length + Lb_length)，空間複雜度為 O(La_length + Lb_length)（用於存儲結果表 LC）。

Java 代碼實現

package com.yds.list;

public class JavaMain {
    /**
     * 歸並兩個有序線性表
     * @param listA 有序線性表 LA
     * @param listB 有序線性表 LB
     * @param listC 結果線性表 LC
     */
    private static void MergeList(SequenceList<Integer> listA, SequenceList<Integer> listB, SequenceList<Integer> listC) {
        int La_length = listA.length();
        int Lb_length = listB.length();
        int i = 0, j = 0;

        // 兩表均未遍歷完時，比較元素大小，插入較小者
        while (i < La_length && j < Lb_length) {
            if (listA.get(i) < listB.get(j)) {
                listC.add(listA.get(i));
                i++;
            } else {
                listC.add(listB.get(j));
                j++;
            }
        }

        // 若 LA 有剩餘元素，全部追加到 LC
        while (i < La_length) {
            listC.add(listA.get(i));
            i++;
        }

        // 若 LB 有剩餘元素，全部追加到 LC
        while (j < Lb_length) {
            listC.add(listB.get(j));
            j++;
        }
    }

    public static void main(String[] args) {
        SequenceList<Integer> listA = new SequenceList<>();
        SequenceList<Integer> listB = new SequenceList<>();
        SequenceList<Integer> listC = new SequenceList<>();

        int[] la = {3, 5, 8, 11};
        int[] lb = {2, 6, 8, 9, 11, 15, 20};

        for (int val : la) listA.add(val);
        for (int val : lb) listB.add(val);

        MergeList(listA, listB, listC);

        // 輸出歸並結果
        for (int k = 0; k < listC.length(); k++) {
            System.out.println(listC.get(k));
        }
    }
}

運行結果

程序輸出如下，與預期的 LC 完全一致：

總結

線性表歸並是掌握多指針協作、順序存儲結構操作的基礎訓練。理解其邏輯有助於後續學習合併排序、外部排序等更複雜的算法。實現時需注意邊界條件處理，確保剩餘元素正確拷貝。