課程名稱：計算機概論 授課老師：李春雄 博士

Presentation on theme: "課程名稱：計算機概論 授課老師：李春雄 博士"— Presentation transcript:

1 課程名稱：計算機概論 授課老師：李春雄 博士
第 五 章 資料結構 課程名稱：計算機概論 授課老師：李春雄 博士

2 本章學習目標 1.讓讀者了解何謂資料結構及線性結構中的陣列、 串列、堆疊及佇列結構。 2.讓讀者了解日常生活中常見的樹狀結構及圖形
結構的例子。

3 本章內容 5-1 何謂資料結構？ 5-2 陣列(Array) 5-3 堆疊(Stack) 5-4 遞迴(Recursive)
5-5 佇列(Queue) 5-6 串列(List) 5-7 樹狀結構(Tree) 5-8 圖形結構(Graph)

4 5-1 何謂資料結構？ 【定義】 資料結構(Data Structure)主要是探討如何將資料更有組織地存放到電腦記憶體中，以提昇程式之執行效率的一門學問。 【程式、資料結構與演算法三者的關係】 程式=資料結構(Data Structure)+演算法(Algorithms) 其中「資料結構」：是指資料在記憶體中的儲存方式。 「演算法」：是指則是如何將資料作有效率的處理過程。 因此，當我們在撰寫程式時，只有選擇適當的【資料結構】，才能夠設計出最有效率的【演算法】，進而轉換成為有效率的【程式】。

5 「資料結構」的種類 基本上，資料結構包含有： 1.遞迴(Recursive) 2.陣列(Array) 3.堆疊(Stack)
4.佇列(Queue) 5.串列(List) 6.樹狀(Tree) 7.圖形(Graph) 8.排序(Sort) 9.搜尋(Search)

6 1.遞迴(Recursive) 【例如】老鼠走迷宮的問題就是屬於「遞迴」結構。 【實務上的應用】 1.計算n階乘(n!) 2.計算費氏數列
3.追蹤河內塔的圓盤搬移過程 4.求最大公因數 5.計算二項係數

7 2.陣列(Array) 【例如】教室座位排列方式就是屬於「陣列」結構。 【實務上的應用】 1. 一維陣列：例如某一位同學多科成績的計算。
2. 二維陣列：例如全班同學之多科成績的計算。 3. 多維陣列：例如三次月考之全班同學之多科成績的計算。 4. 矩陣的各種運算<轉置、相加、相乘及稀疏矩陣>

8 3.堆疊(Stack) 【例如】碗盤的疊法、小朋友排積木、書本裝箱或坐電梯等都具有後進先出的特性就是屬於「堆疊」結構。 【實務上的應用】
1.副程式呼叫與返回 2.遞迴程式呼叫與返回 3.運算式之轉換與求值 4.中斷處理 5.二元樹追蹤 6.巨集呼叫 7.多元處理 8.圖形的深度搜尋 9.資料反序輸出(例如：abccba) 10.自助餐廳取餐盤的行為。

9 4.佇列(Queue) 【例如】排隊買票看球賽，先到先買的方式就是所謂的「佇列」結構。 【實務上的應用】 1.作業系統的工作排程
2.計算機的模擬程式 3. 磁碟管理的輸出入(input/output)排序 4.I/O的緩衝區(Buffer)上 5.優先佇列 6.圖形的BFS廣度追蹤

10 5.串列(List) 【例如】高鐵火車的車箱串接方式就是屬於「串列」結構。 【實務上的應用】 1.動態資料的表示法
2.實作「堆疊」與「佇列」

11 6.樹狀(Tree) 【例如】如果球賽的賽程方式是採用淘汰制，就是一種「樹狀」結構。 【實務上的應用】 1.家族的族譜 2.比賽的賽程
3.尋寶圖遊戲 4.公司的組織圖 5.計算機組織之間的檔案系統

12 7.圖形(Graph) 【例如】當看完球賽要回家的行駛路線圖，可視為所謂的「圖形」結構。 【實務上的應用】 1.自動導航系統
2.Google Map

13 8.排序(Sort) 【例如】球賽成績的結果之排名方式就是屬於「排序」結構。 【實務上的應用】 1.考試成績的排名次 2.統計資料的排序

14 9.搜尋(Search) 【例如】球賽比賽之前找尋某一隊的賽程就是屬於「搜尋」結構。 【實務上的應用】 1.Google的搜尋引擎
2.奇摩的關鍵字查詢

15 5-2 陣列(Array) 【定義】是指一群具有「相同名稱」及「資料型態」的變數之集合。 【特性】1.佔用連續記憶體空間。
2.用來表示有序串列之一種方式。 3.各元素的資料型態皆相同。 4.支援隨機存取與循序存取。 5.插入或刪除元素時較為麻煩，因為須挪移其他元素。 【示意圖】

16 5-2.1 一維陣列 【定義】 宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。 【例如】
一維陣列 【定義】 宣告陣列時，其括弧內的「註標」個數，只有一個時稱為「一維陣列」。 【例如】 假設我們需要5個整數變數來存放資料時，那就必須要宣告一個A陣列為整數型態，其註標是按照順序排列從0~4共有5項，其含義如下： Dim A(4) As Integer 【說明】 (1) A陣列表示內共有5個陣列元素，也就是有5個變數，分別為A(0)、A(1)、A(2)、A(3)、A(4)。 (2)每一個陣列元素可以存放一筆資料。 (3)當我們要連續輸入或輸出資料時，只須要使用「陣列」資料結構 加上「迴圈」演算法 就可以快速且有彈性處理資料了。

17 【優點】 1. 利用註標（Index）可以快速的存取資料。 2. 一次可以處理大批的資料。 (1)利用註標（Index）可以快速的輸入資料。
3. 較容易表達資料處理的技巧。

18 【缺點】 1.在新增或刪除資料時，比較麻煩。 2.當記憶體配置在宣告陣列時就固定大小，缺乏彈性。

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

20 5-2.2 二維陣列(續…) 【定義】 宣告陣列時，其括弧內的「註標」個數，有兩個時稱為「二維陣列」。
二維陣列(續…) 【定義】 宣告陣列時，其括弧內的「註標」個數，有兩個時稱為「二維陣列」。 【語法】Dim 陣列名稱 (M,N) AS 資料型態 【說明】M代表列數，N代表行數 【存取方法】利用二維陣列中的兩個註標來表示。 【示意圖】

21 【例如】Dim A(3,4) As Integer ' 列註標表示範圍： 0~3 共有4列 ' 行註標表示範圍： 0~4 共有5行
【圖解說明】 【說明】 假設我們現在想要計算4位同學的5科成績之總分與平均時，如果使用一維陣列恐怕不容易處理，因此，如果使用二維陣列就可以利用「列註標」來表示 4位同學，及利用「行註標」來表示5科成績，所以，就可以非常容易地計算出總分與平均了。

22 5-2.3 多維陣列 【定義】 宣告陣列時，其括弧內的「註標」個數，是二個以上時，就稱為「多維陣列」。 【三維陣列的思維】
我們可以將「三維陣列」視為「多個」二維陣列的組合。其圖形為三度空間的立體圖形。 【示意圖】

23 【語法】Dim 陣列名稱 (L,M,N) AS 資料型態
【例如】Dim Score (2,3,4) As Integer ' 二維陣列的個數： 0~2 共有3個二維陣列 ' 列註標表示範圍： 0~3 共有4列 ' 行註標表示範圍： 0~4 共有5行 【圖解】

24 【說明】 此例子中Score陣列共有三個註標，故Score陣列是一個三維陣列。 宣告Score是由3個(0~2)二維陣列，每個二維陣列包含4列(0~3)， 5行(0~4)組合而成的整數三維陣列。並且共計有3×4×5＝60元素。

25 5-3 堆疊(Stack) 【引言】 在我們日常生活中，有一些是堆疊的例子，例如堆盤子、書本裝箱…等，都是一層一層的疊上去，如果想要取出箱子中某一本書，也只能從最上面開始取出。亦即資料處理的方式都是在同一邊進行，也就是由相同的一端來進行插入與刪除動作。 【定義】是指一群相同性質元素所組合，並且它具有後進先出(Last In First Out ；LIFO)的特性。 【示意圖 】

26 【兩個操作運算】 1. Push(加入)：將一個項目放入堆疊的頂端。 2. Pop(取出)：從堆疊頂端拿走一個項目。 【圖解】

27 一、Push演算法

28 二、Pop演算法

29 5-4 遞迴(Recursive) 【定義】是指函數本身又可以呼叫自己的副程式。 【舉例】
例如在下圖中，A函數執行到某一段敘述時，又可以呼叫自己。但是，它會有終止條件，亦即符合某一終止條件就會停止。 【說明】 雖然「遞迴」函數可以使得程式變得比較簡潔，但是，要非常謹慎小心使用，否則很容易產生無窮迴圈或無法預期的錯誤。

30 在目前的程式語言中，並非每一種程式語言都具有遞迴呼叫的功能。
【例如】 (1)不具遞迴呼叫的程式語言：BASIC, FORTRAN,COBOL等。 (2)具遞迴呼叫的程式語言：C, C++, PASCAL等。 【特色】 1.函數本身可以呼叫自己 2.必須加入終止條件，以免產生無窮的呼叫自己 3.增加可讀性，但是執行效率一般會比較差 4.某些程式語言沒有支援遞迴的程式撰寫 5.在某些特殊的狀況下可以大幅的降低程式撰寫的困難

31 5-4.1 遞迴函數 【定義】 撰寫程式時，將程式模組化為一支獨立的函數，如果該函數可以反覆地自己呼叫自己，我們稱這個函數為遞迴函數。
【作法】 1. 由上而下將一個大問題切割成若干小問題。 2.小問題的資料量是大問題的縮小版。 【最典型的例子】 在遞迴函數中，最典型的例子就是計算n階層的程式。 一、數學上：n階層的概念：

32 【說明】 在撰寫一個n階層的遞迴函數程式時，則該函數將具備兩個主要特徵： 1.該遞迴函數可以自己反覆地呼叫自己 (1)第一次呼叫時的參數為n (2)第二次呼叫時的參數為n-1 (3)第三次呼叫時的參數為n-2 (4)參數的值會逐次遞減。 2.當參數值等於1時，必須停止遞迴呼叫。

33 二、演算法上：n階層的概念：

34 5-4.2 遞迴函數種類 一般而言，遞迴函數可以分為兩種： 一、直接遞迴 【定義】函數自己直接呼叫自己。 【圖解】
【說明】在上圖中，A函數執行到某一段敘述時，又可以呼叫自己。  二、間接遞迴 【定義】是指兩個以上函數，彼此呼叫對方，形成迴路。 【說明】在A遞迴函數內呼叫B遞迴函數，並且在B遞迴函數內呼叫A遞迴函數。

35 5-4.3 遞迴的應用 【範例一】計算n階乘 遞迴在實務上的應用非常的廣。 【例如】計算n階乘、費氏數列、河內塔的圓盤搬移過程等等。
【定義】n!= n×(n-1)×(n-2)×(n-3)×…×1 【說明】利用遞迴方式來撰寫n階乘(n!)的程式。 【假設】階乘的公式如下：

36 【演算法】 基本上，一個合乎演算法的遞迴函數必須要有下列條件： 1.遞迴函數必須要設定「初值」與「終值」。
例如：行號04的if(n == 1)就是「終值」設定。 2.遞迴函數必須要有更新值。 例如：以上例子中，行號06中的fact (n - 1)。變數n的值每次都會遞減。不可以是常數。 3.遞迴函數必須要自己呼叫自己。 例如：以上例子中，行號06的遞迴函式名稱(fact)必須要與行號01的函式呼叫相同。

37 【圖解說明】

38 【範例二】費氏數列 【定義】是指某一數列的第零項為0，第1項為1，其他每一個數列中 項目的值是由本身前面兩項的值之和。
【假設】費氏數列的公式如下： 【說明】某一數為其前二個數的和。 【舉例】 假設我們現在想求出「費氏數列」第八項的費氏數列值。因此，我們就必須要先從第零項及第1項開始來推算，也就是第零項為0，第1項為1，開始計算。 【圖解說明】

39 費氏數之「數學式」與「演算法」

40 【範例三】河內塔問題 【定義】 是指有A、B、C三根柱子及N個大小不同的套環，並且初始狀態為A柱子上有N個套環。請問至少需要搬多少次，才能將A柱中的N個套環搬移至C柱呢？ 【規則】 第一點：一次只能移動一個套環。 第二點：在搬移過程中，小的套環不能放在大的套環下方。

41 【實例】 如果n=3時，則原來狀態如下： 其搬移3個盤子的過程如下： 步驟一：將盤子1從A移到C 步驟二：將盤子2從A移到B

42 步驟三：將盤子1從C移到B 步驟四：將盤子3從A移到C 步驟五：將盤子1從B移到A 步驟六：將盤子2從B移到C

43 步驟七：將盤子1從A移到C 所以，三個盤子共要搬移7次才能完成。 【說明】當有n個盤子要搬動時，總共要搬動2n-1次。

44 5-5 佇列(Queue) 【引言】 日常生活中，有一些佇列的例子，如排隊上公車、排隊買電影票或是
超市排隊付帳等，皆是先到達的先處理、後到的後處理。 【示意圖 】

45 5-5 佇列(Queue)續… 【定義】 是指一群相同性質元素所組合，並且它具有先進先出(First In First Out;FIFO)的特性。 【圖解說明】

46 【佇列常用的運算】 1. Add(item,Queue)：又稱Enqueue 是指由佇列的後端 (Rear ) 加入一個新項目。
2. Delete(item, Queue) ：又稱Dequeue 是指從佇列的前端 (Front ) 刪除一個項目。

47 一、Add演算法

48 二、Delete演算法

49 5-6 串列(List) 【定義】是指有次序的資料組合而成。 【分類】 1.循序串列(Sequential List)
2.鏈結串列(Linked List)

50 一、循序串列(Sequential List)
【定義】是指資料元素儲存在連續記憶空間，例如「陣列」。 【舉例】 假設我們現在想利用一個A陣列，來存放一年的四季名稱，此時，我們就必須 要建立一個空的陣列來存放資料。然後，再依序存入：春、夏、秋、冬。 【圖解說明】 步驟一：建立空的陣列空間(循序串列) 步驟二：依序存入資料

51 【循序串列】的優點與缺點 【優點】 1.資料的搜尋方便，可隨機讀取資料。 2.設計時，資料結構簡單。 【缺點】
1.事先需宣告固定記憶空間，彈性小。 刪除或加入資料需移動大量資料。

52 【題目】 假設我們現在有一個「陣列」，其內容如下： 此時欲插入數字12到10與15之間，請呈現搬移過程。 【圖解說明】
步驟一：將數字30往右移一格 步驟二：將數字15往右移一格 步驟三：再將數字12插入到A[3]空格中，如下圖所示。

53 二、鏈結串列(Linked List) 【定義】 是指資料元素儲存在「非連續性」的記憶空間，而它是透過指標可以 彈性的在串列上增、減元素。
【題目】在鏈結串列中加入新節點

54 【圖解說明】 步驟一：先把新節點R指向Q節點 步驟二：再將P節點接到節點R，並刪除P節點指向Q節點的指標

55 【鏈結串列】的優點與缺點 【優點】 1.記憶體配置較有彈性 2. 串列分裂、合併容易 【缺點】 1.搜尋某個元素時，可能會較為耗時
2.可靠度低 (∵指標(point)斷裂時，資料會遺失(lost))

56 5-7 樹狀結構(Tree) 【定義】 是由一個或多個節點組合而成的有限集合，它必須要滿足以下兩點：
1. 樹(Tree)不可以為空，至少有一個節點稱為根節點 (Root)。 2. 其餘的節點分成T1 , T2,....., Tn個互斥集合。 亦即稱T1 , T2,....., Tn為根節點的子樹 ( Sub Tree )。 【圖解說明】

57 【樹狀結構的專有術語介紹】 在認識樹狀結構之前，您必須了解相關的專有術語。我們先以下圖的樹狀結構來為您說明：
樹根(root)：每一棵樹的最上層的節點，稱為樹根，而A就是為這棵樹 的樹根。 節點(node)：樹的節點代表著某項資料，A、B…、L都是節點。 A樹根

58 【樹狀結構的專有術語介紹】(續) 子樹(subtree)：把A去掉之後，就剩下以B、C及D為樹根的三棵子樹。 樹林(forest)：是由N≧0個互斥子樹的集合。把樹根A去掉之後，剩下 的部分就叫樹林。 階度(level)：表示節點的階層位置。樹根A的階度是1，B的階度是2， K的階度是4。

59 【樹狀結構的專有術語介紹】(續) 高度(height)：一棵樹中節點的最大階度就是高度， 而此樹的高度為4。 父節點(parent)：每一個節點的上一個節點就是父節點，B節點的父節 點就是A。 子節點(children)：每一個節點的下一個節點就是子節點，D節點的子 節點就是 H、I及J。

60 【樹狀結構的專有術語介紹】(續) 分支度(degree)：一個節點的子樹之個數稱為該節點的分支度。
例如：A節點的子樹之個數為3，所以，分支度為3。 B節點的子樹之個數為2，所以，分支度是2。 終點節點(terminal node)：分支度為0的節點，這棵樹的終點節點 (又稱樹葉節點)共有K、F、G、H、I、L。

61 【日常生活中的應用實例】 【實例一】家族的族譜

62 【實例二】比賽的賽程 假設現在有八個隊伍要進行桌球比賽，並且採用「樹狀」結構的方式來進行，也就是說，將八個隊伍分成四組之後，倆倆互相比賽，當獲勝隊伍就可以進級。

63 【實例三】尋寶圖遊戲 各位同學還記得小時候，常玩的一種尋寶圖遊戲呢？
其作法非常簡單，那就是利用一張長條形的紙上，畫上如同樹根狀的尋寶圖後，再把它捲起來，只剩下根部，來當作「尋寶圖遊戲」的起點。

64 【實例三】尋寶圖遊戲(續…) 接下來，玩家就可以慢慢往上捲，如果遇到叉路時，就必須要選擇某一條路徑之後，才可繼續往上捲動，如此反覆捲動及選擇路徑的動作，直到到達某一個目的地為止(也就是走到樹葉節點)。因此，此種方法就是利用「樹狀結構」中的二元樹來完成。

65 【實例四】學校的組織圖 以「某一大學」組織圖為例，校長就是根(Root)，各學院的院長就是
校長的子節點，並且各學院又是由許多系所組成。如下圖所示：

66 5-7.1 二元樹(Binary tree) 【定義】二元樹可以為空，若不為空，則具有以下兩個特性：
1.具有根節點(Root)及左子樹和右子樹。 2.左、右子樹亦是二元樹(亦即分支度小於或等於2)。 簡單的說，二元樹最多只能有兩個子節點，就是分支度小於或等於2。 根節點(Root) 左子樹 右子樹

67 【二元樹和一般樹的不同之處】 二元樹(binary tree) 樹(tree) 二元樹可以為空集合 樹不可為空集合(至少會有樹根)
分支度為0≦d≦2 分支度為d≧0 左、右子樹有次序之分 左、右子樹無次序之分 不相同 相同

68 【特性】 １、在二元樹的第 i 階度（Level）上最多的節點個數為 2 i-1 , i >= 1 。 【解析】 二元樹 第 i 階度
2 1-1=2 0=1 2 2-1=2 1=2 2 3-1=2 2=4 2 4-1=2 3=8

69 ２、在高度為 h 的二元樹中最多的節點個數為 2 h -1 , h >= 1 。
【解析】 二元樹 高度為 h 2 h -1 h=1 h=2 h=3 h=4 2 1-1=1 2 2-1=3 2 3-1=7 2 4-1=15

70 二元樹表示法 基本上，二元樹的表示方法有兩種： 第一種方法：利用「陣列」來表示。 第二種方法：利用「串列」來表示。

71 一、以陣列(Array)表示 【作法】假設二元樹(Binary Tree)之高度為h，則準備一維陣列
A[1…2h-1]，依照「節點編號」依序存入陣列中。

72 【舉例】 假設在下圖中有一棵二元樹，請問如何利用「陣列」來表示這一棵二元樹呢？ 【解答】
步驟一：將二元樹想像成一個「完滿二元樹」，並加註編號順序 步驟二：建立一個「一維陣列」來儲存以上的二元樹 由於上圖中的二元樹的高度h=3 ∴準備一個一維陣列A[1…2h-1]的空間， 亦即A[1…7]如下所示：

73 步驟三：依照「節點編號」順序存到一維陣列中

74 二、以鏈結串列(Link List)表示 【引言】
由於利用陣列來儲存斜曲二元樹時，造成許多空間的浪費，而且節點之插入與刪除較困難。因此，我們可以利用「串列」來解決此問題。 【節點結構】 第一個欄位(LChild)：是用來儲存指向「左子樹」的指標。 第二個欄位(Data)：是用來儲存節點本身的資料值。 第三個欄位(RChild)：是用來儲存指向「右子樹」的指標。

75 【舉例】 假設在下圖中有一棵二元樹，請問如何利用「串列」來表示這一棵二元樹呢？ 【解答】 A為資料值 指向左子樹 指向左子樹 若沒有右子樹
則指標指向空節點(null) 若為終端節點，則左、右指標指向空節點(null)

76 5-8 圖形結構(Graph) 【引言】 圖形的理論是起源於西元十八世紀，有一位數學家尤拉（Eular）為了解決「肯尼茲堡橋樑」問題，而想出的一種資料結構理論。 【「肯尼茲堡橋樑」問題】 某一個人由某地點出發，最後再回到原出發點，必須要經過每一座橋，並且只能經過一次。

77 【尤拉（Eular）提出的解決方法】 數學家尤拉（Eular）當時所使用的方法就是： 1.頂點（Vertices）來表示每塊土地
2.邊（Edge）代表每一座橋樑，如下圖所示： A,B,C,D代表土地。 代表橋樑

78 尤拉規則 與 肯尼茲堡的結論 「如果每一個頂點的分支度皆為偶數時，才能從某一個頂點出發，經過每一個邊後，再回到出發的頂點。」
肯尼茲堡的情況為，四個頂點的分支度都是奇數（A的分支度為5，B的分支度為3，C的分支度為3，D的分支度為3）。 最後的結論：就是肯尼茲堡的人不可能走過所有的橋樑，並且到過每一個地方，而後又回到肯尼茲堡。

79 5-8.1 何謂圖形 【定義】 圖形(Graph)是由頂點(Vertices)和邊(Edges)所組成，以數學式表示： G=(V,E)
例如： 1.表示圖形所有頂點的集合V(G)={V1,V2,V3,…,Vm}，其中 m>0 2.表示圖形所有邊的集合E(G)={E1,E2,E3,…,En}，其中n>0

80 一般而言，我們可以將圖形結構分為無向圖形(Undirected Graph)與
(1) 邊(Edges)是沒有方向性的。 (2) 邊(V1,V2)與邊(V2,V1)是相同的。並且邊以( )表示。 2. 有向圖形(Directed Graph) (1) 邊(Edges)是有方向性的。 (2) 邊<V1,V2>與邊<V2,V1>是不相同的。並且邊以<>表示。 若有一個邊為<V1,V2>，其中V1為頭(head)，V2為尾(tail)， 方向為：從V1指向V2

81 【舉例1】假設有一個無向圖形，如下圖所示：
請問，此無向圖形的頂點(V)和邊(E)如何表示呢？ 【解答】 V(G)={A,B,C,D,E} E(G)={(A,B),(A,C),(B,A),(B,D),(C,A),(C,E),(D,B) ,(D,E) ,(E,C) ,(E,D)}

82 【舉例2】假設有一個有向圖形，如下圖所示：
請問，此有向圖形的頂點(V)和邊(E)如何表示呢？ 【解答】 V(G)={A,B,C,D,E} E(G)={<A,B>,<A,C>,<B,D>,<C,E>,<D,E>}

83 5-8.2 圖形的表示法 基本上，圖形的表示法，常見兩種方法： 一. 相鄰矩陣(Adjacency Matrix)
圖形的表示法 基本上，圖形的表示法，常見兩種方法： 一. 相鄰矩陣(Adjacency Matrix) 二. 相鄰串列(Adjacency Lists)

84 一、相鄰矩陣 【定義】 若圖形G = ( V , E ) 是具有 n 個頂點的圖形，並且n >= 1時，則要表示圖形G 的相鄰矩陣，我們可以利用一個 n × n 的二維陣列來表示，稱其為相鄰矩陣 ( adjacency matrix ) 。 【圖解】 假設現在有一個圖形G是由 n 個頂點所組成，並且n 大於等於 1時，如果想要表示這個圖形G 的相鄰矩陣，則我們可以利用一個 n 乘 n 的二維陣列來表示。

85 【特性】 1. 矩陣A[i][j] = 0 表示邊E(i,j)不存在 2. 矩陣A[i][j] = 1 表示邊E(i,j)存在 3. 無向圖的相鄰矩陣以對角線對稱，亦即A[i][j]=A[j][i] 4. G=(V,E),|V|=n, 頂點 iV 的分支度（Degree） (1) 無向圖 ，其中i代表某一頂點 (2) 有向圖

86 【範例1】無向圖形 假設現在有一個無向圖形G是由 5 個頂點所組成，如果想要利用「相鄰矩陣」來表示圖形G時，則我們就必須要利用一個 5 乘 5 的二維陣列來表示。因此，當圖形中 i節點 與 j節點之間有連線時，則必須要在「相鄰矩陣」中紀錄1， 如果沒有連線時，則紀錄0。如下圖所示。 在無向圖形的相鄰矩陣中，若A[i][j]=1時，則代表圖形G中有一條邊(Vi,Vj)存在。反之，若A[i][j]=0時，則代表圖形G中沒有一條邊(Vi,Vj)存在。

87 【範例2】有向圖形 假設現在有一個有向圖形G是由 5 個頂點所組成，如果想要利用「相鄰矩陣」來表示圖形G時，則我們就必須要利用一個 5 乘 5 的二維陣列來表示。因此，當圖形中 i節點 與 j節點之間有連線時，則必須要在「相鄰矩陣」中紀錄1， 如果沒有連線時，則紀錄0。如下圖所示。 在有向圖形的相鄰矩陣中，若A[i][j]=1時，則代表圖形G中有一條邊<Vi,Vj>存在。反之，若A[i][j]=0時，則代表圖形G中沒有一條邊<Vi,Vj>存在。

88 二、相鄰串列 【定義】 假設圖形G=(V,E)包含n個頂點(n≧1)時，則我們可以使用n個鏈結串列來存放該圖形，每個鏈結串列分別代表一個頂點及其相鄰的頂點。

89 【圖解】 假設有一個圖形G是由 n 個頂點所組成，並且n 大於等於 1時，則我們可以使用n個鏈結串列來存放該圖形，並且每個鏈結串列分別代表一個頂點及其相鄰頂點的指標位址。

90 【範例1】無向圖形 假設現在有一個無向圖形G是由 5 個頂點所組成，如果想要利用「相鄰串列」來表示圖形G時，則我們可以使用5個鏈結串列來存放該圖形，並且每個鏈結串列分別代表一個頂點及其相鄰頂點的指標位址。 【解答】 說明：在無向圖中，5個頂點7條邊共需5個串列首節點及14個節點， 因此，在無向圖形中，節點數目為邊數的2倍。

91 【範例2】有向圖形 假設現在有一個有向圖形G是由 5 個頂點所組成，如果想要利用「相鄰串列」來表示圖形G時，則我們可以使用5個鏈結串列來存放該圖形，並且每個鏈結串列分別代表一個頂點及其相鄰頂點的指標位址。 【解答】 說明：在有向圖中，5個頂點7條邊共需5個串列首節點及7個節點， 因此，在有向圖形中，節點數目恰等於邊數。