[C++ 小東西] 用 Linked list 做稀疏矩陣加法

這篇是我搬運自己以前在 GitHub Pages 上 2020 年 11 月的文章，看了很久，完全不知為何這篇被獨立拿出來寫XDD 當時好多冗文贅字，盡量精簡了，希望有好閱讀一些。

---

關於 linked list 這裡有很好的講解：

• Linked List: Intro(簡介)
• Linked List: 新增資料、刪除資料、反轉

有很清楚的示意圖輔助觀念的養成，光看這兩篇便省了不少需要花在理解上的時間，也很適合收藏做為日後複習觀看。

雖然寫下關於 linked list 的介紹文有助於自身觀念釐清，但這次先著重在應用上，剛好再次熟悉並釐清了很多在 linked list 上的觀念誤區。

為何而做

本次要使用 linked list 在稀疏矩陣（sparse matrix）的加法上。

稀疏矩陣是其元素大部分為零的矩陣。為什麼特別指定稀疏矩陣？我們一般要存矩陣第一個優先會想到array 型態，然而今天遇上稀疏矩陣，既然大部分元素為 0，事實上我們可以不用做到「每一個元素都要參與運算」這件事。

用 linked list 儲存那些少數且必須的資料，需要的時候直接由 linked list 遍歷即可。

初步設計

輸入資料

這裡的 input 我們設計成： 先輸入矩陣大小 m, n，再輸入矩陣元素。前面數字輸入 column 的位置，後面數字是那個位置的值，並且用 0 判斷元素輸入結束。

以這個矩陣舉例來說：

$$
\begin{pmatrix}
1 & 6 & 0 & 85\\
5 & 0 & 0 & 0\\
0 & 0 & 2 & 0
\end{pmatrix}
$$

先輸入矩陣大小： 3 4
再輸入元素：
> 1 1 2 6 4 85 0
> 1 5 0
> 3 2 0
> 0

Linked list 的設定

Linked list 用比較不精確的話說，就是一個物件有一些自身的性質外，我們會再多存一兩個性質，去指向這個物件的前一個或後一個資料（單向或雙向的）。因為有了這個性質，很巧妙地彼此之間有了連結（link），把每個物件都像是火車一樣都串連起來了。這部分可以講的東西有很多，在此不再贅述。

這次只專注在設計我需要的 linked list。

• 節點（node）

此處的 node 我要存四個資料：值（value）、所在列（row_pos）、所在行（column_pos）以及下個node 的位置（next）：

class llNode {
private:
  int value;
  int row_pos;
  int column_pos;
  llNode *next;

public:
  llNode() : next(NULL){};
  llNode(int a) : value(a), next(NULL){};

  friend class LinkedList;
};

• Linked list 本身

創建好基本元素 node 後，可以來弄 linked list 了。 這裡我需要的功能有新增 node、列印已存在 node、列印矩陣、矩陣相加。其中要新增一個起頭的node，在這裡我們將它命名為 first。

class LinkedList {
private:
  llNode *first;

public:
  LinkedList() : first(NULL){};
  void PrintList();
  void addNode(int newrow_pos, int newcolumn_pos, int newvalue);
  void printMatrix(int m, int n);
  LinkedList matrixAdd(LinkedList A, LinkedList B);
};

功能設計

addNode

這是最基本的功能，linked list 是由節點所組成的。新增節點所需資料：行位置、列位置、值。在這程式中必須準備好這三項才能申請新節點（公務人員口吻）。

void LinkedList::addNode(int newrow_pos, int newcolumn_pos, int newvalue) {
  //content
}

接下來我需要三個 node：

1. 存我要存進去的 node（newNode）
2. 有資料傳進來必須暫時要有地方放（temp）
3. temp 有時會存放先前資料，需要多個空間放新的 node（tempNew）

llNode *newNode = new llNode(newvalue);
llNode *temp = new llNode();
llNode *tempNew = new llNode();

接下來就是要放入資料和做連接。 若是沒有資料的狀況下，linked list 的開頭應該是空的，第一個資料必須放去 first 中。若是已經有了資料，也不需要一一巡覽，只需要確認我們確實到達 linked list 尾端。因此

if (first == NULL) {
    //是空的就直接加入
    temp->value = newvalue;
    temp->row_pos = newrow_pos;
    temp->column_pos = newcolumn_pos;
    temp->next = NULL;

    first = temp;
} else {
    //若不是空的就先到達尾端再加入
    temp = first;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    tempNew->value = newvalue;
    tempNew->row_pos = newrow_pos;
    tempNew->column_pos = newcolumn_pos;
    tempNew->next = NULL;
    temp->next = tempNew;
}

再來要進入重頭戲了。

matrixAdd

在 matrixAdd 中我需要兩個 linked list 當變數（也就是兩個矩陣），並利用 linked list 的特性去做巡覽和相加。

LinkedList LinkedList::matrixAdd(LinkedList A, LinkedList B) {
  //content
}

首先要設新的 linked list C 去放置我們相加處理過後的元素。 在巡覽前我們必須要先設定好開頭，電腦才會知道我們要從 linked list 的哪裡開始。

LinkedList C;
llNode *nodeA = A.first;
llNode *nodeB = B.first;

接下來要設立一個迴圈。我使用的方式是先判斷巡覽到的 node 是否都有東西，再去判斷要怎麼透過辨識 row 和 column 的位置去做相加。如果其中一個矩陣已經巡覽完畢沒東西的話，那個位置就是另一個矩陣巡覽到的元素，直接放進去 linked list C 中

while (nodeA != NULL && nodeB != NULL) {
  //content
}
  
while (nodeA != NULL) {
  C.addNode(nodeA->row_pos, nodeA->column_pos, nodeA->value);
  nodeA = nodeA->next;　//要記得巡覽後指向下一個
}
while (nodeB != NULL) {
  C.addNode(nodeB->row_pos, nodeB->column_pos, nodeB->value);
  nodeB = nodeB->next;
}

接著我們專注在第一個 while 迴圈中。這邊我的方式是先比對 row 的位置一不一樣，接著再比對 column 的位置。

while (nodeA != NULL && nodeB != NULL) {
  if (nodeA row 的位置 = nodeB row 的位置) {
    if (nodeA column 的位置 = nodeB column 的位置) {
      //指定sum = 巡覽到的 nodeA + nodeB;
      //加入C中
      //nodeA指向下一個
      //nodeB指向下一個
    } else { 
      //也就是row一樣但column位置不同，比較column位置大小
      if (nodeA column 的位置較小) {
        //存nodeA 的資料進去C
        //nodeA指向下一個
      } else {
        //存nodeB 的資料進去C
        //nodeB指向下一個
      }
    }
  } else { //兩個row的位置就已經不同的狀況
    //先比較row位置的大小
    if (nodeA row 的位置較小) {
        //存nodeA 的資料進去
        //nodeA指向下一個
    } else {
        //存nodeB 的資料進去C
        //nodeB指向下一個
    }
  }
}

當初在創建 linked list 的元素順序很重要，如果亂了這裡的設置必須要失敗，但是我也懶得寫防呆，用程式碼實現差不多是這樣：

while (nodeA != NULL && nodeB != NULL) {
  if (nodeA->row_pos == nodeB->row_pos) {
    if (nodeA->column_pos == nodeB->column_pos) {
      int sum = nodeA->value + nodeB->value;
      C.addNode(nodeA->row_pos, nodeA->column_pos, sum);
      nodeA = nodeA->next;
      nodeB = nodeB->next;
    } else {
      if (nodeA->column_pos < nodeB->column_pos) {
        C.addNode(nodeA->row_pos, nodeA->column_pos, nodeA->value);
        nodeA = nodeA->next;
      } else {
        C.addNode(nodeB->row_pos, nodeB->column_pos, nodeB->value);
        nodeB = nodeB->next;
      }   
    }
  } else {
    if (nodeA->row_pos < nodeB->row_pos) {
      C.addNode(nodeA->row_pos, nodeA->column_pos, nodeA->value);
      nodeA = nodeA->next;
    } else {
      C.addNode(nodeB->row_pos, nodeB->column_pos, nodeB->value);
      nodeB = nodeB->next;
    }
  }
}

在 GitHub 查看完整程式碼

測試結果

input:

Enter the number of row and column:
> 4 5

Enter the element of matrix A:
> 1 2 5 8 0
> 2 3 4 55 0
> 3 7 0
> 1 100 0

Enter the element of matrix B:
> 2 8 3 4 0
> 2 44 0
> 1 9 3 6 0
> 0

output:

The matrix A:
2 0 0 0 8
0 3 0 55 0
0 0 7 0 0
100 0 0 0 0

The matrix B:
0 8 4 0 0
0 44 0 0 0
9 0 6 0 0
0 0 0 0 0

The matrix A+B:
2 8 4 0 8
0 47 0 55 0
9 0 13 0 0
100 0 0 0 0