Download presentation
Presentation is loading. Please wait.
1
第 三 章 陣 列 課程名稱：資料結構 授課老師：________ 2019/5/15
2
本章學習目標 1.讓讀者了解一維、二維及多維陣列的結構及表示方法。
2.讓讀者了解矩陣中常見的各種運算<轉置、相加、相乘及稀疏矩陣> 2019/5/15
3
本章內容 3-1 陣列的觀念 3-2 陣列的宣告與儲存方式 3-3 二維陣列的觀念 3-4 多維陣列的觀念 3-5 陣列在記憶體中的表示法
3-6 多項式(polynomials) 3-7 矩陣(Matrices) 3-8 特殊矩陣 2019/5/15
4
3-1 陣列的觀念 何謂陣列呢？陣列是指一群具有相同名稱及資料型態的變數之集合。
由於整個陣列中的變數均具有相同的名稱, 因此若要存取陣列中的變 數, 我們只需要透過陣列的編號(註標)來指定變數即可。 2019/5/15
5
【陣列與變數之差異】 陣列與變數的功能都是用來儲存資料，但所不同的是每一個變數只能儲存一項資料，而陣列則是由一連串的主記憶體空間組合而成，所以可以同時連續儲放多項資料，亦即一次可宣告很多個變數，而不用一個一個宣告。因此，可以少寫許多行程式，並且增加程式的可讀性。 2019/5/15
6
【舉例】 Dim x,y ,z as Integer ，亦即利用x, y及z三個變數來存放3個整數。
假設，我們需要3個整數變數來存放資料時, 我們就必須要宣告成 Dim x,y ,z as Integer ，亦即利用x, y及z三個變數來存放3個整數。 問題來了，若我們今天需要50個整數變數來存放資料呢 ? 要如何為這50 個變數來取名，這真是一大頭痛的問題?解決方法：利用「陣列」。 2019/5/15
7
【定義】 1.佔用連續記憶體空間。 2.用來表示有序串列之一種方式。 3.各元素的資料型態皆相同。
4.支援隨機存取(Random Access)與循序存取(Sequential Access)。 5.插入或刪除元素時較為麻煩。因為須挪移其他元素。 2019/5/15
8
【例如】 假設我們需要10個整數變數來存放資料時，那就必須要宣告一個A陣列 為整數型態，其註標是按照順序排列從0~9共有10項，其含義如下：
【說明】 A陣列表示內共有10個陣列元素，也就是有10個變數，分別為A(0)、A(1)、A(2)……A(9)。 (2)每一個陣列元素可以存放一筆資料。 2019/5/15
9
(3)陣列內容的存取，通常是以迴圈指令配合輸入或輸出指令來進行，如下片段程式。
(4) 陣列所存放的每個資料叫做元素，若一個陣列中元素的個數為ｎ時，表示此陣列的長度為ｎ，然後透過「陣列」與「註標」可以用來區分每個元素，註標是以一個數字表示，註標0是代表陣列的第一個元素，註標1代表陣列的第二個元素，......，以此類推，則陣列的第n個元素則以註標n-1代表。 2019/5/15
10
3-2 陣列的宣告與儲存方式 陣列宣告的方式和一般變數的宣告大同小異，所不同的是，在陣列名
3-2 陣列的宣告與儲存方式 陣列宣告的方式和一般變數的宣告大同小異，所不同的是，在陣列名 稱後，必須要再加上陣列註標(索引)值大小，以便VB語言向系統爭取 預留足夠的主記憶體空間。 2019/5/15
11
3-2.1 陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】 (1)「陣列名稱」的命名規則和一般變數相同。
陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】 (1)「陣列名稱」的命名規則和一般變數相同。 (2)「陣列大小」必須是一數字型態。 【舉例】DIM A(2) AS Integer ‘宣告一維陣列A，共有A(0)、A(1)、A(2)三個元素 2019/5/15
12
【舉例】變數宣告與陣列宣告的差異 (1) 變數宣告 宣告三個變數(A,B,C)為整數型態，如圖3-1所示：
Dim A, B, C As Integer 圖3-1 不連續的記憶體空間的配置 以上三個變數只能各儲存一項資料，並且變數與變數之間都是 個別獨立的記憶體空間。 2019/5/15
13
【舉例】變數宣告與陣列宣告的差異 (2) 陣列宣告 宣告一個A(2)的陣列，如下所示：
DIM A(2) AS Integer ‘宣告一維陣列A，共有A[0]、A[1]、A[2]三個元素 此時，主記憶體就會即時配置3個位置，如圖3-2所示： 圖3-2 連續的記憶體空間的配置 以上所配置位置是連續的記憶體空置，可以讓我們連續儲存多項資料 ，並且資料與資料之間都是按照順序排列的記憶體空間。 2019/5/15
14
使用陣列的優點 (1)利用索引值（Index）可以快速的存取資料。 (2)一次可以處理大批的資料。 (3)較容易表達資料處理的技巧。
2019/5/15
15
3-2.2 陣列的儲存方式 當宣告完成一個陣列名稱之後便可以開始儲存資料，其方法則直接在 陣列名稱之後加上“註標或索引值 ”即可。
陣列的儲存方式 當宣告完成一個陣列名稱之後便可以開始儲存資料，其方法則直接在 陣列名稱之後加上“註標或索引值 ”即可。 【舉例】宣告一個A(2)的陣列，並分別儲存10,20,30，如下所示： DIM A(2) AS Integer A(0)= ‘指把10指定給A陣列中的第0項的資料中 A(1)=20 A(2)=30 此時，主記憶體就會配置3個位置，分別存入10,20,30三項資料到陣 列中，如下圖所示： 2019/5/15
16
【實例】 如果想要記錄六位學生的成績，原來方法必需要使用六個不同變數名稱來存
放成績，由於這些成績都是屬於同性質的資料，就可以宣告一個陣列名稱為A 的整數陣列，共含有六個陣列元素。 其寫法：Dim A(5) As Integer 2019/5/15
17
【實作】請依序輸入六位同學的成績到陣列中，並計算及輸出「總和」。
第一種寫法： 未使用for迴圈演算法 2019/5/15
18
第二種寫法：(最佳) 使用for迴圈演算法 2019/5/15
19
3-2.3 使用陣列的注意事項 雖然陣列比變數來得有彈性，但是，也要注意以下事項： 1.不能夠一次讀取或指定整個陣列的資料。
現在寫一個程式，利用A陣列來存放數字10。 (1)直覺想法：以下的方法是錯誤 Dim A(50) As Integer A=10 原因：想把整個陣列的資料都指定為10時，電腦會產生錯誤Error。 不能直接指定給陣列名稱 2019/5/15
20
(2)正確方法：必須把程式改為如下： 2019/5/15
21
2.在使用多維陣列時，最多不可以超過60維陣列。 3.用來指定某一項資料的註標不能超過陣列的註標範圍。
例如：Dim A(50) '宣告一個陣列A其註標是從0~50 A(-1)= '註標是 –1，超出陣列A的範圍 A(51)= '註標是 51，超出陣列A的範圍 2019/5/15
22
3-2.4 陣列的初值設定 指在宣告陣列的同時並指定初值，其方法只要等號(=)在後面接著大 括號，將初值寫在括號內，初值間以逗號隔開即可。
【語法】Dim 陣列名稱( ) As 資料型別 ={陣列初值串列} 【說明】 (1)宣告A是一個含有5個整數的陣列 Dim A( ) As Integer = {1,2,3,4,5} (2)宣告一個A(2,2)的二維整數陣列 Dim A(,) As Integer={{1,2,3},{4,5,6},{7,8,9}} 2019/5/15
23
3-3 二維陣列的觀念 在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般
3-3 二維陣列的觀念 在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般 的問題都可以順利的處理，但是對於比較複雜的問題時，那就必須要 使用二維陣列來處理。否則會增加程式的複雜度。 例如：計算4位同學的5科成績之總分與平均的問題。 2019/5/15
24
【語法】Dim 陣列名稱 (M,N) AS 資料型態 【說明】M代表列數，N代表行數 【例如】Dim A(3,4) As Integer
‘列註標表示範圍： 0~3 共有4列 ‘行註標表示範圍： 0~4 共有5行 2019/5/15 【存取方法】利用二維陣列中的兩個註標來表示。
25
3-4 多維陣列的觀念 當陣列的維度是二維以上時，就稱為多維陣列。而其中最常見是三維
陣列，其圖形為三度空間的立體圖形，並且我們可以將三維陣列視為 多個二維陣列的組合。 2019/5/15
26
【語法】Dim 陣列名稱 (L,M,N) AS 資料型態 【說明】L代表二維陣列個數 M代表列數 N代表行數
【例如】Dim Score (2,3,4) As Integer ‘二維陣列的個數： 0~2 共有3個二維陣列 ‘列註標表示範圍： 0~3 共有4列 ‘行註標表示範圍： 0~4 共有5行 2019/5/15
27
【舉例】設計一個某高中，3次月考，全班4位同學的5科目成績時。 利用三維陣列來存取每人學生的成績。
【說明】此例子中Score陣列共有三個註標，故Score陣列是一個三維陣列。宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列(0~3)，5行(0~4)組合而成的整數三維陣列。並且共計有3×4×5＝60元素。 2019/5/15
28
2019/5/15
29
3-5 陣列在記憶體中的表示法 陣列是由一連串的記憶體組合而成，其陣列元素之儲存位址計算，如下所示： Ⅰ. 一維陣列
[1]若陣列A有N個元素，其陣列的起始位址為Lo，並且索引值從0開始，d 為元素大小，則A[i]的起始位置為多少？ 以C語言宣告方式：int A[N]; 令：Lo為起始位址 d為元素大小 則A[i]之位置計算=Lo+i*d 2019/5/15
30
【舉例】假設每一個整數佔用2個byte，若A陣列的起始位址是100開 始，則A[5]的起始位址為多少？ 令：Lo=100 d=2
2019/5/15
![【舉例】假設每一個整數佔用2個byte，若A陣列的起始位址是100開 始，則A[5]的起始位址為多少？ 令：Lo=100 d=2](http://slidesplayer.com/slide/16797509/97/images/30/%E3%80%90%E8%88%89%E4%BE%8B%E3%80%91%E5%81%87%E8%A8%AD%E6%AF%8F%E4%B8%80%E5%80%8B%E6%95%B4%E6%95%B8%E4%BD%94%E7%94%A82%E5%80%8Bbyte%EF%BC%8C%E8%8B%A5A%E9%99%A3%E5%88%97%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%E6%98%AF100%E9%96%8B+%E5%A7%8B%EF%BC%8C%E5%89%87A%5B5%5D%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%E7%82%BA%E5%A4%9A%E5%B0%91%EF%BC%9F+%E4%BB%A4%EF%BC%9A%EF%82%8CLo%3D100+%EF%82%8Dd%3D2.jpg "2019/5/15.")
31
[2]若陣列A的索引從L到U，其陣列的起始位址為Lo，d為元素大小，則A[i]的起始位置為多少？
則A[i]之位置計算=Lo+(i-L)*d 2019/5/15
![[2]若陣列A的索引從L到U，其陣列的起始位址為Lo，d為元素大小，則A[i]的起始位置為多少？](http://slidesplayer.com/slide/16797509/97/images/31/%5B2%5D%E8%8B%A5%E9%99%A3%E5%88%97A%E7%9A%84%E7%B4%A2%E5%BC%95%E5%BE%9EL%E5%88%B0U%EF%BC%8C%E5%85%B6%E9%99%A3%E5%88%97%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%E7%82%BALo%EF%BC%8Cd%E7%82%BA%E5%85%83%E7%B4%A0%E5%A4%A7%E5%B0%8F%EF%BC%8C%E5%89%87A%5Bi%5D%E7%9A%84%E8%B5%B7%E5%A7%8B%E4%BD%8D%E7%BD%AE%E7%82%BA%E5%A4%9A%E5%B0%91%EF%BC%9F.jpg "則A[i]之位置計算=Lo+(i-L)*d. 2019/5/15.")
32
【舉例】假設每一個整數佔用2個byte，若A[10]起始位址是200開始， 則A[20]的位址為多少？ 令：Lo=200 d=2
2019/5/15
![【舉例】假設每一個整數佔用2個byte，若A[10]起始位址是200開始， 則A[20]的位址為多少？ 令：Lo=200 d=2](http://slidesplayer.com/slide/16797509/97/images/32/%E3%80%90%E8%88%89%E4%BE%8B%E3%80%91%E5%81%87%E8%A8%AD%E6%AF%8F%E4%B8%80%E5%80%8B%E6%95%B4%E6%95%B8%E4%BD%94%E7%94%A82%E5%80%8Bbyte%EF%BC%8C%E8%8B%A5A%5B10%5D%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%E6%98%AF200%E9%96%8B%E5%A7%8B%EF%BC%8C+%E5%89%87A%5B20%5D%E7%9A%84%E4%BD%8D%E5%9D%80%E7%82%BA%E5%A4%9A%E5%B0%91%EF%BC%9F+%E4%BB%A4%EF%BC%9A%EF%82%8CLo%3D200+%EF%82%8Dd%3D2.jpg "2019/5/15.")
33
Ⅱ. 二維陣列 宣告方式：A[0…M-1, 0…N-1] 其中：M代表列數(Row)，橫向。 N代表行數(Column)，縱向。
2019/5/15
![Ⅱ. 二維陣列 宣告方式：A[0…M-1, 0…N-1] 其中：M代表列數(Row)，橫向。 N代表行數(Column)，縱向。](http://slidesplayer.com/slide/16797509/97/images/33/%E2%85%A1.+%E4%BA%8C%E7%B6%AD%E9%99%A3%E5%88%97+%E5%AE%A3%E5%91%8A%E6%96%B9%E5%BC%8F%EF%BC%9AA%5B0%E2%80%A6M-1%2C+0%E2%80%A6N-1%5D+%E5%85%B6%E4%B8%AD%EF%BC%9AM%E4%BB%A3%E8%A1%A8%E5%88%97%E6%95%B8%28Row%29%EF%BC%8C%E6%A9%AB%E5%90%91%E3%80%82+N%E4%BB%A3%E8%A1%A8%E8%A1%8C%E6%95%B8%28Column%29%EF%BC%8C%E7%B8%B1%E5%90%91%E3%80%82.jpg "2019/5/15.")
34
3-5.1 Row-major(以列為主) 在二維陣列中，如何將二維陣列轉成一維陣列，一般而言，有兩種方
式：「以列（Row）為主」或「以行（Column）為主」。但C語言的 記憶體配置方式都是以列為主。 2019/5/15
35
一、以列為主(Row-major)方式：
以列為主的二維陣列要轉為一維陣列時，是將二維陣列「由上往下」 一列一列讀入一維陣列，亦即將二維陣列儲存的邏輯位置轉換成實際 電腦中主記憶體的存儲方式。如下圖所示： 2019/5/15
36
二、以列為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[i*N+j]*d 2019/5/15
![二、以列為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[i*N+j]*d 2019/5/15](http://slidesplayer.com/slide/16797509/97/images/36/%E4%BA%8C%E3%80%81%E4%BB%A5%E5%88%97%E7%82%BA%E4%B8%BB%E7%9A%84%E5%84%B2%E5%AD%98%E5%85%AC%E5%BC%8F%EF%BC%9A+%EF%82%8C%E4%BB%A4Lo%E7%82%BA%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80+%EF%82%8Dd%E7%82%BA%E5%85%83%E7%B4%A0%E5%A4%A7%E5%B0%8F+%E5%89%87A%5Bi%2Cj%5D%E7%9A%84%E4%BD%8D%E7%BD%AE%3DLo%2B%5Bi%2AN%2Bj%5D%2Ad+2019%2F5%2F15.jpg "二、以列為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[i*N+j]*d 2019/5/15")
37
3-5.2 Column-major(以行為主) 【老師上課動態展示】檔案在附書光碟中。 2019/5/15
38
一、以行為主(Column-major)方式：
以行為主的二維陣列要轉為一維陣列時，是將二維陣列「由左往右」一行 一行讀入一維陣列，亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主 記憶體的存儲方式。如下圖所示： 2019/5/15
39
二、以行為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[j*M+i]*d 2019/5/15
![二、以行為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[j*M+i]*d 2019/5/15](http://slidesplayer.com/slide/16797509/97/images/39/%E4%BA%8C%E3%80%81%E4%BB%A5%E8%A1%8C%E7%82%BA%E4%B8%BB%E7%9A%84%E5%84%B2%E5%AD%98%E5%85%AC%E5%BC%8F%EF%BC%9A+%EF%82%8C%E4%BB%A4Lo%E7%82%BA%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80+%EF%82%8Dd%E7%82%BA%E5%85%83%E7%B4%A0%E5%A4%A7%E5%B0%8F+%E5%89%87A%5Bi%2Cj%5D%E7%9A%84%E4%BD%8D%E7%BD%AE%3DLo%2B%5Bj%2AM%2Bi%5D%2Ad+2019%2F5%2F15.jpg "二、以行為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[j*M+i]*d 2019/5/15")
40
3-5.3 二維陣列的四個題型 【題型一】給予所有資料 【題型二到四，請參考課本】 2019/5/15
41
3-5.4 三維陣列之元素儲存 儲存方式只有二種： 以列為主(Row-major)：由左至右
以行為主(Column-major) ：由右至左 2019/5/15
42
【基本題】 假設三維陣列的元素編號從1開始。 宣告方式A[1…U1, 1…U2, 1…U3] 起始位址：Lo 元素大小：d
以列為主(Row-major)的儲存公式： A[i,j,k]的位置=Lo+[(i-1)*U2*U3+(j-1)*U3+(k-1)]*d 以行為主(Column-major)的儲存公式： A[i,j,k]的位置=Lo+[(k-1)*U2*U1+(j-1)*U1+(i-1)]*d 2019/5/15
![【基本題】 假設三維陣列的元素編號從1開始。 宣告方式A[1…U1, 1…U2, 1…U3] 起始位址：Lo 元素大小：d](http://slidesplayer.com/slide/16797509/97/images/42/%E3%80%90%E5%9F%BA%E6%9C%AC%E9%A1%8C%E3%80%91+%E5%81%87%E8%A8%AD%E4%B8%89%E7%B6%AD%E9%99%A3%E5%88%97%E7%9A%84%E5%85%83%E7%B4%A0%E7%B7%A8%E8%99%9F%E5%BE%9E1%E9%96%8B%E5%A7%8B%E3%80%82+%EF%83%98%E5%AE%A3%E5%91%8A%E6%96%B9%E5%BC%8FA%5B1%E2%80%A6U1%2C+1%E2%80%A6U2%2C+1%E2%80%A6U3%5D+%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%EF%BC%9ALo+%E5%85%83%E7%B4%A0%E5%A4%A7%E5%B0%8F%EF%BC%9Ad.jpg "以列為主(Row-major)的儲存公式： A[i,j,k]的位置=Lo+[(i-1)*U2*U3+(j-1)*U3+(k-1)]*d. 以行為主(Column-major)的儲存公式： A[i,j,k]的位置=Lo+[(k-1)*U2*U1+(j-1)*U1+(i-1)]*d. 2019/5/15.")
43
3-5.5 N維陣列之元素儲存 儲存方式只有二種： 以列為主(Row-major)：由左至右
以行為主(Column-major) ：由右至左 2019/5/15
44
宣告方式：A[1…U1, 1…U2, 1…U3,……, 1…Un] 起始位址：Lo 元素大小：d
以列為主(Row-major)的儲存公式以行為主(Column-major)的儲存公式 2019/5/15
![宣告方式：A[1…U1, 1…U2, 1…U3,……, 1…Un] 起始位址：Lo 元素大小：d](http://slidesplayer.com/slide/16797509/97/images/44/%EF%83%98%E5%AE%A3%E5%91%8A%E6%96%B9%E5%BC%8F%EF%BC%9AA%5B1%E2%80%A6U1%2C+1%E2%80%A6U2%2C+1%E2%80%A6U3%2C%E2%80%A6%E2%80%A6%2C+1%E2%80%A6Un%5D+%E8%B5%B7%E5%A7%8B%E4%BD%8D%E5%9D%80%EF%BC%9ALo+%E5%85%83%E7%B4%A0%E5%A4%A7%E5%B0%8F%EF%BC%9Ad.jpg "以列為主(Row-major)的儲存公式以行為主(Column-major)的儲存公式. 2019/5/15.")
45
3-6 多項式(polynomials) 多項式(polynomial)的表示式為
其中Ai為非零項的係數，且多項式的每一項均使用三個欄位來表示 (分別為 coef, exp, link) 。其節點的資料結構如下所示： 其中：Coef：表示該變數的係數 Exp：表示該變數的指數 Link：表示指向下一個節點的指標 2019/5/15
46
多項式的表示方法有兩種： 【方法一】依照指數高低依序儲存係數 【方法二】只儲存非零項次的係數與指數 2019/5/15
47
【方法一】依照指數高低依序儲存係數 【作法】假設最高指數為n，則準備一個一維陣列A[1..n+2]，其內容如下：
【練習】假設f(x)=7X4+5X2+3X 因為最高指數為4，則準備一個一維陣列A[1..6]，其內容如下： 2019/5/15
![【方法一】依照指數高低依序儲存係數 【作法】假設最高指數為n，則準備一個一維陣列A[1..n+2]，其內容如下：](http://slidesplayer.com/slide/16797509/97/images/47/%E3%80%90%E6%96%B9%E6%B3%95%E4%B8%80%E3%80%91%E4%BE%9D%E7%85%A7%E6%8C%87%E6%95%B8%E9%AB%98%E4%BD%8E%E4%BE%9D%E5%BA%8F%E5%84%B2%E5%AD%98%E4%BF%82%E6%95%B8+%E3%80%90%E4%BD%9C%E6%B3%95%E3%80%91%E5%81%87%E8%A8%AD%E6%9C%80%E9%AB%98%E6%8C%87%E6%95%B8%E7%82%BAn%EF%BC%8C%E5%89%87%E6%BA%96%E5%82%99%E4%B8%80%E5%80%8B%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97A%5B1..n%2B2%5D%EF%BC%8C%E5%85%B6%E5%85%A7%E5%AE%B9%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "【練習】假設f(x)=7X4+5X2+3X. 因為最高指數為4，則準備一個一維陣列A[1..6]，其內容如下： 2019/5/15.")
48
(1)只要儲存係數，比較節省儲存指數空間。 (2)適用於零項次較少的多項式。 【缺點】 不適用於零項次極多的多項式，儲存時非常浪費空間。
【優點】 (1)只要儲存係數，比較節省儲存指數空間。 (2)適用於零項次較少的多項式。 【缺點】 不適用於零項次極多的多項式，儲存時非常浪費空間。 Ex: f(X)=5X100+1 則必須要準備一個一維陣列A[1..102]，在實際使用上只用了 3格，因此，會浪費99格。 2019/5/15
49
【方法二】只儲存非零項次的係數與指數 【作法】假設多項式有K個非零項次，則準備一個一維陣列 A[1..2K+1]，其內容如下：
2019/5/15
![【方法二】只儲存非零項次的係數與指數 【作法】假設多項式有K個非零項次，則準備一個一維陣列 A[1..2K+1]，其內容如下：](http://slidesplayer.com/slide/16797509/97/images/49/%E3%80%90%E6%96%B9%E6%B3%95%E4%BA%8C%E3%80%91%E5%8F%AA%E5%84%B2%E5%AD%98%E9%9D%9E%E9%9B%B6%E9%A0%85%E6%AC%A1%E7%9A%84%E4%BF%82%E6%95%B8%E8%88%87%E6%8C%87%E6%95%B8+%E3%80%90%E4%BD%9C%E6%B3%95%E3%80%91%E5%81%87%E8%A8%AD%E5%A4%9A%E9%A0%85%E5%BC%8F%E6%9C%89K%E5%80%8B%E9%9D%9E%E9%9B%B6%E9%A0%85%E6%AC%A1%EF%BC%8C%E5%89%87%E6%BA%96%E5%82%99%E4%B8%80%E5%80%8B%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97+A%5B1..2K%2B1%5D%EF%BC%8C%E5%85%B6%E5%85%A7%E5%AE%B9%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "2019/5/15.")
50
因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下：
【練習】假設f(X)=5X100+1 因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下： 【優點】適用於零項次極多的多項式。 【缺點】當非零項次極多時，不適用。 2019/5/15
![因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下：](http://slidesplayer.com/slide/16797509/97/images/50/%E5%9B%A0%E7%82%BA%E6%9C%892%E5%80%8B%E9%9D%9E%E9%9B%B6%E9%A0%85%E6%AC%A1%EF%BC%8C%E5%89%87%E6%BA%96%E5%82%99%E4%B8%80%E5%80%8B%E4%B8%80%E7%B6%AD%E9%99%A3%E5%88%97A%5B1..5%5D%EF%BC%8C%E5%85%B6%E5%85%A7%E5%AE%B9%E5%A6%82%E4%B8%8B%EF%BC%9A.jpg "【練習】假設f(X)=5X 因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下： 【優點】適用於零項次極多的多項式。 【缺點】當非零項次極多時，不適用。 2019/5/15.")
51
3-7 矩陣(Matrices) 「矩陣」（Matrices）類似二維陣列，一個m × n矩陣表示這個矩陣擁
有m列（Rows）和n行（Columns），在數學上有矩陣，而資料結構 除了使用數學上的矩陣之外，也可以實際應用在電腦科學領域中。 一般而言，資料結構上常用到的矩陣有四種： 1. 矩陣轉置(Matrix Transposition) 2. 矩陣相加(Matrix Addition) 3. 矩陣相乘(Matrix Multiplication) 4. 稀疏矩陣(Sparse Matrix) 2019/5/15
52
3-7.1 矩陣轉置(Matrix Transposition)
假設有一個(m × n)矩陣A，則我們可以將A矩陣轉置為(n × m)的B矩 陣，並且B矩陣的第i列第j行的元素等於A矩陣的第j列第i行的元素， 以數學式來表示為：Bij=Aji。 2019/5/15
53
【假設】A矩陣與B矩陣的m與n都是從1開始計算，因此，A,B矩陣 的表示如下：
2019/5/15
54
【演算法】 2019/5/15
55
【老師上課動態展示】檔案在附書光碟中。 2019/5/15
56
3-7.2 矩陣相加(Matrix Addition)
假設A,B都是(m × n)矩陣，則我們可以將A矩陣加上B矩陣以得到一個 C矩陣，並且此C矩陣亦為(m × n)矩陣，因此，在C矩陣上的第i列第j 行的元素必定等於A矩陣的第i列第j行的元素加上B矩陣的第i列第j行 的元素，以數學式來表示為：Cij= Aij+Bij 2019/5/15
57
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩 陣相加等於C矩陣，其表示如下：
2019/5/15
58
2019/5/15
59
【演算法】 2019/5/15
60
【老師上課動態展示】檔案在附書光碟中。 2019/5/15
61
3-7.3 矩陣相乘(Matrix Multiplication)
假設A為(m × n)矩陣，而B為(n × p)矩陣，則我們可以將A矩陣乘上B 矩陣以得到一個(m × p)的C矩陣，因此，在C矩陣上的第i列第j行的元 素必定等於A矩陣的第i列乘上B矩陣的第j行(兩個向量的內積)，以數 學式來表示為： 2019/5/15
62
【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩 陣相乘等於C矩陣，其表示如下：
2019/5/15
63
2019/5/15
64
【演算法】 2019/5/15
65
【老師上課動態展示】檔案在附書光碟中。 2019/5/15
66
3-7.4 稀疏矩陣(Sparse Matrix) 【定義】 「稀疏矩陣」（Sparse Matrices）屬於矩陣一種非常特殊的
情況，因為矩陣元素大部份元素都沒有使用，元素稀稀落 落，所以稱為稀疏矩陣。 【概念】在M × N 的矩陣中，多數的資料值為０。 2019/5/15
67
【方法一】直接利用M × N的二維陣列一一對應儲存。 【缺點】 1. 浪費空間：因為多數為０。 2. 浪費時間：許多是不必要的計算。
2019/5/15
68
【方法二】利用3-tuple結構來儲存非零元素 【作法】假設有一個M*N的稀疏矩陣中共有K個非零元素，則必須要
準備一個二維陣列A[0..K,1..3] 【優點】只儲存非０之資料，因此，可以減少記憶體空間的浪費。 2019/5/15
69
2019/5/15
70
【老師上課動態展示】檔案在附書光碟中。 2019/5/15
71
3-8 特殊矩陣 在前面已經介紹資料結構中，常用的四種矩陣之外，我們在本單元 中，將介紹比較特殊的矩陣，例如：上、下三角矩陣。
2019/5/15
72
3-8.1 上三角矩陣(Upper-Triangular Matrix)
(一)定義： 上三角矩陣是矩陣在對角線以下的元素均為0，即Aij = 0，i > j。 2019/5/15
73
2019/5/15
74
2019/5/15
75
2019/5/15
76
【老師上課動態展示】檔案在附書光碟中。(以列為主)
2019/5/15
77
3-8.2 下三角矩陣(Lower-Triangular Matrix)
(一)定義：下三角矩陣是矩陣在對角線以上的元素均為0，即Aij = 0，i < j。 2019/5/15
78
2019/5/15
79
2019/5/15
80
2019/5/15
81
【老師上課動態展示】檔案在附書光碟中。(以列為主)
2019/5/15
Similar presentations
