《圖說演算法-使用C#》要點摘錄 – 「數組與鏈表」

數組與鏈表

• 數組

  • 靜態數據結構

  • 使用連續記憶空間儲存

  • 刪除和插入時需要移動大量資料

  • 讀取與修改任一元素為固定時間

• 鏈表

  • 動態數據結構

  • 不使用連續記憶空間儲存

  • 刪除和插入方便，不需要移動資料

  • 讀取和修改都要先循序找到資料為止

矩陣加法

• 相加的矩陣之間，行列數必須相等，相加後的新矩陣行列數也相等

• 將每個對應坐標的元素相加即可

  • public static int[,] Matrix_Add(int[,] A, int[,] B)
    {
        if(A.GetLength(0) != B.GetLength(0) || A.GetLength(1) != B.GetLength(1))
        {
            return null;
        }
    ​
        int[,] res = new int[A.GetLength(0), A.GetLength(1)];
    ​
        for (int i = 0; i < A.GetLength(0); i++)
        {
            for (int j = 0; j < A.GetLength(1); j++)
            {
                //相同坐標的元素相加，再賦值在新矩陣的對應坐標上
                res[i, j] = A[i, j] + B[i, j];
            }
        }
    ​
        return res;
    }

矩陣乘法

• 設矩陣A 需要乘以 矩陣B，矩陣A的列數必須等矩陣B的行數。結果的行列數為矩陣A的行數和B矩陣的列數

  • A[m, n] * B[n, p] = AB[m, p]

  • 設Ma[2, 3], Mb[3, 2]

    • 結果矩陣中的每個元素則為在A矩陣上，該元素的行坐標上每一列和B矩陣上，該元素的列坐標每一行元素的積的總和

    • Mab[0, 0] = Sum(Ma[0, 0~2], Mb[0~2, 0])

  • public static int[,] Matrix_Multiply(int[,] A, int[,] B)
    {
        if (A.GetLength(1) != B.GetLength(0)) { return null; }
    ​
        int resCol = A.GetLength(0);
        int resRow = B.GetLength(1);
    ​
        int loopTime = A.GetLength(1);
    ​
        int[,] res = new int[resCol, resRow];
    ​
        for (int i = 0; i < resCol; i++)
        {
            for (int j = 0; j < resRow; j++)
            {
                int curr = 0;
                for (int k = 0; k < loopTime; k++)
                {
                    //res[i, j] = Sum of A[i, k] * B[k, j]
                    curr += A[i, k] * B[k, j];
                }
                res[i, j] = curr;
            }
        }
    ​
        return res;
    }

轉置矩陣

• 原矩陣的行坐標元素與列坐標元素互換，如果B是A的轉置矩陣，則B[i, j] = A[j, i]

• public static int[,] Matrix_Tranpose(int[,] A)
  {
      int[,] res = new int[A.GetLength(0), A.GetLength(1)];
  ​
      for (int i = 0; i < res.GetLength(0); i++)
      {
          for (int j = 0; j < res.GetLength(1); j++)
          {
              //Tranpose
              res[i, j] = A[j, i];
          }
      }
  ​
      return res;
  }

稀疏矩陣

• 一個矩陣中大部分的元素為0，使用傳統的二維數組去儲存會十分浪費空間。

• 改進方法是利用三項式，把矩陣內的每一個非零項目以（行坐標、列坐標、值）的方式表示。

  • 假如矩陣有n個非零項目，其二維數值取值則為（0:n, 1:3）

  • A(0, 1) = 矩陣列數

  • A(0, 2) = 矩陣行數

  • A(0, 3) = 非零項目總數

  • 從A(1) 開始就是非零項目的具體行、列坐標和值了

• public static (int x, int y, int val)[] Matrix_Tranpose(int[,] A)
  {
      List<(int x, int y, int val)> res = new List<(int x, int y, int val)>();
      int a_Col = A.GetLength(0);
      int a_Row = A.GetLength(1);
  ​
      //定義首項A(ColCount, RowCount, nonZeroCount)
      res.Add((a_Col, a_Row, 0));
  ​
      for (int i = 0; i < A.GetLength(0); i++)
      {
          for (int j = 0; j < A.GetLength(1); j++)
          {
              if(A[i, j] != 0)
              {
                  //Add nonZero element
                  res.Add((i, j, A[i, j]));
                  //nonZeroCount++
                  res[0] = (a_Col, a_Row, res[0].val + 1);
              }
          }
      }
  ​
      return res.ToArray();
  }

單向鏈表算法

• 單向鏈表上的每一個節點需要一個指向下個節點的指針和至少一個數據欄位

  • 通過訪問當前節點.next前往下一個節點

• 只有存在根節點的引用，就可以對整個鏈表進行走訪、加入、刪除等操作。因此盡量不要移動根節點指標

• public class LinkedList
  {
      public StudentNode root;
  ​
      public void Insert(string name, int score)
      {
          StudentNode newStudent = new StudentNode(name, score);
          StudentNode curr = root;
          //遍歷到鏈表結尾，把新節點插入在尾部
          while(curr.nextNode != null)
          {
              curr = curr.nextNode;
          }
          curr.nextNode = newStudent;
      }
  ​
      public bool IsEmpty()
      {
          return root == null;
      }
      
      //從根節點開始打印所有節點
      public void Print()
      {
          StudentNode curr = root;
          while(curr != null)
          {
              Console.WriteLine($"Name:{curr.studentName} - Score:{curr.studentScore}");
              curr = curr.nextNode;
          }
      }
  }
  public class StudentNode
  {
      public StudentNode nextNode; //下一個節點的引用
      public string studentName;
      public int studentScore;
  ​
      public StudentNode(string name, int score)
      {
          this.studentName = name;
          this.studentScore = score;
      }
  }

插入

• 插在第一個節點前：新節點指向原來的根節點，使第一個節點成為根節點

• 插在最後一個節點後：遍歷到最後，將最後的節點指向新節點，新節點指向空

• 插在任意位置：遍歷的同時將位置參數遞減，當遞減數 == 1的時候，代表當前節點的下一個節點就是我們新節點的位置。先讓新節點指當前節點原來的下個節點，再將當前節點的下個節點改為新節點。

• public void Insert(string name, int score, int insertPos)
  {
      StudentNode newStudent = new StudentNode(name, score);
      StudentNode curr = root;
      if(insertPos == 0) //Add at head
      {
          if (curr != null)
          {
              newStudent.nextNode = curr;
          }
          root = newStudent;
          return;
      }
      else
      {
          if(insertPos == -1) //Add at tail
          {
              while(curr.nextNode != null)
              {
                  curr = curr.nextNode;
              }
              curr.nextNode = newStudent;
              return;
          }
          else //Add in specific position
          {
              while (insertPos > 1) //when pos == 1, mean curr.next is our target position
              {
                  if(curr.nextNode == null) //if meet tail while finding position, then just add it at tail
                  {
                      curr.nextNode = newStudent;
                      return;
                  }
                  //Finding target position
                  curr = curr.nextNode;
                  insertPos--;
              }
              //insert newNode at middle of currNode and nextNode;
              newStudent.nextNode = curr.nextNode;
              curr.nextNode = newStudent;
              return;
          }
      }
  }

刪除

• 刪除首節點：將根節點改為原來根節點的下一個節點

• 刪除中間/尾部節點：遍歷的同時將位置參數遞減，當遞減數 == 1的時候，代表當前節點的下一個節點就是我們要刪除的節點。先讓當前節點指向下個節點的下個節點，當前節點的下個節點失去入口後就不會在存在於linked list中。

• public void Delete(int pos)
  {
      StudentNode curr = root;
  ​
      if (pos == 0) //Delete Head
      {
          root = curr.nextNode;
      }
  ​
      while (pos > 1) //finding target delete pos, if pos == 1, mean next node should be deleted
      {
          if(curr.nextNode.nextNode == null) //If pos > linked list lenght, delete tail
          {
              curr.nextNode = null;
              return;
          }
          curr = curr.nextNode;
          pos--;
      }
      curr.nextNode = curr.nextNode.nextNode; //delete curr.next        
  }

反轉

• public void Reverse()
  {
      StudentNode prev = null;
      StudentNode curr = root;
      while(curr != null)
      {
          //由於要切開當前節點與其下個節點之間的鏈接，因此需要保存下個節點的引用
          StudentNode originNext = curr.nextNode;
          //把當前節點的下一個節點設為前面的節點
          curr.nextNode = prev;
          //把前一個節點和當前節點往後推
          prev = curr;
          curr = originNext;                
      }
      //最後prev會變成新的根節點
      root = prev;
  }