Re: [問題] 適合遞迴的資料結構
※ 引述《fjf1980 (聽說 侯佩岑是豬頭)》之銘言：
: ※ [本文轉錄自 C_and_CPP 看板 #1DXuRGWq ]
: 作者: fjf1980 (聽說 侯佩岑是豬頭) 看板: C_and_CPP
: 標題: [問題] 適合遞迴的資料結構
: 時間: Tue Mar 22 01:11:40 2011
: 忘記哪一年的一國考題目：
: 適合用來解決遞迴 (recursion) 問題的資料結構為何？其如何運作？
: 我覺得是陣列
: 因為有很多會用到遞迴演算法的結構都用陣列，像是二元樹的運算
: 還有陣列也剛好可以一格一格跳下去做運算
: 請問各位高手對這個問題有沒有些想法，建議，希望指教一下，感謝！
: ps.找到問題了: 適合用來解決遞迴 (recursion) 問題的資料結構為何？其如何運作？
想了一想覺得這個問題好爛. 如果說答案是 stack, 並且只是因為寫 C 語言遞迴
會用到系統堆疊的話,那真是超級沒哏的問答法.
何謂遞迴問題? 就是一個大問題可以拆成一些小問題,小問題的格式與大問題一模一樣.
( 於是可以解決小問題,把小問題的答案放在一起就解決大問題. )
明確地說,適合解遞迴問題的資料結構,當然是任何具備遞迴性質的資料結構啊!
用資料結構直接對應遞迴問題的問題結構,非常容易解決問題.
遞迴的資料結構,就是大結構可以拆成小結構,而且大結構與小結構格式一模一樣.
所以只要能把結構遞迴定義就可以了: 基本要注意到 base case 與 recursive case.
於是 stack 是遞迴結構,因為 stack 多加一個資料也是 stack.
( base case: 空集合 )
於是 linked list 也是遞迴結構了, 鏈接串列多加一筆資料,仍是鏈接串列.
( base case: 空節點或首節點 )
Tree 一定是遞迴結構,任何一棵樹的子項也是樹.
( base case: 空節點 )
陣列,當然也是遞迴結構,因為陣列多加一格,還是陣列.
( base case: 長度為 0 的陣列 )
--
/yau
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.209.55
推
03/22 02:05, , 1F
03/22 02:05, 1F
→
03/22 02:08, , 2F
03/22 02:08, 2F
→
03/22 02:09, , 3F
03/22 02:09, 3F
→
03/22 02:10, , 4F
03/22 02:10, 4F
推
03/22 10:00, , 5F
03/22 10:00, 5F
→
03/22 20:18, , 6F
03/22 20:18, 6F
→
03/22 20:19, , 7F
03/22 20:19, 7F
→
03/22 20:19, , 8F
03/22 20:19, 8F
→
03/22 20:20, , 9F
03/22 20:20, 9F
→
03/22 20:20, , 10F
03/22 20:20, 10F
推
03/22 21:43, , 11F
03/22 21:43, 11F
→
03/22 21:44, , 12F
03/22 21:44, 12F
→
03/22 21:45, , 13F
03/22 21:45, 13F
→
03/22 21:46, , 14F
03/22 21:46, 14F
→
03/22 21:50, , 15F
03/22 21:50, 15F
→
03/22 21:50, , 16F
03/22 21:50, 16F
→
03/22 21:51, , 17F
03/22 21:51, 17F
→
03/22 21:51, , 18F
03/22 21:51, 18F
推
03/23 11:26, , 19F
03/23 11:26, 19F
→
03/23 11:28, , 20F
03/23 11:28, 20F
推
03/23 11:45, , 21F
03/23 11:45, 21F
推
03/23 12:21, , 22F
03/23 12:21, 22F
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
