Perché dovrei usare una coda per elencare ricorsivamente tutti i file e le sottocartelle

1

Nel libro Algorithms di Robert Sedgewick c'è questo esercizio:

A folder is a list of files and folders. Write a program that takes the name of a folder as a command-line argument and prints out all of the files contained in that folder, with the contents of each folder recursively listed (indented) under that folder’s name. Hint: Use a queue.

Ora non capisco perché dovrei usare una coda per questo. Posso stamparlo direttamente senza prima aggiungere alla coda e scartare in seguito. Ha qualche vantaggio che non riesco a individuare o è solo per rafforzare le mie capacità di lavoro con le code?

AGGIORNAMENTO: Dopo tante risposte e commenti, sono ancora confuso su come stampare cartelle, file e sottocartelle nel modo desiderato dall'autore. Per favore, qualcuno potrebbe dirmi se vuole qualcosa del genere:

root
  folder1                folder2          file3.txt folder4
   folder1_1 file1_1.txt  folder2_1                  file4_1.txt
    folder1_1_1            file2_1_1.txt

Se è così, allora

What
 Is
  Silly
 In
  Displaying
   Files
    This
Way?
    
posta Mikayil Abdullayev 29.11.2017 - 04:41
fonte

3 risposte

3

Ci sono due opzioni per attraversare un albero come un filesystem è tradizionalmente.

  1. Attraversalo usando la ricorsione.
  2. Utilizza i loop e uno stack o una coda per tenere traccia dei nodi rimanenti da elaborare

La ricorsione spesso incorre nell'overhead delle chiamate al metodo in modo che Martin Fowler suggerisca di preferire l'iterazione alla ricorsione.

Con uno stack, tieni traccia del nodo corrente e di tutti gli antenati in cui ti trovi. Spingi un nodo (cartella) su di esso quando salti in su e apri la cartella quando non ci sono più cartelle all'interno di quella corrente. Questo è equivalente a ricerca approfondita .

Con una coda tieni traccia delle cartelle che devi ancora saltare, quindi il livello successivo sotto quello corrente. È ricerca in ampiezza di cui Wikipedia ha una buona descrizione.

    
risposta data 29.11.2017 - 09:51
fonte
8
Because
    Depth
        First
    Traversal
        Is
            A
                Silly
        Way
            To 
                Display
Files                        
    
risposta data 29.11.2017 - 06:39
fonte
1

Poiché questa è una domanda di esercizi a cui non risponderò direttamente, fornisci un suggerimento (dato che il suggerimento di @ CandiedOrange è un po 'criptico).

Ci sono due modi fondamentali per attraversare un albero: profondità prima e larghezza prima. Pensa quale è il preferito in questa situazione e sulle loro implementazioni.

Se si è impostato per ottenere una risposta diretta, si prega di commentare e io modificherò in ulteriori dettagli.

    
risposta data 29.11.2017 - 09:30
fonte

Leggi altre domande sui tag