第二章 鏈結串列 2-1　線性串列 2-2 認識陣列 2-3 矩陣的簡介與運算 2-4 陣列與多項式

線性串列 線性串列(Linear List)或稱為有序串列(Ordered List)是數學觀念應用在電腦科學中一種相當基本的資料結構。 線性串列是n個元素的有限序列(n≧0)，像是26個英文字母的字母串列：A,B,C,D,E…,Z，就是一個線性串列。

線性串列定義 形容如下： 有序串列可以是空集合，或者可寫成(a1,a2,a3．．．,an-1,an)。 除了第一個元素a1外，每一個元素都有唯一的先行者(precessor)，例如ai的先行者為ai-1。 除了最後一個元素an外，每一個元素都有唯一的後續者(successor)，例如ai+1是ai的後續者。

8種常見的運算方式 計算串列的長度n。 取出串列中的第I項元素來加以修正，1≦i≦n。 插入一個新元素到第i項，1≦i≦n，並使得原來的第i，i+1…，n項，後移變成i+1，i+2…，n+1項。 刪除第i項的元素，1≦i≦n，並使得第i+1，i+2，…n項，前移變成第i，i+1…，n-1項。 從右到左或從左到右讀取串列中各個元素的值。 在第i項存入新值，並取代舊值，1<=i<=n。 複製串列。 合併串列。

線性串列在電腦中的應用 靜態資料結構(Static Data Structure) 動態資料結構(dynamic data structure)

靜態資料結構 (Static Data Structure) 或稱為「密集串列」 (dense list)，它是一種將有序串列的資料使用連續記憶空間(contiguous allocation)來儲存。 缺點則是刪除或加入資料時，需要移動大量的資料。 靜態資料結構的記憶體配置是在編譯時，就必須配置給相關的變數。 因此陣列在建立初期，必須事先宣告最大可能的固定憶空間，容易造成記憶體的浪費。

範例2.1.1 密集串列(dense list)於某些應上相當方便，請問 1.何種情況下不適用？

動態資料結構 (dynamic data structure) 又稱為「鍵結串列」 (linked list)，它是一種將線性串列的資料使用不連續記憶空間來儲存。 優點是資料的插或刪除都相當方便，不需要移動大量資料。 缺點就是設計資料結構時較為麻煩，另外在搜尋資料時，也無法像靜態資料一般可隨機讀取資料，必須循序找到該資料為止。

認識陣列 五種屬性： 1.起始位址：表示陣列名稱(或陣列第一個元素)所在記憶體中的起始位址。 2.維度(dimension)：代表此陣列為幾維陣列，如一維陣列、二維陣列、三維陣列等等。 3.索引上下限：指元素在此陣列中，記憶體所儲存位置的上標與下標。 4.陣列元素個數：是索引上限與索引下限的差+1。 5.陣列型態：宣告此陣列的型態，它決定陣列元素在記憶體所佔有的大小。

一維陣列 例如在C語言中一維陣列宣告方式如下： 當C陣列宣告時會在記憶體中配置一段暫存空間，如下圖： 資料型態 陣列名稱[陣列大小]； 資料型態 陣列名稱[陣列大小]={初始值1,初始值2,…}；

二維陣列 宣告方式如下： A[4][4]陣列中各個元素在直觀平面上的排列方式如下： 資料型別[ ] [ ]變數名稱=new資料型別[第一維長度][ 第二維長度]；

以列為主(Row-major) 例如Java、C/C++、PASCAL語言的陣列存放方式。 儲存順序為A(1,1)、A(1,2)…A(1,n)、A(2,1)、A(2,2)……A(m-1,n)、A(m,n)。 假設α為陣列A在記憶體中起始位址，d為單位空間，那麼陣列元素A(i,j)與記憶體位址有下列關係： Loc(A(i,j))= α+n*(i-1)*d+(j-1)*d

以行為主(Column-major) 例如Fortran語言的陣列存放方式。儲存順序為A(1,1)、A(2,1)、A(3,1)…A(m,1)、A(1,2)、A(2,2)……A(m,n)。 假設α為陣列A在記憶體中起始位址，d為單位空間，那麼陣列元素A(i,j)與記憶體位址有下列關係： Loc(A(i,j))= α+(i-1)*d+m*(j-1)*d

範例2.2.1 範例2.2.2 若A(3,3)在位置121，A(6,4)在位置159，則A(4,5)的位置為何？(單位空間d=1) 若A(1,1)在位置2，A(2,3)在位置18，A(3,2)在位置28，試求A(4,5)的位置？

假設α仍為起始位址，而且m=(u1-l1+1),n=(u2-l2+1)。則有下列公式： 以列為主(Row-major) 以行為主(Column-major) Loc A(i,j)=α+((i-l1+1)-1)*n*d+((j-l2+1)-1)*d Loc A(i,j)=α+((j-l2+1)-1)*m*d+((i-l1+1)-1)*d

範例2.2.3 A(-3:5,-4:2)的起始位址A(-3,-4)=100，以row-major排列，請問Loc(A(1,1))=？ 範例2.2.4 二維陣列A[1:5,1:6]，如果以column-major存放，則A(3,3)排在此陣列的第幾個位置？(α=0，d=1)

範例2.2.5 一個陣列(array)被以列(row)為主的順序存放在記憶體內。每個陣列元素佔用4個單位的記憶體。若起始位址是100，在下列宣告中，所列元素的存放位置為何？ 1.Var A=array[-100…1,1…100]，求A[1,12]之位址。 2.Var A=array[5…10,-10…20]，求A[5,-5]之位址。

三維陣列 宣告方式如下： 以下陣列 No[2][2][2]共有8個元素。可以使用立體圖形表示如下： 資料型別[ ] [ ] [ ]變數名稱=new資料型別[第一維長度][ 第二維長度] [ 第三維長度]；

以列為主(Row-major) 我們可以將陣列A視為u1個u2＊u3的二維列陣，再將每個陣列視為有u2個一維陣列，每一個一維陣列可包含u3的元素。 另外每個元素有d個單位空間，且α為陣列起始位址。

以行為主(Column-major) 將陣列A視為u3個u2*u1的二為陣列，再將每個二維陣列視為有u2個一維陣列，每一陣列含有u1個元素。 每個元素有d單位空間，且α為起始位址：

範例2.2.6 範例2.2.7 A(6,4,2)是以Row-major方式排列，若α=300，且d=1，求A(4,4,1)的位址。 有一個三維陣列A(-3:2,-2:3,0:4)，以Row-major方式排列，陣列之起始位址是318，試求Loc(A(1,3,3))=？(d=1)

n維陣列 宣告方式如下： 假設陣列A宣告為A(1:u1,1:u2,1:u3……,1:un)，則可將陣列視為有u1個n-1維陣列，每個n-1維陣列中有u2個n-2維陣列，每個n-2維陣列中，有u3個n-3維陣列………有un-1個一維陣列，在每個一維陣列中有un個元素。 資料型別[ ] [ ].. [ ]變數名稱=new資料型別[第一維長度][ 第二維長度]…[第n維長度]；

以列為主(Row-major) Loc(A(i1,i2,i3………,in)) = α+(i1-1)u2u3u4……und +(i2-1)u3u4……und +(i3-1)u4u5……und +(i4-1)u5u6……und +(i5-1)u6u7……und : +(in-1-1)und +(in-1)d

以行為主(Column-major) Loc(A(i1,i2,i3………,in)) = α+(in-1)un-1un-2……u1d +(in-1-1)un-2……u1d : +(i2-1-1)u1d +(i1-1)d

範例2.2.8 在４-D array A[1:4,1:6,1:5,1:3]中，且α＝200，d=1。並已知是以行排列(Column-major)，求A[3,1,3,1]的位址。　 範例2.2.9 假設陣列 A[-1:3,2:4,1:4,-2:1]是以列為主排列，起始位址α=200，每個陣列元素儲存空間為5，請問A [-1,2,1,-2]、A [3,4,4,1]、A [3,2,1,0]的位置。

Arrays類別實作 方法名稱 說明 static int binarySearch (資料型別[] a, 資料型 別 b) 傳回一整數值。以b為索引資料，對a陣列做二元搜 尋，傳回b在a陣列中的索引位置。當傳回值<0表 示未找到。 static boolean equals (資料型別[] a, 資料型別 [] b) 傳回一boolean值。比較a陣列與b陣列內容值。 true表示陣列內容值相等；false表示陣列內容值不 相等。 static void fill(資料型別 [] a, 資料型別 b) 無傳回值。將資料b填入a陣列。 static void sort(資料型別 [] a) 無傳回值。對a陣列做由小至大排序動作。 [] a, int 起始索引, int 結 束索引) 無傳回值。對a陣列中索引值 起始索引 到 結束索 引 做由小至大排序動作。

範例程式：ch02_01.java

矩陣的簡介與運算 數學的矩陣(Matrix)是一種用來描述二維陣列的最好方式。 例如A為3*3的矩陣，也就是有3列及3行，可如同下列矩陣：

矩陣相加 首先必須兩者的列數與行數都相等，而相加後矩陣的列數與行數也是相同。 例如Amxn+Bmxn=Cmxn。 底下我們就來實際進行一個矩陣相加的例子：

範例程式：ch02_02. java

矩陣相乘 首先必須符合A為一個m*n的矩陣，B為一個n*p的矩陣，對A*B之後的結果為一個m*p的矩陣C。如下圖所示： C11= a11 * b11+ a12* b21+………+ a1n* bn1 : C1p= a11* b1p+ a12* b2p+……+ a1n*bnp Cmp= am1* b1p+am2* b2p+………+ amn* bnp

範例程式：ch02_03. java

轉置矩陣 假設A為mxn矩陣，則At為nxm矩陣，對每一個A(i,j)=At(j,k)則稱At為A的轉置矩陣。例如：

範例程式：ch02_04. java

稀疏矩陣 A(0,1)=>表示此矩陣的列數 A(0,2)=>表示此矩陣的行數 A(0,3)=>表示此矩陣非零項目的總數

範例程式：ch02_05.java

範例2.3.1求下圖稀疏矩陣的壓縮陣列表示法

上三角形矩陣 是一種對角線以下元素皆為0的n*n矩陣。其中又可分為右上三角形矩陣(Right Upper Trangular Matrix)與左上三角形矩陣(Left Upper Triangular Matrix)。 由於上三角形矩陣仍有許多元素為0，為了避免浪費空間，我們可以把三角形矩陣的二維模式，儲存在一維陣列中。

右上三角形矩陣矩陣 即對nxn的矩陣A，假如i>j，那麼A(i,j)=0，如圖所示

以列為主(Row-major) k=n*(i-1)- +j

以行為主(column-major) k= +i

範例2.3.2 假如有一個5x5的右上三角形矩陣A，以行為主對映到一維陣列B，請問a23所對映B(k)的k值為何？

範例程式：ch02_06.java

左上三角形矩陣 即對nxn的矩陣A，假如i>n-j+1時，A(i,j)=0，如下圖所示：

以列為主(Row-major) k=n*(i-1)- +j =n*(i-1)-

以行為主(column-major) k= n*(j-1)- +i

下三角形矩陣 是一種對角線以上元素皆為0的nxn矩陣。 其中也可分為左下三角形矩陣(Left LowerTrangular Matrix)和右下三角形矩陣(Right Lower Triangular Matrix)。

左下三角形矩陣 即對nxn的矩陣A，假如i<j，那麼A(i,j)=0如下圖所示：

以列為主 k= +j

以行為主 k=n*(j-1)+i- =n*(j-1)+i-

範例2.3.4 有一6x6的左下三角形矩陣，以行為主的方式對映到一維陣列B，求元素a32所對映B(k)的大值為何？

範例程式：ch02_07.java

右下三角形矩陣 即對nxn的矩陣A，假如i<n-j+1，那麼A(i,j)=0，如下圖所示:

以列為主 k= *[1+(i-1)]+j-(n-i) = +j-n

以行為主 +i-(n-j) +i-n = k=

範例2.3.5 範例2.3.6 假設有一個4x4的右下三角形矩陣，以行為主對映到一維陣列B，求元素a32所對映B(k)的k值為何？ 一個低部三角陣列(Lower Triangular Array)，B是一個nxn的陣列，其中B[i,j]=0，i<j。 求B陣列中不為0的最大個數。 如何將B陣列以最經濟的方式儲存在記憶中。 寫出在的儲存方式中，如何求得B[i,j]，i>=j。

認識多項式 1.使用一個n+2長度的一維陣列存放，陣列的第一個位置儲存最大指數n，其他位置依照指數n遞減，依序儲存相對應的係數： P=(n,an,an-1,……,a1,a0)儲存在A(1:n+2)，例如P(x)=2x5+3x4+5x2+4x+1，可轉換為成A陣列來表示，例如： A={5,2,3,0,5,4,1}

例如P(x)=2x5+3x4+5x2+4x+1，可表示成A(1:2m+1)陣列，例如： 2.只儲存多項式中非零項目。如果有m項非零項目則使用2m+1長的陣列來儲存每一個非零項的指數及係數，但陣列的第一個元素則為此多項式非零項的個數。 例如P(x)=2x5+3x4+5x2+4x+1，可表示成A(1:2m+1)陣列，例如： A={5,2,5,3,4,5,2,4,1,1,0}

多項式的加法 範例程式：ch02_08.java

範例2.4.1 範例2.4.2 請使用多項式的兩種陣列表示法來儲存P(x)=8x5+7x4+5x2+12。 如何表示與儲存多項式P(x,y)=9x5+4x4y3+14x2y2+13xy2+15？試說明之。