1. Inicio
  2. Pregunta y respuesta
  3. Lista de estructuras de datos fundamentales: ¿qué me falta?

Lista de estructuras de datos fundamentales: ¿qué me falta?

2009-12-07 8 views
9

Recientemente he estado estudiando mis estructuras de datos fundamentales, tratando de asegurarme de que las tengo frías.Lista de estructuras de datos fundamentales: ¿qué me falta?

Por "fundamental", quiero decir los verdaderos básicos. Es claro que vale la pena saber los árboles rojos y negros y los filtros Bloom, pero normalmente son mejoras de los fundamentales (los árboles rojo-negro son árboles de búsqueda binarios con propiedades especiales para mantenerlos equilibrados) o solo son útiles en situaciones específicas (Bloom Filters).

Hasta el momento, estoy "fluidez" en las siguientes estructuras de datos:

  • matrices
  • listas enlazadas
  • Pilas/colas de espera
  • árboles de búsqueda binaria
  • Montones Colas/Prioridad
  • Mesas Hash

Sin embargo, siento que me falta algo. ¿Hay alguno fundamental que me estoy olvidando?

EDIT: Añadido estos después de la publicación de la cuestión

  • Cuerdas (sugerido por catchmeifyoutry)
  • Sets (sugerido por Peter)
  • gráficos (sugerido por Nick D y AJ)
  • B-Trees (Sugerido por tloach)
    • Estoy un poco en la cerca sobre si estos ar Es demasiado elegante o no, pero creo que son lo suficientemente diferentes de las estructuras fundamentales (y lo suficientemente importantes) como para merecer la pena estudiarlas como fundamentales.

Fuente

2009-12-07 jakeboxer

+2

montones y colas prio podrían clasificarse como fantasía: P –

+1

Probablemente cualquier cosa más allá de matrices y listas vinculadas podría clasificarse como fantasía: P – jakeboxer

+1

'fantasía' es casi seguro una escala analógica en lugar de una opción binaria, si puede ser incluso bien definido –

Respuesta

9

Sets

Como principio no digo tratar [anySearhEngine] en él, pero puede obtenerlos esta lista: http://en.wikipedia.org/wiki/List_of_data_structures

Fuente

2009-12-07 16:16:00 Peter

+0

Un conjunto es más una construcción de modelado que una estructura de datos fundamental. –

+4

en mi humilde opinión es una estructura de datos muy fundamental – Peter

+0

Oh wow. Busqué cosas como esta (tanto en Wikipedia como en Google), pero de alguna manera no me encontré con esta lista. Muchas gracias. – jakeboxer

0

Usted ha olvidado los básicos: struct, object y enums.

Fuente

2009-12-07 16:16:49

+0

Estas construcciones son específicas del idioma y pueden ser serializadas ontop de tipos fundamentales. –

+0

Considero que estos son tipos de datos, no estructuras de datos. Me imagino que hay grandes argumentos en ambos lados, pero también sé que son fríos, por lo que son irrelevantes para mis propósitos. Buena llamada sin embargo :) – jakeboxer

+0

Las estructuras son un tipo de mapeo de nombre a valor. Mientras que el lenguaje C 'struct' es específico del idioma. El "registro" (en COBOL o el lenguaje de Pascal) existe en múltiples idiomas. Esta es la base para las definiciones de "clase". Entonces yo diría que no es específico de un idioma, sino que existe en casi todas partes. –

4

B-Trees y otros multi-árboles

Fuente

2009-12-07 16:16:55 tloach

+0

B-Trees están cubiertos, ¿está sugiriendo los de lujo? –

+0

Vainstah: B-Trees son diferentes de Binary Search Trees. Bien llamado tloach, ha pasado un tiempo desde que me he refrescado en esos. – jakeboxer

+0

En ese caso, deberían ser elegantes de acuerdo con su definición. –

0

me gustaría añadir mapas a menos que desee tener en cuenta que al estar bajo conjuntos.

Fuente

2009-12-07 16:18:42 Glenn

0

Matrices ya que sirven como base para los problemas de modelado, tales como:

  • gráficos
  • afín transformaciones
  • Resolución de sistemas lineales cadenas
  • Markov
  • etc

Fuente

2009-12-07 16:19:09 dfa

+0

No es fundamental ya que se pueden emular utilizando matrices. –

+0

¿qué no se puede emular usando matrices? –

+0

@jk todo puede ser, tal vez debería cambiar la respuesta para que sean matrices "dispersas". No deberían emularse usando matrices y creo que son fundamentales. –

10

también el Graph data structure es fundamental.

Fuente

2009-12-07 16:19:28

+0

Los gráficos son una construcción de mondeo y una estructura de datos. +1 –

+0

Impresionante. He estado estudiando varios algoritmos de gráficos, pero debería actualizar la estructura de datos. – jakeboxer

0

Para obtener ayuda, lea la documentación de Colecciones Java. Desglosan las cosas en un nivel abstracto (Conjunto, Lista y Mapa) y un nivel de implementación (ArraySet, HashSet, ArrayList, LinkedList, TreeMap, HashMap).

Para obtener ayuda, lea la documentación de Python Collections. Desglosan las cosas en clases base abstractas, como Set, Sequence y Map, que se crean a partir de las funciones mixin de una colección.

Fuente

2009-12-07 16:20:48

+0

publicación offtopic, él no está preguntando sobre los nombres de los manuales de programación. –

+0

Lo sentimos, pero el material de referencia en estas referencias de idiomas responderá la pregunta. –

+0

Bueno, la mayoría de esos tipos existen para proporcionar garantías de complejidad, y como tales no son fundamentales. Dudo que los manuales vayan a discutir los contenedores de una manera neutral para el idioma tampoco. –

4

cuerdas, a pesar de que pueden implementarse como matrices bajo el capó (como lo son varias otras estructuras de datos).

Cualquier programa que interactúe con el usuario usará cadenas. Es importante saber cómo manipular cadenas.

Fuente

2009-12-07 16:22:19 catchmeifyoutry

+0

Tipos de datos variables, muchos elementos de implementación para ser considerados un tipo de datos fundamental ... pero +1 ya que son demasiado importantes como para ignorarlos. –

+0

Bastante justo. Estoy un poco al margen sobre si las cadenas merecen consideración por separado de las matrices, pero no puede doler, sobre todo porque son tan importantes. – jakeboxer

1

algunas pueden ser consideradas menos fundamental que otros: vectores

  • matemáticos/matrices de
  • gráficos, listas de adyacencia/matrices de
  • tries árboles prefijo/sufijo
  • indexación espaciales - árboles quad/kd -trees r-trees
  • secuencias/secuencias cadenas terminadas nulas/grandes entradas

Fuente

2009-12-07 16:26:59

+0

Hay bastante sofisticado:/ –

2

Quadtree s, como el tipo más simple de índice espacial.

Fuente

2009-12-07 16:29:11

+0

interesante y complejo, pero al igual que se aplica estrechamente al espacio en 2-d, es fundamental. –

+0

¿Podría sugerir árboles R o árboles QR? son una extensión interesante de quadtrees. http://en.wikipedia.org/wiki/R-tree – rmeador

+0

Vale, para aclarar, el árbol R es más como una extensión de un árbol B, y el árbol QR es una fusión de un árbol cuadrangular y una R -tree – rmeador

1

Bit array no es fundamental, pero es muy práctico y se puede representado de manera eficiente el uso de números enteros (y operadores bit a bit)

Fuente

2009-12-07 16:35:39 dfa

+0

+1 úselos todos los días, ¡muy fácil y rápido! –

1

Tuples.

Además, si pudiera nominar una estructura de datos no básica, sería el prefijo con partición de bits persistente Hash Tries de Clojure.En general, creo que la persistencia es una propiedad muy importante y con frecuencia pasada por alto de cualquier estructura de datos.

Fuente

2009-12-07 16:42:56

3

creo que su pregunta no es clara, ya que está mezclando aplicación y propósito ...

la siguiente tipos describen aplicación:

  • lista enlazada
  • lista doblemente enlazada
  • skip list
  • array
  • dynamic array
  • tabla hash
  • (binario) árbol
  • "gestiona" árboles (binarios) (montones, niveladas árboles etc., es decir, árboles donde inserción y eliminación no se realiza directamente, sino a través de un procedimiento que garantiza ciertas limitaciones para el árbol)
  • gráfico (aunque muy elegante)

el siguiente objetivo describir:

  • pila (significa FILO & puede ser implementado por una lista vinculada, pero también con una matriz o vector)
  • cola (significa FIFO & puede ser implementado por una lista doblemente enlazada, o tal vez de otras maneras sensibles)
  • quitar de la cola (...)
  • cola de prioridad (significa "más alto/bajo llave, primero en salir" este es un concepto abstracto, que puede ser implementado en many different ways)
  • mapa/gama/diccionario asociativa (que significa asignar claves a los valores a menudo requiere una función adicional para convertir claves en claves válidas para la tabla o árbol hash subyacente)
  • conjunto (es decir, es una colección, que es iterable y puede decir si un valor es un elemento del conjunto o no) cada valor, que es un elemento del conjunto debe aparecer exactamente una vez durante la iteración. Un conjunto puede ser mutable, o no (puede permitir agregar o eliminar elementos). Se pueden proporcionar rutinas para intersección, unión, diferencia (por ejemplo, como métodos en OOP .) cuando se trata de la aplicación, hay una serie de posibilidades)

así, no habría una última cosa que considero mucho la pena mencionar: algebraic data types ... en función del idioma, que o bien existen de forma nativa, o tienes que emularlos ... haXe y C# (hasta donde he oído) serían dos idiomas imperativos que los ofrecerían simplemente permitiendo parámetros para enumeraciones ... se pueden usar para implementar listas, árboles y muchas otras cosas agradables ... por ejemplo, son perfecto para representar AST sy muchas otras estructuras complejas ...

Fuente

2009-12-07 17:50:40 back2dos

+0

Entiendo lo que dices, pero todavía son estructuras de datos distintas; puede estar bien versado en listas vinculadas, matrices y otras formas de implementar stacks sin entender las pilas, y puede estar bien versado en stacks sin entender sus implementaciones. Estoy intentando enumerar las estructuras de datos fundamentales, ya sean implementaciones o interfaces. – jakeboxer

0

Un "objeto de función", "puntero de función" o "cierre" no se puede implementar en ciertos lenguajes restrictivos que tienen matrices, listas vinculadas, etc. Pero quizás estén más cerca de los tipos de datos que de las estructuras de datos.

El "rope" implementation (como se implementó en la biblioteca "cord") es mi implementación favorita de la estructura de datos abstractos de "cadena", pero quizás no es realmente "fundamental".

Fuente

2010-05-21 22:47:13

Cuestiones relacionadas

 Cuestiones relacionadas