Chapter 2

陣列結構

資料結構導論 - C語言實作 1
兩個重點
⚫陣列 (特別是多維度) 在實體記憶
(memory) 空間 (線性，i.e.，一維) 中如
何擺置？
⚫如何安排擺放某些特別的多維陣列 (e.g.,
sparse matrix)，以節省記憶 (memory)
空間。

資料結構導論 - C語言實作 2
回顧 (程式執行的一些觀念)
⚫程式編譯好 (e.g., [Link]) 存在 Disk
⚫點擊 [Link] (檔案總管) 即可執行程式
◼[Link] 由 disk copy 至 memory
◼CPU 由 memory 讀入程式內指令執行

From: [Link]
A benchmark test (throughput)

[Link] 4
Latency is another issue …

[Link] 5
回顧(程式執行的一些觀念)：續上

From: [Link]
記憶體管理 Memory
Management

記憶體管理：電腦提供(或安排)記憶體給程式
與資料使用

2024/10/17 7
記憶體管理與旅館客房管理之類比
⚫想像一間很大、有很多客房的旅館
◼旅館房間管理=電腦記憶體管理
⚫住宿旅館的客人分兩類
◼事先訂房入住  靜態
◼住宿當天在櫃台詢問、並在有房位情況下入
住  動態
⚫電腦記憶體管理也是：靜態(事先)宣告、
動態取得

2024/10/17 8
靜態記憶體分配 = 事先訂房入住
• 在旅館裡，客人事先訂房，旅館提前為這位客人保留房間。
這意味著即使旅館還沒準備好，房間已經是這位客人的了，
並且無法被其他人使用。
• 類似地，靜態記憶體分配是指在程式編譯期間就已經確定了
記憶體的大小和位置。這種記憶體會自動分配並在程式運行
時被保留。例如，當你在 C 語言中聲明一個陣列或變數時，
這些變數的記憶體位置在編譯時就被確定了
動態記憶體分配 = 當天詢問入住
• 有些客人並沒有提前訂房，而是當天來到旅館，根據當時
的房間情況，若有空房則分配給他們，若沒有空房則無法
入住。
• 這與 動態記憶體分配類似，記憶體在程式執行期間按需求
分配。只有在程式運行中需要的時候，才會向系統請求記
憶體，並且分配的記憶體大小可以根據需求來調整。C 語
言中常用的動態記憶體管理函數是 malloc() 和 free()
資料結構導論 - C語言實作 9
靜態記憶體管理
#include <stdio.h>
int main()
{
int i;
long j;
事先宣告(系統保留)
= 事先預約 (旅館預留房間)
…
}
本章討論的陣列(Array)屬事先宣告，即
所謂靜態陣列(Static Array) 亦可動態取得
2024/10/17 10
動態記憶體管理

• 需要記憶體空間時跟系統要、系統
有才給 (動態記憶體管理)
• 就像：住宿當天在櫃台詢問、並在
有房位情況下才給入住

 下個主題 (Pointer)

2024/10/17 11
2.1 前言
⚫「陣列」(Array)結構具有以下重要特徵：
◼一個陣列可以包含許多個陣列元素，陣列元
素之個數又稱為陣列之大小。
◼同一個陣列裡的元素都具備相同的資料型態
(Data Type)。
◼為方便資料的存取，可將陣列設計成一維
(Dimension)、二維、三維，...，甚至更多維
的陣列。

資料結構導論 - C語言實作 12
2.1 前言
◼宣告一個陣列時，作業系統會在記憶體空間
指定一個起始位置給該陣列，並且根據陣列
的資料型態和大小來配予一組連續的記憶體
位置。
◼陣列元素在記憶體中的位置是連續且相鄰的，
因此只要透過一套簡單的陣列元素位址計算
公式，便能得知某陣列元素所在之記憶體位
置。
◼ 經由陣列索引(Index)，可以迅速且直接地
存取陣列中的元素資料。

資料結構導論 - C語言實作 13
2.2 宣告陣列
⚫宣告陣列時須定義下列幾項屬性：
◼陣列的資料型態。
◼陣列的名稱。
◼陣列的維度，即中括號([ ])的個數。
◼陣列每一維度的元素個數，亦即陣列大小。
◼陣列元素的初值，此項可以省略。

資料結構導論 - C語言實作 14
2.2 宣告陣列
⚫以C語言為例，宣告陣列的語法如下：

資料結構導論 - C語言實作 15
2.2.1 一維陣列
【例1】宣告一個可以用來存放6次考試成
績的整數陣列。

int grades[6] = {83, 75, 92, 74, 88, 93};

資料結構導論 - C語言實作 16
亦可以垂直圖示之…

From: [Link]
2.2.2 二維陣列
【例2】宣告二維陣列。

資料結構導論 - C語言實作 18
2.2.2 二維陣列
【例3】宣告grades[50][6]為一個可以用來
儲存50位同學之6次資料結構考試
成績之二維陣列。
int grades[50][6] ;

資料結構導論 - C語言實作 19
2.3 陣列的表示法
⚫一維陣列的表示法
⚫二維陣列的表示法
⚫三維陣列的表示法
⚫多維度陣列的表示法
⚫上三角矩陣
⚫下三角矩陣
⚫我們將「陣列」與「矩陣」視為同義詞

資料結構導論 - C語言實作 20
2.3.1 一維陣列的表示法
⚫A[n] = {A[0]，A[1]，…，A[n-1]}
⚫假設
◼一維陣列A在記憶體的起始位置為α。
◼每個陣列元素所需的儲存空間是z個位元組
(Byte) 。
◼陣列元素A[i]的記憶體位址為Loc(A[i]) 。
⚫則：
Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移
= α + i  z。

資料結構導論 - C語言實作 21
資料結構導論 - C語言實作 22
資料結構導論 - C語言實作 23
2.3.1 一維陣列的表示法
【例1】設陣列A是一個大小為10的一維陣
列，且陣列A在記憶體之起始位置
為1000，且每個元素都需要2個位
元組的儲存空間。則 A[7]的記憶體
位置為何？

【解答】
Loc(A[7]) = A的起始位址 + A[7]相對於陣列起始位置之位移
= 1000 + 7  2
= 1014。

資料結構導論 - C語言實作 24
2.3.1 一維陣列的表示法
【例2】設d[100] 為一個實數陣列，每一個
元素佔4個位元組。若d[10]的位址
為2000，則d[88]的位址為何？

【解答】
Loc(d[88]) = d[10]的位址 + d[88]相對於d[10]之位移
= 2000 + (88-10)  4
= 2312。

資料結構導論 - C語言實作 25
2.3.1 一維陣列的表示法
⚫A[f:t] = {A[f] ，A[f-1] ，... ， A[0] ，
A[1] ， ... ，A[t] } 。
⚫假設
◼一維陣列A[f]在記憶體的起始位置為α。
◼每個陣列元素所需的儲存空間是z個位元組
(Byte) 。
◼陣列元素A[i]的記憶體位址為Loc(A[i])。
⚫則：
Loc(A[i]) = A的起始位址 + A[i]相對於陣列起始位置之位移
= α + (i-f)  z。
資料結構導論 - C語言實作 26
2.3.1 一維陣列的表示法
【例3】設A[-15:25]在記憶體的起始位置為
123，且每一元素佔4個位元組，則
A[3]的位址為何？

【解答】
Loc(A[3]) = A[-15:25]的起始位址 + A[3]相對於A[-15:25]之位移
= 123 + (3-(-15))  4
= 195。

資料結構導論 - C語言實作 27
2.3.2 二維陣列的表示法
⚫B[m][n] = {B[0][0]，B[0][1]，…，
B[m-1][n-1] } 。
⚫共計有mn 個元素。

資料結構導論 - C語言實作 28
2.3.2 二維陣列的表示法
⚫將二維的陣列元素轉換成一維排列的方
式有下列兩種：
◼以列為主(Row Major) 。
◼以行為主(Column Major) 。

資料結構導論 - C語言實作 29
2.3.2 二維陣列的表示法
⚫以列為主(Row Major)的表示法：
⚫假設
◼假設二維陣列B在記憶體的起始位置為α 。
◼陣列之個別元素所需的記憶體空間大小為z 。
◼陣列元素B[i][j]的記憶體位址為Loc(B[i][j]) 。
⚫則：
LocRM(B[i][j]) = B的起始位址 + B[i][j]相對於陣列起始位置之位移
= α + (i  n + j)  z 。

資料結構導論 - C語言實作 30
資料結構導論 - C語言實作 31
資料結構導論 - C語言實作 32
二維陣列 (Row Major)

看起來是二維，實際
儲存在記憶體時是線
性的 (linear)，如下：

From: [Link]

資料結構導論 - C語言實作 33
2.3.2 二維陣列的表示法
⚫以行為主(Column Major)的表示法：
⚫假設
◼假設二維陣列B在記憶體的起始位置為α 。
◼陣列之個別元素所需的記憶體空間大小為z 。
◼陣列元素B[i][j]的記憶體位址為Loc(B[i][j]) 。
⚫則：
LocCM(B[i][j]) = B的起始位址 + B[i][j]相對於陣列起始位置之位移
= α + (j  m + i)  z 。

資料結構導論 - C語言實作 34
資料結構導論 - C語言實作 35
資料結構導論 - C語言實作 36
二維陣列 (Column Major)

看起來是二維，實際
儲存在記憶體時是線
性的 (linear)，如下：

From: [Link]

資料結構導論 - C語言實作 37
2.3.2 二維陣列的表示法
【例1】已知A[1][2]之記憶體位置為22，且
A[2][4]和A[4][2] 之記憶體位置分別為
30和40，則A[5][5]之位置為何？

【解答】
因為A[2][4]的記憶體位置30小於A[4][2] 的
記憶體位置40，可見該陣列是採「以列為
主」排列。因此：
LocRM(A[i][j]) = A的起始位址 + A[i][j]相對於陣列起始位置之位移
= α + (i  n + j)  z。

資料結構導論 - C語言實作 38
2.3.2 二維陣列的表示法
LocRM(A[2][4]) = A[1][2]的位址 + A[2][4]相對於A[1][2]之位移
= 22 + ((2-1)  n + (4-2))  z
= 22 + (n + 2)  z = 30。
所以，nz + 2z = 8 …………(1)

LocRM(A[4][2]) = A[1][2]的位址 + A[4][2]相對於A[1][2]之位移

= 22 + ((4-1)  n + (2-2))  z
= 22 + (3n + 0)  z = 40。

所以，3nz = 18 ，nz = 6 …………(2) ，將(2)代入(1)得到

6 + 2z = 8，z = 1，代入(2) 得到 n = 6 ，因此

資料結構導論 - C語言實作 39
2.3.2 二維陣列的表示法
LocRM(A[5][5]) = A[1][2]的位址 + A[5][5]相對於A[1][2]之位移
= 22 + ((5-1)  n + (5-2))  z
= 22 + (4  6 + 3)  1
= 49。

資料結構導論 - C語言實作 40
2.3.2 二維陣列的表示法
【例2】設A[f1:t1][f2:t2] 為一個二維陣列宣
告，其記憶體起始位置為α，每個元
素所佔的記憶體空間為z。則陣列元
素A[i][j]之位置為何？
【解答】
◼ 已知A[f1][f2]在記憶體之起始位置為α，
且每個元素所佔的記憶體空間為
z。
◼ 設二維陣列A共有m列n行，則
m = t1-f1+1，
n = t2-f2+1。

資料結構導論 - C語言實作 41
2.3.2 二維陣列的表示法
◼以列為主
LocRM(A[i][j]) = A[f1][f2]的起始位址 +
A[i][j]相對於A[f1][f2]之位移
= α + ((i-f1)  n + (j-f2))  z
◼以行為主
LocCM(A[i][j]) = A[f1][f2]的起始位址 +
A[i][j]相對於A[f1][f2]之位移
= α + ((j-f2)  m + (i-f1))  z

資料結構導論 - C語言實作 42
Column Major?

資料結構導論 - C語言實作 43
2.3.3 三維陣列的表示法
int cubic[3][2][3] = { {1,2,3,4,5,6},
{7,8,9,1,2,3},
{4,5,6,7,8,9}};
平面 列 行

⚫ 它包括3個平面，每個平面有2列及3行。

資料結構導論 - C語言實作 44
2.3.3 三維陣列的表示法
⚫假設我們宣告了一個三維陣列C[l][m][n]
◼ l 代表第一個維度的大小。
◼ m 代表第二個維度的大小。
◼ n 代表第三個維度的大小。
◼共計有 lmn 個陣列元素。
⚫假設
◼C[0][0][0]在記憶體中的起始位置為α。
◼陣列之個別元素所需的記憶體空間大小為z 。

資料結構導論 - C語言實作 45
2.3.3 三維陣列的表示法
⚫以列為主(Row Major)的表示法：
◼共計有 l 個平面，每個平面有 m 列與 n 行。
LocRM(C[i][j][k]) = α + (imn + jn + k)  z

⚫以行為主(Column Major)的表示法：
◼共計有 n 個平面，每個平面有 l 列與 m 行。
LocCM(C[i][j][k]) = α + (klm + jl + i)  z

資料結構導論 - C語言實作 46
2.3.4 多維度陣列的表示法
⚫假設
◼ n 維度陣列D[s1][s2][s3]…[sn]在記憶體中的起
始位置為α。
◼其中s1，s2，…，sn分別為D陣列的第1維、
第2維，…，第n維的元素個數。
◼每個陣列元素所須要的記憶體儲存空間為z。

資料結構導論 - C語言實作 47
2.3.4 多維度陣列的表示法
⚫ 以列為主(Row Major)的表示法：
LocRM(D[i1][i2]…[in]) = α + (i1s2s3…sn-1sn
+ i2s3s4…sn-1sn
+ i3s4s5…sn-1sn
+…
+ in-3sn-2sn-1sn
+ in-2sn-1sn
+ in-1sn
+ in)  z 。

資料結構導論 - C語言實作 48
2.3.4 多維度陣列的表示法
⚫以行為主(Column Major)的表示法：
LocCM(D[i1][i2]…[in]) = α + (ins1s2…sn-2sn-1
+ in-1s1s2…sn-3sn-2
+ in-2s1s2…sn-4sn-3
+…
+ i3s1s2
+ i2s1
+ i1)  z 。

資料結構導論 - C語言實作 49
2.3.5 對角線矩陣的表示法
⚫對角線矩陣(Diagonal Matrix)
◼是一個「方陣」 。
◼除了對角線的元素值可能不為0外，其餘元
素值均為0。
◼亦即，矩陣元素vi,j = 0，i ≠ j。

資料結構導論 - C語言實作 50
2.3.5 對角線矩陣的表示法
⚫對角線矩陣(Diagonal Matrix)
◼ 對角線矩陣DM[m][m]共有m個非0元素。
◼ 我們可以直接用一個一維陣列X[m]來表示對
角線矩陣。
◼ 亦即X[i]= DM[i][i]。

資料結構導論 - C語言實作 51
2.3.6 下三角矩陣的表示法
⚫下三角矩陣(Lower Triangular Matrix)
◼它是一個「方陣」。
◼對角線以上(不含對角線)的元素值均為 0。

資料結構導論 - C語言實作 52
2.3.6 下三角矩陣的表示法
⚫假設
◼下三角矩陣式的陣列X在記憶體之起始位置
為α。
◼且每個陣列元素所需的記憶體空間為z。
⚫採「以列為主」(row major) 的儲存策略，
則

LocRM(Xi,j)=  + ((i(i+1))/2 + j)  z 。

資料結構導論 - C語言實作 53
 1+2+3+…+i

資料結構導論 - C語言實作 54
2.3.6 下三角矩陣的表示法
【例1】設X[n][n]為一個下三角矩陣，若要
用一個一維陣列Y[m]來表示X，則
m的最小值應該宣告為何？

【解答】
m = 1+2+3+...+n
= n(n+1)/2。

資料結構導論 - C語言實作 55
2.3.7 上三角矩陣的表示法
⚫上三角矩陣(Upper Triangular Matrix)
◼它是一個「方陣」。
◼對角線以下 (不含對角線)的元素值均為 0。

資料結構導論 - C語言實作 56
2.3.7 上三角矩陣的表示法
⚫假設
◼下三角矩陣式的陣列X在記憶體之起始位置
為α。
◼且每個陣列元素所需的記憶體空間為z。
⚫採「以行為主」(column-major) 的儲存
策略，則

LocCM(Xi,j)=  + ((j(j+1))/2 + i)  z 。

資料結構導論 - C語言實作 57
資料結構導論 - C語言實作 58
2.4 一維陣列的應用
⚫2.4.1 計數器(Counter)
⚫2.4.2 暫存(Temporary Store)
⚫2.4.3 取代(Substitution)
⚫2.4.4 索引(Indexing)
⚫2.4.5 搜尋(Searching)
⚫2.4.6 排序(Sorting)

資料結構導論 - C語言實作 59
2.4.1 計數器(Counter)
⚫ i = i + 1; (或 i++; ) 。

⚫ int count[n]; //宣告

...
count[i] = count[i] + 1; //計數器 + 1
或
count[i]++ ; //計數器 + 1

資料結構導論 - C語言實作 60
2.4.2 暫存(Temporary Store)
⚫「質數」：大於1的數，除了1與本身以
外沒有任何一個數能夠整除它時，該數
稱為質數。
◼ 2是最小的質數。
◼ 3、5、7均是質數。
◼ 4、6不是質數，因為4可以被2整除，6可以
被2、3整除 。

資料結構導論 - C語言實作 61
2.4.2 暫存(Temporary Store)
⚫如何找出小於等於100的所有質數呢？
⚫第一種方法：
◼根據質數的定義，判斷5是否為質數時，須
將5除以2、3、4，只要能被其中一個數整除，
那麼5就非質數，否則5就是質數。
◼依此類推，判斷x是否為質數時，須將x除以
2、3、4...、x-1，只要能被其中一個數整除，
那麼x就非質數，否則x就是質數。

資料結構導論 - C語言實作 62
2.4.2 暫存(Temporary Store)
⚫第二種方法：
◼將第1個找到的質數暫存於prime[0]，將第2
個找到的質數暫存於prime[1]，將第3個找到
的質數暫存於prime[2]，依此類推。
◼要判斷一個整數x是否為質數時，我們只須
取出prime陣列裡已經找到的質數來當做除
數，將x除以這些質數，如果都不能被這些
質數整除，即可斷定x為質數。
◼因此，要判斷6是否為質數時，只須分別判
斷6是否能被2、3、5整除即可，只要能被其
中一個質數整除，6就非質數。因6能被2整
除，非質數，不須再判斷能否被3、5整除了。
資料結構導論 - C語言實作 63
2.4.3 取代(Substitution)
⚫要印出

⚫則可用陣列來儲存花色和點數以取代之

資料結構導論 - C語言實作 64
2.4.4 索引(Indexing)
⚫「索引」：利用某一個陣列的元素值來
當做另一個陣列的索引值。
⚫尋找出眾數及其出現頻率
◼一維陣列x[15]是一個含有15個元素的整數
陣列，且陣列中的元素值均介於0與5之間。
我們稱陣列x中出現次數最多的數為「眾
數」。
◼宣告一個整數陣列count[6]，然後用count[i]
來記錄x陣列中 i 的出現次數。
◼亦即 count[x[i]] = count[x[i]]++ ;
資料結構導論 - C語言實作 65
2.4.5 搜尋(Searching)
⚫搜尋(Search)：從一群資料中找出滿足特
定條件的資料之動作稱之。
⚫搜尋條件通常有：
◼大於、等於、小於、大於或等於、不等於、
小於或等於等多種組合。

資料結構導論 - C語言實作 66
[Link] 循序搜尋法(Sequential Search)
⚫循序搜尋法(Sequential Search)：就是從
頭到尾一筆一筆地搜尋、比較。

【例1】找出鍵值大於70的資料？
◼ 必須從d[0]開始逐筆加以比對，直到比完d[7]為止
(共計比較8次)
◼ 結果找到d[2]、d[4]、d[5]、d[7]等4筆資料

資料結構導論 - C語言實作 67
[Link] 二元搜尋法(Binary Search)
⚫二元搜尋法的特徵如下：
◼資料須事先經過排序。
◼每次都從可能有符合條件的一組資料中，拿
第中間筆資料(假設d[i])出來跟鍵值k相比。
◼每次比較完之後，大約可以捨去一半的資料，
所以搜尋的速度很快。

資料結構導論 - C語言實作 68
[Link] 二元搜尋法(Binary Search)
【例2】二元搜尋法。
◼ 找出鍵值等於120的資料？

資料結構導論 - C語言實作 69
[Link] 二元搜尋法(Binary Search)
【例2】二元搜尋法。
◼找出鍵值大於70的資料？

資料結構導論 - C語言實作 70
2.4.6 排序(Sorting)
⚫排序(SORT)：乃將原始資料依照某個特
定的次序加以重新排列。
⚫排序時須指定：
◼用哪一個資料項來排序？
被用來排序的資料項又稱為「鍵(Key)」
◼排序的順序
✓遞增：即由小到大。
✓遞減：即由大到小。

資料結構導論 - C語言實作 71
[Link] 氣泡浮昇排序法(Bubble Sort)
⚫假設我們已經宣告了一個整數陣列d[n]，
用來存放編號為0、1、2、...、n-1的n筆
資料。且
d[0] = v0、
d[1] = v1、
d[2] = v2、...
d[n-2] = vn-2、
d[n-1] = vn-1。

資料結構導論 - C語言實作 72
[Link] 氣泡浮昇排序法(Bubble Sort)
⚫採用氣泡浮昇排序法的將一組資料依
「鍵值遞增」排序之步驟說明如下：
◼第1回合：
✓從第0筆資料開始一直到第n-1筆資料，持續比較
相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者
交換位置，亦即須將vi 儲存到d[i+1]，vi+1 儲存到
d[i]。換言之，必須保持小的在前，大的在後之
順序。
✓在第1回合處理完後，陣列中最大的數值已經被
存放到d[n-1]的位置。

資料結構導論 - C語言實作 73
[Link] 氣泡浮昇排序法(Bubble Sort)
◼第2回合：
✓從第0筆資料開始一直到第n-2筆資料，持續比較
相鄰兩筆資料之大小，若vi大於vi+1，則須將兩者
交換位置，亦即須將vi 儲存到d[i+1]，vi+1 儲存到
d[i]。
✓在第2回合處理完後，陣列中第2大數的值已經
被存放到d[n-2]的位置。
◼重複執行上述步驟，共計(n-1)回合，即可將
陣列資料排列成由小到大的遞增順序。

資料結構導論 - C語言實作 74
[Link] 氣泡浮昇排序法(Bubble Sort)
【例2】氣泡浮昇排序法。

資料結構導論 - C語言實作 75
[Link] 氣泡浮昇排序法(Bubble Sort)
【例2】氣泡浮昇排序法。

資料結構導論 - C語言實作 76
2.5 二維陣列的應用
⚫2.5.1 轉置矩陣(Transpose Matrix)
⚫2.5.2 對稱矩陣(Symmetric Matrix)
⚫2.5.3 反射矩陣(Reflection Matrix)
⚫2.5.4 矩陣相加(Matrix Addition)
⚫2.5.5 矩陣相減(Matrix Subtraction)
⚫2.5.6 矩陣乘積(Matrix Multiplication)
⚫2.5.7 稀疏矩陣(Sparse Matrix)

資料結構導論 - C語言實作 77
2.5.1 轉置矩陣(Transpose Matrix)
⚫設M是一個mn矩陣，而TM為其轉置矩
陣，則：
◼ TM為一個nm矩陣。
◼ M的第0列元素成為TM的第0行元素，
M的第1列元素成為TM的第1行元素，…，
M的第m-1列元素成為TM的第m-1行元素。
◼ 亦即 TM[j][i] = M[i][j]。

資料結構導論 - C語言實作 78
2.5.1 轉置矩陣(Transpose Matrix)
【例1】轉置矩陣。

資料結構導論 - C語言實作 79
2.5.2 對稱矩陣(Symmetric Matrix)
⚫ 對稱矩陣為一方陣，且元素值vij = vji。

資料結構導論 - C語言實作 80
2.5.3 反射矩陣(Reflection Matrix)
⚫反射矩陣(RMmxn)是將原始矩陣(Mmxn)進
行水平方向的鏡射。

資料結構導論 - C語言實作 81
2.5.4 矩陣相加(Matrix Addition)
⚫cij=aij+bij。

【例1】矩陣相加。

資料結構導論 - C語言實作 82
2.5.5 矩陣相減(Matrix Subtraction)
⚫cij=aij-bij。

【例1】矩陣相減。

資料結構導論 - C語言實作 83
2.5.6 矩陣乘積(Matrix Multiplication)

資料結構導論 - C語言實作 84
2.5.6 矩陣乘積(Matrix Multiplication)
【例1】矩陣乘積。

資料結構導論 - C語言實作 85
2.5.7 稀疏矩陣(Sparse Matrix)
⚫一個矩陣中，若大多數的元素值均為0，
則稱該矩陣為「稀疏矩陣」。
⚫這裡所謂的元素值為0在應用上包括幾種
涵義：
◼真的為0。
◼為虛值(Null Value)
，亦即沒有資料值

資料結構導論 - C語言實作 86
2.5.7 稀疏矩陣(Sparse Matrix)
【例1】稀疏矩陣的表示法。

資料結構導論 - C語言實作 87
2.5.7 稀疏矩陣(Sparse Matrix)
【例2】試設計一個用以表示三維稀疏矩陣
的表示法。
【解答】設三維稀疏矩陣SMmxnxo各維之大小
分別為m、n、o，且稀疏矩陣中非0元素
共計p個。

資料結構導論 - C語言實作 88
兩個重點 … (again)
⚫陣列 (特別是多維度) 在實體記憶
(memory) 空間 (線性，i.e.，一維) 中如
何擺置？
⚫如何安排擺放某些特別的多維陣列 (e.g.,
sparse matrix)，以節省記憶 (memory)
空間。

資料結構導論 - C語言實作 89