使用C语言3024多项式表示法资料结构课件.ppt
Chapter 2 陣列,2.1 陣列表示法2.2 C 語言的陣列表示法2.3 矩陣2.4 多項式表示法2.5 上三角形和下三角形表示法2.6 魔術方陣2.7 生命細胞遊戲,資料結構-使用 C 語言 2,2.1 陣列的表示法,線性串列又稱循序串列（sequential list）或有序串列（ordered list）。其特性乃是每一項依據它在串列的位置，可以形成一個線性的排列次序，所以xi在xi+1之前。,資料結構-使用 C 語言 3,2.1 陣列的表示法,線性串列經常發生的操作如下：取出串列中的第i項；0 i n-1。計算串列的長度。由左至右或由右至左讀此串列。在第i項加入一個新值，使其原來的第i，i+1，.，n項變為第i+1，i+2，.，n+1項。刪除第i項，使原來的第i+1，i+2，.，n項變為第i，i+1，.，n-1項。,資料結構-使用 C 語言 4,2.1 陣列的表示法,C程式語言表示法 在C程式語言中常利用陣列設置線性串列，以線性的對應方式將元素ai置於陣列的第i個位置上，若要讀取ai時，可利用ai的相對位址等於陣列的起始位址加i*d來求得，其中d是每一元素所佔空間的大小，不要忘記C的陣列從0開始喔！,資料結構-使用 C 語言 5,2.1 陣列的表示法,2.1.1 一維陣列（one dimension array）若陣列是A(0:u-1)，並假設每一個元素佔d個空間，則A(i)=l0+i*d，其中l0是陣列的起始位置。,資料結構-使用 C 語言 6,2.1 陣列的表示法,2.1.2 二維陣列假若有一陣列是A0:u1-1,0:u2-1，表示此陣列有u1列及u2行；每一列是由u2個元素組成。二維陣列化成一維陣列時，對映方式有二種：一種以列為主（row-major），二為以行為主（column-major）。,資料結構-使用 C 語言 7,2.1 陣列的表示法,以列為主：視此陣列有u1個元素0,1,2,.,u1-1，每一元素有u2個單位，每個單位佔d個空間。其情形如圖2-1所示：由圖2-1知A(i,j)=l0+i*u2d+j*d，其中為此陣列第一個元素的位址,資料結構-使用 C 語言 8,2.1 陣列的表示法,資料結構-使用 C 語言 9,2.1 陣列的表示法,以行為主：視此陣列有u2個元素0,1,2,.,u2，其中每一元素含有u1個單位，每單位佔d個空間，其情形如圖2-2所示：由圖2-2知A(i,j)=l0+j*u1d+i*d,資料結構-使用 C 語言 10,2.1 陣列的表示法,資料結構-使用 C 語言 11,2.1 陣列的表示法,假若陣列是Al1:u1,l2:u2，則此陣列共有m=u1-l1+1列，n=u2-l2+1行。計算A(i,j)的位址如下：以列為主：A(i,j)=l0+(i-s1)nd+(j-s2)d以行為主：A(i,j)=l0+(j-s2)md+(i-s1)d,資料結構-使用 C 語言 12,2.1 陣列的表示法,資料結構-使用 C 語言 13,2.1 陣列的表示法,資料結構-使用 C 語言 14,2.1 陣列的表示法,2.1.3 三維陣列,資料結構-使用 C 語言 15,2.1 陣列的表示法,一般三維陣列皆先化為二維陣列後再對映到一維陣列，對映方式也有二種：以列為主以行為主,資料結構-使用 C 語言 16,2.1 陣列的表示法,以列為主：視此陣列有u1個u2u3的二維陣列，每一個二維陣列有u2個元素，每個u2皆有u3d個空間。,資料結構-使用 C 語言 17,2.1 陣列的表示法,以行為主,資料結構-使用 C 語言 18,2.1 陣列的表示法,資料結構-使用 C 語言 19,2.1 陣列的表示法,資料結構-使用 C 語言 20,2.1 陣列的表示法,2.1.4 n維陣列假若有一n 維陣列(n dimension array)為A(0：u11,0：u12,0：u31,0：un1)，表示A 陣列為n 維陣列，同樣n 維陣列亦有二種表示方式：(1)以列為主，(2)以行為主。,資料結構-使用 C 語言 21,2.2 C語言的陣列表示方法,資料結構-使用 C 語言 22,2.3 矩陣,矩陣相乘,資料結構-使用 C 語言 23,2.3 矩陣,資料結構-使用 C 語言 24,2.3 矩陣,資料結構-使用 C 語言 25,2.3 矩陣,稀疏矩陣,資料結構-使用 C 語言 26,2.4 多項式表示法,有一多項式p=anxn+an-1xn-1+.+a1x+a0，我們稱A為n次多項式，aixj是多項式的項（0 i n,1 j n）其中ai為係數，x為變數，j為指數。,資料結構-使用 C 語言 27,2.4 多項式表示法,多項式使用線性串列來表示有兩種方法：使用一個n+2長度的陣列，依據指數由大至小依序儲存係數，陣列的第一個元素是此多項式最大的指數，如p=(n,an,an-1,.,a0)。另一種方法只考慮多項式中非零項的係數，若有m項，則使用一個2m+1長度的陣列來儲存，分別存每一個非零項的指數與係數，而陣列中的第一個元素是此多項式非零項的個數。,資料結構-使用 C 語言 28,2.4 多項式表示法,例如有一多項式p=8x5+6x4+3x2+12分別利用第1種和第2種方式來儲存，其情形如下：p=(5,8,6,0,3,0,12)p=(4,5,8,4,6,2,3,0,12),資料結構-使用 C 語言 29,2.4 多項式表示法,假若是一個兩變數的多項式，那如何利用線性串列來儲存呢？此時需利用二維陣列，若m,n分別是兩變數最大的指數，則需要一個(m+1)(n+1)的二維陣列。如多項式pxy=8x5+6x4y3+4x2y+3xy2+7，則需要一個(5+1)(3+1)=24的二維陣列，表示的方法如下：,資料結構-使用 C 語言 30,2.4 多項式表示法,資料結構-使用 C 語言 31,2.4 多項式表示法,兩多項式A、B相加其原理很簡單，比較兩多項式時，有下列三種情況：A指數B指數；A指數B指數；A指數B指數。這三種情況的運作情形，請參閱程式實作。,資料結構-使用 C 語言 32,2.4 多項式表示法,資料結構-使用 C 語言 33,2.4 多項式表示法,資料結構-使用 C 語言 34,2.5 上三角形和下三角形表示法,若一矩陣的對角線以下的元素均為零時，亦即aij=0，ij，則稱此矩陣為上三角形矩陣（upper triangular matrix）。反之若一矩陣的對角線以上的元素均為零，亦即aij=0，ij，此矩陣稱為下三角形矩陣（lower triangular matrix），如圖2-4所示：,資料結構-使用 C 語言 35,2.5 上三角形和下三角形表示法,由上述得知一個nn個的上、下三角形矩陣共有 n(n+1)/2個元素，依序對映至D(1:n(n+1)/2)。,資料結構-使用 C 語言 36,2.5 上三角形和下三角形表示法,以列為主：一個nn的上三角形矩陣其元素分別對映至D陣列，如下所示：aij=D(k)其中k=n(i-1)-i(i-1)/2+j例如圖2-4之(a)的a34元素對映D(k)：k=4(3-1)-3(3-1)/2+4=8-3+4=9,資料結構-使用 C 語言 37,2.5 上三角形和下三角形表示法,假使是一個nn的下三角形矩陣，其元素分別對映至D陣列，如下所示：aij=D(k)其中k=i(i-1)/2+j 例如圖2-4之(b)的下三角形矩陣的a32位於D(k)，而k=3(3-1)/2+2=5,資料結構-使用 C 語言 38,2.5 上三角形和下三角形表示法,以行為主：上三角形矩陣的對應情形如下：aij=D(k)其中k=j(j-1)/2+i例如圖2-4之(a)的a34位於D(k)，其中k=4(4-1)/2+3=6+3=9,資料結構-使用 C 語言 39,2.5 上三角形和下三角形表示法,而下三角形矩陣對應情形如下：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,資料結構-使用 C 語言 40,2.5 上三角形和下三角形表示法,由此可知上三角形矩陣以列為主和下三角形以行為主的計算方式略同，而上三角形矩陣以行為主的計算方式與下三角形以列為主的計算方式略同。,資料結構-使用 C 語言 41,2.6 魔術方陣,有一nn的方陣，其中n為奇數，請你nn的魔術方陣，將1到n2的整數填入其中，使其各列、各行及對角線之和皆相等。,資料結構-使用 C 語言 42,2.6 魔術方陣,做法很簡單，首先將1填入最上列的中間格，然後往左上方走，(1)以1的級數增加其值，並將此值填入空格；(2)假使方格已填滿，則在原地的下一方格填上數字，並繼續做；(3)若超出方陣，則往下到最底層或往右到最右方，視兩者那一個有方格，則將數目填上此方格；(4)若兩者皆無方格，則在原地的下一方格填上數字。,資料結構-使用 C 語言 43,2.6 魔術方陣,例如有一55的方陣，其形成魔術方陣的步驟如下，並以上述(1)、(2)、(3)、(4)規則來說明。,資料結構-使用 C 語言 44,2.6 魔術方陣,將1填入此方陣最上列的中間方格，如下所示：,資料結構-使用 C 語言 45,2.6 魔術方陣,承1.往左上方走，由於超出方陣，依據規格(3)發現往下的最底層有空格，因此將2填上。如下所示：,資料結構-使用 C 語言 46,2.6 魔術方陣,承2.往左上方，依據規格(1)將3填上，然後再往左上方，此時，超出方陣，依據規則(3)將4填在最右方的方格，如下所示：,資料結構-使用 C 語言 47,2.6 魔術方陣,承3.往左上方，依據規則(1)將5填上，再往左上方時，此時方格已有數字，依據規則(2)往5的下方填，如下所示：,資料結構-使用 C 語言 48,2.6 魔術方陣,餘此類推，依據上述四個規格繼續填，填到15的結果如下：,資料結構-使用 C 語言 49,2.6 魔術方陣,承5.此時往左上方，發現往下的最底層和往右的最右方皆無空格，依據規則(4)在原地的下方，將此數字填上，如下所示：,資料結構-使用 C 語言 50,2.6 魔術方陣,繼續往下填，並依據規則(1)、(2)、(3)、(4)最後的結果如下：此時可以算算各行、各列及對角線之和是否皆相等，答案是肯定的，其和皆為65。,資料結構-使用 C 語言 51,2.6 魔術方陣,奇數魔術方陣,資料結構-使用 C 語言 52,2.7 生命細胞遊戲,在1970 年由英國數學家J.H.CONWAY 所提出。生命細胞遊戲將陣列元素視為細胞，而某一細胞鄰居乃是指在其垂直、水平、對角線相鄰之細胞(cells)。,資料結構-使用 C 語言 53,2.7 生命細胞遊戲,資料結構-使用 C 語言 54,2.7 生命細胞遊戲,資料結構-使用 C 語言 55,2.7 生命細胞遊戲,資料結構-使用 C 語言 56,2.7 生命細胞遊戲,由上規則可得：有0,1,4,5,6,7,8 個相鄰細胞者在下一代將因孤單或擁擠而死。有2 個相鄰活細胞者，下一代會繼續其狀態不會改變。有3 個相鄰活細胞者不管其現在是生是死，下一代一定會是活的。,
