《第7章资料结构教材课程》由会员分享,可在线阅读,更多相关《第7章资料结构教材课程(30页珍藏版)》请在金锄头文库上搜索。
1、第7章 資料結構,7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構,7-1 陣列,表示一系列相同型態的資料,如:學號1號到5號同學的數學成績 範例宣告: int score5; 陣列內資料的指定可利用註標,範例如下:,陣列的順序,邏輯順序:也就是註標的順序 實體順序 :在記憶體裡的順序,示意圖如下: 陣列的實體順序,也是由註標小的依序排到註標大的,正好和邏輯順序一樣;所以,某一個註標在記憶體的位置可以很快決定出來,其公示如下:,二維陣列,應用範例:同時表示5位同學的數學成績和英文成績 範例宣告: int scores25; 所有同學的數學成績可以記錄在 “scores” 二
2、維陣列的第一列,英文成績可以記錄在 “scores” 二維陣列的第二列,每個同學這兩科成績的對應註標如下所示:,7-2 鏈結串列,可表示不確定大小或會動態增減的資料 由一個個節點所組成,其資料型態宣告如下: 宣告一個指標變數 “front”,用來指到一個鏈結串列的起始節點: 鏈結串列範例如下:,指標變數,根據C語言的語法,在宣告一個變數時前面加上符號 *,即為指標變數 指標變數記錄的值是資料在記憶體裡的位置 取出資料的方法 在變數前面加上符號 *,如 *front.data會傳回該節點在 “data”欄位的值 在變數後面加上箭頭 “-” ,如front-data 空指標 表示為 “null”
3、通常用來表示一個串列的結束,鏈結串列程序(一),把一個新的節點加入到鏈結串列的起點 程序 “insert” 定義如下:,程序insert執行步驟,執行 insert(front, 7) 的步驟 利用 “malloc”函數建立一個新的節點,並利用局部變數 “temp”指到該節點; 把數值 “7”指定給節點 “temp”的欄位 “data”; 將節點 “temp”的欄位 “next” 指到 “p”所指到的節點,也就是串列的第一個節點; 將參數 “p”(也就是 “front”)指到新建立的節點。 執行之後的鏈結串列如下所示,鏈結串列的實體順序,鏈結串列的實體順序和邏輯順序無關。 原因:利用函數 “m
4、alloc”向系統要一塊記憶體的空間時,系統會根據當時記憶體哪裡有空位 實體順序的示意圖: 要取出鏈結串列的某一個節點,只能依循事先建立好的指標,一一探訪中間經過的節點。,鏈結串列程序(二),把一個鏈結串列內所有節點的內容值依照邏輯順序列出來 程序 “print_linked_list” 定義如下:,鏈結串列程序(三),把第一個參數 “p”指到的鏈結串列的起始節點,變成第二個參數 “q” 指到的鏈結串列的起始節點 程序 “changehead” 定義如下:,7-3 堆疊和佇列,堆疊 後進先出 先進後出 右圖範例 最早放進去的1號球會在球桶的最下方,而最後放進去的5號球會在球桶的最上方。 要用球
5、時,首先拿到的是球桶最上方的5號球,最後才會拿到1號球。,以陣列實作堆疊,宣告一個一維整數陣列來存放堆疊中的元素 int stack10; 定義整數變數 “top”,對應到最上層元素的註標 int top = -1; 定義將資料放入堆疊的程序 “push” 定義將資料從堆疊取出的程序 “pop”,佇列,佇列 先進先出 後進後出 下圖範例 最先駛入巷道的編號1號的車子會在最前面,最靠近燈號,其次為編號2號的車子。 綠燈的時候,首先開出巷道的會是等在最前面的1號車,接著是2號車。,以陣列實作佇列,宣告一個一維整數陣列來存放佇列中的元素 int queue10; 定義兩個變數 “front”和 “r
6、ear”,它們可用來找最前面和最後面元素的註標 int front = -1;rear = -1; 定義將資料放入佇列的程序 “put” 定義將資料從佇列取出的程序 “get”,環狀佇列,特色:可以再度回到之前曾被使用過,但是現在已經是空的位置,以有效利用空間 範例資料宣告: int queue6;front = 0;rear = 0; 使用運算子 “%”,決定下一個要加入資料的註標位置 rear = (rear + 1)%6; 利用運算子 “%”,決定將資料取出的註標位置 front = (front + 1)%6; 判斷佇列是空的式子 front = = rear 判斷佇列是滿的式子 (r
7、ear+1)%6 = = front,環狀佇列示意圖,環狀佇列的相關程序,7-4 樹狀結構,由節點(Node)和邊(Edge)所構成,如下圖 節點又可細分為三種 外部節點(External node):又稱作葉節點,位於樹的最下層,如編號 “E”、 “F”、 “H”等的節點。 內部節點(Internal node):不是外部的節點,如編號 “C”、 “I”、 “G”等的節點。 根節點(Root node):位於最上層的節點,如編號 “L”的節點。,樹的特性,只有唯一一個根節點。 樹中沒有迴圈(Loop),也就是任一節點循著邊往下走的話,不可能走回自己。 任兩點只有唯一路徑。譬如說,節點 “E”
8、要走到節點 “I”的話,一定會經過節點 “G”,而沒有其他方法;另一個例子,從節點 “J”要走到節點 “C”的話,也一定會經過節點 “K”和節點 “L”。,樹的相關定義,樹的高度 從根節點到樹中所有葉節點的最長可能路徑 樹的階層 任何一個節點,距離根節點的距離 祖先節點 在某一個節點往上走到根節點的那一條路徑上的所有節點(不包含自己)。父節點為最靠近該節點的祖先節點。 子孫節點 在某一個節點往下走到葉節點的所有可能路徑上的所有節點(不包含自己)。子節點為最靠近該節點的子孫節點。,二元樹,每一個節點最多只有2個子節點(可能沒有子節點,或是只有1個) 很常見且具有很多應用 下圖的範例,也稱作運算樹
9、,是將運算子以父節點表示,運算元以子節點表示。,左右子樹,左子節點:位於左邊的子節點 左子樹:以該左子節點為根節點所對應的樹 右子節點:位於右邊的子節點 右子樹:以該右子節點為根節點所對應的樹 針對上頁的範例樹,其左右子樹如下圖,實做二元樹,定義樹中每一個節點的資料型態 將左子節點(或左子樹)以指標 “left”表示,而將右子節點(或右子樹)以指標 “right”表示,示意圖如下:,二元樹的三種探訪法,前序法(Preorder): 先探訪父節點、再探訪左子節點、最後探訪右子節點 對應到運算式的前序法,如:+*AB*CD 中序法(Inorder): 先探訪左子節點、再探訪父節點、最後探訪右子節點 對應到運算式的中序法,如:A*B+C*D 後序法(Postorder): 先探訪左子節點、再探訪右子節點、最後探訪父節點 對應到運算式的後序法,如:AB*CD*+,遞迴程序,為二元樹探訪程序的基礎 在程序的本體中,又呼叫到自己本身 遞迴範例: fact(0) = 1; fact(n) = n * fact(n-1); (if n = 1) 在此階乘函數中的第二式,我們利用 n-1的階乘來計算 n的階乘,這就是遞迴的觀念,前序法程序,中序法程序,後序法程序,