Помогите, пожалуйста, найти способ в Java обойти все директории на диске без рекурсии? У меня как на зло без рекурсии ничего не выходит.
-
без рекурсии -- это самоцель? или у вас переполнение стека? о_О по делу: используйте стек отложенных заданий, будет вам счастье.– VladD30 ноя 2012 в 13:40
-
если не использовать рекурсию явно, придется ее эмулировать. А можно просто запустить dir/ls/tree/find и распарсить вывод:)– KoVadim30 ноя 2012 в 13:44
-
@VladD, только не стек, а очередь, именно ее Вы и сделали в ответе (псевдокод).– avp30 ноя 2012 в 14:54
-
1@avp: ага :) забыл обновить комментарий. Со стеком получился бы DFS.– VladD30 ноя 2012 в 14:58
-
@KoVadim, про эмуляцию рекурсии без рекурсии - можно подробней?– PinkTux24 июн 2016 в 16:00
8 ответов
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());
}
}
- Делаете список директорий. Изначально он пустой.
- Берете в качестве текущего элемента начало списка.
- Заполняете его директориями, лежащими в корне диска.
- Пока не дошли до конца списка: получаете директории для текущего элемента, добавляете их в список сразу после текущего.
Таким образом, когда вы дойдете до конца - у вас будет список всех директорий. Причем отсортированный так, как если бы мы обходили дерево рекурсией:
C:\A
C:\A\A
C:\A\A\A
C:\A\A\B
c:\A\B
C:\B
c:\B\A
и.т.п.
Попробуйте так (псевдокод)
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.
Код на скорую руку, но рабочий:
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());
}
}
Начиная с 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;
}
}
Обход всех каталогов без стека и рекурсии.
- Добавляем корень в пустой Массив
- i=0 (начало Массива)
- Если i-й элемент Массива каталог, то добавляем все его елементы в конец Массива
- i=i+1
- Если i < длины массива, то переход к пункту 3
-
-
-
@Nofate я ваш алгоритм не понял и порядок вывода по вашему описанию у него другой. Здесь массив заполняется по уровням, да BFS наверно, только текущий элемент не удаляется из списка за счёт перемещения на следующий. / /A /B /A/A /A/B /B/B– sercxjo1 дек 2012 в 4:07
-
-
@rasmisha, согласен, просто можно немного сэкономить памяти и операций в зависимости от используемых методов хранения, если нужен список всех файлов и директорий, в противном случае можно удалять обработанные элементы. Можно ещё добавить удаление по условию, если мы делаем поиск.– sercxjo1 дек 2012 в 6:06
очень удобно такую задачу делать со стеком. изначально в стек ложится корневая папка. дальше алгоритм такой:
1) выталкиваем последний элемент
2) получаем для папки список подпапок, добавляем все в стек
3) если стек не пустой повторяем пункт 1
-
К сожалению я ещё не умею работать со стеком. Я только начинающий. Но всё равно огромное спасибо. Теперь знаю где ещё рыть.– pre-term1 дек 2012 в 9:30
попробую расписать свой код подробно можно так для директорий
#! /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