资源描述
2-1陣列可說是最基本的資料結構，也可將陣列稱為循序串列，因為每一元素的排列是依序的。2-22.1 陣列的表示法陣列的表示法 線性串列又稱循序串列（sequential list）或有序串列（ordered list）。其特性乃是每一項依據它在串列的位置，可以形成一個線性的排列次序，所以xi在 xi+1之前。2-32.1 陣列的表示法陣列的表示法線性串列經常發生的操作如下：1.取出串列中的第i項；0 i n-1。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項。2-42.1 陣列的表示法陣列的表示法 在C程式語言中常利用陣列設置線性串列，以線性的對應方式將元素ai置於陣列的第i個位置上，若要讀取ai時，可利用ai的相對位址等於陣列的起始位址加i*d來求得，其中d是每一元素所佔空間的大小，不要忘記C的陣列從0開始喔！2-52.1 陣列的表示法陣列的表示法2.1.1 一維陣列（one dimension array）若陣列是A0:u-1，並假設每一個元素佔d個空間，則Ai=+i*d，其中是陣列的起始位置。2-62.1 陣列的表示法陣列的表示法2.1.2 二維陣列 假若有一陣列是A0:u1-1,0:u2-1，表示此陣列有u1列及u2行；每一列是由u2個元素組成。二維陣列化成一維陣列時，對映方式有二種：一種以列為主（row-major），二為以行為主（column-major）。2-72.1 陣列的表示法陣列的表示法 以列為主：視此陣列有u1個元素0,1,2,.,u1-1，每一元素有u2個單位，每個單位佔d個空間。其情形如圖2-1所示：2-82.1 陣列的表示法陣列的表示法2-92.1 陣列的表示法陣列的表示法 由圖2-1知Ai,j=+i*u2d+j*d，其中為此陣列第一個元素的位址2-102.1 陣列的表示法陣列的表示法以行為主：視此陣列有u2個元素0,1,2,.,u2，其中每一元素含有u1個單位，每單位佔d個空間，其情形如圖2-2所示：2-112.1 陣列的表示法陣列的表示法2-122.1 陣列的表示法陣列的表示法 由圖2-2知Ai,j=+j*u1d+i*d2-132.1 陣列的表示法陣列的表示法 假若陣列是As1:u1,s2:u2，則此陣列共有m=u1-s1+1列，n=u2-s2+1行。計算A(i,j)的位址如下：1.以列為主：Ai,j=+(i-s1)nd+(j-s2)d 2.以行為主：Ai,j=+(j-s2)md+(i-s1)d2-142.1 陣列的表示法陣列的表示法2-152.1 陣列的表示法陣列的表示法2-162.1 陣列的表示法陣列的表示法2.1.3 三維陣列2-172.1 陣列的表示法陣列的表示法 一般三維陣列皆先化為二維陣列後再對映到一維陣列，對映方式也有二種：一為以列為主，二為以行為主。2-182.1 陣列的表示法陣列的表示法 以列為主：視此陣列有u1個u2u3的二維陣列，每一個二維陣列有u2個元素，每個u2皆有u3d個空間。2-192.1 陣列的表示法陣列的表示法2-202.2 上三角形和下三角形表示法上三角形和下三角形表示法 若一矩陣的對角線以下的元素均為零時，亦即aij=0，ij，則稱此矩陣為上三角形矩陣（upper triangular matrix）。反之若一矩陣的對角線以上的元素均為零，亦即aij=0，ij，此矩陣稱為下三角形矩陣（lower triangular matrix），如圖2-4所示：2-212.2 上三角形和下三角形表示法上三角形和下三角形表示法2-222.2 上三角形和下三角形表示法上三角形和下三角形表示法 由上述得知一個nn個的上、下三角形矩陣共有 n(n+1)/2個元素，依序對映至D(1:n(n+1)/2)。2-232.2 上三角形和下三角形表示法上三角形和下三角形表示法1.以列為主：一個nn的上三角形矩陣其元素分別對映至D陣列，如下所示：aij=D(k)其中k=n(i-1)-i(i-1)/2+j2-242.2 上三角形和下三角形表示法上三角形和下三角形表示法例如圖2-4之(a)的a34元素對映D(k)：k=4(3-1)-3(3-1)/2+4=8-3+4=92-252.2 上三角形和下三角形表示法上三角形和下三角形表示法 假使是一個nn的下三角形矩陣，其元素分別對映至D陣列，如下所示：aij=D(k)其中k=i(i-1)/2+j 例如圖2-4之(b)的下三角形矩陣的a32位於D(k)，而k=3(3-1)/2+2=52-262.2 上三角形和下三角形表示法上三角形和下三角形表示法2.以行為主：上三角形矩陣的對應情形如下：aij=D(k)其中k=j(j-1)/2+i 例如圖2-4之(a)的a34位於D(k)，其中 k=4(4-1)/2+3=6+3=92-272.2 上三角形和下三角形表示法上三角形和下三角形表示法 而下三角形矩陣對應情形如下：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=62-282.2 上三角形和下三角形表示法上三角形和下三角形表示法 由此可知上三角形矩陣以列為主和下三角形以行為主的計算方式略同，而上三角形矩陣以行為主的計算方式與下三角形以列為主的計算方式略同。2-292.3 多項式表示法多項式表示法 有一多項式p=anxn+an-1xn-1+.+a1x+a0，我們稱A為n次多項式，aixj是多項式的項（0 i n,1 j n）其中ai為係數，x為變數，j為指數。2-302.3 多項式表示法多項式表示法多項式使用線性串列來表示有兩種方法：1.使用一個n+2長度的陣列，依據指數由大至小依序儲存係數，陣列的第一個元素是此多項式最大的指數，如p=(n,an,an-1,.,a0)。2.另一種方法只考慮多項式中非零項的係數，若有m項，則使用一個2m+1長度的陣列來儲存，分別存每一個非零項的指數與係數，而陣列中的第一個元素是此多項式非零項的個數。2-312.3 多項式表示法多項式表示法 例如有一多項式p=8x5+6x4+3x2+12分別利用第1種和第2種方式來儲存，其情形如下：(1)p=(5,8,6,0,3,0,12)(2)p=(4,5,8,4,6,2,3,0,12)2-322.3 多項式表示法多項式表示法 假若是一個兩變數的多項式，那如何利用線性串列來儲存呢？此時需利用二維陣列，若m,n分別是兩變數最大的指數，則需要一個(m+1)(n+1)的二維陣列。如多項式pxy=8x5+6x4y3+4x2y+3xy2+7，則需要一個(5+1)(3+1)=24的二維陣列，表示的方法如下：2-332.3 多項式表示法多項式表示法2-342.3 多項式表示法多項式表示法 兩多項式A、B相加其原理很簡單，比較兩多項式時，有下列三種情況：(1)A指數B指數；(2)A指數B指數；(3)A指數B指數。這三種情況的運作情形，請參閱程式實作。2-352.3 多項式表示法多項式表示法2-362.3 多項式表示法多項式表示法2-372.4 魔術方陣魔術方陣 有一nn的方陣，其中n為奇數，請你nn的魔術方陣，將1到n2的整數填入其中，使其各列、各行及對角線之和皆相等。2-382.4 魔術方陣魔術方陣 做法很簡單，首先將1填入最上列的中間格，然後往左上方走，(1)以1的級數增加其值，並將此值填入空格；(2)假使方格已填滿，則在原地的下一方格填上數字，並繼續做；(3)若超出方陣，則往下到最底層或往右到最右方，視兩者那一個有方格，則將數目填上此方格；(4)若兩者皆無方格，則在原地的下一方格填上數字。2-392.4 魔術方陣魔術方陣 例如有一55的方陣，其形成魔術方陣的步驟如下，並以上述(1)、(2)、(3)、(4)規則來說明。2-402.4 魔術方陣魔術方陣1.將1填入此方陣最上列的中間方格，如下所示：2-412.4 魔術方陣魔術方陣2.承1.往左上方走，由於超出方陣，依據規格(3)發現往下的最底層有空格，因此將2填上。如下所示：2-422.4 魔術方陣魔術方陣3.承2.往左上方，依據規格(1)將3填上，然後再往左上方，此時，超出方陣，依據規則(3)將4填在最右方的方格，如下所示：2-432.4 魔術方陣魔術方陣4.承3.往左上方，依據規則(1)將5填上，再往左上方時，此時方格已有數字，依據規則(2)往5的下方填，如下所示：2-442.4 魔術方陣魔術方陣5.餘此類推，依據上述四個規格繼續填，填到15的結果如下：2-452.4 魔術方陣魔術方陣6.承5.此時往左上方，發現往下的最底層和往右的最右方皆無空格，依據規則(4)在原地的下方，將此數字填上，如下所示：2-462.4 魔術方陣魔術方陣7.繼續往下填，並依據規則(1)、(2)、(3)、(4)最後的結果如下：此時讀者可以算算各行、各列及對角線之和是否皆相等，答案是肯定的，其和皆為65。2-472.5 生命細胞遊戲生命細胞遊戲 本章將以生命細胞遊戲（game of life）做為結束，此遊戲在1970年由英國數學家J.H.CONWAY所提出。生命細胞遊戲將陣列元素視為細胞，而某一細胞鄰居乃是指其垂直、水平、對角線相鄰之細胞（cells）。2-482.5 生命細胞遊戲生命細胞遊戲 生命細胞遊戲的規則：1.孤單死：若一活細胞只有一個或沒有鄰居細胞存活的，則在下一代，它將孤單而死。（下圖中以表示一細胞，而符號表示此細胞將死去）如：2-492.5 生命細胞遊戲生命細胞遊戲2.擁擠死：一活細胞有四個或四個以上鄰居亦是活的，則在下一代，它將因擁擠而死。（下圖中以符號表示此細胞將死去）如：2-502.5 生命細胞遊戲生命細胞遊戲3.穩定：一活細胞有二個或三個相鄰活細胞，則下一代它將繼續生存。（下圖中以符號表示此細胞將繼續存活之）如：2-512.5 生命細胞遊戲生命細胞遊戲2-522.5 生命細胞遊戲生命細胞遊戲2-532.5 生命細胞遊戲生命細胞遊戲
展开阅读全文