作者yauhh (哟)
看板Programming
标题Re: [问题] 适合递回的资料结构
时间Tue Mar 22 01:44:49 2011
※ 引述《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
1F：推 VictorTom:y大的解释感觉更像Divide & Conquer@@"111.240.167.159 03/22 02:05
2F：→ VictorTom:Wiki上的简意是: "functions calling111.240.167.159 03/22 02:08
3F：→ VictorTom:themselves". 只是D&C的实作中Recur常被111.240.167.159 03/22 02:09
4F：→ VictorTom:使用就是了:)111.240.167.159 03/22 02:10
5F：推 fjf1980:y大真是强者， 感谢你的解释 219.84.57.222 03/22 10:00
6F：→ yauhh:不敢当,还没算多强218.160.208.226 03/22 20:18
7F：→ yauhh:V,你显然抓错方向了. 递回本来就是D&C,但递218.160.208.226 03/22 20:19
8F：→ yauhh:回重要的是大问题与小问题的结构相同. 所以218.160.208.226 03/22 20:19
9F：→ yauhh:可说凡递回必定是D&C,但是并不是任何D&C都是218.160.208.226 03/22 20:20
10F：→ yauhh:递回.218.160.208.226 03/22 20:20
11F：推 VictorTom:小弟我的意思是, 您对Recur的解释其实是 220.134.18.177 03/22 21:43
12F：→ VictorTom:Wiki上D&C的解释; Recur是一种实现它的 220.134.18.177 03/22 21:44
13F：→ VictorTom:方式. 其实小弟的疑问就是您最後说的, 220.134.18.177 03/22 21:45
14F：→ VictorTom:"递回必是D&C", 恕小弟再想想先:) 220.134.18.177 03/22 21:46
15F：→ yauhh:我也觉得这样回答有点松散. 原问题是问:218.160.208.226 03/22 21:50
16F：→ yauhh:最适合解决递回问题的结构. 并不只是递回程218.160.208.226 03/22 21:50
17F：→ yauhh:式用到,而是一种能够帮助递回问题解决的结构218.160.208.226 03/22 21:51
18F：→ yauhh:这样想如果不是stack就是queue或tree.218.160.208.226 03/22 21:51
19F：推 arcred:这样看任何一个有序集成的结构都可以是答案 68.98.169.112 03/23 11:26
20F：→ arcred:不过我满好奇答案的.. 希望不是stack XD 68.98.169.112 03/23 11:28
21F：推 purpose:>都可以是答案 用 queue 也适当? 124.8.130.53 03/23 11:45
22F：推 arcred:嗯...的确FIFO好像不适合 @@ 68.98.169.112 03/23 12:21