Elenco delle strutture di dati fondamentali: cosa mi manca?

Question

Ultimamente ho studiato un po 'le mie strutture di dati fondamentali, cercando di assicurarmi di farle raffreddare.

Per "fondamentale", intendo i reali di base. Quelli fantastici come i Red-Black Trees e Bloom Filters sono chiaramente degni di nota, ma di solito sono o miglioramenti di quelli fondamentali (gli alberi Red-Black sono alberi di ricerca binari con proprietà speciali per tenerli in equilibrio) o sono utili solo in molto situazioni specifiche (filtri Bloom).

Finora, io sono "fluente" nei seguenti strutture di dati:

• Array
• liste concatenate
• Stacks/code
• Binary Search Trees
• Heaps code/Priority
• Hash Tabelle

Tuttavia, mi sento come se mi mancasse qualcosa. Ci sono dei fondamentali di cui mi sto dimenticando?

EDIT: Aggiunta questi dopo aver postato la questione

• Strings (suggerito da catchmeifyoutry)
• Sets (suggerito da Peter)
• grafici (suggerito da Nick D e AJ)
• B-Trees (suggerito da tloach)
  • Sono un po 'fuori discussione sul fatto che questi ar Sono troppo stravagante o no, ma penso che siano abbastanza diversi dalle strutture fondamentali (e abbastanza importanti) da meritare di essere studiate come fondamentali.

Answer 1

Sets

In linea di principio non ho mai dire provare [anySearhEngine] su di esso, ma è possibile verifica questa lista: http://en.wikipedia.org/wiki/List_of_data_structures

Answer 2

Hai dimenticato quelli di base: struct, object e enums.

Answer 3

B-Alberi e altre multi-alberi

Answer 4

Vorrei aggiungere mappe a meno che non si voglia considerare che ad essere sotto insiemi.

Answer 5

Matrices in quanto servono come base per problemi di modellazione, quali:

• Grafici
• Affine trasformazioni di
• risoluzione di sistemi lineari catene
• Markov
• ecc

Answer 6

anche lo Graph data structure è fondamentale.

Answer 7

Per informazioni, leggere la documentazione di Java Collections. Scompongono le cose in un livello astratto (Set, List e Map) e un livello di implementazione (ArraySet, HashSet, ArrayList, LinkedList, TreeMap, HashMap).

Per informazioni, leggere la documentazione delle raccolte Python. Rompono le cose in classi di base astratte come Set, Sequence e Map che sono costruite dalle caratteristiche di mix di una collezione.

Answer 8

Matrices

Graphs

Answer 9

stringhe, anche se possono essere implementate come array sotto il cofano (come sono diverse altre strutture di dati).

Qualsiasi programma che interagisce con l'utente utilizzerà stringhe. È importante sapere come manipolare le stringhe.

Answer 10

alcuni possono essere considerati meno fondamentale rispetto ad altri: vettori

• matematiche/da matrici
• grafici, liste di adiacenza/da matrici
• tries alberi prefisso/suffisso
• spaziali indicizzazione - alberi Quad/kd -trees r-alberi
• flussi/sequenze stringhe terminate null/big ints

Answer 11

Quadtree s, come il tipo più semplice di indice spaziale.

Answer 12

Bit array non è fondamentale, ma è molto utile e può rappresentato in modo efficiente utilizzando numeri interi (e operatori bit per bit)

Answer 13

Si potrebbe considerare union/find datastructures. Sono fondamentali per alcuni algoritmi di grafi.

Answer 14

L'array associativo è il modo generico di dire dizionari, mappe, ecc. È possibile trovare questo in quasi tutti i framework.

http://en.wikipedia.org/wiki/Associative_array

Answer 15

Tuples.

Inoltre, se potessi nominare una struttura di dati non di base, sarebbe il prefisso di partizione bit persistente Hash Tries di Clojure.In generale, credo che la persistenza sia una proprietà molto importante e spesso trascurata di qualsiasi struttura di dati.

Answer 16

Contro cella. Con che si può costruire diverse altre strutture di dati (liste, alberi, etc.)

http://en.wikipedia.org/wiki/Cons

Answer 17

Penso che la tua domanda non è chiara, perché si sta mescolando implementazione e lo scopo ...

il seguente tipi descrivono implementazione:

• lista collegata
• doppia lista collegata
• skip list
• matrice
• dynamic array
• tabella hash
• (binario) albero
• "gestito" alberi (binari) (cumuli, livellati alberi, ecc, cioè alberi dove inserimento e cancellazione non viene effettuata direttamente ma attraverso una procedura che garantisca determinati vincoli per l'albero)
• grafico (anche se molto elegante)

seguente descrive scopo:

• pila (significa FILO & può essere implementata da una lista collegata, ma anche con un array o vettore)
• coda (mezzi FIFO & può essere implementato da un elenco doppio collegato, o forse in altri modi sensibili)
• dequeue (...)
• coda di priorità (significa "alto/basso chiave First out" questo è un concetto astratto, che può essere implementato in many different ways)
• mappa/array associativo/dizionario (si significa mappare le chiavi ai valori. spesso richiede una funzione extra per convertire le chiavi in ​​chiavi valide per la tabella hash o albero sottostante)
• set (significa, è una raccolta, che è iterabile e può dire, se un valore è un elemento dell'insieme o meno. valore, ovvero un elemento dell'insieme deve apparire esattamente una volta durante l'iterazione, un set può essere mutabile o no (può consentire di aggiungere o rimuovere elementi). Le routine per l'intersezione, l'unione, la differenza possono essere fornite (ad esempio come metodi in OOP) .) quando si tratta di realizzazione, c'è un certo numero di possibilità)

bene, non ci sarebbe un'ultima cosa che considero molto degni di nota: algebraic data types ... a seconda della lingua, che sia esistono in modo nativo, o devi emularli ... haXe e C# (per quanto ho sentito) sarebbero due lingue imperative che li offrono semplicemente consentendo parametri per enumerazioni ... possono essere usati per implementare liste, alberi e molte altre cose carine ... per esempio, sono perfetto per rappresentare AST s e molte altre strutture complesse ...

Answer 18

Un "oggetto funzione", "puntatore di funzione" o "chiusura" non può essere implementato in alcune lingue restrittive che dispongono di matrici, elenchi concatenati, ecc. Ma forse sono più vicini ai tipi di dati piuttosto che alle strutture dati.

"rope" implementation (come implementato nella libreria "cord") è la mia implementazione preferita della struttura di dati astratta "a stringa", ma forse non è davvero "fondamentale".