首页 1 2 3 4 5 6 7

非递归实现文件夹遍历

之前有个电话面试，其中一道题就是：用非递归的方式实现文件夹遍历？在电面的时候没有答出来，过后分分钟就想到了答案，因为之前自己实现过按层序的方式打印一棵树，用的也是非递归的方式，现在遍历文件夹不就是遍历这颗树吗！怎么就没想出来呢！在这里简单的记录下，用了C#和C++两个版本实现。

我这里的实现的功能是：用非递归的方式获得一个文件夹中文件的个数。

思路简单介绍：

1：先将这个文件夹的路径加入一个队列中；

2：判断队列的元素个数是否大于0，如果元素个数大于0，遍历第一个元素对应的文件夹，用一个变量fileCounts记录这个文件夹中文件的个数，如果这个文件夹中有文件夹，就将这个文件夹的路径加入队列中，扫描完一个文件夹后,第一个元素弹出队列，继续执行第二步，如果队列中没有元素，就执行第三步；

3：退出循环

C++版如下：

#include "stdafx.h"
#include <Windows.h>
#include <iostream>
#include <queue>
using namespace std;

int QueryFileCounts( LPCTSTR Path )
{
    queue<std::wstring> qFolders; 
    qFolders.push(Path);

    int fileCounts = 0;   
    WIN32_FIND_DATA findResult;
    HANDLE handle=NULL;
      
    while(qFolders.size()>0)
    { 
        std::wstring tempFolder = qFolders.front();
        tempFolder.append(L"\\*.*");
        handle = FindFirstFile(tempFolder.c_str(), &findResult);
        do
        {   
            if (findResult.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
            {
                if (lstrcmp(L".",findResult.cFileName)==0 || lstrcmp(L"..",findResult.cFileName)==0)
                {
                    continue;
                } 
                tempFolder=qFolders.front();
                tempFolder.append(L"\\").append(findResult.cFileName);
                qFolders.push(tempFolder); 
            }else{
                fileCounts++;
            } 
        }
        while (FindNextFile(handle, &findResult));
        qFolders.pop();
    } 
    if (handle)
    {
        FindClose(handle);
        handle = NULL;
    } 
    return fileCounts;
}

int _tmain(int argc, _TCHAR* argv[])
{
    {    
        cout<< "文件个数："<<QueryFileCounts(L"D:\\feinno\\RunImage")<<endl; 
    }
    system("pause");
    return 0;
}

运行结果如下：

C#版代码如下：

using System;
using System.Collections.Generic;
namespace FileFind
{  
    class Program
    {
        [Serializable, System.Runtime.InteropServices.StructLayout(System.Runtime.InteropServices.LayoutKind.Sequential,
            CharSet = System.Runtime.InteropServices.CharSet.Auto),System.Runtime.InteropServices.BestFitMapping(false)]
        private struct WIN32_FIND_DATA
        {
            public int dwFileAttributes;
            public int ftCreationTime_dwLowDateTime;
            public int ftCreationTime_dwHighDateTime;
            public int ftLastAccessTime_dwLowDateTime;
            public int ftLastAccessTime_dwHighDateTime;
            public int ftLastWriteTime_dwLowDateTime;
            public int ftLastWriteTime_dwHighDateTime;
            public int nFileSizeHigh;
            public int nFileSizeLow;
            public int dwReserved0;
            public int dwReserved1;
            [System.Runtime.InteropServices.MarshalAs(System.Runtime.InteropServices.UnmanagedType.ByValTStr,SizeConst = 260)]
            public string cFileName;
            [System.Runtime.InteropServices.MarshalAs(System.Runtime.InteropServices.UnmanagedType.ByValTStr,SizeConst = 14)]
            public string cAlternateFileName;
        }
        [System.Runtime.InteropServices.DllImport("kernel32.dll", CharSet = System.Runtime.InteropServices.CharSet.Auto, SetLastError = true)]
        private static extern IntPtr FindFirstFile(string pFileName, ref WIN32_FIND_DATA pFindFileData);
        [System.Runtime.InteropServices.DllImport("kernel32.dll",CharSet = System.Runtime.InteropServices.CharSet.Auto,SetLastError = true)]
        private static extern bool FindNextFile(IntPtr hndFindFile, ref WIN32_FIND_DATA lpFindFileData);
        [System.Runtime.InteropServices.DllImport("kernel32.dll", SetLastError = true)]
        private static extern bool FindClose(IntPtr hndFindFile);
 
        static int QueryFileCounts( string Path )
        {
            Queue<string> qFolders=new Queue<string>(); 
            qFolders.Enqueue(Path);
            IntPtr INVALID_HANDLE_VALUE = new IntPtr(-1);
            int fileCounts = 0;   
            WIN32_FIND_DATA FindFileData=new WIN32_FIND_DATA();
            System.IntPtr hFind=INVALID_HANDLE_VALUE;
              
            while(qFolders.Count>0)
            {
                string floder=qFolders.Dequeue(); 
                string tempFolder = floder;
                tempFolder+="\\*.*";
                hFind = FindFirstFile(tempFolder ,ref FindFileData);
                if (hFind == INVALID_HANDLE_VALUE)
                {
                    continue;
                }
                do
                {
                    if ((FindFileData.dwFileAttributes & 0x10) != 0)
                    {
                        if (FindFileData.cFileName.Equals(".") || FindFileData.cFileName.Equals(".."))
                        { 
                            continue;
                        }
                        tempFolder=floder+"\\"+FindFileData.cFileName;
                        qFolders.Enqueue(tempFolder); 
                    }else{
                        fileCounts++;
                    } 
                }
                while (FindNextFile(hFind,ref FindFileData));
            }
            if (hFind != INVALID_HANDLE_VALUE)
            {
                FindClose(hFind);
            } 
            return fileCounts;
        }

        static void Main(string[] args)
        {
            int count=QueryFileCounts(@"D:\\feinno\\RunImage");
            Console.WriteLine("文件个数：" + count );
            Console.Read();
        }
    }
}

运行结果如下：