Come posso riscrivere questa manipolazione della lista collegata come coda ricorsiva?

Question

Come posso riscrivere questa manipolazione della lista collegata come coda ricorsiva?

#1 da (5 voti)

3

Dato un elenco piaciuto, vorrei scambiare ogni coppia di nodi come segue:

input : a-b-c-d-e-f-g

output : b-a-d-c-f-e-g

Se c'è un numero dispari di nodi, allora l'ultimo nodo viene virato così com'è. Questo dovrebbe essere fatto sul posto. Implementa il metodo: Node* SwapTo(Node* start)

Sto usando questa definizione di nodo:

class Node {
    public:
        char data;
        Node* next;
};

Ecco la soluzione ricorsiva non ottimizzata:

Node* SwapTwo(Node* start) {
    if (!start) {
        return start;
    }

    Node* second = start->next;
    if (!second) {
        return start;
    }

    Node* third = second->next;
    second->next = start;
    start->next = SwapTwo(third);
    return second;
}

Che cos'è la soluzione ricorsiva di coda?

language-agnostic recursion algorithms linked-list

posta Shamster 25.06.2014 - 08:32

fonte

1 risposta

Leggi altre domande sui tag language-agnostic recursion algorithms linked-list

Come posso modellare questo scenario in un database grafico? Forking di un repository GitHub e inclusione del codice da richieste pull in una licenza LGPL?

score 5 · Accepted Answer

Dato che hai taggato la domanda con un linguaggio indipendente, ecco una soluzione in un linguaggio adatto alle funzioni ricorsive e alle strutture dati:

let rec swapTwo lst acc =
    match lst with
    | a::b::tail -> swapTwo tail (a::b::acc)
    | h::tail -> swapTwo tail (h::acc)
    | [] -> List.rev acc

Per quanto riguarda una soluzione in C ++, non mi piace fare i dettagli del puntatore del puntatore, ma inizierei con una funzione con la seguente firma:

Node* SwapTwo (Node* start, Node *prev, Node *curr)

Dove start sarebbe il capo dell'elenco e curr sarebbe ciò che inizia nel tuo snippet, il primo dei due elementi da scambiare. Quindi devi anche prev , l'ultimo nodo del precedente 'blocco' per impostare il puntatore successivo su di esso.

Probabilmente il prev bit è il più difficile, dal momento che devi aggiornare il blocco precedente quando stai già elaborando il prossimo. La parte fondamentale da ricordare quando si creano oggetti ricorsivi di coda è che non si ha lo stack da utilizzare per costruire il calcolo, è necessario passare tutto intorno esplicitamente alla chiamata ricorsiva successiva. Nel tuo caso, quella parte è dove assegni il SwapTwo risultato a start->next .

Questo dovrebbe più o meno coprirlo. Non penso di dover commentare molto su quale di quelle due soluzioni trovo preferibile.