親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化： 1、本教具為非賣品，不得作為商業之用。 2、本教具僅授權使用原著作為授課教材之教師作為教學或研究等學術用途。 3、本教具未授權提供學生任何拷貝、影印、引用、翻印等行為。 4、教師若需申請網站或內容授權，可透過您的博碩業務協助處理，謝謝。 博碩文化： 總公司：台北縣汐止市新台五路一段94號6樓A棟 電話：(02) 2696-2869 分機 313 傳真：(02) 2696-2867 網址：www.drmaster.com.tw 客服信箱：school@drmaster.com.tw 出書提案信箱 schoolbook@drmaster.com.tw

資料結構 請老師填入姓名主講 課本：圖解資料結構使 用Java 博碩文化出版發行

第二章 線性串列 課前指引 是數學應用在電腦科學中一種相當簡單與基本的資料結構，簡單的說，線性串列是n個元素的有限序列(n≧0)，像是26個英文字母的字母串列：A,B,C,D,E…,Z，就是一個線性串列，串列中的資料元素是屬於字母符號，或是10個阿拉伯數字的串列0,1,2,3,4,5,6,7,8,9。

章節大綱 2-1 線性串列的定義 2-2 陣列 2-3 矩陣 備註：可依進度點選小節

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

2-1 線性串列的定義 「線性串列」(Linear List)的用途(1/2) ： 例如C/C++程式中的陣列或字串結構，就是一種典型線性串列的應用。 特性是使用連續記憶空間(Contiguous Allocation)來儲存，記憶體配置是在編譯時，就必須配置給相關的變數，容易造成記憶體的浪費。 Array_Name代表佔有一塊連續的記憶體空間，並擁有5筆資料的陣列

2-1 線性串列的定義 「線性串列」(Linear List)的用途(2/2）： 又或者如鏈結串列(Linked Lists)結構，也是在C/C++中，多半是以指標變數型態來實作線性串列的資料結構。 特點是串列節點的記憶體配置是在執行時才發生，所以不需事先宣告，或稱為「動態記憶體配置」 指標變數是指內含值為指到記憶體儲存位置的一種資料型態變數

2-2 陣列 在程式語言中，可看作是一群相同名稱與資料型態的集合，並且在計憶體中佔有一塊連續的記憶體空間。 要存取陣列中的資料時，則配合索引值(index)尋找出資料在陣列的位置。

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

2-2 陣列 多維陣列也必須在一維的實體記憶體中表示，因為記憶體位置是依線性順序遞增。通常依照不同的語言，又可區分為 1、以列為主(Row-major)：一列一列來依序儲存，例如Java、C/C++、PASCAL語言的陣列存放方式。 2、以行為主(Column-major)：一行一行來依序儲存，例如Fortran語言的陣列存放方式。

2-2 陣列 一維陣列： 例如假設A是一維陣列(One-dimension Array)名稱，如果宣告為A(1:u1)，表示A含有n個元素，其中1為下標，u1為上標。 不過如果一維陣列A是宣告為A(l1：u1)，且l1為小於或等於u1的任何整數，α為起始位址，d為單位空間，那麼公式如下： A(1)、A(2)、A(3)、…… A(u1) 　α α＋1*d α+2*d …… ……… α+( u1-1)*d =>Loc(A(i))= α+(i-1)*d　 　(Loc(A(i))表示A(i)所在的住址) Loc(A(i))=α+(i- l1)*d

2-2 陣列 範例 2.2.1 假設A為一個具有1000個元素的陣列，每個元素為4個位元組的實數 ，若A[500]的位置為100016，請問A[1000]的位址為何？ 解答：本題主要是位址以16進位法表式→ →loc(A[1000])=loc(A[500])+(1000-500)×4 =4096+2000=6096

2-2 陣列 範例 2.2.2 有一PASCAL陣列 A:ARRAY[6..99] of REAL(假設REAL元素大小有4)，如果已知陣列A的起始位址為500，則元素A[30]的位址為何？ 解答： Loc(A[30])=Loc(A[6]+(30-6)*4=500+96=596

2-2 陣列 例如在Java語言中一維陣列宣告方式如下： 當Java陣列宣告時會在記憶體中配置一段暫存空間，如下圖： 資料型別[　] 變數名稱=new資料型別[長度];

2-2 陣列 範例 2.2.3 請利用一維陣列尋找與儲存範圍為1到MAX內的所有質數，所謂質數(prime number)是指不能被１和本身以外的數值所整除的整數。

2-2 陣列 二維陣列(Two-dimension Array) ： 可視為一維陣列的延伸，都是處理相同資料型態資料，差別只在於維度的宣告。 例如一個含有m*n個元素的二維陣列A (1:m,1:n)，m代表列數，n代表行數，各個元素在直觀平面上的排列方式如下矩陣，A[4][4]陣列中各個元素在直觀平面上的排列方式如下

2-2 陣列 以列為主(Row-major) 存放順序為a11,a12,...a1n,a21,a22,...,..amn，假設α為陣列A在記憶體中起始位址，d為單位空間，那麼陣列元素aij與記憶體位址有下列關係： Loc(aij)= α+n* (i-1)*d+(j-1)*d

2-2 陣列 以行為主(Column-major) 存放順序為a11,a21,...am1,a12,a22,...,..amn，假設α為陣列A在記憶體中起始位址，d為單位空間，那麼陣列元素aij與記憶體位址有下列關係： Loc(aij)= α+(i-1)*d+m*(j-1)*d

2-2 陣列 宣告陣列A(1:2,1:4)，表示法如下：

2-2 陣列 範例 2.2.4 現有一二維陣列A，有3*5個元素，陣列的起始位址A(1,1)是100，以列為主(Row-major)排列，每個元素佔2 bytes，請問A(2,3)的位址？ 解答：代入公式，Loc(A92,30=100+(2-1)*5*2+(3-1)*2=114

2-2 陣列 範例 2.2.5 二維陣列A[1:5,1:6]，如果以column-major存放，則A(4,5)排在此陣列的第幾個位置？(α=0，d=1)？ 解答：Loc(A(4,5))=0+(4-1)*5*1+(5-1)*1=19(下一個)，所以A(4,5)在第20個位置

2-2 陣列 範例 2.2.6 陣列(Array)是以PASCAL語言來宣告，每個陣列元素佔用4個單位的記憶體。若起始位址是255，在下列宣告中，所列元素存放位置為何？ VarA=array[-55…1,1…55]，求A[1,12]之位址。 VarA=array[5…20,-10…40]，求A[5,-5]之位址。 解答： 1：先求得陣列中的實際列數及行數。 1-(-55)+1=57…列數 ；55-1+1=55...行數 由於PASCAL語言是以列為主的語言，可代入以下計算公式中： 255+55*4*(1-(-55))+(12-1)*4=12619 2：同樣是先求得陣列中的實際列數及行數。 20-5+1=16…列數； 40-(-10)+1=51...行數 255+4*51*((5-5)+4*(-5-(-10))=275

2-2 陣列 範例 2.2.7 A(-3:5,-4:2)的起始位址A(-3,-4)=1200，以row-major排列，每個元素佔1bytes，請問Loc(A(1,1))=？ 解答： 假設A陣列以row-major排列，且α=Loc(A(-3,-4))=100 m=5-(-3)+1=9(列)、n=2-(-4)=1=7(行)， A(1,1)=1200+1*7*(1-(-3))+1*(1-(-4))=1233

2-2 陣列 範例2.2.8 假設我們以FORTRAN語言來宣告浮點數陣列A[8][10]，且每個陣列元素佔用4個單位的記憶體，如果A[0][0]的起始位址是200，則元素A[5][6]的位址為何？ 解答： Loc(A[5][6])=200+5*4+8*4*4=448

2-2 陣列 範例2.2.9 請設計一Java程式，可利用了二維陣列來儲存產生的亂數。亂數產生時還需要檢查號碼是否重複，請利用二維陣列的索引值特性及while迴圈機制做反向檢查，完成了6個不會重複的號碼。

2-2 陣列 多維陣列（1/3） 在程式語言中，只要記憶體大小許可時，都可以宣告成更多維陣列來存取資料，通常凡是二維以上的陣列都可以稱作多維陣列。 三維陣列的表示法和二維陣列一樣，皆可視為是一維陣列的延伸，如果陣列A宣告為A(1:u1,1:u2,1:u3)，表示A為一個含有u1*u2*u3元素的三維陣列，可以看作是一個立方體，如下圖

2-2 陣列 多維陣列（2/3） 以列為主(Row-major) 在想像轉換公式時，是要計算A(i,j,k)看看它是在一直線排列的第幾個各位。 可以得到aijk元素的以下位址計算公式： Loc(A(i,j,k))=α+(i-1)u2u3d+(j-1)u3d+(k-1)d

2-2 陣列 多維陣列（3/3） 以行為主(Row-major) 也可以直觀地將陣列A視為u3個u2*u1的二為陣列，再將每個二維陣列視為有u2個一維陣列，每一陣列含有u1個元素。每個元素有d單位空間，且α為起始位址。 可以得到aijk元素的以下位址計算公式： Loc( A(aijk)=α+(k-1)u2u1d+(j-1)u1d+(i-l)d

2-2 陣列 範例 2.2.10 假設有以列為主排列的程式語言，宣告A(1:3,1:4,1:5)陣列，且Loc(A(1,1,1))=100，請求出Loc(A(1,2,3))=？ 解答：直接代入公式 Loc(A(1,2,3))=100+(1-1)*4*5*1+(2-1)*5*1+(3-1)*1=107

2-2 陣列 範例 2.2.11 A(6,4,2)是以行為主方式排列，若α=300，且d=1，求A(4,4,1)的位址？ 解答：這題是以列為主(Row-Major)，直接代入公式即可：Loc(A(4,4,1))=300+(1-1)*6*4+(4-1)*2+(6-1)=300+6+5=311

2-2 陣列 範例 2.2.12 假設有一三維陣列宣告為A(1:3,1:4,1:5)，A(1,1,1)=300，且d=1，試問以行為主的排列方式下，求出A(2,2,3)的所在位址。 解答： Loc(A(1,2,3))=300+(3-1)*3*4*1+(2-1)*3*1+(2-1)=328

2-2 陣列 範例 2.2.13 有一個三維陣列A(-3:2,-2:3,0:4)，以Row-major方式排列，陣列之起始位址是1118，試求Loc(A(1,3,3))=？(d=1) 解答： 假設A為u1*u2*u3陣列，且以row-major方式排列 m=2-(-3)+1=6 n=3-(-2)+1=6 o=4-0+1=5 公式如下： =>Loc(A(1,3,3))=318+(1-(-3))*6*5+(3-(-2))*5+(3-0)=318+120+25+3=1266

2-2 陣列 範例 2.2.14 假設有一三維陣列宣告為A(-3:2,-2:3,0:4)，A(1,1,1)=300，且d=2，試問以行為主的排列方式下，求出A(2,2,3)的所在位址。 解答： m=2-(-3)+1=6 n=3-(-2)+1=6 o=4-0+1=5 Loc(A(1,2,3))=300+(3-0)*6*6*1+(2-(-2))*6*1+(2-(-3))*1=437

2-2 陣列 在C中，凡是二維以上的陣列都可以稱作多維陣列 想要提高陣列的維度，只要在宣告陣列時，增加中括號與索引值即可。 定義方式如下所示： 例如： 資料型態 陣列名稱[元素個數] [元素個數] [元素個數]……. [元素個數]; float No[2][2][2]；

2-2 陣列 n維陣列 在Java語言中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維長度]；

2-2 陣列 範例2.2.14 在４-D array A[1:4,1:6,1:5,1:3]中，且α＝200，d=1。並已知是以行排列(Column-Major)，求A[3,1,3,1]的位址。 解答： 由於本題中原本就是陣列的簡單表示法，所以不須經過轉換。並直接代入計算公式即可。 Loc(A[3,1,3,1]) =200+(1-1)*5*6*4+(3-1)*6*4+(1-1)*4+3-1 =250

2-2 陣列 範例2.2.15 假設陣列 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]的位置。 解答： Loc(A[-1,2,1,-2])=200、Loc(A[3,4,4,1])=1395、Loc(A [3,2, 1,0])=1170

2-3 矩陣 從數學的角度來看，對於m×n矩陣(Matrix)的形式，可以描述一個電腦中A(m,n)二維陣列 許多矩陣的運算與應用，都可以使用電腦中的二維陣列解決，例如討論到兩個矩陣的相加、相乘，或是某些稀疏矩陣(Sparse Matrix)、轉置矩陣(At)等等

2-3 矩陣 矩陣的運算 轉置矩陣 「轉置矩陣」(At)就是把原矩陣的行座標元素與列座標元素相互調換，假設At為A的轉置矩陣，則有At[j,i]=A[i,j]如下所示： m*n矩陣的轉置矩陣的C演算法： for(i=0;i<m;i++) for(j=0;j<n;j++) arrB[i][j]=arrA[j][i];

2-3 矩陣 範例2.3.1 請設計一Java程式，可任意輸入m與n值，來實作一m*n二維陣列的轉置矩陣。

2-3 矩陣 矩陣的運算 矩陣的加法 前題是相加的兩矩陣列數與行數都必須相等，而相加後矩陣的列數與行數也是相同。例如Amxn+Bmxn=Cmxn。 底下為矩陣相加的例子： 2個m*n矩陣的矩陣相加C演算法： for(i=0;i<3;i++) for(j=0;j<3;j++) C[i][j]=A[i][j]+B[i][j];/* 矩陣C=矩陣A+矩陣B */

2-3 矩陣 範例2.3.2 請設計一Java程式，來實作2個3*3矩陣相加的過程，並顯示兩矩陣相加後的結果。

2-3 矩陣 矩陣的運算 矩陣相乘 兩個矩陣A與B的相乘，首先必須符合A為一個m*n的矩陣，B為一個n*p的矩陣，對A*B之後的結果為一個m*p的矩陣C。 m*n矩陣與n*p矩陣的矩陣相乘C演算法： for(i=0;i<3;i++) for(j=0;j<3;j++) { C[i][j]=0; for(k=0;k<2;k++) C[i][j]=C[i][j]+A[i][k]*B[k][j];/* 矩陣C=矩陣A+矩陣B */ }

2-3 矩陣 範例2.3.3 請設計一Java程式來實作下列兩個可自行輸入矩陣維數的相乘過程，並顯示相乘後的結果。

2-3 矩陣 稀疏矩陣 對於抽象資料型態而言，我們希望闡述的是在電腦應用中具備某種意義的特別概念(Concept)。 什麼是稀疏矩陣呢？ 「如果一個矩陣中的大部分元素為零的話，就可以稱為稀疏矩陣」。 典型的稀疏矩陣：

2-3 矩陣 稀疏矩陣 對稀疏矩陣而言，實際儲存的資料項目很少，如果在電腦中利用傳統的二維陣列方式存放，就會十分浪費儲存的空間。 改進記憶體空間浪費的方法： 利用三項式(3-tuple)的資料結構。我們把每一個非零項目以(i,j,item-value)來表示。就是假如一個稀疏矩陣有n個非零項目，那麼可以利用一個A(0:n,1:3)的二維陣列來表示，我們稱為壓縮矩陣。

2-3 矩陣 稀疏矩陣 A(0,1)代表此稀疏矩陣的列數 A(0,2)代表此稀疏矩陣的行數 A(0,3)則是此稀疏矩陣非零項目的總數。 壓縮矩陣 稀疏矩陣

2-3 矩陣 範例2.3.4 請設計一Java程式，並利用3項式(3-tuple)資料結構，來壓縮8*8稀疏矩陣，以達到減少記憶體不必要的浪費。

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

2-3 矩陣 右上三角形矩陣矩陣 即對nxn的矩陣A，假如i>j，那麼A(i,j)=0，如下圖所示： 由於此二維矩陣的非零項目可依序對映成一維矩陣，且需要一個一維陣列B(1: )來儲存。對映方式也可區分為 以列為主(Row-major) 以行為主(Column-major)兩種陣列記憶體配置方式。

2-3 矩陣 右上三角形矩陣矩陣 以列為主(Row-major) 以列為主(Row-major) k=n*(i-1)- +j k= +i

2-3 矩陣 範例 2.3.5 假如有一個5x5的右上三角形矩陣A，以行為主對映到一維陣列B，請問a23所對映B(k)的k值為何？ 解答：直接代入右上三角形矩陣公式： k= +I = +2=5=>對映到B(5)

2-3 矩陣 範例2.3.6 請練習設計一Java程式，將右上三角形矩陣壓縮為一維陣列。

2-3 矩陣 左上三角形矩陣矩陣 即對nxn的矩陣A，假如i>n-j+1時，A(i,j)=0，如下圖所示： 與右上三角形矩陣相同，對應方式也分為以列為主及以行為主兩種陣列記憶配體置方式。

2-3 矩陣 左上三角形矩陣矩陣 以列為主(Row-major) 以列為主(Row-major) k=n*(i-1)- +j k= n*(j-1)- +i

2-3 矩陣 範例 2.3.7 假如有一個5*5的左上三角形矩陣，以行為主對映到一維陣列B，請問a23所對映b(k)的k值為何？ 解答：由公式可得k=n*(j-1)+i- =5*(3-1)+2- =10+2-1=11

2-3 矩陣 左下三角形矩陣矩陣 即對nxn的矩陣A，假如i<j，那麼A(i,j)=0如下圖所示： 同樣的，對映到一維陣列B(1: )的方式，也可區分為以列為主及以行為主兩種陣列記憶體配置方式。

2-3 矩陣 左下三角形矩陣矩陣 以列為主(Row-major) 以列為主(Row-major) k= +j k=n*(j-1)+i-

2-3 矩陣 範例 2.3.8 有一6x6的左下三角形矩陣，以行為主的方式對映到一維陣列B，求元素a32所對映B(k)的大值為何？ 解答：代入公式可得 代入公式k=n*(j-1)+i- =6*(2-1)+3- =6+3-1=8

2-3 矩陣 範例2.3.8 請設計一Java程式，將左下三角形矩陣壓縮為一維陣列。

2-3 矩陣 右下三角形矩陣矩陣 即對nxn的矩陣A，假如i<n-j+1，那麼A(i,j)=0，如下圖所示 同樣的，對映到一維陣列B(1: )的方式，也可區分為以列為主與以行為主兩種陣列記憶體配置方式

2-3 矩陣 右下三角形矩陣矩陣 以列為主(Row-major) 以列為主(Row-major) k= *[1+(i-1)]+j-(n-i) k= +i-(n-j) = +i-n

2-3 矩陣 範例 2.3.10 假設有一個4x4的右下三角形矩陣，以行為主對映到一維陣列B，求元素a32所對映B(k)的k值為何？ 解答： 代入公式k= +i-n = +3-4 =2

2-3 矩陣 範例 2.3.11 一個低部三角陣列(Lower Triangular Array)，B是一個nxn的陣列，其中B[i,j]=0，i<j。 求B陣列中不為0的最大個數。  如何將B陣列以最經濟的方式儲存在記憶體中。 寫出在的儲存方式中，如何求得B[i,j]，i>=j。

2-3 矩陣 解答： 由題意得知B為左下三角形矩陣，因此不為0的個數為 可將B陣列非零項目的值以列為主(Row-major)對映到一維陣列A中，且如下圖所示： 以列為主的對映方式，bij=A(k)   k= +j

2-3 矩陣 帶狀矩陣 一種在應用上較為特殊且稀少的矩陣。 定義就是在上三角形矩陣中，右上方的元素皆為零，在下三角形矩陣中，左下方的元素也為零，也就是除了第一列與第n列有兩個元素外，其餘每列都具有三個元素，使得中間主軸附近的值形成類似帶狀的矩陣。如下圖所示：

本章結束 Q&A討論時間