hvordan man kan rekursivt krydse på en linket liste

Indlæg af Allan Busk-Mathiasen     opdateret: 2011-10-10

Den linkede liste datastruktur er et godt alternativ til simple arrays . I modsætning til arrays , kan data hurtigt tilføjes og fjernes fra en linket liste uden at genskabe listen ét element ad gangen . Men i modsætning til arrays , kan data i en sammenkædet liste kun er tilgængelig i orden . Du kan gøre dette med en simpel loop eller med en rekursiv ( eller selvstændig ringer ) funktion . Dette vil blive skrevet i Java , men koden kan implementeres i alle sprog med kun mindre ændringer , der passer til den syntaks forskelle
1
Åbn en teksteditor
2
Indsæt følgende Java- kode . :

public class RecursiveLLTraverser {

public static void traverseList ( LinkedList l ) {



}

}


Alle koden vil gå i " traverseList " metode
3
Indsæt følgende inde i " traverseList " -metoden : .


if ( l. size ( ) == 0 ) tilbage ;
if ( l. størrelse ( ) > 0 ) {
LinkedList n=l. clone () ;
Objekt o=n. removeFirst () ;
o. doSomething () ;
traverseList ( n ) ;
}



Det tager en linket liste og gør en lavvandet klon af det med det første fjernet element ( og nogle forarbejdning , udføres på det . ) Denne klon er derefter køre gennem traversen listen. Til sidst , vil klonen være tom , i hvilket tilfælde traversen Liste metoden vil blot returnere

gode råd og advarsler


  • Alle rekursive algoritmer kræver mindst to tilfælde : en base case , som skal vende tilbage, og en rekursiv sag, der reducerer data størrelse til noget mere håndterligt . En almindelig fejl i rekursive metoder glemmer basen sagen . Dette medfører en uendelig løkke , som til sidst går ned , når computeren løber tør for stakplads .
  • Rekursiv metoder afhænger af en ordning , der kaldes " stack størrelse " , som ændrer sig med operativsystem og sprog . Denne del af hukommelse holder styr på alle aktuelt kørende metoder . Forsøg på en rekursiv algoritme på en meget lang liste kan producere stable fejl .


  • Previous:hvordan man lærer adgang VBA 2003 Next:hvordan man åbner en postsættet



     

    Kommentarer

    Code:
    change