資料結構 - notesHazuya筆記長也

圖形結構-如何求出最小成本擴展樹

何謂擴展樹 擴展樹就是以最少的邊,連接圖形中的所有頂點。而在"圖形結構之走訪-DFS與BFS之介紹與範例"一文中所提到的深度優先與廣度優先搜尋也可以求出不同的擴展樹。 最小成本擴展樹 若在邊加上權重,並將權重作為邊的成本或距離,則稱為網路。而一網......

圖形結構-深度優先與廣度優先搜尋之介紹與範例

在上一篇文章"圖形結構-基本介紹與表示方法"已經介紹過兩種圖形結構在電腦中的表示方法,本文將介紹如何走訪已經建立好的圖形。 DFS(Depth first search)深度優先搜尋 又稱縱向優先搜尋,其拜訪順序為:(1)拜訪起點V,(2)拜訪V鄰近尚未被拜訪的節點W,(3)若有任一......

圖形結構-基本介紹與表示方法

圖形結構的專有名詞

AVL高度平衡二元搜尋樹介紹與範例

AVL-高度平衡二元搜尋樹 關於AVL樹的介紹,其實與我共筆的作者已經介紹過基本的四種型態,本文將著重於各種旋轉的實作,關於基本介紹請參考:AVL高度平衡二元搜尋樹介紹。 AVL樹的加入與平衡......

Heap結構的基本介紹與範例

Heap - 堆積 堆積是一棵二元樹,其樹根大於子樹,且不管左右大小為何,這是與二元搜尋樹最大的差異。 將二元樹調整為堆積 將二元樹轉為堆積的方式有兩種,第一種是由上而下整理,這種整理方式有兩種: 1.由樹根開始,與其左右節點比較,若樹根較大,則不必交換,反之則要交換  

樹-二元搜尋樹之介紹與範例

二元搜尋樹的特性 1.左子樹的資料(鍵值)均小於樹根的資料 2.右子樹的資料(鍵值)均大於樹根的資料 3.左子樹與右子樹也是二元搜尋樹 二元搜尋樹的加入與搜尋 只要依照左子樹小於樹根,右子樹大於樹根的規則尋找合適的插入點即可 例如我們將87加入,將會加在65的右邊。

樹—二元樹的介紹與走訪

二元樹 二元樹與一般的樹不同的地方 1.二元樹有左右之分,一般樹則沒有 2.二元樹每一節點的分支度至多為2,一般樹則沒有此限制   而二元樹的左子樹和右子樹也可以是空集合,如下圖所示,A與B為兩棵不同的樹,A樹右子樹為空,B樹左子樹為空。

樹—樹狀結構的基本名詞與介紹

樹狀結構 樹是由節點(node)與邊(edge)所組成的集合。包含一個特殊的節點樹根(root),其餘節點分成n個集合,每個集合都是一棵樹。  

遞迴—河內塔

河內塔 一般河內塔有三個柱子,與N個碟盤,要將N個碟盤由A柱移動至C柱,其規則如下: 1.一次只能搬動一個盤子 2.大盤子不可以疊在小盤子上面 (小盤子必須在大盤子上) 演算法 假設要移動n個碟盤: a.當 n=1時,直接將碟盤由A移動至C b.否則: 1.搬移n-1個碟盤,由A至B藉由C 2.搬移第n個碟盤,由A......

串列之應用—多項式相加

多項式相加 多項式相加可利用串列完成,其資料之表示方法如下: COEF EXP