Question

Je lis le Le manuel de conception de l'algorithme Réservez sur les structures de données et indique ce qui suit sur l'implémentation répertoriée liée:

L'insertion dans une liste unique est un bel exercice dans la manipulation du pointeur, comme indiqué ci-dessous. Puisque nous n'avons pas besoin de maintenir la liste dans un ordre particulier, nous pourrions aussi bien insérer chaque nouvel élément à l'endroit le plus simple. L'insertion au début de la liste évite tout besoin de traverser la liste, mais nous oblige à mettre à jour le pointeur (indiqué L) à la tête de la structure de données.

Je me demande quel type de liste est cela car je ne peux pas l'utiliser pour l'accès basé sur l'index. Toutes les autres implémentations de base que j'ai vues offrent un accès basé sur l'index.

Lors de la recherche d'un élément, leur implémentation affiche une comparaison directe d'objets:

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) );
}

Je pense donc qu'ils ne tenaient peut-être pas compte de l'accès basé sur l'index.

Ce livre distingue également Container et Dictionary Catégories de DS:

Nous utilisons le terme conteneur pour désigner une structure de données qui permet le stockage et la récupération des éléments de données indépendants du contenu. Ils se distinguent par l'ordre de récupération particulier qu'ils soutiennent (LIFO, FIFO). En revanche, les dictionnaires sont des types de données abstraits qui se récupèrent en fonction des valeurs clés ou du contenu.

Il semble que l'implémentation répertoriée liée entre dans une catégorie de conteneurs avec la référence d'objet comme clé, quelque chose comme une carte DS.

Cette hypothèse est-elle valable?

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top