書籍資訊

  • 書名：《圖解演算法：使用 C#》
  • 類型：線性結構與矩陣操作讀書筆記

這篇在講什麼

這一篇把幾個很常一起出現的主題放在一起整理：

  • 陣列與鏈結串列的差別
  • 矩陣的基本運算
  • 稀疏矩陣的表示方式
  • 鏈結串列的基本操作

陣列與鏈結串列怎麼選

這兩種結構都很常見，但設計取向不一樣。

陣列

  • 記憶體通常是連續的
  • 可以用索引直接存取
  • 讀取快，插刪通常要搬動元素

鏈結串列

  • 節點彼此靠指標串起來
  • 中間插入與刪除比較靈活
  • 想找第 k 個元素時，通常得一路走過去

所以可以先用一句話記住：

  • 要快取值：偏向陣列
  • 要快改結構：偏向鏈結串列

矩陣加法

矩陣加法的前提很簡單：

  • 兩個矩陣的列數與行數都要一樣

做法就是把相同位置的元素相加。
它本質上是「同座標做對應運算」。

矩陣乘法

矩陣乘法比加法多一個前提：

  • A 的欄數必須等於 B 的列數

如果：

  • A 是 m x n
  • B 是 n x p

那結果 AB 會是 m x p。

每個位置的值，都是：

  • A 某一列
  • 與 B 某一欄
  • 做逐項相乘後加總

這類計算在圖學、線性代數、轉換運算裡都很常見。

矩陣轉置

轉置就是把列和欄對調。

也就是：

  • 原本的 A[i, j]
  • 會變成 B[j, i]

它常被用在：

  • 資料方向調整
  • 演算法推導
  • 線性代數相關處理

稀疏矩陣

如果一個矩陣裡大部分元素都是 0，直接用完整二維陣列存，有時很浪費空間。

這時可以改用稀疏矩陣表示法，只記錄：

  • 行索引
  • 列索引
  • 非零值

這樣的好處是：

  • 節省空間
  • 更適合做只關心非零元素的運算

鏈結串列的基本操作

鏈結串列最常見的操作包括：

  • 插入
  • 刪除
  • 遍歷
  • 反轉

這些操作的關鍵，通常都不是值本身，而是：

你有沒有把節點之間的連結關係接對。

插入

插入新節點時，要先把新節點接到正確位置，再改動前一個節點的指向。
順序錯了，很容易把後面的鏈結弄丟。

刪除

刪除節點時，重點不是把節點內容清空，而是讓前一個節點直接指向下一個節點。

反轉

反轉鏈結串列最常見的做法是用三個指標：

  • prev
  • curr
  • next

每走一步，就把箭頭反過來。

public static ListNode Reverse(ListNode head)
{
    ListNode prev = null;
    ListNode curr = head;

    while (curr != null)
    {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

我自己的整理

這一篇看似把很多主題塞在一起，但其實中心很一致：

  • 陣列與鏈結串列在講「資料怎麼排」
  • 矩陣運算在講「二維資料怎麼算」
  • 稀疏矩陣在講「怎麼更省空間」

也就是說，底層問題還是同一個：

資料的形狀不同，操作方式就要跟著改。

先記住的重點

  • 陣列擅長索引存取，鏈結串列擅長結構調整
  • 矩陣加法看同位置，矩陣乘法看列乘欄
  • 轉置的本質是把列與欄交換
  • 稀疏矩陣的重點是只存非零值
  • 鏈結串列題目最容易錯在節點連結順序