Struttura collegata lineare ad anello

di il
15 risposte

Struttura collegata lineare ad anello

Una struttura collegata lineare (SCL) `e detta ad anello se uno dei suoi nodi ha come successore il primo
nodo della struttura. La struttura `e invece detta non ad anello se uno dei suoi nodi (l’ultimo) non ha
successori. La SCL vuota non `
e ad anello.

1. Fornire un’implementazione ricorsiva in C della funzione int anello(TipoSCL scl)
che, presa in input una SCL scl, restituisce 1 se scl è ad anello e 0 altrimenti (è ammesso l’uso
di funzioni ausiliare, purchè ricorsive).


Potreste darmi delle linee guida? Non so proprio da dove cominciare.

Il primo controllo che farei è vedere che non sia nulla. Poi non so come continuare..

15 Risposte

  • Re: Struttura collegata lineare ad anello

    Se la lista fosse stampata su carta, nodo per nodo, come faresti a identificare che è una struttura ad anello?
  • Re: Struttura collegata lineare ad anello

    Il puntatore di quella determinata struttura punterebbe alla prima..
  • Re: Struttura collegata lineare ad anello

    Non hai risposto alla domanda.
    Se tu hai i nodi stampati su carta, per esempio:

    puntatore di partenza al nodo 0001

    nodo 0001 elemento "5" next 0002
    nodo 0002 elemento "8" next 0003
    nodo 0003 elemento "9" next 0004
    nodo 0004 elemento "4" next 0001

    come fai a capire che si tratta, o non si tratta, di una struttura ad anello?
  • Re: Struttura collegata lineare ad anello

    E non rispondere "perché l'ultima punta alla prima" ... mettiti dalla parte di un computer che esegue un programma ... quali regole in dettaglio dovrebbe seguire?
  • Re: Struttura collegata lineare ad anello

    Ok. Allora, è ad anello perché next 0001 punta al nodo 0001.
    Se l'ultimo next avrebbe puntato a NULL non sarebbe stata ad anello.
  • Re: Struttura collegata lineare ad anello

    Se l'ultimo next avrebbe puntato a NULL
    se avesse puntato...
    Come fai a determinare l'ultimo next?
  • Re: Struttura collegata lineare ad anello

    Aia!! Errore di distrazione, scusate.

    candaluar ha scritto:


    Come fai a determinare l'ultimo next?
    if(scl -> next == NULL)
    ...
  • Re: Struttura collegata lineare ad anello

    davide.fruci ha scritto:


    Se l'ultimo next avrebbe puntato a NULL non sarebbe stata ad anello.
    Poveri congiuntivi ....
  • Re: Struttura collegata lineare ad anello

    Secondo te questa struttura è ad anello?

    puntatore di partenza al nodo 0001

    nodo 0001 elemento "5" next 0003
    nodo 0002 elemento "8" next 0001
    nodo 0003 elemento "9" next 0002
    nodo 0004 elemento "4" next NULL
  • Re: Struttura collegata lineare ad anello

    Sì, perché next 0002 punta a nodo 0002 e successivamente next 0001 punta a nodo 0001.

    Il testo dice: detta ad anello se uno dei suoi nodi ha come successore il primo
    nodo della struttura
    .

    "Se uno dei suoi nodi", quindi non esclusivamente l'ultimo..
  • Re: Struttura collegata lineare ad anello

    Quindi... dicci come fai a determinare che è ad anello
  • Re: Struttura collegata lineare ad anello

    Innanzitutto controllo che non sia vuota.

    Se così fosse faccio un return che mi esce dalla ricorsione.

    Quindi:

    if(scl == NULL)
    return;


    Poi potrei controllare che:

    if(scl -> next == NULL)
    return 0;


    Cioè non è ad anello.
    No, aspetta questo non va bene. Perché non necessariamente non è ad anello se l'ultimo next punta a NULL.

    Scandisco l'intera lista: praticamente, non appena incontro un puntatore di una struttura che punta ad una struttura precedente allora è ad anello.

    ...?
  • Re: Struttura collegata lineare ad anello

    Descrivi passo passo come hai fatto a determinare che è ad anello la seguente struttura

    puntatore di partenza al nodo 0001

    nodo 0001 elemento "5" next 0002
    nodo 0002 elemento "8" next 0003
    nodo 0003 elemento "9" next 0004
    nodo 0004 elemento "4" next 0001
  • Re: Struttura collegata lineare ad anello

    Nodo 0001 elemento "5" next 0002
    nodo 0002 elemento "8" next 0003
    nodo 0003 elemento "9" next 0004
    nodo 0004 elemento "4" next 0001

    Allora,
    Ho "scandito" la lista fino a quando non mi sono imbattuto in un puntatore (next 0001) che puntava ad un nodo già passato.
Devi accedere o registrarti per scrivere nel forum
15 risposte