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

Presentation on theme: "第二章 鏈結串列 2-1　線性串列 2-2 認識陣列 2-3 矩陣的簡介與運算 2-4 陣列與多項式."— Presentation transcript:

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

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

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

4 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。 複製串列。 合併串列。

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

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

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

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

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

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

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

12 以列為主(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

13 以行為主(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

14 範例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)的位置？

15 假設α仍為起始位址，而且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

16 範例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)

17 範例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]之位址。

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

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

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

21 範例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)

22 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維長度]；

23 以列為主(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

24 以行為主(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

25 範例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]的位置。

26 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陣列中索引值 起始索引 到 結束索 引 做由小至大排序動作。

27 範例程式：ch02_01.java

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

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

30 範例程式：ch02_02. java

31 矩陣相乘 首先必須符合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

32 範例程式：ch02_03. java

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

34 範例程式：ch02_04. java

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

36 範例程式：ch02_05.java

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

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

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

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

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

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

43 範例程式：ch02_06.java

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

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

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

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

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

49 以列為主 k= +j

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

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

52 範例程式：ch02_07.java

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

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

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

56 範例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。

57 認識多項式 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}

58 例如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}

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

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