3

Помогите, пожалуйста, найти способ в Java обойти все директории на диске без рекурсии? У меня как на зло без рекурсии ничего не выходит.

6
  • без рекурсии -- это самоцель? или у вас переполнение стека? о_О по делу: используйте стек отложенных заданий, будет вам счастье.
    – VladD
    30 ноя 2012 в 13:40
  • если не использовать рекурсию явно, придется ее эмулировать. А можно просто запустить dir/ls/tree/find и распарсить вывод:)
    – KoVadim
    30 ноя 2012 в 13:44
  • @VladD, только не стек, а очередь, именно ее Вы и сделали в ответе (псевдокод).
    – avp
    30 ноя 2012 в 14:54
  • 1
    @avp: ага :) забыл обновить комментарий. Со стеком получился бы DFS.
    – VladD
    30 ноя 2012 в 14:58
  • @KoVadim, про эмуляцию рекурсии без рекурсии - можно подробней?
    – PinkTux
    24 июн 2016 в 16:00

8 ответов 8

6
File rootDir = new File(root);
List<String> result = new ArrayList<>();
Queue<File> fileTree = new PriorityQueue<>();

Collections.addAll(fileTree, rootDir.listFiles());

while (!fileTree.isEmpty())
{
    File currentFile = fileTree.remove();
    if(currentFile.isDirectory()){
        Collections.addAll(fileTree, currentFile.listFiles());
    } else {
        result.add(currentFile.getAbsolutePath());
    }
}
1
  • Спасибо. Очень крутой алгоритм.
    – Alex Belke
    30 ноя 2016 в 20:02
3
  1. Делаете список директорий. Изначально он пустой.
  2. Берете в качестве текущего элемента начало списка.
  3. Заполняете его директориями, лежащими в корне диска.
  4. Пока не дошли до конца списка: получаете директории для текущего элемента, добавляете их в список сразу после текущего.

Таким образом, когда вы дойдете до конца - у вас будет список всех директорий. Причем отсортированный так, как если бы мы обходили дерево рекурсией:

C:\A
C:\A\A
C:\A\A\A
C:\A\A\B
c:\A\B
C:\B
c:\B\A

и.т.п.

1
  • Спасибо! Буду разбираться дальше.
    – pre-term
    30 ноя 2012 в 14:01
3

Попробуйте так (псевдокод)

queue<string> taskList = new queue<string>();
taskList.add(startDir);
while (!taskList.empty())
{
    string dir = taskList.first();
    taskList.popFirst();
    for each dirEntry in dir
    {
        if entry is directory
            taskList.add(entry);
        else
            processFile(entry);
    }
}

А вообще, почитайте про обходы дерева, например, BFS/DFS.

3

Код на скорую руку, но рабочий:

import java.io.File;
public class Main {
    public static void main(String[] args) {
        String rootDir = "d:\\";

        File root = new File(rootDir);
        File[] files = root.listFiles();
        int i = 0;

        while(i<files.length) {
            File firstElement = files[i];
            File[] subFiles = null;

            if (firstElement.isDirectory()) {
                subFiles = firstElement.listFiles();
            }
            else {
                i++;
                continue;
            }
            File[] temp = new File[files.length + subFiles.length];
            for (int j = 0; j<=i; j++) 
                temp[j] = files[j];
            for (int k = 0; k<subFiles.length; k++)
                temp[i+1+k] = subFiles[k];
            for (int m = i+1; m<files.length; m++)
                temp[m+subFiles.length] = files[m];

            files = temp;
            i++;
        }

        for (File file : files)
            System.out.println(file.getPath());
    }

}
1
  • Очень благодарен за помощь.
    – pre-term
    1 дек 2012 в 9:28
2

Начиная с Java 1.7

import java.io.IOException;
import java.nio.file.*;
import java.nio.file.attribute.BasicFileAttributes;

public class FileTree {
    public static void main(String[] args) {

        Path pathSource = Paths.get("Введите сюда путь к какому-либо каталогу, содержащему другие каталоги и файлы");
        try {
            Files.walkFileTree(pathSource, new MyFileVisitor());
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

class MyFileVisitor extends SimpleFileVisitor {
    public FileVisitResult visitFile(Path path,
                                     BasicFileAttributes fileAttributes) {
        System.out.println("file name:" + path.getFileName());
        return FileVisitResult.CONTINUE;
    }

    public FileVisitResult preVisitDirectory(Path path,
                                             BasicFileAttributes fileAttributes) {
        System.out.println("Directory name:" + path);
        return FileVisitResult.CONTINUE;
    }
}

The Java™ Tutorials - Walking the File Tree

1

Обход всех каталогов без стека и рекурсии.

  1. Добавляем корень в пустой Массив
  2. i=0 (начало Массива)
  3. Если i-й элемент Массива каталог, то добавляем все его елементы в конец Массива
  4. i=i+1
  5. Если i < длины массива, то переход к пункту 3
5
  • да, именно я так я и сказал
    – Nofate
    30 ноя 2012 в 20:25
  • да тут половина ответов bfs
    – misha_m
    30 ноя 2012 в 20:54
  • @Nofate я ваш алгоритм не понял и порядок вывода по вашему описанию у него другой. Здесь массив заполняется по уровням, да BFS наверно, только текущий элемент не удаляется из списка за счёт перемещения на следующий. / /A /B /A/A /A/B /B/B
    – sercxjo
    1 дек 2012 в 4:07
  • @sercxjo i=i+1 равноценно удалению без "физического" удаления правда
    – misha_m
    1 дек 2012 в 5:45
  • @rasmisha, согласен, просто можно немного сэкономить памяти и операций в зависимости от используемых методов хранения, если нужен список всех файлов и директорий, в противном случае можно удалять обработанные элементы. Можно ещё добавить удаление по условию, если мы делаем поиск.
    – sercxjo
    1 дек 2012 в 6:06
1

очень удобно такую задачу делать со стеком. изначально в стек ложится корневая папка. дальше алгоритм такой:

1) выталкиваем последний элемент
2) получаем для папки список подпапок, добавляем все в стек
3) если стек не пустой повторяем пункт 1
1
  • К сожалению я ещё не умею работать со стеком. Я только начинающий. Но всё равно огромное спасибо. Теперь знаю где ещё рыть.
    – pre-term
    1 дек 2012 в 9:30
0

попробую расписать свой код подробно можно так для директорий

#! /usr/bin/env python
#coding=utf-8

import os

#-----------------------------------------------------
# Формирует список поддиректорий  от текущей директории 
# на один уровень ниже
#-----------------------------------------------------
def getCurrDir(rootDir=''):
    currListDirs=[]; onlyDirsLst=[]

    currListDirs=os.listdir(rootDir)
    for i in range(0,len(currListDirs)):
        currListDirs[i]=(rootDir+'/'+currListDirs[i])
        if os.path.isdir(currListDirs[i])==True:
            if os.path.islink(currListDirs[i])==False:                 
                # добавляем только дирректорию (исключая ссылки)   
                onlyDirsLst.append(currListDirs[i])
    return onlyDirsLst


#---------------------------------------------
# Формирует список поддиректорий, начиная от текущей rootDir
# на всю глубину дерева дирректорий
#---------------------------------------------
def getLstAllDirs(rootDir=''):
    oldLst=[]; newLst=[]; currPosLst=0

    oldLst.append(rootDir)

    while True:
        try:
            newLst=getCurrDir(oldLst[currPosLst])
            for i in newLst: oldLst.append(i)
            currPosLst+=1
        except IndexError:
            return oldLst



или так для директорий и всех в них файлов


#--------------------------------------------------------------
# Возвращает кортеж, где первый список - файлы, второй - каталоги
# Для одного уровня ниже от rootDir
#--------------------------------------------------------------
def getCurrFileDir(rootDir=''):
    currListDirs=[]; onlyDirsLst=[]; onlyFilesLst=[]

    currListDirs=os.listdir(rootDir)
    for i in range(0,len(currListDirs)):
        currListDirs[i]=(rootDir+'/'+currListDirs[i])
        if os.path.isdir(currListDirs[i])==True:
            if os.path.islink(currListDirs[i])==False:
                onlyDirsLst.append(currListDirs[i])
        else:
            if os.path.isfile(currListDirs[i])==True:
                if os.path.islink(currListDirs[i])==False:
                    onlyFilesLst.append(currListDirs[i])

    return onlyFilesLst, onlyDirsLst

#--------------------------------------------------------------
# Возвращает кортеж, где первый список - файлы, второй - каталоги
# Для всех уровней от rootDir;
# Если Lst=getLstAllFilesDirs(...), то кортеж Lst==([fa,fb,..],[da,db,..])
# Lst[0]==[fa,fb,..]  - список файлов;
#                       Lst[0][1] - второй файл в списке файлов.
# Lst[1]==[da,db,..]  - список каталогов;
#                       Lst[1][5] - шестой каталог в сп. каталогов.
#--------------------------------------------------------------
def getLstAllFilesDirs(rootDir=''):
    oldLst=([],[]); newLst=([],[]); currPosLst=0

    oldLst[1].append(rootDir)

    while True:
        try:
            newLst=getCurrFileDir(oldLst[1][currPosLst])
            for i in newLst[1]: oldLst[1].append(i)
            for i in newLst[0]: oldLst[0].append(i)
            currPosLst+=1
        except IndexError:
            return oldLst

-----------------------
проверяем:

cDir='/home'

print '=  Ждём. Обработка  ============================='
Lst=getLstAllFilesDirs(cDir)

print 'Список файлов:'
print '========================'
for i in range(len(Lst[0])): print '%4d: %s'%(i,Lst[0][i])
print '================================================='
print 'Список каталогов:'
print '========================'
for i in range(len(Lst[1])): print '%4d: %s'%(i,Lst[1][i])
print '=================================================\n'

print '   Каталоги  другой функцией (отсортированные)'
print '== Ждём. Обработка =============================='
Lst=getLstAllDirs(cDir)

Lst.sort()
for i in Lst: print i
1
  • каким образом код на питон ответит на вопрос по java?
    – Grundy
    17 мар 2017 в 21:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.