古城微笑少年丶 2021-09-07 05:59 539阅读 0赞

**目录**

递归实现

非递归实现

--------------------

我们知道，许多操作系统中的目录结构都是使用树结构。

> 使用递归的方法定义树是比较容易的。一棵树地一些节点的集合。  
> 这个集合可以为空，若非空，则树由树根和0个或者多个非空的子树组成。  
> 子树中的根都被来自树根的一条有向的边所连接。

因此，可以很自然地想到使用递归的方式来遍历指定的目录。

除了递归，还可以考虑使用非递归方式实现，这样效率会更高，但也更复杂。

### 递归实现 ###

*  思路：递归实现较简单，对于一个给定的目录，遍历目录下所有文件，有三种情况：
    
     *  本目录或父目录，忽略
     *  普通文件，输出
     *  目录，递归调用
 *  源代码如下：

#include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <dirent.h>
    #include <sys/stat.h>
    
    #define MAX_PATH_LEN (256)
    
    static void trave_dir(char* path) {
        DIR *d = NULL;
        struct dirent *dp = NULL; /* readdir函数的返回值就存放在这个结构体中 */
        struct stat st;    
        char p[MAX_PATH_LEN] = {0};
        
        if(stat(path, &st) < 0 || !S_ISDIR(st.st_mode)) {
            printf("invalid path: %s\n", path);
            return;
        }
    
        if(!(d = opendir(path))) {
            printf("opendir[%s] error: %m\n", path);
            return;
        }
    
        while((dp = readdir(d)) != NULL) {
            /* 把当前目录.，上一级目录..及隐藏文件都去掉，避免死循环遍历目录 */
            if((!strncmp(dp->d_name, ".", 1)) || (!strncmp(dp->d_name, "..", 2)))
                continue;
    
            snprintf(p, sizeof(p) - 1, "%s/%s", path, dp->d_name);
            stat(p, &st);
            if(!S_ISDIR(st.st_mode)) {
                printf("%s\n", dp->d_name);
            } else {
                printf("%s/\n", dp->d_name);
                trave_dir(p);
            }
        }
        closedir(d);
    
        return;
    }
    
    int main(int argc, char **argv)
    {   
        char *path = NULL;
     
        if (argc != 2) {
            printf("Usage: %s [dir]\n", argv[0]);
            printf("use DEFAULT option: %s .\n", argv[0]);
            printf("-------------------------------------------\n");
            path = "./";
        } else {
            path = argv[1];
        }
    
        trave_dir(path);
    
        return 0;
    }

### 非递归实现 ###

非递归实现的方法会有很多，一个思路是，每次遍历目录时，把查找到的文件直接输出，目录则保存，用于下次遍历目录下的内容。

此处使用链表实现，结构体用于存储目录路径和下一个目录，遍历目录的过程同上，代码如下：

#include <stdio.h>
    #include <dirent.h> 
    #include <stdlib.h> 
    #include <string.h>
    #include <unistd.h>
    #include <error.h>
    #include <sys/stat.h>  
    
    #define MAX_FILE_NAME_LEN 256
    
    typedef struct foldernode_t {
      char *path;                // point to foldername or filename path
      struct foldernode_t *next;   
    } foldernode;
    
    static void travel_files(char *path)
    {
        DIR *dir;
        struct dirent *ptr;
        char foldername[MAX_FILE_NAME_LEN] = {0};
        char folderpath[MAX_FILE_NAME_LEN] = {0};
    
        foldernode *folderstart;
        folderstart = calloc(1, sizeof(foldernode));/* ignore err case */
        folderstart->path = calloc(1, MAX_FILE_NAME_LEN + 1); 
        strncpy(folderstart->path, path, MAX_FILE_NAME_LEN);
        folderstart->next = NULL;
    
        foldernode *folderfirst = folderstart; /* use to search */
        foldernode *folderlast = folderstart; /* use to add foldernode */
        foldernode *oldfirst = NULL;
    
        while(folderfirst != NULL) {
            printf("dir=%s\n", folderfirst->path);
            if ((dir = opendir(folderfirst->path)) != NULL) {
                while ((ptr = readdir(dir)) != NULL) {
                    if(strcmp(ptr->d_name, ".") == 0 || strcmp(ptr->d_name, "..") == 0) {
                        continue;  
                    } else if (ptr->d_type == DT_REG) { /* regular file */
                        printf("%s\n", ptr->d_name);
                    } else if (ptr->d_type == DT_DIR) { /* dir */
                        bzero(foldername, sizeof(foldername));
                        bzero(folderpath, sizeof(folderpath));
                        strncpy(foldername, ptr->d_name, sizeof(foldername));
                        snprintf(folderpath, sizeof(folderpath), "%s/%s", folderfirst->path , foldername);
                        printf("%s\n", folderpath);
                        
                        foldernode *foldernew;
                        foldernew = calloc(1, sizeof(foldernode));
                        foldernew->path = calloc(1, MAX_FILE_NAME_LEN + 1); 
                        strncpy(foldernew->path, folderpath, MAX_FILE_NAME_LEN);
                        foldernew->next = NULL;
                        
                        folderlast->next = foldernew;
                        folderlast = foldernew;
    
                    }
                }
            } else {
                printf("opendir[%s] error: %m\n", folderfirst->path);
                return;
            }
            oldfirst = folderfirst;
            folderfirst = folderfirst->next; // change folderfirst point to next foldernode
            if (oldfirst) {
                if (oldfirst->path) {
                    free(oldfirst->path);
                    oldfirst->path = NULL;
                }
                free(oldfirst);
                oldfirst = NULL;
            }
            closedir(dir);
        }
    }
    
    int main(int argc,char **argv)
    {
        if (argc != 2) {
            printf("Usage: %s path\n", argv[0]);
            return 0;
        }
    
        travel_files(argv[1]);
    
        return 0;
    }

对目录的遍历是比较基本的功能，对于理解文件系统和数据结构有一定的帮助。

也可以参考bash命令中ls的源码，增加对命令行参数的支持，实现更加复杂的功能。