如何用广度优先算法也就是队列实现文件夹的遍历？
如题:
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;
}
#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;
}
