第 三 章 陣 列 課程名稱：資料結構 授課老師：________ 2019/5/15

本章學習目標 1.讓讀者了解一維、二維及多維陣列的結構及表示方法。 2.讓讀者了解矩陣中常見的各種運算<轉置、相加、相乘及稀疏矩陣> 2019/5/15

本章內容 3-1 陣列的觀念 3-2 陣列的宣告與儲存方式 3-3 二維陣列的觀念 3-4 多維陣列的觀念 3-5 陣列在記憶體中的表示法 3-6 多項式(polynomials) 3-7 矩陣(Matrices) 3-8 特殊矩陣 2019/5/15

3-1 陣列的觀念 何謂陣列呢？陣列是指一群具有相同名稱及資料型態的變數之集合。 由於整個陣列中的變數均具有相同的名稱, 因此若要存取陣列中的變 數, 我們只需要透過陣列的編號(註標)來指定變數即可。 2019/5/15

【陣列與變數之差異】 陣列與變數的功能都是用來儲存資料，但所不同的是每一個變數只能儲存一項資料，而陣列則是由一連串的主記憶體空間組合而成，所以可以同時連續儲放多項資料，亦即一次可宣告很多個變數，而不用一個一個宣告。因此，可以少寫許多行程式，並且增加程式的可讀性。 2019/5/15

【舉例】 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

【定義】 1.佔用連續記憶體空間。 2.用來表示有序串列之一種方式。 3.各元素的資料型態皆相同。 4.支援隨機存取(Random Access)與循序存取(Sequential Access)。 5.插入或刪除元素時較為麻煩。因為須挪移其他元素。 2019/5/15

【例如】 假設我們需要10個整數變數來存放資料時，那就必須要宣告一個A陣列 為整數型態，其註標是按照順序排列從0~9共有10項，其含義如下： 【說明】 A陣列表示內共有10個陣列元素，也就是有10個變數，分別為A(0)、A(1)、A(2)……A(9)。 (2)每一個陣列元素可以存放一筆資料。 2019/5/15

(3)陣列內容的存取，通常是以迴圈指令配合輸入或輸出指令來進行，如下片段程式。 (4) 陣列所存放的每個資料叫做元素，若一個陣列中元素的個數為ｎ時，表示此陣列的長度為ｎ，然後透過「陣列」與「註標」可以用來區分每個元素，註標是以一個數字表示，註標0是代表陣列的第一個元素，註標1代表陣列的第二個元素，......，以此類推，則陣列的第n個元素則以註標n-1代表。 2019/5/15

3-2 陣列的宣告與儲存方式 陣列宣告的方式和一般變數的宣告大同小異，所不同的是，在陣列名 3-2 陣列的宣告與儲存方式 陣列宣告的方式和一般變數的宣告大同小異，所不同的是，在陣列名 稱後，必須要再加上陣列註標(索引)值大小，以便VB語言向系統爭取 預留足夠的主記憶體空間。 2019/5/15

3-2.1 陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】 (1)「陣列名稱」的命名規則和一般變數相同。 3-2.1 陣列的宣告 【語法】Dim 陣列名稱(陣列大小) As 資料型態 【說明】 (1)「陣列名稱」的命名規則和一般變數相同。 (2)「陣列大小」必須是一數字型態。 【舉例】DIM A(2) AS Integer ‘宣告一維陣列A，共有A(0)、A(1)、A(2)三個元素 2019/5/15

【舉例】變數宣告與陣列宣告的差異 (1) 變數宣告 宣告三個變數(A,B,C)為整數型態，如圖3-1所示： Dim A, B, C As Integer 圖3-1 不連續的記憶體空間的配置 以上三個變數只能各儲存一項資料，並且變數與變數之間都是 個別獨立的記憶體空間。 2019/5/15

【舉例】變數宣告與陣列宣告的差異 (2) 陣列宣告 宣告一個A(2)的陣列，如下所示： DIM A(2) AS Integer ‘宣告一維陣列A，共有A[0]、A[1]、A[2]三個元素 此時，主記憶體就會即時配置3個位置，如圖3-2所示： 圖3-2 連續的記憶體空間的配置 以上所配置位置是連續的記憶體空置，可以讓我們連續儲存多項資料 ，並且資料與資料之間都是按照順序排列的記憶體空間。 2019/5/15

使用陣列的優點 (1)利用索引值（Index）可以快速的存取資料。 (2)一次可以處理大批的資料。 (3)較容易表達資料處理的技巧。 2019/5/15

3-2.2 陣列的儲存方式 當宣告完成一個陣列名稱之後便可以開始儲存資料，其方法則直接在 陣列名稱之後加上“註標或索引值 ”即可。 3-2.2 陣列的儲存方式 當宣告完成一個陣列名稱之後便可以開始儲存資料，其方法則直接在 陣列名稱之後加上“註標或索引值 ”即可。 【舉例】宣告一個A(2)的陣列，並分別儲存10,20,30，如下所示： DIM A(2) AS Integer A(0)=10 ‘指把10指定給A陣列中的第0項的資料中 A(1)=20 A(2)=30 此時，主記憶體就會配置3個位置，分別存入10,20,30三項資料到陣 列中，如下圖所示： 2019/5/15

【實例】 如果想要記錄六位學生的成績，原來方法必需要使用六個不同變數名稱來存 放成績，由於這些成績都是屬於同性質的資料，就可以宣告一個陣列名稱為A 的整數陣列，共含有六個陣列元素。 其寫法：Dim A(5) As Integer 2019/5/15

【實作】請依序輸入六位同學的成績到陣列中，並計算及輸出「總和」。 第一種寫法： 未使用for迴圈演算法 2019/5/15

第二種寫法：(最佳) 使用for迴圈演算法 2019/5/15

3-2.3 使用陣列的注意事項 雖然陣列比變數來得有彈性，但是，也要注意以下事項： 1.不能夠一次讀取或指定整個陣列的資料。 現在寫一個程式，利用A陣列來存放數字10。 (1)直覺想法：以下的方法是錯誤 Dim A(50) As Integer A=10 原因：想把整個陣列的資料都指定為10時，電腦會產生錯誤Error。 不能直接指定給陣列名稱 2019/5/15

(2)正確方法：必須把程式改為如下： 2019/5/15

2.在使用多維陣列時，最多不可以超過60維陣列。 3.用來指定某一項資料的註標不能超過陣列的註標範圍。 例如：Dim A(50) '宣告一個陣列A其註標是從0~50 　　　 A(-1)=100 '註標是 –1，超出陣列A的範圍 A(51)=100 '註標是 51，超出陣列A的範圍 2019/5/15

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

3-3 二維陣列的觀念 在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般 3-3 二維陣列的觀念 在前面所介紹一維陣列，可以視為直線方式來存取資料，這對於一般 的問題都可以順利的處理，但是對於比較複雜的問題時，那就必須要 使用二維陣列來處理。否則會增加程式的複雜度。 例如：計算4位同學的5科成績之總分與平均的問題。 2019/5/15

【語法】Dim 陣列名稱 (M,N) AS 資料型態 【說明】M代表列數，N代表行數 【例如】Dim A(3,4) As Integer ‘列註標表示範圍： 0~3 共有4列 ‘行註標表示範圍： 0~4 共有5行 2019/5/15 【存取方法】利用二維陣列中的兩個註標來表示。

3-4 多維陣列的觀念 當陣列的維度是二維以上時，就稱為多維陣列。而其中最常見是三維 陣列，其圖形為三度空間的立體圖形，並且我們可以將三維陣列視為 多個二維陣列的組合。 2019/5/15

【語法】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

【舉例】設計一個某高中，3次月考，全班4位同學的5科目成績時。 利用三維陣列來存取每人學生的成績。 【說明】此例子中Score陣列共有三個註標，故Score陣列是一個三維陣列。宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列(0~3)，5行(0~4)組合而成的整數三維陣列。並且共計有3×4×5＝60元素。 2019/5/15

2019/5/15

3-5 陣列在記憶體中的表示法 陣列是由一連串的記憶體組合而成，其陣列元素之儲存位址計算，如下所示： Ⅰ. 一維陣列 [1]若陣列A有N個元素，其陣列的起始位址為Lo，並且索引值從0開始，d 為元素大小，則A[i]的起始位置為多少？ 以C語言宣告方式：int A[N]; 令：Lo為起始位址 d為元素大小 則A[i]之位置計算=Lo+i*d 2019/5/15

【舉例】假設每一個整數佔用2個byte，若A陣列的起始位址是100開 始，則A[5]的起始位址為多少？ 令：Lo=100 d=2 2019/5/15

[2]若陣列A的索引從L到U，其陣列的起始位址為Lo，d為元素大小，則A[i]的起始位置為多少？ 則A[i]之位置計算=Lo+(i-L)*d 2019/5/15

【舉例】假設每一個整數佔用2個byte，若A[10]起始位址是200開始， 則A[20]的位址為多少？ 令：Lo=200 d=2 2019/5/15

Ⅱ. 二維陣列 宣告方式：A[0…M-1, 0…N-1] 其中：M代表列數(Row)，橫向。 N代表行數(Column)，縱向。 2019/5/15

3-5.1 Row-major(以列為主) 在二維陣列中，如何將二維陣列轉成一維陣列，一般而言，有兩種方 式：「以列（Row）為主」或「以行（Column）為主」。但C語言的 記憶體配置方式都是以列為主。 2019/5/15

一、以列為主(Row-major)方式： 以列為主的二維陣列要轉為一維陣列時，是將二維陣列「由上往下」 一列一列讀入一維陣列，亦即將二維陣列儲存的邏輯位置轉換成實際 電腦中主記憶體的存儲方式。如下圖所示： 2019/5/15

二、以列為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[i*N+j]*d 2019/5/15

3-5.2 Column-major(以行為主) 【老師上課動態展示】檔案在附書光碟中。 2019/5/15

一、以行為主(Column-major)方式： 以行為主的二維陣列要轉為一維陣列時，是將二維陣列「由左往右」一行 一行讀入一維陣列，亦即將二維陣列儲存的邏輯位置轉換成實際電腦中主 記憶體的存儲方式。如下圖所示： 2019/5/15

二、以行為主的儲存公式： 令Lo為起始位址 d為元素大小 則A[i,j]的位置=Lo+[j*M+i]*d 2019/5/15

3-5.3 二維陣列的四個題型 【題型一】給予所有資料 【題型二到四，請參考課本】 2019/5/15

3-5.4 三維陣列之元素儲存 儲存方式只有二種： 以列為主(Row-major)：由左至右 以行為主(Column-major) ：由右至左 2019/5/15

【基本題】 假設三維陣列的元素編號從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

3-5.5 N維陣列之元素儲存 儲存方式只有二種： 以列為主(Row-major)：由左至右 以行為主(Column-major) ：由右至左 2019/5/15

宣告方式：A[1…U1, 1…U2, 1…U3,……, 1…Un] 起始位址：Lo 元素大小：d 以列為主(Row-major)的儲存公式以行為主(Column-major)的儲存公式 2019/5/15

3-6 多項式(polynomials) 多項式(polynomial)的表示式為 其中Ai為非零項的係數，且多項式的每一項均使用三個欄位來表示 (分別為 coef, exp, link) 。其節點的資料結構如下所示： 其中：Coef：表示該變數的係數 Exp：表示該變數的指數 Link：表示指向下一個節點的指標 2019/5/15

多項式的表示方法有兩種： 【方法一】依照指數高低依序儲存係數 【方法二】只儲存非零項次的係數與指數 2019/5/15

【方法一】依照指數高低依序儲存係數 【作法】假設最高指數為n，則準備一個一維陣列A[1..n+2]，其內容如下： 【練習】假設f(x)=7X4+5X2+3X 因為最高指數為4，則準備一個一維陣列A[1..6]，其內容如下： 2019/5/15

(1)只要儲存係數，比較節省儲存指數空間。 (2)適用於零項次較少的多項式。 【缺點】 不適用於零項次極多的多項式，儲存時非常浪費空間。 【優點】 (1)只要儲存係數，比較節省儲存指數空間。 (2)適用於零項次較少的多項式。 【缺點】 不適用於零項次極多的多項式，儲存時非常浪費空間。 Ex: f(X)=5X100+1 則必須要準備一個一維陣列A[1..102]，在實際使用上只用了 3格，因此，會浪費99格。 2019/5/15

【方法二】只儲存非零項次的係數與指數 【作法】假設多項式有K個非零項次，則準備一個一維陣列 A[1..2K+1]，其內容如下： 2019/5/15

因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下： 【練習】假設f(X)=5X100+1 因為有2個非零項次，則準備一個一維陣列A[1..5]，其內容如下： 【優點】適用於零項次極多的多項式。 【缺點】當非零項次極多時，不適用。 2019/5/15

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

3-7.1 矩陣轉置(Matrix Transposition) 假設有一個(m × n)矩陣A，則我們可以將A矩陣轉置為(n × m)的B矩 陣，並且B矩陣的第i列第j行的元素等於A矩陣的第j列第i行的元素， 以數學式來表示為：Bij=Aji。 2019/5/15

【假設】A矩陣與B矩陣的m與n都是從1開始計算，因此，A,B矩陣 的表示如下： 2019/5/15

【演算法】 2019/5/15

【老師上課動態展示】檔案在附書光碟中。 2019/5/15

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

【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩 陣相加等於C矩陣，其表示如下： 2019/5/15

2019/5/15

【演算法】 2019/5/15

【老師上課動態展示】檔案在附書光碟中。 2019/5/15

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

【假設】A、B、C矩陣的m與n都是從1開始計算，因此，A,B兩個矩 陣相乘等於C矩陣，其表示如下： 2019/5/15

2019/5/15

【演算法】 2019/5/15

【老師上課動態展示】檔案在附書光碟中。 2019/5/15

3-7.4 稀疏矩陣(Sparse Matrix) 【定義】 「稀疏矩陣」（Sparse Matrices）屬於矩陣一種非常特殊的 情況，因為矩陣元素大部份元素都沒有使用，元素稀稀落 落，所以稱為稀疏矩陣。 【概念】在M × N 的矩陣中，多數的資料值為０。 2019/5/15

【方法一】直接利用M × N的二維陣列一一對應儲存。 【缺點】 1. 浪費空間：因為多數為０。 2. 浪費時間：許多是不必要的計算。 2019/5/15

【方法二】利用3-tuple結構來儲存非零元素 【作法】假設有一個M*N的稀疏矩陣中共有K個非零元素，則必須要 準備一個二維陣列A[0..K,1..3] 【優點】只儲存非０之資料，因此，可以減少記憶體空間的浪費。 2019/5/15

2019/5/15

【老師上課動態展示】檔案在附書光碟中。 2019/5/15

3-8 特殊矩陣 在前面已經介紹資料結構中，常用的四種矩陣之外，我們在本單元 中，將介紹比較特殊的矩陣，例如：上、下三角矩陣。 2019/5/15

3-8.1 上三角矩陣(Upper-Triangular Matrix) (一)定義： 上三角矩陣是矩陣在對角線以下的元素均為0，即Aij = 0，i > j。 2019/5/15

2019/5/15

2019/5/15

2019/5/15

【老師上課動態展示】檔案在附書光碟中。(以列為主) 2019/5/15

3-8.2 下三角矩陣(Lower-Triangular Matrix) (一)定義：下三角矩陣是矩陣在對角線以上的元素均為0，即Aij = 0，i < j。 2019/5/15

2019/5/15

2019/5/15

2019/5/15

【老師上課動態展示】檔案在附書光碟中。(以列為主) 2019/5/15