免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: siseniao

[算法] 发个Win下的非递归目录遍历代码 [复制链接]

论坛徽章:
30
摩羯座
日期:2013-12-23 17:28:38牛市纪念徽章
日期:2015-07-13 11:35:582022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57青铜圣斗士
日期:2015-11-27 17:45:3815-16赛季CBA联赛之天津
日期:2016-02-15 13:44:3615-16赛季CBA联赛之江苏
日期:2018-05-02 16:56:2715-16赛季CBA联赛之辽宁
日期:2018-08-08 13:41:1015-16赛季CBA联赛之深圳
日期:2018-10-02 18:05:0315-16赛季CBA联赛之天津
日期:2019-05-31 15:05:0615-16赛季CBA联赛之北京
日期:2022-06-30 13:34:1115-16赛季CBA联赛之同曦
日期:2022-07-06 19:33:5415-16赛季CBA联赛之吉林
日期:2022-12-28 14:16:22
发表于 2012-12-10 14:02 |显示全部楼层
回复 10# linux_c_py_php

这个是我刚学C的时候练手写的,至于栈之类方法如何使用,恳求大神指点
   

论坛徽章:
0
发表于 2014-07-08 13:00 |显示全部楼层
看你们怎么乱遭的,我给你写个
vector<string>& CreateFileInfo(string &fullpath)
{
        queue<string> tmp;
        static vector<string> v;
        tmp.push(fullpath);
        do {
                _chdir(tmp.front().c_str());
                struct _finddata_t fData;
                long hFile = _findfirst( "*", &fData );

                do{
                        if (strcmp(fData.name, ".") == 0 || strcmp(fData.name, "..") == 0 ) continue;
                        string path =tmp.front() + "\\" + fData.name;
                        _chmod(path.c_str(), _S_IWRITE | _S_IREAD );
                       
                        if(fData.attrib == _A_SUBDIR) tmp.push(path);
                        v.push_back(path);
                       
                }while(_findnext(hFile,&fData) == 0);

                _findclose(hFile);
                tmp.pop();

        } while (!tmp.empty());

        return v;
}

//测试
        vector<string>& v = CreateFileInfo(string("D:\\testdir"));
        for(vector<string>::iterator ite= v.begin();
                ite!=v.end();ite++){
                printf("%s\n",ite->c_str());
        }

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-08 14:58 |显示全部楼层
递归没什么不好。像这种层次确定有限的递归不仅节约内存,而且速度还快。

论坛徽章:
30
摩羯座
日期:2013-12-23 17:28:38牛市纪念徽章
日期:2015-07-13 11:35:582022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57青铜圣斗士
日期:2015-11-27 17:45:3815-16赛季CBA联赛之天津
日期:2016-02-15 13:44:3615-16赛季CBA联赛之江苏
日期:2018-05-02 16:56:2715-16赛季CBA联赛之辽宁
日期:2018-08-08 13:41:1015-16赛季CBA联赛之深圳
日期:2018-10-02 18:05:0315-16赛季CBA联赛之天津
日期:2019-05-31 15:05:0615-16赛季CBA联赛之北京
日期:2022-06-30 13:34:1115-16赛季CBA联赛之同曦
日期:2022-07-06 19:33:5415-16赛季CBA联赛之吉林
日期:2022-12-28 14:16:22
发表于 2014-07-08 16:12 |显示全部楼层
回复 13# cobras


    不知道你用递归试过文件和目录超多的目录没有,默认的栈大小肯定会爆掉的,增大栈不是更浪费内存吗

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-08 17:15 |显示全部楼层
回复 14# siseniao


    不知道你是真么设计递归算法的。目录遍历递归栈空间需求只跟目录深度有关,与广度无关。而且windows默认栈空间是1m。能耗完吗

论坛徽章:
30
摩羯座
日期:2013-12-23 17:28:38牛市纪念徽章
日期:2015-07-13 11:35:582022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:57青铜圣斗士
日期:2015-11-27 17:45:3815-16赛季CBA联赛之天津
日期:2016-02-15 13:44:3615-16赛季CBA联赛之江苏
日期:2018-05-02 16:56:2715-16赛季CBA联赛之辽宁
日期:2018-08-08 13:41:1015-16赛季CBA联赛之深圳
日期:2018-10-02 18:05:0315-16赛季CBA联赛之天津
日期:2019-05-31 15:05:0615-16赛季CBA联赛之北京
日期:2022-06-30 13:34:1115-16赛季CBA联赛之同曦
日期:2022-07-06 19:33:5415-16赛季CBA联赛之吉林
日期:2022-12-28 14:16:22
发表于 2014-07-09 10:03 |显示全部楼层
回复 15# cobras


    递归还能怎么设计,事实就是用递归会崩溃

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-09 15:29 |显示全部楼层
本帖最后由 cobras 于 2014-07-09 16:00 编辑

随手写个通用版的递归目录函数。使用方式超简单。见下面的例子。

  1. #include <windows.h>

  2. #define PATH_SPLITTER        '\\'

  3. int enum_dir(char *path_buf, int path_len, int buff_len, int (*enum_dir_func)(void *data, char *path_buf, int path_len, int buff_len), void *data)
  4. {
  5.         WIN32_FIND_DATA find_data;
  6.         HANDLE hFind;
  7.         int name_len;
  8.         int full_len;

  9.         if (path_len > 0 && path_buf[path_len - 1] == PATH_SPLITTER) {
  10.                 if (path_len + 4 <= buff_len) {
  11.                         strncpy(path_buf + path_len, "*.*", 4);
  12.                         ZeroMemory(&find_data, sizeof(find_data));
  13.                         hFind = FindFirstFile(path_buf, &find_data);
  14.                         if (hFind != INVALID_HANDLE_VALUE) {
  15.                                 do {
  16.                                         if (find_data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
  17.                                                 if (strcmp(find_data.cFileName, ".") == 0
  18.                                                         || strcmp(find_data.cFileName, "..") == 0) {
  19.                                                         continue;
  20.                                                 }
  21.                                         }
  22.                                         name_len = strlen(find_data.cFileName);
  23.                                         if (path_len + name_len <= buff_len) {
  24.                                                 strncpy(path_buf + path_len, find_data.cFileName, name_len);
  25.                                                 full_len = path_len + name_len;
  26.                                                 if (find_data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY) {
  27.                                                         if (full_len + 2 <= buff_len) {
  28.                                                                 path_buf[full_len++] = PATH_SPLITTER;
  29.                                                                 path_buf[full_len] = '\0';
  30.                                                         }else {
  31.                                                                 FindClose(hFind);
  32.                                                                 return -2; /* ERROR: BUFFER OVERFLOW */
  33.                                                         }
  34.                                                 }else {
  35.                                                         if (full_len + 1 <= buff_len) {
  36.                                                                 path_buf[full_len] = '\0';
  37.                                                         }else {
  38.                                                                 FindClose(hFind);
  39.                                                                 return -2; /* ERROR: BUFFER OVERFLOW */
  40.                                                         }
  41.                                                 }
  42.                                         }else {
  43.                                                 FindClose(hFind);
  44.                                                 return -2; /* ERROR: BUFFER OVERFLOW */
  45.                                         }
  46.                                         if ((*enum_dir_func)(data, path_buf, full_len, buff_len) == -1) {
  47.                                                 FindClose(hFind);
  48.                                                 return -4; /* ERROR: USER BREAK */
  49.                                         }
  50.                                 }while (FindNextFile(hFind, &find_data));
  51.                                 FindClose(hFind);
  52.                                 return 0;
  53.                         }
  54.                         return -3; /* ERROR: UNKNOWN PATH */
  55.                 }
  56.                 return -2; /* ERROR: BUFFER OVERFLOW */
  57.         }
  58.         return -1; /* ERROR: INVALID PARAMETERS */
  59. }

  60. #include <stdio.h>

  61. int list_file_func(int *data, char *path_buf, int path_len, int buff_len)
  62. {
  63.         ++ *data;
  64.         printf("%.*s\n", path_len, path_buf);
  65.         if (path_len > 0 && path_buf[path_len - 1] == PATH_SPLITTER) {
  66.                 enum_dir(path_buf, path_len, buff_len, list_file_func, data);
  67.         }
  68.         return 0;
  69. }

  70. int main(void)
  71. {
  72.         char buff[MAX_PATH];
  73.         int path_len;
  74.         int count;

  75.         strcpy(buff, "c:\\");
  76.         path_len = strlen(buff);
  77.         count = 0;
  78.         enum_dir(buff, path_len, MAX_PATH, list_file_func, &count);
  79.         printf("Total %d nodes\n", count);
  80.         return 0;
  81. }
复制代码

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-09 15:30 |显示全部楼层
至少在我的系统中没有崩溃。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-09 15:48 |显示全部楼层
我的C盘共有6万多个结点(包括目录和文件)。没有出现传说中的崩溃。

论坛徽章:
3
15-16赛季CBA联赛之山东
日期:2016-10-30 08:47:3015-16赛季CBA联赛之佛山
日期:2016-12-17 00:06:31CU十四周年纪念徽章
日期:2017-12-03 01:04:02
发表于 2014-07-09 17:11 |显示全部楼层
回复 15# cobras


    正解. 栈会不会爆掉只和递归的深度有关. 就算在递归函数里面放 8K 的局部变量, 要爆掉 1MB 大小的栈, 深度也需要 128. 考虑到调用递归函数前已经有调用链占据了一定的栈空间, 可以进去的目录层次的深度也应该是接近 100+. 系统上有多少深度达到 100 层的目录?... 这么 BT 的深度恐怕一个都没有. 除非出现循环引用, 否则根本就不可能爆栈.

    Linux 系统进程栈大小通常是 8 MB / 10 MB, 这样的栈要爆掉, 真心是程序有问题了.

    另外, 递归真心快, 写起来又顺手, 比那些乱七八糟的渣代码好多了, 实在不行写个手工栈搬到堆上去存总行了吧(手工栈的效率一般低于进程栈).
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP