第7部分资料结构ppt课件

《第7部分资料结构ppt课件》由会员分享，可在线阅读，更多相关《第7部分资料结构ppt课件（30页珍藏版）》请在装配图网上搜索。

1、第7章 資料結構7-1 陣列7-2 鏈結串列7-3 堆疊和佇列7-4 樹狀結構7-2全華科技圖書全華科技圖書7-1 陣列陣列n表示一系列一样型態的資料，如：學號1號到5號同學的數學成績 n範例宣告：nint score5;n陣列內資料的指定可利用註標，範例如下：7-3全華科技圖書全華科技圖書陣列的順序陣列的順序n邏輯順序：也就是註標的順序n實體順序：在記憶體裡的順序，表示圖如下：n陣列的實體順序，也是由註標小的依序排到註標大的，正好和邏輯順序一樣；所以，某一個註標在記憶體的位置可以很快決定出來，其公示如下：7-4全華科技圖書全華科技圖書二維陣列二維陣列n應用範例：同時表示5位同學的數學成績和英

2、文成績n範例宣告：nint scores25;n一切同學的數學成績可以記錄在“scores 二維陣列的第一列，英文成績可以記錄在“scores 二維陣列的第二列，每個同學這兩科成績的對應註標如下所示：7-5全華科技圖書全華科技圖書二維陣列的實體順序二維陣列的實體順序n以列為主：先存放好第一列的元素，接著再存放第二列，依此類推 n其表示圖如下：n其公式如下：n以欄為主：先存放好第一欄的元素，接著再存放第二欄，依此類推，其公式如下：107-6全華科技圖書全華科技圖書7-2 鏈結串列鏈結串列n可表示不確定大小或會動態增減的資料 n由一個個節點所組成，其資料型態宣告如下：n宣告一個指標變數“front

3、，用來指到一個鏈結串列的起始節點：n鏈結串列範例如下：7-7全華科技圖書全華科技圖書指標變數指標變數 n根據C語言的語法，在宣告一個變數時前面加上符號*，即為指標變數n指標變數記錄的值是資料在記憶體裡的位置 n取出資料的方法n在變數前面加上符號*，如*front.data會傳回該節點在“data欄位的值 n在變數後面加上箭頭“-，如front-datan空指標 n表示為“null n通常用來表示一個串列的結束 7-8全華科技圖書全華科技圖書鏈結串列程序一鏈結串列程序一n把一個新的節點参与到鏈結串列的起點 n程序“insert 定義如下：7-9全華科技圖書全華科技圖書程序程序insert執行步驟

4、執行步驟n執行 insert(front,7)的步驟 n利用“malloc函數建立一個新的節點，並利用部分變數“temp指到該節點；n把數值“7指定給節點“temp的欄位“data；n將節點“temp的欄位“next 指到“p所指到的節點，也就是串列的第一個節點；n將參數“p也就是“front指到新建立的節點。n執行之後的鏈結串列如下所示 7-10全華科技圖書全華科技圖書鏈結串列的實體順序鏈結串列的實體順序n鏈結串列的實體順序和邏輯順序無關。n缘由：利用函數“malloc向系統要一塊記憶體的空間時，系統會根據當時記憶體哪裡有空位n實體順序的表示圖：n要取出鏈結串列的某一個節點，只能依循事先建立

5、好的指標，一一探訪中間經過的節點。7-11全華科技圖書全華科技圖書鏈結串列程序二鏈結串列程序二n把一個鏈結串列內一切節點的內容值按照邏輯順序列出來 n程序“print_linked_list 定義如下：7-12全華科技圖書全華科技圖書鏈結串列程序三鏈結串列程序三n把第一個參數“p指到的鏈結串列的起始節點，變成第二個參數“q 指到的鏈結串列的起始節點 n程序“changehead 定義如下：7-13全華科技圖書全華科技圖書7-3 堆疊和佇列堆疊和佇列n堆疊n後進先出n先進後出n 右圖範例n最早放進去的1號球會在球桶的最下方，而最後放進去的5號球會在球桶的最上方。n要用球時，首先拿到的是球桶最上方

6、的5號球，最後才會拿到1號球。7-14全華科技圖書全華科技圖書以陣列實作堆疊以陣列實作堆疊n宣告一個一維整數陣列來存放堆疊中的元素nint stack10;n定義整數變數“top，對應到最上層元素的註標 nint top=-1;n定義將資料放入堆疊的程序“push nn定義將資料從堆疊取出的程序“popn7-15全華科技圖書全華科技圖書佇列佇列n佇列n先進先出n後進後出 n 下圖範例n最先駛入巷道的編號1號的車子會在最前面，最接近燈號，其次為編號2號的車子。n綠燈的時候，首先開出巷道的會是等在最前面的1號車，接著是2號車。7-16全華科技圖書全華科技圖書以陣列實作佇列以陣列實作佇列n宣告一個一

7、維整數陣列來存放佇列中的元素nint queue10;n定義兩個變數“front和“rear，它們可用來找最前面和最後面元素的註標nint front=-1;rear=-1;n定義將資料放入佇列的程序“put n定義將資料從佇列取出的程序“getn7-17全華科技圖書全華科技圖書環狀佇列環狀佇列n特征：可以再度回到之前曾被运用過，但是現在已經是空的位置，以有效利用空間 n範例資料宣告：nint queue6;front=0;rear=0;n运用運算子“%，決定下一個要参与資料的註標位置nrear=(rear+1)%6;n利用運算子“%，決定將資料取出的註標位置 nfront=(front+1)

8、%6;n判斷佇列是空的式子nfront=rear n判斷佇列是滿的式子 n(rear+1)%6=front 7-18全華科技圖書全華科技圖書環狀佇列表示圖環狀佇列表示圖7-19全華科技圖書全華科技圖書環狀佇列的相關程序環狀佇列的相關程序7-20全華科技圖書全華科技圖書7-4 樹狀結構樹狀結構n由節點Node和邊Edge所構成，如下圖 n節點又可細分為三種n外部節點External node：又稱作葉節點，位於樹的最下層，如編號“E、“F、“H等的節點。n內部節點Internal node：不是外部的節點，如編號“C、“I、“G等的節點。n根節點Root node：位於最上層的節點，如編號“L的

9、節點。7-21全華科技圖書全華科技圖書樹的特性樹的特性n只需独一一個根節點。n樹中沒有迴圈Loop，也就是任一節點循著邊往下走的話，不能够走回本人。n任兩點只需独一路徑。譬如說，節點“E要走到節點“I的話，一定會經過節點“G，而沒有其他方法；另一個例子，從節點“J要走到節點“C的話，也一定會經過節點“K和節點“L。7-22全華科技圖書全華科技圖書樹的相關定義樹的相關定義n樹的高度n從根節點到樹中一切葉節點的最長能够路徑n樹的階層n任何一個節點，距離根節點的距離n祖先節點n在某一個節點往上走到根節點的那一條路徑上的一切節點不包含本人。父節點為最接近該節點的祖先節點。n子孫節點n在某一個節點往下走

10、到葉節點的一切能够路徑上的一切節點不包含本人。子節點為最接近該節點的子孫節點。7-23全華科技圖書全華科技圖書二元樹二元樹n每一個節點最多只需2個子節點能够沒有子節點，或是只需1個 n很常見且具有很多應用n下圖的範例，也稱作運算樹，是將運算子以父節點表示，運算元以子節點表示。7-24全華科技圖書全華科技圖書左右子樹左右子樹n左子節點：位於左邊的子節點n左子樹：以該左子節點為根節點所對應的樹 n右子節點：位於右邊的子節點n右子樹：以該右子節點為根節點所對應的樹 n針對上頁的範例樹，其左右子樹如下圖7-25全華科技圖書全華科技圖書實做二元樹實做二元樹n定義樹中每一個節點的資料型態 n將左子節點或左

11、子樹以指標“left表示，而將右子節點或右子樹以指標“right表示，表示圖如下：7-26全華科技圖書全華科技圖書二元樹的三種探訪法二元樹的三種探訪法n前序法Preorder：n先探訪父節點、再探訪左子節點、最後探訪右子節點n對應到運算式的前序法，如：+*AB*CD n中序法Inorder：n先探訪左子節點、再探訪父節點、最後探訪右子節點n對應到運算式的中序法，如：A*B+C*D n後序法Postorder：n先探訪左子節點、再探訪右子節點、最後探訪父節點n對應到運算式的後序法，如：AB*CD*+7-27全華科技圖書全華科技圖書遞迴程序遞迴程序n為二元樹探訪程序的基礎n在程序的本體中，又呼叫到本人本身 n遞迴範例：nfact(0)=1;nfact(n)=n*fact(n-1);(if n=1)n在此階乘函數中的第二式，我們利用 n-1的階乘來計算 n的階乘，這就是遞迴的觀念7-28全華科技圖書全華科技圖書前序法程序前序法程序7-29全華科技圖書全華科技圖書中序法程序中序法程序7-30全華科技圖書全華科技圖書後序法程序後序法程序