Domanda

Sto leggendo il Il manuale di design dell'algoritmo Prenota le strutture di dati e dice quanto segue sull'implementazione elencata collegata:

L'inserimento in una lista singolarmente collegata è un bell'esercizio nella manipolazione del puntatore, come mostrato di seguito. Dal momento che non abbiamo bisogno di mantenere l'elenco in nessun ordine particolare, potremmo anche inserire ogni nuovo elemento nel luogo più semplice. L'inserimento all'inizio dell'elenco evita qualsiasi necessità di attraversare l'elenco, ma ci richiede di aggiornare il puntatore (indicato L) alla testa della struttura dei dati.

Mi chiedo che tipo di elenco sia questo perché non posso usarlo per l'accesso basato sull'indice. Tutte le altre implementazioni di base che ho visto forniscono l'accesso basato sull'indice.

Quando si cerca un elemento, la loro implementazione mostra un confronto diretto degli oggetti:

list *search_list(list *l, item_type x)
{
    if (l == NULL) return(NULL);
    if (l->item == x)
        return(l);
    else
        return( search_list(l->next, x) );
}

Quindi penso che forse non hanno tenuto conto dell'accesso basato sull'indice.

Questo libro distingue anche Container e Dictionary Categorie di DS:

Utilizziamo il termine contenitore per indicare una struttura di dati che consente l'archiviazione e il recupero degli elementi di dati indipendenti dal contenuto. Si distinguono per il particolare ordine di recupero che supportano (LiFO, FIFO). Al contrario, i dizionari sono tipi di dati astratti che recuperano in base a valori chiave o contenuti.

Sembra che l'implementazione elencata collegata rientri in una categoria contenitore con il riferimento dell'oggetto come chiave, qualcosa di simile a una mappa DS.

Questo presupposto è valido?

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top