串列的應用：多項式與稀疏矩陣

大部分是 0 的資料

有些資料「看起來很大，其實幾乎都是 0」：

• 多項式 5x^1000 + 3：如果用陣列存，索引當作次方、內容當作係數，要開 1001 格，其中 999 格是 0
• 一個系有 50 位學生、學校開了 2,000 門課，「誰修了哪門課」的表有 50 × 2000 = 100,000 格，但每個人只修 8 門左右，有值的格子只有約 400 格
• 社群網站的「誰追蹤誰」：一億個帳號排成一億乘一億的表，每個人平均只追蹤幾百人

這種資料叫做稀疏（sparse）。把每一格都存下來，空間大部分花在 0 上，走訪時也大部分時間在看 0。 這一課的做法是只存非零的項，並且記下它在哪裡：

鏈結串列的節點與指標操作在第 06 課講過；這一課直接拿來用，重點放在「節點裡要放什麼」和「操作時怎麼維持排序」。

多項式的節點

每個節點代表多項式的一項，存三個欄位：

3x^4 + 7x^3 + 6x^2 - 5 存成：

head → [3 | 4] → [7 | 3] → [6 | 2] → [-5 | 0] → null
        係數 次方

串列裡一律依次方由大到小排，而且同一個次方只出現一次。維持這兩條規則，後面的相加、印出、求值都可以從頭到尾走一次就完成。

加入新的一項時，要找到它該插入的位置：

1. 串列是空的，或新項的次方比第一項還大：新節點放在最前面
2. 否則從第一項往後走，停在「最後一個次方 ≥ 新次方」的節點 cur
3. cur 的次方剛好等於新次方：只把係數加上去，不新增節點（合併同類項）
4. 否則新節點插在 cur 後面：先讓新節點指向 cur.next，再讓 cur 指向新節點

C++ 的節點寫成 struct Node { int coef, exp; Node* next; };，用 new Node{3, 4, nullptr} 建立；範例最後會把節點一個一個 delete 掉。

多項式相加：比較次方，大的先放

兩個多項式 a、b 都依次方由大到小排好。相加的做法和「合併兩條已排序的串列」幾乎一樣：用 pa、pb 分別指著兩邊目前的項，每一輪比較它們的次方：

結果串列用一個哨兵節點（dummy，第 06 課）當開頭：新的項一律接在 tail 後面，不必特別處理「結果還是空的」的情況，最後回傳 dummy.next。

每一輪至少有一邊往後走一步，所以 a 有 m 項、b 有 n 項時，迴圈最多跑 m + n 輪，時間是 O(m + n)。 如果兩邊沒有排序，每一項都要到另一邊從頭找有沒有同次方的項，會變成 O(m × n)。維持排序就是為了讓相加只要走一次。

稀疏矩陣的三元組

矩陣也一樣：只記下非零的元素，每個元素存成一個三元組（triple）：（列, 行, 值）。

    0  1  2  3  4  5                列  行  值
0 [ 0  0  3  0  0  0 ]          0:  5   6   5     ← 第 0 列：列數、行數、非零個數
1 [ 0  0  0  0  0  0 ]          1:  0   2   3
2 [ 7  0  0  0  0  2 ]   ──→    2:  2   0   7
3 [ 0  0  0  0  0  0 ]          3:  2   5   2
4 [ 0  5  0  0  8  0 ]          4:  4   1   5
                                5:  4   4   8

三元組陣列的慣例：

• 第 0 列存整個矩陣的列數、行數與非零元素個數，否則只看三元組無法知道矩陣原本多大（最後一列、最後一行可能全是 0）
• 其他列依列號、再依行號由小到大排，和一列一列掃過矩陣的順序相同；後面的轉置、相加都靠這個順序

空間比較：r 列 c 行、有 t 個非零元素的矩陣

所以 t 小於約 r × c ÷ 3 時，三元組比較省。上面的例子 30 格對 18 格；如果是 1000 × 1000、只有 5,000 個非零元素的矩陣，就是一百萬格對大約一萬五千格。

下面的範例掃兩趟：第一趟數有幾個非零元素，才知道三元組陣列要開多大；第二趟依序填入。

轉置：列與行對調，順序要重排

轉置（transpose）就是把每個元素的列與行對調：（列, 行, 值） 變成 （行, 列, 值）。

麻煩的是順序。原本的三元組依「列」排好，對調之後要依「新的列」，也就是原本的行來排，直接逐列對調會亂掉。

一般轉置：對每一行 c（0 到 cols - 1），掃一遍整個三元組，把行號是 c 的元素依序取出：

k = 1
for c in range(cols):                  # 原本的每一行
    for i in range(1, n + 1):          # 都要掃過全部 n 個元素
        if a[i][1] == c:
            b[k] = [c, a[i][0], a[i][2]]
            k += 1

兩層迴圈是 O(cols × n)。n 很小時沒問題，但如果非零元素接近 rows × cols 個，就變成 O(rows × cols²)，比直接轉置二維陣列的 O(rows × cols) 還慢。

快速轉置先花兩趟算好「每個元素該放在哪一列」：

1. count[c]：原本第 c 行有幾個非零元素（掃一遍三元組）
2. start[c]：第 c 行的元素在結果裡從第幾列開始放。第 0 行從第 1 列開始，之後每一行接在前一行後面：start[c] = start[c - 1] + count[c - 1]
3. 再掃一遍三元組：元素 （列, 行 c, 值） 直接放到 b[start[c]]，然後 start[c] 加 1，讓同一行的下一個元素放在下一列

總共是 O(cols + n)。「先數個數、再算起始位置、最後一次放好」和計數排序（演算法軌第 9 課）是同一個想法。

十字鏈結串列

三元組陣列很省空間，但它是排好序的陣列：在中間加入或刪除一個非零元素，後面的元素都要搬動，是 O(t)。 如果矩陣會一直改（例如模擬中一直有元素從 0 變成非 0），可以改用十字鏈結串列（orthogonal list）：

• 每個非零元素是一個節點，存 row、col、val，另外有兩個指標： right 指向同一列的下一個非零元素，down 指向同一行的下一個非零元素
• 每一列有一個列首、每一行有一個行首，分別串起那一列、那一行的節點

用上面的矩陣，第 2 列與第 4 列的 right 方向是：

列2 ─→ [2,0,7] ─right→ [2,5,2] ─→ null
列4 ─→ [4,1,5] ─right→ [4,4,8] ─→ null

第 0 行、第 4 行的 down 方向各只有一個節點：行0 ─→ [2,0,7]、行4 ─→ [4,4,8]。 同一個節點 [2,0,7] 同時在「列2」和「行0」兩條串列上。

每個節點同時在兩條串列上，所以可以快速走完某一列（沿著 right）或某一行（沿著 down），插入時只要在兩條串列上各改幾個指標，不必搬動其他元素。 代價是每個節點多了兩個指標，比三元組占更多空間。

重點整理

• 稀疏的資料只存非零的項，並記下它的位置：多項式記次方，矩陣記列與行
• 多項式串列的節點存 coef、exp、next，依次方由大到小、同次方只出現一次；插入時找到位置，同次方就合併係數
• 多項式相加像合併兩條已排序的串列：比較次方，大的先抄；次方相同時係數相加，和為 0 不放進結果；O(m + n)
• 用哨兵節點當結果的開頭，就不必特別處理「結果還是空的」
• 三元組：第 0 列放（列數, 行數, 非零個數），其他依列、再依行排序；空間 3 × (t + 1)，非零元素少於約三分之一時才划算
• 快速轉置先算 count（每一行幾個）與 start（每一行從哪裡放），再一次放好，O(cols + n)
• 經常插入、刪除非零元素時用十字鏈結串列：每個節點同時串在所屬的列與行上

下一課：雜湊表的實作。自己寫雜湊函數，比較鏈結法和開放定址兩種處理碰撞的方法。