Tag Archive 'tree'

Posted By Mr. Thursday 不知道各位是否有接聽電話插撥 (call waiting) 的經驗? 我們會先把第一個接聽的人先暫時停著,然後接聽新打來的電話。不知道目前插撥最多能接聽多少通電話?假設依照這個方法一直接聽新的插撥電話,就會一直把上一通電話暫時儲存,等新接通的電話結束後,再回復上一通、上上一通、一直到第一通接聽的電話。 堆疊 (Stack) 就是類似的資料結構。「堆疊」有兩個方法 (method) 可以呼叫:推進 (push) 和 彈出 (pop)。透過這兩個方法的使用,我們可以達到讓資料「先進後出」的效果 (LIFO: Last In First Out)。甚麼是先進後出呢?讓我們再舉一個例子:搭電梯。當我們搭電梯的時候,通常最先進電梯的會擠在後面,後進電梯的比較靠近門口。如果都是同一層離開電梯,剛才比較慢近來電梯的人,反而是比較早離開電梯的人,這就是「先進後出」(LIFO) 的效果了。 再回到剛才接聽插撥電話的例子,正好就是先進後出的例子!最後插撥的先結束對話,最早打來的最慢結束對話。接下來讓我們看看,堆疊實際運作的情形,會向下面這一張動畫所顯示的:  

Read Full Post »

Posted By Mr. Thursday 在〈二元樹在排序的應用〉裡面,我們提到了演算法就是完成一件事情的步驟,資料結構則是和演算法搭配,讓步驟有運作的東西,像是刮鬍刀的步驟,會運作在刮鬍刀或是插頭上面。「樹」(tree) 是一種資料結構,有樹根樹枝,看起來像是倒立的一棵樹。二元數則是每個節點只有兩個分支的樹。此外,我們可以用二元樹這個資料結構,完成「排序」(sorting) 的演算法。下面是一段各種排序演算法的影片:   除了排序以外,今天要和各位介紹,當我們把資料用一棵樹排序之後,要如何進行搜尋?排序或是沒有排序,對搜尋的效率有甚麼樣子的影響?我們先看看下面這兩張圖,左邊是排序過程,右邊是搜尋過程的動畫:

Read Full Post »

Posted By Mr. Thursday 在以前的文章裡面有幾次有提到「演算法」(Algorithm),可以把他想程式完成一件事情所需要的步驟,可能包含重覆某些步驟、依照條件執行部份步驟、或是從頭到尾執行固定的步驟。然而演算法通常需要資料結構的配合。不是主修計算機的讀者,也許不知道資料結構是甚麼東西,即使我說資料結構的英文是 Data Structure,可能還是沒辦法了解「資料結構」代表的意思。簡單地說,演算法是完成一件事情的步驟,那麼資料結構就是這些步驟作用的物品,譬如說刮鬍子,可能要先插插頭,準備鏡子,然後開始刮鬍子。但是如果沒有插座,沒有鏡子,沒有刮鬍刀,或是沒有鬍子,這些步驟就沒有東西可以作用了。因此演算法和資料結構,有一點點類似軟體和硬體的對應,只不過資料結構並不是完全屬於硬體的角色就是了。接下來我們就來看一下某些資料結構,尤其是樹 (tree) 的結構,以及不同的拜訪順序,產生的效果。  

Read Full Post »