【教学课件】第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範例宣告：int score5;n陣列內資料的指定可利用註標，範例如下：7-3計算機概論全華科技圖書全華科技圖書陣列的順序陣列的順序n邏輯順序：也就是註標的順序n實體順序：在記憶體裡的順序，示意圖如下：n陣列的實體順序，也是由註標小的依序排到註標大的，正好和邏輯順序一樣；所以，某一個註標在記憶體的位置可以很快決定出來，其公示如下：7-4計算機概論全華科技圖書全華科技圖書二維陣列二維陣列n應用範例：同

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

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

4、nsert”定義如下：7-9計算機概論全華科技圖書全華科技圖書程序程序insert執行步驟執行步驟n執行 insert(front,7)的步驟 n利用“malloc”函數建立一個新的節點，並利用局部變數“temp”指到該節點；n把數值“7”指定給節點“temp”的欄位“data”；n將節點“temp”的欄位“next”指到“p”所指到的節點，也就是串列的第一個節點；n將參數“p”（也就是“front”）指到新建立的節點。n執行之後的鏈結串列如下所示 7-10計算機概論全華科技圖書全華科技圖書鏈結串列的實體順序鏈結串列的實體順序n鏈結串列的實體順序和邏輯順序無關。n原因：利用函數“malloc”

5、向系統要一塊記憶體的空間時，系統會根據當時記憶體哪裡有空位n實體順序的示意圖：n要取出鏈結串列的某一個節點，只能依循事先建立好的指標，一一探訪中間經過的節點。7-11計算機概論全華科技圖書全華科技圖書鏈結串列程序（二）鏈結串列程序（二）n把一個鏈結串列內所有節點的內容值依照邏輯順序列出來 n程序“print_linked_list”定義如下：7-12計算機概論全華科技圖書全華科技圖書鏈結串列程序（三）鏈結串列程序（三）n把第一個參數“p”指到的鏈結串列的起始節點，變成第二個參數“q”指到的鏈結串列的起始節點 n程序“changehead”定義如下：7-13計算機概論全華科技圖書全華科技圖書7-

6、3 堆疊和佇列堆疊和佇列n堆疊n後進先出n先進後出n 右圖範例n最早放進去的1號球會在球桶的最下方，而最後放進去的5號球會在球桶的最上方。n要用球時，首先拿到的是球桶最上方的5號球，最後才會拿到1號球。7-14計算機概論全華科技圖書全華科技圖書以陣列實作堆疊以陣列實作堆疊n宣告一個一維整數陣列來存放堆疊中的元素int stack10;n定義整數變數“top”，對應到最上層元素的註標 int top=-1;n定義將資料放入堆疊的程序“push”n定義將資料從堆疊取出的程序“pop”7-15計算機概論全華科技圖書全華科技圖書佇列佇列n佇列n先進先出n後進後出 n 下圖範例n最先駛入巷道的編號1號的

7、車子會在最前面，最靠近燈號，其次為編號2號的車子。n綠燈的時候，首先開出巷道的會是等在最前面的1號車，接著是2號車。7-16計算機概論全華科技圖書全華科技圖書以陣列實作佇列以陣列實作佇列n宣告一個一維整數陣列來存放佇列中的元素int queue10;n定義兩個變數“front”和“rear”，它們可用來找最前面和最後面元素的註標int front=-1;rear=-1;n定義將資料放入佇列的程序“put”n定義將資料從佇列取出的程序“get”7-17計算機概論全華科技圖書全華科技圖書環狀佇列環狀佇列n特色：可以再度回到之前曾被使用過，但是現在已經是空的位置，以有效利用空間 n範例資料宣告：in

8、t queue6;front=0;rear=0;n使用運算子“%”，決定下一個要加入資料的註標位置rear=(rear+1)%6;n利用運算子“%”，決定將資料取出的註標位置 front=(front+1)%6;n判斷佇列是空的式子front=rear n判斷佇列是滿的式子(rear+1)%6=front 7-18計算機概論全華科技圖書全華科技圖書環狀佇列示意圖環狀佇列示意圖7-19計算機概論全華科技圖書全華科技圖書環狀佇列的相關程序環狀佇列的相關程序7-20計算機概論全華科技圖書全華科技圖書7-4 樹狀結構樹狀結構n由節點（Node）和邊（Edge）所構成，如下圖 n節點又可細分為三種n外部

9、節點（External node）：又稱作葉節點，位於樹的最下層，如編號“E”、“F”、“H”等的節點。n內部節點（Internal node）：不是外部的節點，如編號“C”、“I”、“G”等的節點。n根節點（Root node）：位於最上層的節點，如編號“L”的節點。7-21計算機概論全華科技圖書全華科技圖書樹的特性樹的特性n只有唯一一個根節點。n樹中沒有迴圈（Loop），也就是任一節點循著邊往下走的話，不可能走回自己。n任兩點只有唯一路徑。譬如說，節點“E”要走到節點“I”的話，一定會經過節點“G”，而沒有其他方法；另一個例子，從節點“J”要走到節點“C”的話，也一定會經過節點“K”和節點

10、“L”。7-22計算機概論全華科技圖書全華科技圖書樹的相關定義樹的相關定義n樹的高度從根節點到樹中所有葉節點的最長可能路徑n樹的階層任何一個節點，距離根節點的距離n祖先節點在某一個節點往上走到根節點的那一條路徑上的所有節點（不包含自己）。父節點為最靠近該節點的祖先節點。n子孫節點在某一個節點往下走到葉節點的所有可能路徑上的所有節點（不包含自己）。子節點為最靠近該節點的子孫節點。7-23計算機概論全華科技圖書全華科技圖書二元樹二元樹n每一個節點最多只有2個子節點（可能沒有子節點，或是只有1個）n很常見且具有很多應用n下圖的範例，也稱作運算樹，是將運算子以父節點表示，運算元以子節點表示。7-24計

11、算機概論全華科技圖書全華科技圖書左右子樹左右子樹n左子節點：位於左邊的子節點n左子樹：以該左子節點為根節點所對應的樹 n右子節點：位於右邊的子節點n右子樹：以該右子節點為根節點所對應的樹 n針對上頁的範例樹，其左右子樹如下圖7-25計算機概論全華科技圖書全華科技圖書實做二元樹實做二元樹n定義樹中每一個節點的資料型態 n將左子節點（或左子樹）以指標“left”表示，而將右子節點（或右子樹）以指標“right”表示，示意圖如下：7-26計算機概論全華科技圖書全華科技圖書二元樹的三種探訪法二元樹的三種探訪法n前序法（Preorder）：n先探訪父節點、再探訪左子節點、最後探訪右子節點n對應到運算式的

12、前序法，如：+*AB*CD n中序法（Inorder）：n先探訪左子節點、再探訪父節點、最後探訪右子節點n對應到運算式的中序法，如：A*B+C*D n後序法（Postorder）：n先探訪左子節點、再探訪右子節點、最後探訪父節點n對應到運算式的後序法，如：AB*CD*+7-27計算機概論全華科技圖書全華科技圖書遞迴程序遞迴程序n為二元樹探訪程序的基礎n在程序的本體中，又呼叫到自己本身 n遞迴範例：fact(0)=1;fact(n)=n*fact(n-1);(if n=1)n在此階乘函數中的第二式，我們利用 n-1的階乘來計算 n的階乘，這就是遞迴的觀念7-28計算機概論全華科技圖書全華科技圖書前序法程序前序法程序7-29計算機概論全華科技圖書全華科技圖書中序法程序中序法程序7-30計算機概論全華科技圖書全華科技圖書後序法程序後序法程序