读书人
栏目▼

怎么用广度优先算法也就是队列实现文件

发布时间： 2013-08-23 15:57:36 作者： rapoo

如何用广度优先算法也就是队列实现文件夹的遍历？
如题:
1.现在需要检索一个文件夹，文件夹里面的子目录有20多W 文件有6W之多。
2.由于文件夹的宽度大，所以适合用广度优先来提高效率。
3.需要用纯C实现！
4.需要有人能提高答案。
谢谢！ 算法 遍历 广度优先
[解决办法]
网上一搜大把的。
[解决办法]
广度优先你需要一个队列结构。

1. 把根文件夹路径放入队列。
2. 从队列中取出一个文件夹路径，获得这个目录下的文件夹和文件列表。
3. 文件夹列表中的文件夹路径一一放入队列。
4. 一一处理文件列表。
5. 如果队列为空，则结束，如果队列不为空，转到第二条。
[解决办法]
是文件夹，就push进队列
是文件，就处理
循环完毕，从队列中pop一个出来，继续。
队列空，完毕。
[解决办法]
system("dir /b /a-d c:\\*.* >d:\\allfiles.txt");
//读文件d:\\allfiles.txt的内容即C:\\下所有文件的名字
system("dir /b /a-d /s c:\\*.* >d:\\allfilesinsub.txt");
//读文件d:\\allfilesinsub.txt的内容即C:\\下所有文件的名字包含子目录
system("dir /b /ad c:\\*.* >d:\\alldirs.txt");
//读文件d:\\alldirs.txt的内容即C:\\下所有子目录的名字
请记住，能用shell命令获取文件、文件夹信息或者操作文件、文件夹最好用shell命令获取或者操作，而不要用各种API获取或者操作，因为当遇到非法文件夹名或非法文件名或非法文件长度、非法文件日期、压缩文件、链接文件、稀疏文件……等各种意料之外的情况时，API会处理的不全面或陷入死循环，而shell命令不会。

[解决办法]
一个队列就搞定的广度搜索啊。
[解决办法]
这是我写的一段代码，相互学习。


#include <windows.h>
#include <stdio.h>

/*A simple queue*/
#define SIZE 256
struct queue
{
char data[SIZE][SIZE];
int head_index;
int tail_index;
int size;
};
typedef struct queue Queue;

Queue q;
void init_queue(Queue *q)
{
q->head_index = 0;
q->tail_index = 0;
q->size = 0;
}

int enter_queue(Queue *q, char *dir)
{
if (q->size == SIZE - 1)
return -1;
q->tail_index ++;
q->size ++;
strncpy(q->data[q->tail_index], dir, SIZE);
return 0; 
 
}

char *del_queue(Queue *q)
{
q->head_index ++;
q->size --;
return q->data[q->head_index];
}

int is_empty_queue(Queue *q)
{
return q->size == 0 ? 1 : 0;
}

/*broad first search the directory*/
void broad_first_search_dir(char *path)
{
char next_path[SIZE];
HANDLE find;
WIN32_FIND_DATA find_file_data;

find = FindFirstFile(path, &find_file_data);
if (find == INVALID_HANDLE_VALUE)
{
printf("failed to find: %d\n", GetLastError());
return;
}

do
{
if (find_file_data.cFileName[0] == '.')
continue;
if (find_file_data.dwFileAttributes == FILE_ATTRIBUTE_DIRECTORY)
{
memset(next_path, 0, SIZE);
strncat(next_path, path, strlen(path) - 2);
strcat(next_path, "\\");
strcat(next_path, find_file_data.cFileName);
strcat(next_path, "\\*");
enter_queue(&q, next_path);
}
else
printf("%s\n", find_file_data.cFileName);
}while (FindNextFile(find, &find_file_data));

while (!is_empty_queue(&q)) 
{
broad_first_search_dir(del_queue(&q));
}
}

int main()
{
init_queue(&q);
broad_first_search_dir("E:\\vm\\*");
return 0;
}

[解决办法]
最近写了复制整个文件夹的，包括子文件夹，一层一层find，自己定义一个栈，是文件夹是push进栈，是文件是处理，循环，直到栈为空。
[解决办法]
以前写过一个，最后简单测试过，没啥问题
#ifndef _DIR_LIST_H_
#define _DIR_LIST_H_

#ifdef  __cplusplus
extern "C" {
#endif

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
#include <errno.h>
#include <dirent.h>

typedef struct file_list_s file_list_t;
struct file_list_s
{
    char file_name[512];
    file_list_t *next;
};

typedef struct cur_dir_s cur_dir_t;
struct cur_dir_s
{
    char dir_name[512];
    file_list_t *dir;
    file_list_t *regular;
    file_list_t *slink;
    cur_dir_t *next; 
 
};

cur_dir_t *dir_init();
int dir_file(cur_dir_t *head, char *file_path);
void dir_info(cur_dir_t *head);
void dir_free(cur_dir_t *head);

cur_dir_t *recursive_dir_file(char *file_path);
void recursive_dir_info(cur_dir_t *head);
void recursive_dir_free(cur_dir_t *head);

void recursive_dir_and_print(char *file_path);


#ifdef __cplusplus
}
#endif


#endif



#include "filelist.h"

//static fix_mpool_t *mem_pool = NULL;
#define POOL_NUM 10000

static void destroy_list(file_list_t *head)
{
    if(!head) return;

    file_list_t *tmp;
    while(head)
    {
        tmp = head->next;
        //fmem_free(mem_pool, head);
        free(head);
        head = tmp;
    }

    return;
}

static void display_file(file_list_t *node)
{
    if(!node) return;

    while(node)
    {
        printf("name : [%s]\n", node->file_name);
        //LOG(LOG_DEBUG, "show list node : [%s]", p->file_name);
        node = node->next;
    }

    return;
}

cur_dir_t *dir_init()
{
    cur_dir_t *tmp = (cur_dir_t *)malloc(sizeof(cur_dir_t));
    if(!tmp)
    {
        fprintf(stderr,"dir_init() failed, Out Of Memory!!!\n");
        abort();
    }
    memset(tmp, 0, sizeof(cur_dir_t));
    tmp->dir = NULL;
    tmp->regular = NULL;
    tmp->slink = NULL;
    tmp->next = NULL;

    //if(!mem_pool) mem_pool = fmem_init(POOL_NUM, sizeof(file_list_t));

    return tmp;
}

void dir_free(cur_dir_t *head) 
 
{
    if(!head) return;

    destroy_list(head->dir);
    destroy_list(head->regular);
    destroy_list(head->slink);
    free(head);

    return ;
}

int dir_file(cur_dir_t *head, char *file_path)
{
    if(!head 
[解决办法]
 !file_path) return -1;

/*
    char work_dir[512] = {0};
    if(getcwd(work_dir, sizeof(work_dir)) == NULL)
        snprintf(work_dir, sizeof(work_dir), "%s/bin", getenv("HOME"));

    if(chdir(file_path) == -1)
    {
        fprintf(stderr, "chdir() failed, path:[%s], error:[%s]\n",
                        file_path, strerror(errno));
        return -1;
    }
*/

    DIR *dir = NULL;
    struct dirent *entry;
    struct stat st;
    memset(&st, 0, sizeof(struct stat));

    if((dir = opendir(file_path)) == NULL)
    {
        fprintf(stderr, "opendir() failed, path:[%s], error:[%s]\n",
                        file_path, strerror(errno));
        return -1;
    }
    else
    {
        strncpy(head->dir_name, file_path, sizeof(head->dir_name));
        char full_name[512];
        while((entry = readdir(dir)) != NULL)
        {
            sprintf(full_name, "%s/%s", file_path, entry->d_name);
            if(stat(full_name, &st) == 0)
            { 
 
                if(strncmp(entry->d_name, ".", 1) == 0
                   
[解决办法]
 strncmp(entry->d_name, "..", 2) == 0) continue;

                if(S_ISREG(st.st_mode))
                {
                    file_list_t *node = (file_list_t *)malloc(sizeof(*node));
                    strncpy(node->file_name, entry->d_name, sizeof(node->file_name));
                    node->next = head->regular;
                    head->regular = node;
                }
                else if(S_ISDIR(st.st_mode))
                {
                    file_list_t *node = (file_list_t *)malloc(sizeof(*node));
                    strncpy(node->file_name, entry->d_name, sizeof(node->file_name));
                    node->next = head->dir;
                    head->dir = node;
                }
                else if(S_ISLNK(st.st_mode))
                {
                    file_list_t *node = (file_list_t *)malloc(sizeof(*node)); 
 
                    strncpy(node->file_name, entry->d_name, sizeof(node->file_name));
                    node->next = head->slink;
                    head->slink = node;
                }
            }
        }
        closedir(dir);
    }

/*
    if(chdir(work_dir) == -1)
    {
        fprintf(stderr, "chdir() failed, path:[%s], error:[%s]\n",
                        work_dir, strerror(errno));
    }
*/

    return 0;
}


void dir_info(cur_dir_t *head)
{
    if(!head) return;

    printf("\n>>>>>>>>>>>>>>>cur dir name:[%s]<<<<<<<<<<<<<<<<<\n", head->dir_name);
    printf("show sub_directory info:\n");
    printf("-----------------------\n");
    display_file(head->dir);
    printf("-----------------------\n\n");

    printf("show regular file info:\n");
    printf("-----------------------\n");
    display_file(head->regular);
    printf("-----------------------\n\n");

    printf("show link file info:\n");
    printf("-----------------------\n");
    display_file(head->slink);
    printf("-----------------------\n\n");

    return ;
}

static void make_absolute_path(char *out, char *parent, char *sub)
{
    int len = strlen(parent);
    memcpy(out, parent, len+1);

    if(out[len-1] != '/')
    {
        out[len]='/'; 
 
        out[len+1] = '\0';
    }
    strcat(out, sub);

    return;
}

cur_dir_t *recursive_dir_file(char *file_path)
{
    if(!file_path) return NULL;

    cur_dir_t *dir_head = dir_init();
    int ret = dir_file(dir_head, file_path);
    if(ret == -1)
    {
        dir_free(dir_head);
        return NULL;
    }

    cur_dir_t *tail = dir_head;
    cur_dir_t *head = dir_head;
    char absolute_path[512];
    while(head)
    {
        file_list_t *sub_dir = head->dir;
        while(sub_dir)
        {
            cur_dir_t *sub_dir_info = dir_init();
            make_absolute_path(absolute_path, head->dir_name, sub_dir->file_name);
            int ret = dir_file(sub_dir_info, absolute_path);
            if(ret == -1)
            {
                dir_free(sub_dir_info);
                sub_dir = sub_dir->next;
                continue;
            }
            tail->next = sub_dir_info;
            tail = sub_dir_info;

            sub_dir = sub_dir->next;
        }
        head = head->next;
    }

    return dir_head;
}

void recursive_dir_info(cur_dir_t *head)
{
    while(head) 
 
    {
        dir_info(head);
        head = head->next;
    }

    //fmem_info(mem_pool);
    return;
}
void recursive_dir_free(cur_dir_t *head)
{
    cur_dir_t *tmp = head;
    while(head)
    {
        tmp = head->next;
        dir_free(head);
        head = tmp;
    }
    printf("recursive_dir_free ok\n");
    //fmem_info(mem_pool);
    //fmem_destroy(mem_pool);

    return;
}

void recursive_dir_and_print(char *file_path)
{
    if(!file_path) return;

    cur_dir_t *dir_head = dir_init();
    int ret = dir_file(dir_head, file_path);
    if(ret == -1)
    {
        dir_free(dir_head);
        return;
    }

    cur_dir_t *tail = dir_head;
    cur_dir_t *head = dir_head;
    cur_dir_t *tmp;
    char absolute_path[512];
    while(head)
    {
        file_list_t *sub_dir = head->dir;
        while(sub_dir)
        {
            cur_dir_t *sub_dir_info = dir_init();
            make_absolute_path(absolute_path, head->dir_name, sub_dir->file_name);
            int ret = dir_file(sub_dir_info, absolute_path);
            if(ret == -1)
            {
                dir_free(sub_dir_info);
                sub_dir = sub_dir->next;
                continue; 
 
            }
            tail->next = sub_dir_info;
            tail = sub_dir_info;

            sub_dir = sub_dir->next;
        }
        tmp = head;
        head = head->next;
        dir_info(tmp);
        dir_free(tmp);
    }

    //fmem_info(mem_pool);
    //fmem_destroy(mem_pool);

    return;
}


读书人网 >C语言

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net