考研相關文章參考資料為 wjungle 大神提供的筆記

Array 元素之位置

一維陣列

$A: array[l...u]$ $A : a r r a y [l . . . u]$ of items
- 共有 $u - l + 1$ 格
- 起始位置: $l_0$
- 元素大小: $d$
- $A[i]$ 的位置: $l_0 + (i - l) * d$

$A: array[l_1...u_1, l_2...u_2]$ $A : a r r a y [l_{1} . . . u_{1}, l_{2} . . . u_{2}]$ of items
- 有 $u_1 - l_1 + 1$ 列， $u_2 - l_2 + 1$ 行
Row-major
- $A[i, j] = l_0 + [(i - l_1) * (u_2 - l_2 + 1) + (j - l_2)] * d$
Column-major
- $A[i, j] = l_0 + [(j - l_2) * (u_1 - l_1 + 1) + (i - l_1)] * d$

$A: array[l_1...u_1, l_2...u_2, l_3...u_3, ... , l_n...u_n]$ of items
令 $k_m = u_m - l_m + 1 (m = 1,2,...,n)$
Row-major (由左往右)
- $A[i_1, i_2,...,i_n] = l_0 + [(i_1 - l_1) * k_2 * k_3 *...*k_n + (i_2 - l_2) * k_3 *...*k_n + ... + (i_{n-1} - l_{n-1}) * k_n + (i_n - l_n)] * d$
- $=l_0 + \{\sum_{p=1}^n [(i_p - l_p)*\prod_{q=p+1}^n k_q]\} * d$ $= l_{0} + {\sum_{p = 1}^{n} [(i_{p} - l_{p}) * \prod_{q = p + 1}^{n} k_{q}]} * d$
  - 令 $\prod_{q=n+1}^n k_q=1$
Column-major (由右往左)
- $A[i_1, i_2,...,i_n] = l_0 + [(i_n - l_n) * k_{n-1} * k_{n-2} *...*k_1 + (i_{n-1} - l_{n-1}) * k_{n-2} *...*k_1 + ... + (i_2 - l_2) * k_1 + (i_1 - l_1)] * d$
- $=l_0 + \{\sum_{p=1}^n [(i_p - l_p)*\prod_{q=1}^{p-1} k_q]\} * d$ $= l_{0} + {\sum_{p = 1}^{n} [(i_{p} - l_{p}) * \prod_{q = 1}^{p - 1} k_{q}]} * d$
  - 令 $\prod_{q=1}^0 k_q=1$

Lower-Triangular Matrix

令 $A$ $A$ 為 $n*n$ $n * n$ 方陣，且對角線 (不含) 右上方均為 0 元素，其餘為元素
- $A[i, j] = 0,~if~i < j$
元素個數: $\frac{n(n+1)}{2}$
為了節省空間，可用一個矩陣 $B: array[1...\frac{n(n+1)}{2}]$ $B : a r r a y [1 . . . \frac{n ( n + 1 )}{2}]$ 存放 $A[i, j]$ $A [i, j]$ 的元素，其中 $B[k]$ $B [k]$ 對應 $i,j$ $i, j$ 的方式為:
- Row-major
  - $k = \frac{i(i-1)}{2} + j$
- Column-major
  - $k = n(j - 1) - \frac{j(j-1)}{2} + i$

Upper-Triangular Matrix

令 $A$ $A$ 為 $n*n$ $n * n$ 方陣，且對角線 (不含) 左下方均為 0 元素，其餘為元素
- $A[i, j] = 0,~if~i > j$
元素個數: $\frac{n(n+1)}{2}$
為了節省空間，可用一個矩陣 $B: array[1...\frac{n(n+1)}{2}]$ $B : a r r a y [1 . . . \frac{n ( n + 1 )}{2}]$ 存放 $A[i, j]$ $A [i, j]$ 的元素，其中 $B[k]$ $B [k]$ 對應 $i,j$ $i, j$ 的方式為:
- Row-major
  - $k = n(i - 1) - \frac{i(i-1)}{2} + j$
  - 下三角之 Column-major 公式 $i,j$ 對調
- Column-major
  - $k = \frac{j(j-1)}{2} + i$
  - 下三角之 Row-major 公式 $i,j$ 對調

Symmetrix Matrix

令 $A$ 為 $n*n$ 方陣，且 $A[i, j] = A[j, i]$
為了節省空間，可用一個矩陣 $B: array[1...\frac{n(n+1)}{2}]$ $B : a r r a y [1 . . . \frac{n ( n + 1 )}{2}]$ 存放下/上三角部分元素即可，其中 $B[k]$ $B [k]$ 對應 $i,j$ $i, j$ 的 Single expression (單一公式) 為:
- $k = \frac{Max(i,j)(Max(i,j) - 1)}{2} + Min(i,j)$

Band Matrix

令 $A_{n,a,b}$ $A_{n, a, b}$ 為 $n*n$ $n * n$ 方陣，且
- 對角線左下方 $a$ 條斜線為元素
- 對角線右上方 $b$ 條斜線為元素
- 其餘為 0 元素
元素個數: $\frac{a(2n-a+1)}{2} + \frac{b(2n-b+1)}{2} - n$

Linking 方向有兩個之 link list
- LLink: 指向前一個 Node
- RLink: 指向後一個 Node
- 通常會加入 Head node (串列首): 不存資料
插入 Node: 需要改變 4 個 pointer
刪除 Node: 需要改變 2 個 pointer

令 $A = (a_1, a_2,..., a_n)$ 是一個 Generalize list， $A$ 有 $n$ 個元素 $a_1, a_2,..., a_n$ ，而 $a_i$ 元素的型態有兩種:
- Atomic data
- Sublist (另一個 Generalize list)
術語:
- $|A|$ : 表 $A$ 之長度
- Head of A: $a_1$
- Tail of A: $(a_2,..., a_n)$
資料結構:

Tag 變動欄位 Link

True Data (Atomic data)

False dlink (Pointer to Sublist)

Tag	變動欄位	Link
True	Data (Atomic data)
False	dlink (Pointer to Sublist)

根據指數由高至低儲存其係數，假設最高項指數為 $n$ $n$ ，則準備 $A: array[1,2...,n+2]$ $A : a r r a y [1, 2 . . ., n + 2]$ of int
- 第一位儲存 $n$ 的數值
- 之後依序儲存各項係數
- 缺點: 對於最高項指數很大，但零項次很多的多項式，會浪費空間
只儲存非零項次的指數與係數，假設多項式有 $k$ $k$ 個非零項次，則準備 $A: array[1,2...,2k+1]$ $A : a r r a y [1, 2 . . ., 2 k + 1]$ of int
- 第一位儲存 $k$ 的數值
- 之後依序儲存各項指數及係數
- 缺點: 不適用於零項次很少的多項式 (需要空間約為 1. 的兩倍)

使用 Link list 儲存指數與係數
- 資料結構: exp (指數) | coe (係數) | link
- 擴展 (多變數): x-exp | y-exp | coe | link
- 缺點: 可能導致各個 Node 資料結構不一致 (變數數量不同)
使用 Generalize list 儲存資料
- 資料結構:
Tripple 變動欄位 exp link

Var Variable (存變數名稱) 空

Ptr dlink (Pointer to Sublist)

No. coe (係數值)
- ex:

Tripple	變動欄位	exp
Var	Variable (存變數名稱)	空
Ptr	dlink (Pointer to Sublist)
No.	coe (係數值)

稀疏矩陣: 含有大量 0 元素的 $m*n$ 矩陣

直接用 $m*n$ $m * n$ 矩陣存放
- 浪費空間
只存非零元素之資訊，以 <Row, Col, Value> 的結構儲存資料
- 假設一個 $m*n$ $m * n$ Sparse Matrix 含有 $k$ $k$ 個非零元素，則以 $A: array[0...k, 1...3]$ $A : a r r a y [0 . . . k, 1 . . . 3]$ of int 表示
  - 第 0 列儲存 matrix 資訊: <m, n, k>

使用 Double link list: 儲存 Row 及 Col 方向，且 Node 分為兩類:
Head node: 串列首，不存資料
- 資料結構: Head (True) | Down | Right | Next
  - Down: pointer 指向所在行的第一個元素
  - Right: pointer 指向所在列的第一個元素
  - Next: pointer 指向下一個 Head node
- Head node 數量 = $Max(列數, 行數)$
Element node
- 資料結構: Head (False) | Down | Right | Row | Col | Value
  - Down: pointer 指向下一個行元素
  - Right: pointer 指向下一個列元素
  - Row, Col, Value: 非零元素之資料