# [資料結構] CH3. Arrays

* 陣列是連續的儲存空間，它會有一個索引(index)對應到一個資料(data)。
* 在C++中，索引從`0`開始。
* 下圖是個陣列A的範例：
* A[0]=5, A[3]=4, A[4]=26

digraph Array
{	
    label="陣列A"
	node[shape=record]
	store1 [label="<f0> \<0,5\>|<f1> \<1,8\>|<f2>\<2,3\>|<f3>\<3,4\>|<f4>\<4,26\>"];
}

* 因為在記憶體中，陣列是連續的空間，我們便可以利用指標來尋找我們要的地方。
* 假設有一指標`p`指向陣列A的頭，而陣列A一格的資料大小是`d`，我們可以說：
* A[0]的位置是p。
* A[4]的位置是p+4d。
* 上面那種題目在這邊頗愛考，給你p和d，要你求某位置的表示法等等。
* 在接下來的2D或是三角矩陣都會要你求，等等會介紹。
## 2D Array
* 2D Array稱作**二維陣列**，有時候我們直接叫做**矩陣**。
* 假設今天有個矩陣A：$A=\begin{bmatrix}1 &5 &9 \\ 2 &6 &10 \\ 3 &7 &11 \\ 4 &8 &12 \end{bmatrix}$
* 該矩陣的row數(直排數)為4，column數(橫列數)為3。
* $A_{i,j}$表示矩陣中第`i` row，第`j` column的值。
* 由於C++是從0開始，因此$A_{1,1}$是A[0][0]=1；$A_{3,2}$=A[2][1]=7。
`特別注意下面的所有式子到底是Aij還是A[i][j]，切記不要搞混！！`
* 前面說過，陣列是連續的空間。在二維中根據連接方式不同，分為`Row-major`和`Column-major`。
* C++中預設的二維都是Row-major，我個人不知道有沒有辦法更改。

### Row-major
* 同樣以上面的矩陣$A=\begin{bmatrix}1 &5 &9 \\ 2 &6 &10 \\ 3 &7 &11 \\ 4 &8 &12 \end{bmatrix}$來舉例，當A是個Row-major的矩陣時，代表它在記憶體中儲存的順序是：

digraph Array
{	
	node[shape=record]
	store1 [label="<f0>1 |<f1>5 |<f2>9|<f3>2|<f4>6|<f5>10|<f6>..."];
}

* 因此同樣可以利用指標來找元素：
* `p`是指向開頭的指標，`i`是元素的row，`j`是元素的column，`c`是陣列的總column，`d`是每格的大小。
* A[i][j]=p+((i)*c+(j))*d.
* A[2][1]=p+(2*3+1)*d = p+7d = 7

### Column-major
* 同樣以上面的矩陣$A=\begin{bmatrix}1 &5 &9 \\ 2 &6 &10 \\ 3 &7 &11 \\ 4 &8 &12 \end{bmatrix}$來舉例，當A是個Column-major的矩陣時，代表它在記憶體中儲存的順序是：

digraph Array
{	
	node[shape=record]
	store1 [label="<f0>1 |<f1>2|<f2>3|<f3>4|<f4>5|<f5>6|<f6>..."];
}

* 當然，同樣可以利用指標來找元素：
* `p`是指向開頭的指標，`i`是元素的row，`j`是元素的column，`r`是陣列的總row，`d`是每格的大小。
* A[i][j]=p+((j)*r+(i))*d.
* A[2][1]=p+(1*4+2)*d = p+6d = 7

#### 練習
* 已知一個矩陣A，$A_{3,2}$的記憶體位置為1110，$A_{2,3}$的位置是1115，每個空間大小為1，請問
- a) 此矩陣是Row-major還是Column-major？
- b) 此矩陣的開頭指標應為哪個位置？
- c) $A_{5,4}$的位置在哪裡？
* 答案請反白
* <p><font color="#FFFFFF">Column-major</font></p>
* <p><font color="#FFFFFF">1102</font></p>
* <p><font color="#FFFFFF">1124</font></p>

## Lower-Triangular Matrix
* Lower-Triangular Matrix(下三角矩陣)，$A_{i,j}=0$, when $i<j$，且必定為方陣。
* 
* 在Row-major和Column-major的情形下都可推導出公式：
* Row-major: $Location(A_{i,j})=l_s+[\frac{i*(i-1)}{2}+j-1]*d$。
* Column-major： $Location(A_{i,j})=l_s+[i+n*(j-1)-\frac{j*(j-1)}{2}-1]*d$。

## Upper-Triangular Matrix
* 其實就反過來，$A_{i,j}=0$, when $i>j$，且必定為方陣。
* 
* 也一樣可以推導公式：
* Row-major: $Location(A_{i,j})=l_s+[\frac{j*(j+1)}{2}+i-1]*d$。
* Column-major: $Location(A_{i,j})=l_s+[j+n*(i-1)-\frac{i*(i-1)}{2}-1]*d$。

###### tags: `DS` `note`