第7章 資料結構 7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構.

Presentation on theme: "第7章 資料結構 7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構."— Presentation transcript:

1 第7章 資料結構 7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構

2 7-1 陣列 表示一系列相同型態的資料，如：學號1號到5號同學的數學成績 範例宣告： int score[5];
陣列內資料的指定可利用註標，範例如下：

3 陣列的順序 邏輯順序：也就是註標的順序 實體順序 ：在記憶體裡的順序，示意圖如下：
陣列的實體順序，也是由註標小的依序排到註標大的，正好和邏輯順序一樣；所以，某一個註標在記憶體的位置可以很快決定出來，其公示如下：

4 二維陣列 應用範例：同時表示5位同學的數學成績和英文成績 範例宣告： int scores[2][5];
所有同學的數學成績可以記錄在 “scores” 二維陣列的第一列，英文成績可以記錄在 “scores” 二維陣列的第二列，每個同學這兩科成績的對應註標如下所示：

5 二維陣列的實體順序 以列為主：先存放好第一「列」的元素，接著再存放第二「列」，依此類推
其示意圖如下： 其公式如下： 以欄為主：先存放好第一「欄」的元素，接著再存放第二「欄 」，依此類推，其公式如下：

6 7-2 鏈結串列 可表示不確定大小或會動態增減的資料 由一個個節點所組成，其資料型態宣告如下：
宣告一個指標變數 “front”，用來指到一個鏈結串列的起始節點： 鏈結串列範例如下：

7 指標變數 根據C語言的語法，在宣告一個變數時前面加上符號 「*」，即為指標變數 指標變數記錄的值是資料在記憶體裡的位置 取出資料的方法
在變數前面加上符號 「*」，如 「*front.data」會傳回該節點在 “data”欄位的值 在變數後面加上箭頭 “->” ，如「front->data」 空指標 表示為 “null” 通常用來表示一個串列的結束

8 鏈結串列程序（一） 把一個新的節點加入到鏈結串列的起點 程序 “insert” 定義如下：

9 程序insert執行步驟 執行 「insert(front, 7) 」的步驟 執行之後的鏈結串列如下所示
利用 “malloc”函數建立一個新的節點，並利用局部變數 “temp”指到該節點； 把數值 “7”指定給節點 “temp”的欄位 “data”； 將節點 “temp”的欄位 “next” 指到 “p”所指到的節點，也就是串列的第一個節點； 將參數 “p”（也就是 “front”）指到新建立的節點。 執行之後的鏈結串列如下所示

10 鏈結串列的實體順序 鏈結串列的實體順序和邏輯順序無關。 實體順序的示意圖：
原因：利用函數 “malloc”向系統要一塊記憶體的空間時，系統會根據當時記憶體哪裡有空位 實體順序的示意圖： 要取出鏈結串列的某一個節點，只能依循事先建立好的指標，一一探訪中間經過的節點。

11 鏈結串列程序（二） 把一個鏈結串列內所有節點的內容值依照邏輯順序列出來 程序 “print_linked_list” 定義如下：

12 鏈結串列程序（三） 把第一個參數 “p”指到的鏈結串列的起始節點，變成第二個參數 “q” 指到的鏈結串列的起始節點
程序 “changehead” 定義如下：

13 7-3 堆疊和佇列 堆疊 右圖範例 後進先出 先進後出 最早放進去的1號球會在球桶的最下方，而最後放進去的5號球會在球桶的最上方。
要用球時，首先拿到的是球桶最上方的5號球，最後才會拿到1號球。

14 以陣列實作堆疊 宣告一個一維整數陣列來存放堆疊中的元素 int stack[10]; 定義整數變數 “top”，對應到最上層元素的註標
int top = -1; 定義將資料放入堆疊的程序 “push” 定義將資料從堆疊取出的程序 “pop”

15 佇列 佇列 先進先出 後進後出 下圖範例 最先駛入巷道的編號1號的車子會在最前面，最靠近燈號，其次為編號2號的車子。
綠燈的時候，首先開出巷道的會是等在最前面的1號車，接著是2號車。

16 以陣列實作佇列 宣告一個一維整數陣列來存放佇列中的元素 int queue[10];
定義兩個變數 “front”和 “rear”，對應到最前面和最後面元素的註標 int front = -1; rear = -1; 定義將資料放入佇列的程序 “put” 定義將資料從佇列取出的程序 “get”

17 環狀佇列 特色：可以再度回到之前曾被使用過，但是現在已經是空的位置，以有效利用空間 範例資料宣告：
int queue[6]; front = 0; rear = 0; 使用運算子 “%”，決定下一個要加入資料的註標位置 rear = (rear + 1)%6; 利用運算子 “%”，決定將資料取出的註標位置 front = (front + 1)%6; 判斷佇列是空的式子 front = = rear 判斷佇列是滿的式子 (rear+1)%6 = = front

18 環狀佇列示意圖

19 環狀佇列的相關程序

20 7-4 樹狀結構 由節點（Node）和邊（Edge）所構成，如下圖 節點又可細分為三種
外部節點（External node）：又稱作葉節點，位於樹的最下層，如編號 “E”、 “F”、 “H”等的節點。 內部節點（Internal node）：不是外部的節點，如編號 “C”、 “I”、 “G”等的節點。 根節點（Root node）：位於最上層的節點，如編號 “L”的節點。

21 樹的特性 只有唯一一個根節點。 樹中沒有迴圈（Loop），也就是任一節點循著邊往下走的話，不可能走回自己。
任兩點只有唯一路徑。譬如說，節點 “E”要走到節點 “I”的話，一定會經過節點 “G”，而沒有其他方法；另一個例子，從節點 “J”要走到節點 “C”的話，也一定會經過節點 “K”和節點 “L”。

22 樹的相關定義 樹的高度 從根節點到樹中所有葉節點的最長可能路徑 樹的階層 任何一個節點，距離根節點的距離 祖先節點
在某一個節點往上走到根節點的那一條路徑上的所有節點（不包含自己）。父節點為最靠近該節點的祖先節點。 子孫節點 在某一個節點往下走到葉節點的所有可能路徑上的所有節點（不包含自己）。子節點為最靠近該節點的子孫節點。

23 二元樹 每一個節點最多只有2個子節點（可能沒有子節點，或是只有1個） 很常見且具有很多應用
下圖的範例，也稱作運算樹，是將運算子以父節點表示，運算元以子節點表示。

24 左右子樹 左子節點：位於左邊的子節點 左子樹：以該左子節點為根節點所對應的樹 右子節點：位於右邊的子節點
右子樹：以該右子節點為根節點所對應的樹 針對上頁的範例樹，其左右子樹如下圖

25 實做二元樹 定義樹中每一個節點的資料型態 將左子節點（或左子樹）以指標 “left”表示，而將右子節點（或右子樹）以指標 “right”表示，示意圖如下：

26 二元樹的三種探訪法 前序法（Preorder）： 中序法（Inorder）： 後序法（Postorder）：
先探訪父節點、再探訪左子節點、最後探訪右子節點 對應到運算式的前序法，如：+*AB*CD 中序法（Inorder）： 先探訪左子節點、再探訪父節點、最後探訪右子節點 對應到運算式的中序法，如：A*B+C*D 後序法（Postorder）： 先探訪左子節點、再探訪右子節點、最後探訪父節點 對應到運算式的後序法，如：AB*CD*+

27 遞迴程序 為二元樹探訪程序的基礎 在程序的本體中，又呼叫到自己本身 遞迴範例： fact(0) = 1;
fact(n) = n * fact(n-1); (if n >= 1) 在此階乘函數中的第二式，我們利用 n-1的階乘來計算 n的階乘，這就是遞迴的觀念

28 前序法程序

29 中序法程序

30 後序法程序