《使用C语言3024多项式表示法资料结构课件》由会员分享，可在线阅读，更多相关《使用C语言3024多项式表示法资料结构课件（56页珍藏版）》请在金锄头文库上搜索。
1、 Chapter 2 陣列陣列2.1 2.1 陣列表示法陣列表示法2.2 2.2 C C 語言的陣列表示法語言的陣列表示法2.3 2.3 矩陣矩陣2.4 2.4 多項式表示法多項式表示法2.5 2.5 上三角形和下三角形表示法上三角形和下三角形表示法2.6 2.6 魔術方陣魔術方陣2.7 2.7 生命細胞遊戲生命細胞遊戲2.1 陣列的表示法陣列的表示法線性串列又稱循序串列（sequential list）或有序串列（ordered list）。其特性乃是每一項依據它在串列的位置，可以形成一個線性的排列次序，所以xi在xi + 1之前。22.1 陣列的表示法陣列的表示法線性串列經常發生的操作如下
2、：n取出串列中的第i項；0 i n-1。n計算串列的長度。n由左至右或由右至左讀此串列。n在第i項加入一個新值，使其原來的第i，i+1，.，n項變為第i+1，i+2，.，n+1項。n刪除第i項，使原來的第i+1，i+2，.，n項變為第i，i+1，.，n-1項。32.1 陣列的表示法陣列的表示法C程式語言表示法 在C程式語言中常利用陣列設置線性串列，以線性的對應方式將元素ai置於陣列的第i個位置上，若要讀取ai時，可利用ai的相對位址等於陣列的起始位址加i*d來求得，其中d是每一元素所佔空間的大小，不要忘記C的陣列從0開始喔！42.1 陣列的表示法陣列的表示法2.1.1 一維陣列（一維陣列（on
3、e dimension array）若陣列是A(0 : u-1)，並假設每一個元素佔d個空間，則A(i)= l0 +i*d，其中l0是陣列的起始位置。52.1 陣列的表示法陣列的表示法2.1.2 二維陣列二維陣列假若有一陣列是A0 : u1-1, 0 : u2-1，表示此陣列有u1列及u2行；每一列是由u2個元素組成。二維陣列化成一維陣列時，對映方式有二種：一種以列為主（row-major），二為以行為主（column-major）。62.1 陣列的表示法陣列的表示法以列為主：視此陣列有u1個元素0, 1, 2, ., u1-1，每一元素有u2個單位，每個單位佔d個空間。其情形如圖2-1所示：
4、由圖2-1知A(i,j)= l0 +i*u2d+j*d，其中為此陣列第一個元素的位址72.1 陣列的表示法陣列的表示法82.1 陣列的表示法陣列的表示法以行為主：視此陣列有u2個元素0, 1, 2, ., u2，其中每一元素含有u1個單位，每單位佔d個空間，其情形如圖2-2所示：由圖2-2知A(i,j)= l0 +j*u1d+i*d92.1 陣列的表示法陣列的表示法102.1 陣列的表示法陣列的表示法假若陣列是Al1 : u1 , l2 : u2，則此陣列共有m=u1- l1+1列，n=u2-l2+1行。計算A(i,j)的位址如下：n以列為主：A(i,j)= l0 +(i-s1)nd+(j-s
5、2)dn以行為主：A(i,j)= l0 +(j-s2)md+(i-s1)d112.1 陣列的表示法陣列的表示法122.1 陣列的表示法陣列的表示法132.1 陣列的表示法陣列的表示法2.1.3 三維陣列三維陣列142.1 陣列的表示法陣列的表示法一般三維陣列皆先化為二維陣列後再對映到一維陣列，對映方式也有二種：n以列為主n以行為主152.1 陣列的表示法陣列的表示法以列為主：視此陣列有u1個u2u3的二維陣列，每一個二維陣列有u2個元素，每個u2皆有u3d個空間。162.1 陣列的表示法陣列的表示法以行為主172.1 陣列的表示法陣列的表示法182.1 陣列的表示法陣列的表示法192.1 陣列
6、的表示法陣列的表示法2.1.4 n維陣列維陣列假若有一n 維陣列(n dimension array)為A(0： u11, 0： u12, 0： u31, , 0： un1 )，表示A 陣列為n 維陣列，同樣n 維陣列亦有二種表示方式：(1)以列為主，(2)以行為主。202.2 C語言的陣列表示方法語言的陣列表示方法212.3 矩陣矩陣矩陣相乘222.3 矩陣矩陣232.3 矩陣矩陣242.3 矩陣矩陣稀疏矩陣252.4 多項式表示法多項式表示法有一多項式p=anxn+an-1xn-1+.+a1x+a0，我們稱A為n次多項式，aixj是多項式的項（0 i n, 1 j n）其中ai為係數，x為
7、變數，j為指數。262.4 多項式表示法多項式表示法多項式使用線性串列來表示有兩種方法：n使用一個n+2長度的陣列，依據指數由大至小依序儲存係數，陣列的第一個元素是此多項式最大的指數，如p=(n, an, an-1, ., a0) 。n另一種方法只考慮多項式中非零項的係數，若有m項，則使用一個2m+1長度的陣列來儲存，分別存每一個非零項的指數與係數，而陣列中的第一個元素是此多項式非零項的個數。272.4 多項式表示法多項式表示法例如有一多項式p=8x5+6x4+3x2+12分別利用第1種和第2種方式來儲存，其情形如下：np=(5, 8, 6, 0, 3, 0, 12)np=(4, 5, 8,
8、4, 6, 2, 3, 0, 12)282.4 多項式表示法多項式表示法假若是一個兩變數的多項式，那如何利用線性串列來儲存呢？此時需利用二維陣列，若m, n分別是兩變數最大的指數，則需要一個(m+1)(n+1)的二維陣列。如多項式pxy=8x5+6x4y3+4x2y+3xy2+7，則需要一個(5+1)(3+1)=24的二維陣列，表示的方法如下：292.4 多項式表示法多項式表示法302.4 多項式表示法多項式表示法兩多項式A、B相加其原理很簡單，比較兩多項式時，有下列三種情況：nA指數B指數；nA指數B指數；nA指數B指數。這三種情況的運作情形，請參閱程式實作。312.4 多項式表示法多項式表
9、示法322.4 多項式表示法多項式表示法332.5 上三角形和下三角形表示法上三角形和下三角形表示法若一矩陣的對角線以下的元素均為零時，亦即aij=0，ij，則稱此矩陣為上三角形矩陣（upper triangular matrix）。反之若一矩陣的對角線以上的元素均為零，亦即aij= 0，ij，此矩陣稱為下三角形矩陣（lower triangular matrix），如圖2-4所示：342.5 上三角形和下三角形表示法上三角形和下三角形表示法由上述得知一個nn個的上、下三角形矩陣共有 n(n+1) /2個元素，依序對映至D(1: n(n+1) /2 ) 。352.5 上三角形和下三角形表示法上
10、三角形和下三角形表示法以列為主：一個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=9362.5 上三角形和下三角形表示法上三角形和下三角形表示法假使是一個nn的下三角形矩陣，其元素分別對映至D陣列，如下所示： aij=D(k)其中k=i(i-1)/2+j 例如圖2-4之(b)的下三角形矩陣的a32位於D(k)，而k=3(3-1) /2 +2=5372.5 上三角形和下三角形表示法上三角形和下三角形表示法以行為主：上三角形矩陣的
11、對應情形如下： aij=D(k)其中k=j(j-1)/2+i例如圖2-4之(a)的a34位於D(k)，其中k= 4(4-1) /2+3=6+3=9382.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=6392.5 上三角形和下三角形表示法上三角形和下三角形表示法由此可知上三角形矩陣以列為主和下三角形以行為主的計算方式略同，而上三角形矩陣以行為主的計算方式與下三角形以列為主的計算方式略同。402.6 魔術方
12、陣魔術方陣有一nn的方陣，其中n為奇數，請你nn的魔術方陣，將1到n2的整數填入其中，使其各列、各行及對角線之和皆相等。412.6 魔術方陣魔術方陣做法很簡單，首先將1填入最上列的中間格，然後往左上方走，(1)以1的級數增加其值，並將此值填入空格；(2)假使方格已填滿，則在原地的下一方格填上數字，並繼續做；(3)若超出方陣，則往下到最底層或往右到最右方，視兩者那一個有方格，則將數目填上此方格；(4)若兩者皆無方格，則在原地的下一方格填上數字。422.6 魔術方陣魔術方陣例如有一55的方陣，其形成魔術方陣的步驟如下，並以上述(1)、(2)、(3)、(4)規則來說明。432.6 魔術方陣魔術方陣1
13、.將1填入此方陣最上列的中間方格，如下所示：442.6 魔術方陣魔術方陣2.承1.往左上方走，由於超出方陣，依據規格(3)發現往下的最底層有空格，因此將2填上。如下所示：452.6 魔術方陣魔術方陣3.承2.往左上方，依據規格(1)將3填上，然後再往左上方，此時，超出方陣，依據規則(3)將4填在最右方的方格，如下所示：462.6 魔術方陣魔術方陣4.承3.往左上方，依據規則(1)將5填上，再往左上方時，此時方格已有數字，依據規則(2)往5的下方填，如下所示：472.6 魔術方陣魔術方陣5.餘此類推，依據上述四個規格繼續填，填到15的結果如下：482.6 魔術方陣魔術方陣6.承5.此時往左上方，
14、發現往下的最底層和往右的最右方皆無空格，依據規則(4)在原地的下方，將此數字填上，如下所示：492.6 魔術方陣魔術方陣7.繼續往下填，並依據規則(1)、(2)、(3)、(4)最後的結果如下：此時可以算算各行、各列及對角線之和是否皆相等，答案是肯定的，其和皆為65。502.6 魔術方陣魔術方陣奇數魔術方陣512.7 生命細胞遊戲生命細胞遊戲 在1970 年由英國數學家J. H.CONWAY 所提出。生命細胞遊戲將陣列元素視為細胞，而某一細胞鄰居乃是指在其垂直、水平、對角線相鄰之細胞(cells)。522.7 生命細胞遊戲生命細胞遊戲532.7 生命細胞遊戲生命細胞遊戲542.7 生命細胞遊戲生命細胞遊戲552.7 生命細胞遊戲生命細胞遊戲由上規則可得：有0, 1, 4, 5, 6, 7, 8 個相鄰細胞者在下一代將因孤單或擁擠而死。有2 個相鄰活細胞者，下一代會繼續其狀態不會改變。有3 個相鄰活細胞者不管其現在是生是死，下一代一定會是活的。56
