iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 13
0

資料結構 - 樹和堆疊

今天會講到資料結構中比較複雜的部分,
但是這些複雜的結構也可以用很簡單的方式,理解到他們的機制,
現在來看一下吧~

樹 ( tree )

樹資料結構圖,就是跟大家都知道的『 樹 』很相似(不知道樹長怎樣的...痾...)
附上一張來自維基百科的『 樹資料結構截圖 』:
https://ithelp.ithome.com.tw/upload/images/20181027/20107758CPapSyZ1P9.png

有沒有跟樹很像呀?
他的特色就是每筆資料,都是一個『節點』,英文稱作 node ,
例如圖片中 『 A 』 這個節點繼續往下延伸,那這個『 A 』就會是一個『父節點』,
延伸下去的 B 和 C 就是『 子節點 』,
那 C 後來又有所延伸,那他又會是 G 和 H 的『 父節點 』,
也會是 A的『子節點』。
利用程式寫起來可以像是這樣:


class Company
	attr_accessor :ceo_name
	def initialize(name)
		@position = Position.new(name)
	end
end

class Position
	attr_accessor :name
	attr_accessor :left, :right
	
	def initialize(name)
		@member_name = name
		left = nil
		right = nil
	end
end

這是一個模擬公司組織結構的樹狀資料結構,
公司下都會有個『位置』的節點,然後每個位置下都會再有其他的位置,
分別是 left 和 right 來儲存這個位置。
而你看到的 nil ,就是 ruby 中 null 的意思~

堆疊 ( stack )

堆疊,是一種類似陣列的資料儲存方式,
只是他比較像在堆樂高,是把資料從下面往上排,
類似這樣的方式:

https://ithelp.ithome.com.tw/upload/images/20181027/20107758GBJ6kp7l9R.png

讀者也會注意到,圖中有『push』和『pop』兩個詞彙,
push 是把資料放入堆疊中的意思,pop 則是把資料從堆疊中取出之意。
除了堆疊外,很類似的資料結構也有佇列 (Quene), 堆( Heap ) 等等,

有興趣更深入的讀者,歡迎參考;
(Array)、堆疊(Stack)、佇列(Queue) - Mark Lin Blog - Logdown

Java 面試 02 - JVM 的 Stack 和 Heap

那 Stack 的用處為何呢?
目前最常使用在『錯誤訊息』的傳遞上,
當程式出錯時,會提供錯誤發生在程式碼的第幾行,
但在大型的程式中,可能這樣的資訊還不夠,
因此會把『使用發生錯誤程式』的『程式碼』給在列印出來。
聽起來應該有點玄唷~
大家對 function 函式設計的理念還有印象嗎?
我們會用 function 去包裝不同的程式,
而這個 function 可能是其他 function 執行的,
因此發生錯誤的程式碼,外面可能包了十幾層,
而造成錯誤的真實原因,可能是在倒數第 3, 4 行的位置。

來看看下面這個真實的錯誤堆疊案例:
https://ithelp.ithome.com.tw/upload/images/20181027/20107758COW4Obsq6c.png

最上面的,就是 stack 內最新的資料,也就是程式碼錯誤發生的地方,
是在 front_controller.rb 第 248 行中, tender 這個函式內,
看到第二行,tender 這個函式,又是 basic_implicit_render 第 4 行的 send_action 函式執行的,
剩下的以此類推...
因此可以很方便的知道說,資料的順序相依性~
這樣大家能懂堆疊了嗎?

結論

筆者這兩天只講解了資料結構最常用的幾種,
並且也只提到這幾種中,基本常用的概念,
分別都還是有一些進階的概念,像樹( tree )也會有二元樹、完全二元樹等等不同的類型,
對於讀者們來說,最重要的概念不是哪種資料結構最好,
而是懂得針對不同環節,去使用不同的資料結構儲存資料,
才能展現更好的程式效能,並進一步的增進使用者體驗喔~~

如果有任何問題,或是指證文中的錯誤,歡迎寄信給我或留言在下面喔~


上一篇
[Day12] 資料結構 - 陣列和雜湊
下一篇
[Day14] 演算法
系列文
菜鳥後端工程師的第一門課30

尚未有邦友留言

立即登入留言