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

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

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

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

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

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

5 二維陣列的實體順序 以列為主：先存放好第一「列」的元素，接著再存放第二「列」，依此類推 其示意圖如下： 其公式如下：
第一列 第二列 [0][0] [0][1] [0][2] [0][3] [0][4] [1][1] [1][2] [1][3] [1][4] 80 70 60 90 95 65 75 85 81 74 其公式如下： 以欄為主：先存放好第一「欄」的元素，接著再 存放第二「欄 」，依此類推，其公式如下：

6 7-2 鏈結串列 front 3 5 null 可表示不確定大小或會動態增減的資料 由一個個節點所組成，其資料型態宣告如下：
鏈結串列範例如下： front 3 5 null

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

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

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

10 鏈結串列的實體順序 鏈結串列的實體順序和邏輯順序無關。
原因：利用函數“malloc”向系統要一塊記憶體的空間時，系統會根據當時記憶體哪裡有空位，而把位址回傳給你 實體順序的示意圖： 要取出鏈結串列的某一個節點，只能依循事先建立好的指標，一一探訪中間經過的節點。 第二個節點 第一個節點 第三個節點 3 L5 7 L1 5 null L2 L3 L4 L6

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

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

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

14 定義整數變數“top”，對應到最上層元素的註標 int top=-1;
以陣列實作堆疊 宣告一個一維整數陣列來存放堆疊中的元素 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];
特色：可以再度回到之前曾被使用過，但是現在已經是空的 位置，以有效利用空間 範例資料宣告： 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 樹狀結構 L C I K D G H A B J E F

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

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

24 二元樹 + * A B C D 每一個節點最多只有2個子節點(可能沒有子節點，或是只有1個) 很常見且具有很多應用
下圖的範例，也稱作運算樹，是將運算子以父節點表示，運算元以子節點表示。 + * A B C D

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

26 實作二元樹 定義樹中每一個節點的資料型態 將左子節點(或左子樹)以指標“left”表示，而將右子節點(或右子樹)以指標“right”表示，示意圖如下： ＋ ＊ ＊ A null B null C null D null

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

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

29 前序法程序 中序法程序 後序法程序