陣列 (Array) 　　　　　授課老師：蕭志明.

Presentation on theme: "陣列 (Array) 　　　　　授課老師：蕭志明."— Presentation transcript:

1 陣列 (Array) 　　　　　授課老師：蕭志明

2 陣列特性 陣列可說是最基本的資料結構，也可將陣列稱為循序串列，因為每一元素的排列是依序的。
線性串列又稱循序串列（sequential list）或有序串列（ordered list）。其特性乃是每一項依據它在串列的位置，可以形成一個線性的排列次序，所以x[i]在 x[i + 1]之前。

3 陣列的表示法 線性串列經常發生的操作如下： 1. 取出串列中的第i項；0≤ i ≤ n-1。 2. 計算串列的長度。
2. 計算串列的長度。 3. 由左至右或由右至左讀此串列。 4. 在第i項加入一個新值，使其原來的第i，i+1，......，n項變為第i+1，i+2，......，n+1項。 5. 刪除第i項，使原來的第i+1，i+2，......，n項變為第i，i+1，......，n-1項。

4 陣列的表示法 在C程式語言中常利用陣列設置線性串列，以線性的對應方式將元素ai置於陣列的第i個位置上，若要讀取ai時，可利用ai的相對位址等於陣列的起始位址加i*d來求得，其中d是每一元素所佔空間的大小，不要忘記C的陣列從0開始喔！

5 一維陣列 一維陣列（one dimension array）
若陣列是A[0 : u-1]，並假設每一個元素佔d個空間，則A[i]=α+i*d，其中α是陣列的起始位置。

6 一維陣列（續） Example: 記憶體配置 圖示 1 2 3 4 5 6 7 8 9 int ary[10];
ary[i]的記憶體位置 = 陣列第一個元素位置 + (i * 所宣告資料型態所佔的大小) = ary + i*4 //整數長度為4Bytes 圖示 索引值 1 2 3 4 5 6 7 8 9 內容值

7 一維陣列記憶體圖示 記憶體位置 ary[10] 陣列索引 x+0*4 ary[0] x+1*4 ary[1] x+2*4 = x+8

8 二維陣列 假若有一陣列是A[0 : u1-1, 0 : u2-1]，表示此陣列有u1列及u2行；每一列是由u2個元素組成。
二維陣列化成一維陣列時，對映方式有二種：一種以列為主（row-major），二為以行為主（column-major）。

9 二維陣列（以列為主） 以列為主：視此陣列有u1個元素0, 1, 2, ..., u1-1，每一元素有u2個單位，每個單位佔d個空間。其情形如圖2-1所示：

10 二維陣列（以列為主） 　由圖2-1知A[i,j]=α+i*u2d+j*d，其中α為此陣列第一個元素的位址

11 二維陣列（以行為主） 以行為主：視此陣列有u2個元素0, 1, 2, ..., u2，其中每一元素含有u1個單位，每單位佔d個空間，其情形如圖2-2所示：

12 二維陣列（以行為主） 由圖2-2知A[i,j]=α+j*u1d+i*d，其中α為此陣列第一個元素的位址

13 陣列的表示法 　假若陣列是A[s1 : u1 , s2 : u2]，則此陣列共有m=u1- s1+1列，n=u2-s2+1行。計算A(i,j)的位址如下： 1. 以列為主： A[i,j]=α+(i-s1)nd+(j-s2)d 2. 以行為主： A[i,j]=α+(j-s2)md+(i-s1)d

14 二維陣列 Example: 二維陣列的記憶體位置 圖示 int ary2d[5][4]; ary2d[i][j]的記憶體位置
= 陣列第一個元素位置 +[ i*每一列的元素個數 + j]*(所宣告資料型態所佔的大小) = ary2d + (i*4 + j) * 4 圖示 第一行 第二行 第三行 第四行 第一列 (0,0) (0,1) (0,2) (0,3) 第二列 (1,0) (1,1) (1,2) (1,3) 第三列 (2,0) (2,1) (2,2) (2,3) 第四列 (3,0) (3,1) (3,2) (3,3) 第五列 (4,0) (4,1) (4,2) (4,3)

15 二維陣列記憶體圖示 記憶體位置 ary2d[5][4] 陣列索引 x+(0*4+0)*4 = x ary2d[0][0]
… x+(4*4+0)*4 = x+64 ary2d[4][0] x+(4*4+1)*4 = x+68 ary2d[4][1] x+(4*4+2)*4 = x+72 ary2d[4][2] x+(4*4+3)*4 = x+76 ary2d[4][3]

16 二維陣列練習

17 二維陣列練習

18 三維陣列 Example: 二維陣列的記憶體位置 圖示 int ary3d[3][4][3]; ary3d[i][j][k]的記憶體位置
= 陣列第一個元素位置 +[i*j的個數*k的個數 + j*k的個數 + k]*(所宣告資料型態所佔的大小) = ary3d + (i*4*3 + j*3 + k) * 4 圖示 i j k

19 陣列的一些應用 上三角形和下三角形表示法 多項式表示法 魔術方陣

20 上三角形和下三角形表示法 若一矩陣的對角線以下的元素均為零時，亦即aij=0，i>j，則稱此矩陣為上三角形矩陣（upper triangular matrix）。反之若一矩陣的對角線以上的元素均為零，亦即aij= 0，i<j，此矩陣稱為下三角形矩陣（lower triangular matrix），如圖2-4所示：

21 上三角形和下三角形表示法 由上述得知一個n×n個的上、下三角形矩陣共有[ n(n+1) ]/2個元素，依序對映至D(1:[ n(n+1) ]/2 ) 。

22 上三角形和下三角形表示法 以列為主： 一個n×n的上三角形矩陣其元素分別對映至D陣列，如下所示：
∴aij=D(k)　其中k=n(i-1)-[i(i-1)]/2+j

23 上三角形和下三角形表示法 例如圖2-4之(a)的a34元素對映D(k)：

24 上三角形和下三角形表示法 假使是一個n×n的下三角形矩陣，其元素分別對映至D陣列，如下所示：
∴aij=D(k)其中k=[i(i-1)]/2+j 例如圖2-4之(b)的下三角形矩陣的a32位於D(k)，而k=[3(3-1) ] /2 +2=5

25 上三角形和下三角形表示法 2.以行為主： 上三角形矩陣的對應情形如下： ∴aij=D(k) 其中k=[j(j-1)]/2+i
例如圖2-4之(a)的a34位於D(k)，其中 k=[ 4(4-1) ] /2+3=6+3=9

26 上三角形和下三角形表示法 而下三角形矩陣對應情形如下： ∴aij=D(k)其中k=n(j-1)-[j(j-1)]/2+i
如圖2-4之(b)的a32位於D(k)，其中 k=4(2-1)-[2(2-1) /2 ]+3=4-1+3=6

27 上三角形和下三角形表示法 　由此可知上三角形矩陣以列為主和下三角形以行為主的計算方式略同，而上三角形矩陣以行為主的計算方式與下三角形以列為主的計算方式略同。

28 多項式表示法 有一多項式p=anxn+an-1xn a1x+a0，我們稱A為n次多項式，aixj是多項式的項（0≤ i ≤ n, 1≤ j ≤ n）其中ai為係數，x為變數，j為指數。

29 多項式表示法 多項式使用線性串列來表示有兩種方法：
使用一個n+2長度的陣列，依據指數由大至小依序儲存係數，陣列的第一個元素是此多項式最大的指數，如p=(n, an, an-1, ..., a0) 。 另一種方法只考慮多項式中非零項的係數，若有m項，則使用一個2m+1長度的陣列來儲存，分別存每一個非零項的指數與係數，而陣列中的第一個元素是此多項式非零項的個數。

30 多項式表示法 例如有一多項式 p=8x5+6x4+3x2+12分別利用第1種和第2種方式來儲存，其情形如下：

31 多項式表示法 假若是一個兩變數的多項式，那如何利用線性串列來儲存呢？此時需利用二維陣列，若m, n分別是兩變數最大的指數，則需要一個(m+1)×(n+1)的二維陣列。如多項式pxy=8x5+6x4y3+4x2y+3xy2+7，則需要一個(5+1)×(3+1)=24的二維陣列，表示的方法如下：

32 多項式表示法

33 多項式表示法 兩多項式A、B相加其原理很簡單，比較兩多項式時，有下列三種情況： 這三種情況的運作情形，請參閱程式實作。

34 多項式表示法

35 多項式表示法

36 魔術方陣 有一n×n的方陣，其中n為奇數，請你n×n的魔術方陣，將1到n2的整數填入其中，使其各列、各行及對角線之和皆相等。

37 魔術方陣 做法很簡單，首先將1填入最上列的中間格，然後往左上方走， (1)以1的級數增加其值，並將此值填入空格；
(2)假使方格已填滿，則在原地的下一方格填上數字，並繼續做； (3)若超出方陣，則往下到最底層或往右到最右方，視兩者那一個有方格，則將數目填上此方格； (4)若兩者皆無方格，則在原地的下一方格填上數字。

38 魔術方陣 例如有一5×5的方陣，其形成魔術方陣的步驟如下，並以上述(1) 、(2) 、(3) 、(4)規則來說明。

39 魔術方陣 1.將1填入此方陣最上列的中間方格，如下所示：

40 魔術方陣 2.承1.往左上方走，由於超出方陣，依據規格(3)發現往下的最底層有空格，因此將2填上。如下所示：

41 魔術方陣 3.承2.往左上方，依據規格(1)將3填上，然後再往左上方，此時，超出方陣，依據規則(3)將4填在最右方的方格，如下所示：

42 魔術方陣 4.承3.往左上方，依據規則(1)將5填上，再往左上方時，此時方格已有數字，依據規則(2)往5的下方填，如下所示：

43 魔術方陣 5.餘此類推，依據上述四個規格繼續填，填到15的結果如下：

44 魔術方陣 6.承5.此時往左上方，發現往下的最底層和往右的最右方皆無空格，依據規則(4)在原地的下方，將此數字填上，如下所示：

45 魔術方陣 7.繼續往下填，並依據規則(1)、(2)、(3)、(4)最後的結果如下：
此時讀者可以算算各行、各列及對角線之和是否皆相等，答案是肯定的，其和皆為65。