免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 5634 | 回复: 21

[算法] 发个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-07 13:04 |显示全部楼层
本帖最后由 siseniao 于 2012-12-07 13:09 编辑
  1. typedef int (__stdcall *LISTDIRCALLBACK)(int type,char *fullpath,char *name,void *userdata);
  2. typedef struct dirs
  3. {
  4.         char *file;
  5.         struct dirs *father;
  6.         struct dirs  *child;
  7.         struct dirs *next;
  8.        
  9. } dirs_t;

  10. void DelTree(dirs_t *peer)   //销毁目录树函数
  11. {
  12.     dirs_t *p=peer;
  13.         dirs_t *tmp;
  14.         while(p->father!=NULL||(p->child!=p&&p->child!=NULL))
  15.         {
  16.                 if(p->child!=NULL&&p->child!=p)
  17.                 {
  18.                         p=p->child;
  19.                         p->father->child=p->next;
  20.                         // continue;
  21.                 }
  22.                 else if(!(p->child!=NULL&&p->child!=p)&&p->father!=NULL)
  23.                 {
  24.                         tmp=p;
  25.                         if(p->next!=NULL)
  26.                         {
  27.                                 p=p->next;
  28.                                 p->father->child=p->next;
  29.                         }
  30.                         else
  31.                         {
  32.                                 p=p->father;
  33.                                 p->child=NULL;
  34.                                
  35.                         }
  36.                         free(tmp->file);
  37.                         free(tmp);
  38.                 }
  39.                 else
  40.                 {
  41.                         free(p);
  42.                         break;
  43.                 }
  44.         }
  45. }
复制代码
  1. int DoProcFile(LISTDIRCALLBACK CallbackFun,char *path,char *filename,void *userdata,int type)
  2. {
  3.         char *fullpath;
  4.         if(CallbackFun!=NULL)
  5.         {
  6.                 fullpath=(char *)malloc((strlen(path)+strlen(filename)+5)*sizeof(char));
  7.                 if(fullpath==NULL)
  8.                 {
  9.                         return -2;
  10.                 }
  11.                 strcpy(fullpath,path);
  12.                 strcat(fullpath,"\\");
  13.                 strcat(fullpath,filename);
  14.                 if(CallbackFun(type,fullpath,filename,userdata)==-1)
  15.                         return -1;
  16.                
  17.                 free(fullpath);
  18.         }
  19.         return 0;
  20. }
复制代码
  1. int __stdcall DirListAll(char *topdir,LISTDIRCALLBACK CallbackFun,void *userdata)                       //功能函数
  2. {
  3.         dirs_t *top,*p,*pfather,*tmp;
  4.         int callret;
  5.         WIN32_FIND_DATA FindFileData;
  6.         HANDLE hFind = INVALID_HANDLE_VALUE;
  7.         int firstflag;   //下行标志
  8.        
  9.         char *pathname;
  10.         int  pathsize;
  11.         char *ptmp;
  12. //        int num=0;
  13.         if(topdir==NULL)
  14.                 return -1;
  15.        
  16.         top=(dirs_t *)malloc(sizeof(dirs_t));
  17.         if(top==NULL)
  18.                 return -1;
  19.        
  20.         top->file=topdir;
  21.         top->father=NULL;
  22.         top->next=NULL;
  23.         top->child=top;
  24.         p=top;
  25.         do
  26.         {
  27.                 firstflag=0;
  28.                 if(p->father!=NULL&&p->child==NULL)//上行判断
  29.                 {
  30.                         if(p->next!=NULL)
  31.                         {
  32.                                 tmp=p;
  33.                                 p=p->next;
  34.                                 p->father->child=p->next;
  35.                                 free(tmp->file);
  36.                                 free(tmp);
  37.                         }
  38.                         else
  39.                         {
  40.                                 tmp=p;
  41.                                 p=p->father;
  42.                                 p->child=NULL;
  43.                                 free(tmp->file);
  44.                                 free(tmp);
  45.                                 continue;
  46.                         }
  47.                 }
  48.                
  49.                 tmp=p;
  50.                 pathsize=strlen(top->file);
  51.                 while(tmp!=top)
  52.                 {
  53.                         pathsize+=strlen(tmp->file);
  54.                         pathsize++;
  55.                         tmp=tmp->father;
  56.                 }
  57.                 pathname=(char *)malloc((pathsize+6)*sizeof(char));
  58.                 if(pathname==NULL)
  59.                 {
  60.                         DelTree(p);
  61.                         return -1;
  62.                 }
  63.                 tmp=p;
  64.                
  65.                 strcpy(pathname,top->file);
  66.                 ptmp=pathname+pathsize;
  67.                 while(tmp!=top)
  68.                 {
  69.                         ptmp=ptmp-strlen(tmp->file);
  70.                         memcpy(ptmp,tmp->file,strlen(tmp->file));
  71.                         memcpy(ptmp-1,"\\",1);
  72.                         ptmp--;
  73.                         tmp=tmp->father;
  74.                 }
  75.                 pathname[pathsize]='\0';
  76.                 strcat(pathname,"\\*.*");
  77.                 hFind = FindFirstFile(pathname, &FindFileData);
  78.                 if(hFind!=INVALID_HANDLE_VALUE)
  79.                 {
  80.                         do       
  81.                         {
  82.                                 if(strcmp(FindFileData.cFileName,".")!=0&&strcmp(FindFileData.cFileName,"..")!=0)
  83.                                 {
  84.                                         if(FindFileData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
  85.                                         {
  86.                                                 if(!firstflag)                                             //下行标志
  87.                                                 {
  88.                                                         p->child=(dirs_t *)malloc(sizeof(dirs_t));
  89.                                                         if(p->child==NULL)
  90.                                                         {
  91.                                                                 DelTree(p);
  92.                                                                 FindClose(hFind);
  93.                                                                 free(pathname);
  94.                                                                 return -1;
  95.                                                         }
  96.                                                         pfather=p;
  97.                                                         p=p->child;
  98.                                                         p->father=pfather;
  99.                                                         firstflag=1;
  100.                                                 }
  101.                                                 else
  102.                                                 {
  103.                                                         p->next=(dirs_t *)malloc(sizeof(dirs_t));
  104.                                                         if(p->next==NULL)
  105.                                                         {
  106.                                                                 DelTree(p);
  107.                                                                 FindClose(hFind);
  108.                                                                 free(pathname);
  109.                                                                 return -1;
  110.                                                         }
  111.                                                         p=p->next;
  112.                                                 }
  113.                                                 p->father=pfather;
  114.                                                 p->next=NULL;
  115.                                                 p->child=p;
  116.                                                 p->file=(char *)malloc((strlen(FindFileData.cFileName)+1)*sizeof(char));
  117.                                                 if(p->file==NULL)
  118.                                                 {
  119.                                                         DelTree(p);
  120.                                                         FindClose(hFind);
  121.                                                         free(pathname);
  122.                                                         return -1;
  123.                                                 }
  124.                                                 strcpy(p->file,FindFileData.cFileName);
  125.                                                 pathname[pathsize]='\0';
  126.                                                
  127.                                                 callret=DoProcFile(CallbackFun,pathname,FindFileData.cFileName,userdata,TYPE_DIR);
  128.                                                 if(callret<0)
  129.                                                 {
  130.                                                         DelTree(p);
  131.                                                         free(pathname);
  132.                                                         FindClose(hFind);
  133.                                                         if(callret==-1)
  134.                                                                 return 0;
  135.                                                         else
  136.                                                                 return -1;
  137.                                                 }
  138.                                         }
  139.                                         else
  140.                                         {
  141.                                                 pathname[pathsize]='\0';
  142.                                                 callret=DoProcFile(CallbackFun,pathname,FindFileData.cFileName,userdata,TYPE_FILE);
  143.                                                 if(callret<0)
  144.                                                 {
  145.                                                         DelTree(p);
  146.                                                         free(pathname);
  147.                                                         FindClose(hFind);
  148.                                                         if(callret==-1)
  149.                                                                 return 0;
  150.                                                         else
  151.                                                                 return -1;
  152.                                                 }
  153.                                                
  154.                                         //        num++;
  155.                                         }
  156.                                 }
  157.                         }
  158.                         while(FindNextFile(hFind, &FindFileData));
  159.                 }
  160.                 FindClose(hFind);
  161.                 free(pathname);
  162.                 if(firstflag!=0)  //进入子目录
  163.                 {
  164.                         //  updownflag=0;
  165.                         p=p->father->child;
  166.                         p->father->child=p->next;
  167.                 }
  168.                 else if(firstflag==0&&p->father!=NULL)
  169.                 {
  170.                         tmp=p;
  171.                         if(p->next==NULL) //进入父目录
  172.                         {
  173.                                 p=p->father;
  174.                                 p->child=NULL;
  175.                         }
  176.                         else  //进入同级目录
  177.                         {
  178.                                 p=p->next;
  179.                                 p->father->child=p->next;
  180.                         }
  181.                         free(tmp->file);
  182.                         free(tmp);
  183.                 }
  184.                 else
  185.                 {
  186.                         break;
  187.                 }
  188.         }while(p->father!=NULL||p->child!=NULL);
  189.   free(top);
  190. //printf("共%d个文件\n",num);
  191. return 0;
  192. }
复制代码

论坛徽章:
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-07 13:10 |显示全部楼层
本帖最后由 siseniao 于 2012-12-07 13:10 编辑

测试代码:
  1. int CALLBACK CallbackFun(int type,char *fullpath,char *name,void *userdata)
  2. {
  3.         switch(type)
  4.         {
  5.         case TYPE_FILE:
  6.                 printf("<FILE> %s\n",name);
  7.                 break;
  8.         case TYPE_DIR:
  9.                 printf("<DIR> %s\n",fullpath);
  10.                 break;
  11.         default:
  12.                 break;
  13.         }
  14.         return 0;
  15. }

  16. int main(int argc, char* argv[])
  17. {

  18.     char userdata[10];       

  19.         for(int i=0;i<10;i++)
  20.         {
  21.                 DirListAll("e:",CallbackFun,(void *)userdata);
  22.                 getchar();
  23.         }

  24.         return 0;
  25. }
复制代码

论坛徽章:
0
发表于 2012-12-07 13:16 |显示全部楼层
关于目录遍历,自已从根路径开始跑一下,看看效果怎么样再说。

论坛徽章:
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-07 13:20 |显示全部楼层
好吧,早就把自己电脑所有的磁盘都跑过了,几十万个目录没问题的,没有内存泄露

论坛徽章:
59
2015年亚洲杯之约旦
日期:2015-01-27 21:27:392015年亚洲杯之日本
日期:2015-02-06 22:09:41拜羊年徽章
日期:2015-03-03 16:15:432015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:50:282015元宵节徽章
日期:2015-03-06 15:50:392015年亚洲杯之阿联酋
日期:2015-03-19 17:39:302015年亚洲杯之中国
日期:2015-03-23 18:52:23巳蛇
日期:2014-12-14 22:44:03双子座
日期:2014-12-10 21:39:16处女座
日期:2014-12-02 08:03:17天蝎座
日期:2014-07-21 19:08:47
发表于 2012-12-07 14:53 |显示全部楼层
lzv5, 871b

论坛徽章:
0
发表于 2012-12-07 22:18 |显示全部楼层
如果把文件目录的组织结构看成一棵树的话,进而把树看成图的话,那么遍历它,通常的两种方法,就是深度遍历跟广度遍历

论坛徽章:
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-08 11:58 |显示全部楼层
回复 6# 耗资喜欢猫

遍历不是要先建立整个树然后每个都走一遍,这样内存开销太大,通常做法就是把已经遍历过且不再用到的目录所占的空间释放掉,例如最下级目录,遍历完就销毁整个节点下的树
   

论坛徽章:
0
发表于 2012-12-08 12:33 |显示全部楼层
siseniao 发表于 2012-12-08 11:58
回复 6# 耗资喜欢猫

遍历不是要先建立整个树然后每个都走一遍,这样内存开销太大,通常做法就是把已经遍 ...


这取决于你需要将遍历得到的文件信息做何种处理,如果单纯只是需要得到文件的路径信息的话,不需要多少内存

论坛徽章:
0
发表于 2012-12-08 12:35 |显示全部楼层
而且你也不需要去建立那个树,它本身就是一个树型结构。

论坛徽章:
4
水瓶座
日期:2013-09-06 12:27:30摩羯座
日期:2013-09-28 14:07:46处女座
日期:2013-10-24 14:25:01酉鸡
日期:2014-04-07 11:54:15
发表于 2012-12-09 20:47 |显示全部楼层
用个栈就解决了.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP