[算法]一个非递归的目录历遍算法[原创]

韩三普

　　在群里聊天时讨论到递归的问题，我觉得所有递归的实现都可以化为不采用递归的实现，比如这个目录历遍，本来想用数据库来做的，后来想想太麻烦了，就写了这个，把所有信息都存在数组中了。当然我这个算法是目录树的核心算法部分，如果想有直接的表现，结合js跟据这个数组，操作dom是最快，最容易的一种方法。
　　友情邀请，欢迎来群里讨论PHP。
[群名]：PHP focus
[号]：2558759

1. 
   
2. <?php
   
3. //author:HanSanpu(韩三普)
   
4. $dir[0][-1] = './';
   
5. $out = $dir;
   
6. $num = 1;
   
7. $layer = 0;
   
8. while ($out = new_dir($out, $num)) {
   
9.     ++$layer;
   
10.     $layer_dirs[$layer] = $out;
    
11. }
    
12. echo "<pre>";
    
13. var_dump($layer_dirs);
    
14. echo "</pre>";
    
15. function new_dir($in, &$num) {//in and out
    
16.     $out = array();
    
17.     foreach ($in as $k=>$v) {
    
18.             $s = current($v);
    
19.             $out = $out + dir_maping($s, $k, $num);
    
20.     }
    
21.     return $out;
    
22. }
    
23. function dir_maping($root_dir, $p, &$num) {
    
24.     $fdir = array();
    
25.     if (is_dir($root_dir)) {
    
26.         if ($DH = opendir($root_dir)) {
    
27.             while (($file = readdir($DH)) !== false) {
    
28.                 if (is_dir($root_dir.$file)) {
    
29.                     if ('.' != $file && '..' != $file) {
    
30.                         $fdir[$num][$p] = $root_dir.$file.'/';
    
31.                         $num++;
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36.     }
    
37.     return $fdir;
    
38. }
    
39. ?>
    

复制代码

　　
　　这种算法与递归的不同在于，函数闭合上，如果到N层递归不闭合，可想而知会消耗多少内存，系统会垮掉的。

[ 本帖最后由 韩三普 于 2006-5-28 16:19 编辑 ]

Namelessxp

这个，跟递归有什么区别吗？

韩三普

区别在于这个在循环的过程中函数每次都马上可以闭合，而递归函数不能闭合

韩三普

递归的是函数需要调用自身。也就是说一个直接调用自己或通过一系列的函数调用语句间接地调用自己的函数成为递归函数。根据调用方式的不同，它分为直接递归和间接递归。而很明显，我写的这个算法没有涉及到调用自身的部分。是在一系列循环中完成的。

macleo

太高深了!不懂啊

hightman

PHP的递归不是硬性限制,而是内存用完了就不行了

缺省内存用量比较少

hightman

递归就是比较漂亮的运用了 栈, 无论你怎么改都会用到栈的, 即后进先出原则.

所以也没什么特别的意义

韩三普

　　首先，很赞成你说的存储概念。

原帖由 Yarco 于 2006-5-28 11:37 发表
假如递归是数组形式，那么只需要数组形式的存储; 假如递归是树的形式，那么就作成树的形式的存储，没什么难的.

　　在php中，应用递归时树的形式的存储是什么意思？能否解释一下上面的话。我觉得PHP 中的数组实际上是一个有序图，也可以很容易地模拟树。但是不管怎么存，还不是要用数组存吗？你分出的“树的形式的存储”仍然是“数组形式的存储”，并不是两个概念。至于要不要模拟树，那就是输出的事了。

递归会有效是因为每次递归都会多出了几个局部变量做存储.所以，要转换成非递归很简单， 额外做个存储就行了.

　　是这样的，递归多出的局部变量存储是要到算法结束才能销毁，这是个比较大的缺点。如果需要递归的层次比较深，并且数据量比较大，不应该采用这种方法。其实在php版我们研究的所有算法，可能前人都研究过了，毕竟，我们不是搞算法的，如果这样，算法问题就不用在这里发了。这里写一写这个，一是玩玩，二是让大家也讨论一下算法问题，算法很重要的，谁有更有意思的发上来玩玩呀，呵呵。

[ 本帖最后由 韩三普 于 2006-5-28 16:42 编辑 ]

crazysoul

递归->非递归的核心:自建入栈和出栈操作.
一般是用数组做栈.
有个细节,PHP的数组深度有没限制?