Блог

Я пытаюсь создать программу, использующую C и WIN32 API для выполнения итераций по деревьям каталогов. Кто-нибудь может помочь изменить код, чтобы он работал без рекурсивной функции?

 void WINAPI IterateFiles(char* Directory)
{
    HANDLE hFind;
    WIN32_FIND_DATA Win32FindData;

    char SearchName[MAX_PATH], FullPath[MAX_PATH];

    memset(SearchName, 0, sizeof(SearchName));
    memset(amp;Win32FindData, 0, sizeof(WIN32_FIND_DATA));

    sprintf(SearchName, "%s\*", Directory);

    hFind = FindFirstFileA(SearchName, amp;Win32FindData);

    if (hFind != INVALID_HANDLE_VALUE)
    {
        while (FindNextFileA(hFind, amp;Win32FindData))
        {
            if (Win32FindData.cFileName[0] == '.')
            {
                continue;
            }

            memset(FullPath, 0, sizeof(FullPath));
            sprintf(FullPath, "%s\%s", Directory, Win32FindData.cFileName);

            if (Win32FindData.dwFileAttributes amp; FILE_ATTRIBUTE_DIRECTORY)
            {
                MessageBoxA(NULL, FullPath, "Directory", MB_OK);
                IterateFiles(FullPath);
            }

            else
            {
                MessageBoxA(NULL, FullPath, "File", MB_OK);
            }

        }

        FindClose(hFind);
    }
}
  

Базовый подход заключается:

1. Реализуйте коллекцию (стек или очередь, в зависимости от того, требуется ли вам первый обход по глубине или ширине) каталогов для поиска
2. Инициализируйте его корневым каталогом для поиска
3. Запустите цикл, который выполняется до тех пор, пока он не станет пустым, каждый раз извлекая один каталог, повторяя его содержимое и добавляя любые новые каталоги, обнаруженные во время итерации, в коллекцию (которые будут обрабатываться один за другим, когда цикл завершит обработку каждого каталога)

По сути, это просто выполнение той же работы, которую рекурсия сделала бы для вас, но ограничивает область действия стека, который вы поддерживаете, информацией каталога, без репликации всего стека функций.

Существует два конкретных метода: обход в ширину, реализованный с помощью очередей, и обход в глубину, реализованный со стеками.

Я подробно объясняю, как использовать очереди (аналогично использованию стеков):

1. Сначала добавьте путь к этой папке в очередь.
2. Определите, больше ли количество элементов в очереди, чем 0. Если количество элементов больше 0, перейдите в папку, соответствующую первому элементу. Если в этой папке есть папка, добавьте путь к этой папке в очередь. После сканирования папки первый элемент извлекается из очереди, и второй шаг продолжается. Если в очереди нет элемента, выполняется третий шаг.
3. Выйдите из цикла.

Вот пример, который я реализовал на C :

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

void QueryFileCounts(string Path)
{
    queue<std::string> qFolders;
    qFolders.push(Path);

    WIN32_FIND_DATA findResu<
    HANDLE handle = NULL;

    while (qFolders.size() > 0)
    {
        std::string tempFolder = qFolders.front();
        tempFolder.append("\*.*");
        handle = FindFirstFile(tempFolder.c_str(), amp;findResult);
        do
        {
            if (findResult.dwFileAttributes amp; FILE_ATTRIBUTE_DIRECTORY)
            {
                if (lstrcmp(".", findResult.cFileName) == 0 || lstrcmp("..", findResult.cFileName) == 0)
                {
                    continue;
                }
                tempFolder = qFolders.front();
                tempFolder.append("\").append(findResult.cFileName);
                qFolders.push(tempFolder);
            }
            else {
                cout << findResult.cFileName << endl;
            }
        } while (FindNextFile(handle, amp;findResult));
        qFolders.pop();
    }
    if (handle)
    {
        FindClose(handle);
        handle = NULL;
    }
}

int main()
{
    QueryFileCounts("D:\test");
    return 0;
}
  

Редактировать:

Существует много способов реализации очередей и стеков. Я рекомендую вам использовать связанные очереди (или связанные стеки). Вы можете найти множество способов их реализации в Интернете. Я предоставлю способ моей реализации для вашей справки.

Вот пример, реализованный на чистом C:

 #include <stdio.h>
#include <Windows.h>
#include <string.h>
struct Link 
{
    char data[1024];
    struct Link* next;
};

struct Queue
{
    struct Link* front;
    struct Link* rear;
    int size;
};

void QueueInit(struct Queue* queue)
{
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

int QueueEmpty(struct Queue* queue)
{
    return (queue->size == 0);
}

void QueuePush(struct Queue* queue, const char * data)
{
    struct Link* node;
    node = (struct Link*)malloc(sizeof(struct Link));
    if (node)
    {
        strcpy(node->data, data);
        node->next = NULL;
        if (QueueEmpty(queue))
        {
            queue->front = node;
            queue->rear = node;
        }
        else
        {
            queue->rear->next = node;
            queue->rear = node;
        }
          queue->size;
    }
    
}

int QueuePop(struct Queue* queue)
{
    if (QueueEmpty(queue))
    {
        return 0;
    }
    struct Link* tmp = queue->front;
    queue->front = queue->front->next;
    free(tmp);
    --queue->size;
    return 1;
}

void QueueDestroy(struct Queue* queue)
{
    struct Link* tmp;
    while (queue->front)
    {
        tmp = queue->front;
        queue->front = queue->front->next;
        free(tmp);
    }
}


void QueryFileCounts(const char * Path)
{
    struct Queue qFolders;
    QueueInit(amp;qFolders);
    QueuePush(amp;qFolders, Path);
    WIN32_FIND_DATA findResu<
    HANDLE handle = NULL;

    while (qFolders.size > 0)
    {
        char tempFolder[1024];
        strcpy(tempFolder, qFolders.front->data);
        sprintf(tempFolder, "%s\*.*", tempFolder);
        handle = FindFirstFile(tempFolder, amp;findResult);
        do
        {
            if (findResult.dwFileAttributes amp; FILE_ATTRIBUTE_DIRECTORY)
            {
                if (lstrcmp(".", findResult.cFileName) == 0 || lstrcmp("..", findResult.cFileName) == 0)
                {
                    continue;
                }
                strcpy(tempFolder, qFolders.front->data);
                sprintf(tempFolder, "%s\%s", tempFolder, findResult.cFileName);
                QueuePush(amp;qFolders, tempFolder);
            }
            else {
                printf("%sn", findResult.cFileName);
            }
        } while (FindNextFile(handle, amp;findResult));
        QueuePop(amp;qFolders);
    }
    if (handle)
    {
        FindClose(handle);
        handle = NULL;
    }
    QueueDestroy(amp;qFolders);
}

int main()
{
    QueryFileCounts("D:\test");
    return 0;
}