[資料結構] CH3. Arrays

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

• 因為在記憶體中，陣列是連續的空間，我們便可以利用指標來尋找我們要的地方。
  • 假設有一指標p指向陣列A的頭，而陣列A一格的資料大小是d，我們可以說：
    • A[0]的位置是p。
    • A[4]的位置是p+4d。
• 上面那種題目在這邊頗愛考，給你p和d，要你求某位置的表示法等等。
  • 在接下來的2D或是三角矩陣都會要你求，等等會介紹。

2D Array

• 2D Array稱作二維陣列，有時候我們直接叫做矩陣。
• 假設今天有個矩陣A：
  $A=\left[\begin{array}{ccc}1& 5& 9\\ 2& 6& 10\\ 3& 7& 11\\ 4& 8& 12\end{array}\right]$
  • 該矩陣的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=\left[\begin{array}{ccc}1& 5& 9\\ 2& 6& 10\\ 3& 7& 11\\ 4& 8& 12\end{array}\right]$來舉例，當A是個Row-major的矩陣時，代表它在記憶體中儲存的順序是：

• 因此同樣可以利用指標來找元素：
  • 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=\left[\begin{array}{ccc}1& 5& 9\\ 2& 6& 10\\ 3& 7& 11\\ 4& 8& 12\end{array}\right]$來舉例，當A是個Column-major的矩陣時，代表它在記憶體中儲存的順序是：

• 當然，同樣可以利用指標來找元素：
  • 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}$的位置在哪裡？
• 答案請反白

  • Column-major

  • 1102

  • 1124

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\ast (i-1)}{2}+j-1]\ast d$。
  • Column-major：
    $Location(A_{i,j})=l_s+[i+n\ast (j-1)-\frac{j\ast (j-1)}{2}-1]\ast d$。

Upper-Triangular Matrix

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

tags: DS note