uniones programacion funciones estructuras estructura ejemplos datos con ats arreglo anidadas c++ data-structures

c++ - programacion - Estructuras de datos... entonces, ¿cómo los entiendo?



programacion ats struct (21)

Aquí hay un buen artículo para comenzar: http://www.codeproject.com/KB/cpp/linked_list.aspx Comience con una simple lista vinculada. Es muy fácil y lo entenderás mucho más fácil que las otras estructuras de datos. La pila y la cola son conceptualmente incluso más fáciles, pero se basan en la lista vinculada simple. Luego puede pasar a listas y árboles doblemente vinculados. Esperando ver sus preguntas de codificación, ¡Buena suerte! :)

Así que soy un estudiante de Ciencias de la Computación y en aproximadamente una semana más o menos ... Retomaré un curso de Estructuras de Datos, usando C ++ para aplicar la teoría. Sí, dije "retomando". Tomé el curso el otoño pasado y siento que hay más que necesito aprender. Siendo estudiante, siento que DEBO conocer los conceptos básicos porque será mucho más fácil comprender nuevos conceptos en clases futuras al conocer los conceptos básicos ... sin tener que volver a aprender cada vez.

La primera vez, no tenía experiencia en C ++ y el curso esperaba que codificáramos para el final de la primera semana. Luché para superar varias de las primeras asignaciones de programación (MP). Huelga decir que me acostumbré y tuve pocos problemas con la sintaxis durante el resto del semestre. Pero luego surgieron las estructuras de datos más duras y la teoría (Big O) se convirtió en la parte difícil.

En general, fue una gran experiencia, pero creo que mi problema fue que no desarrollé buenos hábitos de estudio. Hice a los diputados y aparecí para dar una conferencia, pero parece que mi corazón no estaba allí conmigo. Quiero cambiar esto la segunda vez porque mirando hacia atrás en la clase, lo pasé muy bien y disfruté el material. Pero me encontré pasando demasiado tiempo pensando / configurando las estructuras de datos cuando necesitaba pasar el tiempo pensando en cómo usar la estructura de datos para usarla de manera efectiva.

La teoría del aprendizaje es difícil (sobre todo porque no es tan emocionante), entonces, ¿cómo debo aplicarme para comprender realmente la clase cubierta de estructuras de datos? Siempre he sido un aprendiz visual, un aprendiz interactivo ... No quiero perder el tiempo simplemente haciendo mis MP. Por el contrario, quiero pasar el tiempo de tal manera que realmente aprenda / entienda los conceptos y luego aplique directamente el conocimiento.

Estoy buscando sugerencias ... tal vez consejos sobre hábitos de estudio que han funcionado para ti en el pasado aprendiendo tales conceptos ... o sugerencias sobre buenas técnicas para tomar notas ... cualquier cosa que quieras compartir :) ... y lo más importante, cómo prepararse antes de que comience el semestre.

Por favor, siéntase libre de enviar comentarios, incluso si se ha seleccionado una respuesta. Estoy buscando su consejo ... esta es la razón por la que publiqué :) ¡Gracias!

NOTA : Estructuras de datos y temas cubiertos en el curso: listas, pilas, colas, árboles (diferentes tipos), tablas hash, gráficos, técnicas de búsqueda / clasificación / recorrido.

ACTUALIZACIÓN : Aquí hay una lista de enlaces y referencias compilados a partir de las respuestas hasta el momento.

ACTUALIZACIÓN 2 : Aquí hay una lista de algunas fuentes más que encontré:

Cuando enseñé programación, siempre refería los libros Demystified a mis alumnos.

Te sugiero que leas:
- Estructuras de datos desmitificadas
- OOP Desmitificado

Estos dos libros hacen un buen trabajo al desglosar las estructuras de datos y el principio de OOP en términos más simples y fáciles de leer, con ejemplos fáciles de seguir. Es una buena visión general, pero no entra en las estructuras de datos proporcionadas por el STL.

En mi opinión, estas cosas se aprenden mejor en el trabajo, o por experiencia que en un curso de teoría. La mayoría de las veces, mientras estaba en la escuela, trabajar duro para estar por delante de la curva era la parte importante, que creo que es similar a la experiencia que ha tenido. Si bien es encomiable que desee comprenderlo a fondo, siempre que sepa dónde encontrar un buen material de referencia cuando lo necesite, entonces el curso ha logrado su objetivo.

La mayoría de las clases se basarán en el conocimiento que has adquirido en clases pasadas. Volverá a encontrarse con estos detalles en sus estudios y sus profesores deberían poder ayudarlo a aplicar lo que aprendió en el pasado a su trabajo de clase actual. Como aprendiz interactivo, las horas de oficina, las pasantías y las oportunidades de mentor parecen mejores formas de obtener la información que desea.

¡Buena suerte!

En términos prácticos, encuentro que las estructuras de datos requieren una sólida comprensión de los indicadores y la memoria.

Por ejemplo, debería poder comprender por qué la lista vinculada a continuación no funciona en menos de un minuto.

Pero, para comprender por qué no funciona, debe comprender cómo se presenta la memoria en C y C ++, y comprender intuitivamente el concepto de un puntero.

A algunas personas les gustan las fotos y dibujar imágenes. A otras personas les gusta ver el MIT OpenCourseware. Recomiendo intentarlo al menos.

class node { int data; node* next; node* addnode() { node newnode; this->next = &newnode; return &newnode; } };

Esta es una aproximación de una implementación (con errores) de una lista vinculada que escribí hace 10 años cuando estaba aprendiendo estructuras de datos.

Y como nota final, la práctica y la teoría son el yin y el yang de un programador / desarrollador / informático de calidad. No puedes ser realmente competente sin ambos.

Esto es lo que más me ayudó ... Dado que usted es una persona visual, busque algunos algoritmos de clasificación visualizados, recorridos de árbol, hashing y etc. para tener una idea general de lo que está sucediendo. Después de eso, intente hacer un programa simple usando diferentes estructuras y experimente con diferentes permutaciones de ellas; tal vez para un ejemplo, puede hacer una lista vinculada para comenzar, luego conviértala en una lista circular enlazada, luego conviértala en una lista doblemente enlazada, luego conviértalo en una lista enlazada doblemente circular, y así sucesivamente ...

Solo tienes que experimentar con las estructuras y, a medida que lo haces, comenzarás a ver qué estructuras de datos son apropiadas para las aplicaciones que desarrollarás.

Aquí hay algunas buenas referencias para usted. Algoritmos de clasificación: http://www.sorting-algorithms.com/ Traversales de árbol: http://nova.umuc.edu/~jarc/idsv/lesson1.html Cruces de gráficos: http: //www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html

En cuanto a la eficiencia (análisis Big O), te llegará de forma más o menos natural una vez que entiendas lo que está sucediendo en el nivel algorítmico de cada operación de la estructura de datos.

Una cosa que mi universidad enfatiza es el desarrollo de nuestra propia implementación de estructuras de datos (que es el aprendizaje de abajo hacia arriba) sin sumergirse en las plantillas de C ++ preestablecidas (aprendizaje de arriba hacia abajo). Al hacerlo desde cero, realmente comprende la sobrecarga que implica insertar, eliminar, buscar (atravesar) y acceder a los datos de una determinada estructura, lo que ayudará a su intuición cuando diseñe un sistema en el futuro.

Honestamente, originalmente soy un programador de C ++ autodidacta (con mi referencia principal es el código de dominio público del motor de juegos Source de Half-Life 2), y aprendí mucho de lo que me ayudó a través de Data Structures al elaborar diagramas y leer comentarios y código

Tal vez soy solo un prodigio o algo así, porque siempre me pareció relativamente fácil, pero aprendí durante MUCHO tiempo leyendo, pensando y analizando cuáles podrían ser los usos particulares de cada estructura, y por qué cada estructura existe como algo separado de las otras estructuras de datos en primer lugar.

Después de haber escrito algunos proyectos de código serio (es decir, Connect Four y un tirador de desplazamiento lateral, así como trazadores tridimensionales en 3D y programas de dibujo en 2D) en la calculadora TI-83 Plus severamente limitada en la escuela secundaria (ps Uso de TI-Basic, not Assembly), me di cuenta de que tipo de operaciones eran más eficientes, y me di cuenta de cuán limitado era el sistema de listas incorporado (un Vector básico) para el almacenamiento de datos en ciertas situaciones. También descubrí cómo funcionaba Big-O cuando probé a programar el tiempo de ejecución de un programa con listas de entrada de diferentes tamaños.

Practique, piense en cosas mientras las hace, y trate de descubrir cómo y por qué funcionan, y nunca tenga miedo de ensuciarse con las pruebas. Después de todo, ¿qué es la ciencia sin experimentación?

La única forma de aprender de manera significativa estructuras de datos y algoritmos es verlos aplicados a problemas del mundo real y usarlos para resolver problemas del mundo real. Codificarlos en aplicaciones que funcionen, incluso si se idearon, reforzará los conocimientos teóricos de tal forma que tendrá una mejor oportunidad de conservar las ideas e integrarlas en su enfoque personal de resolución de problemas.

La clave para aprender estructuras de datos es comenzar con algo pequeño, y luego construir sobre eso. Comencemos con una estructura C simple:

struct Person { char name[100]; int age; };

Esta estructura de datos representa a una persona. Debe asegurarse de comprender los conceptos de estructura simple como estos, y luego puede pasar a cosas más grandes.

Cuando empiezas a hablar sobre estructuras de datos como apilamientos y colas, por ejemplo, primero intenta comprender conceptualmente lo que está haciendo la estructura de datos. Por ejemplo, con un stack, estamos utilizando el principio LIFO, es decir, Last In First Out. Con una cola, estamos utilizando el principio FIFO (primero en entrar primero en salir).

Y luego está el que hace tropezar a muchas personas, la lista vinculada. Debes entender bien los punteros para este, así que antes de intentar abordar listas enlazadas, comienza con algo simple:

int* x; int y = 10; x = &y;

Debería poder mirar ese código e inmediatamente saber qué está haciendo. Si no puede, entonces no está listo para pasar a estructuras de datos más avanzadas como listas vinculadas.

El punto principal que trato de hacer es que necesites descifrar lo básico, y luego construir sobre eso. También es importante mantenerse al día con la clase con mucha diligencia, pregúntele a su maestro o tutor si tiene problemas, y asegúrese de estar en el camino cada semana y no quedarse atrás.

Las clases de informática se parecen mucho a las clases de matemáticas, cada semana usualmente se basa en todo lo que aprendió de las últimas N semanas. Entonces, si no está comprendiendo un concepto clave, como los indicadores, por ejemplo, tendrá grandes dificultades durante el resto del semestre.

Me gusta la respuesta de dcp.

La mejor forma de familiarizarse con las estructuras de datos es escribir mini ejemplos. Incluso si los copia de su libro, si puede lograr que funcionen y se compilen, y los tipeó con sus propios dedos, aprenderá mucho.

Mientras lee su libro, y después de cada conferencia, escriba los programas más cortos que pueda crear y trabajar con (mostrar, usar, etc.) la estructura de datos que acaba de aprender.

Luego, cuando tenga que hacer sus asignaciones reales, aprenderá aún más a medida que lo intente, tome sus mini ejemplos y los conecte a la solución de los problemas de asignación.

Creo que escribir el código de trabajo más corto / más pequeño posible para las estructuras de datos individuales es muy útil. Además, no tema copiar el código (para su propia edificación, no para sus asignaciones entregadas) ... Si copia al escribir y no copiar pegando, termina aprendiendo mucho, ya que lo obliga a mira cada personaje en el código.

Si las estructuras de datos completas parecen "demasiado" para entender, entonces comience escribiendo pequeños ejemplos de los componentes de las estructuras de datos. Así que guarde un título de libro con un puntero. A continuación, almacene muchos títulos de libros con punteros a punteros. Lea el título de un libro con notación de corchetes y aritmética de punteros. Usa la recursión en funciones simples donde está claro lo que está sucediendo ... Por ejemplo, la recursividad para mostrar el factorial de un número es más simple para envolverte que recursividad para mostrar un árbol binario (en mi opinión) ... ..

Verá cuáles son sus áreas problemáticas, y trate de aislarlas para que sean lo más pequeñas y específicas posible, y luego escriba un programa tan breve como sea posible que trate con esa área problemática ... y luego construir.

Sus conferencias tratan sobre estructuras de datos completas ... gigantescos bancos de nubes Cummulus de teoría ... así que, esencialmente, son de arriba hacia abajo. Aislar pequeños problemas de sintaxis y uso en mini problemas es de abajo hacia arriba. Entonces tu maestra te ayuda a atacar desde arriba, atacas desde abajo practicando, ¡y muy pronto no hay nada en el medio!

No estoy seguro si esto es de alguna ayuda, de verdad, pero puede ser algo alentador.

Estaba en el mismo barco cuando tomé Data Structures hace 4 años. Pasé por la clase con suficiente conocimiento para pasar y obtener la B, al menos, en la clase, aunque no entendí mucho.

No entendí las plantillas, las listas enlazadas, los punteros "de este", y realmente tampoco entendí los punteros en general, lo cual dificultó enormemente mi habilidad. Milagrosamente hice lo que se requería en la tarea y las pruebas (aunque los puntajes de las pruebas seguían siendo bajos para todos y mi maestra terminó curvándolos) y terminé con una B.

Después de eso, tomé otras clases durante algunos años. Encontré que en estas clases se enseñaban conceptos diferentes por separado que me ayudaron a comprenderlos mejor. Los algoritmos enseñaron más sobre clasificación y Big O, Assembly enseñó más sobre lo que sucedía "debajo del capó" de la computadora que me ayudó a entender los indicadores, etc.

Me di cuenta del penúltimo semestre de mi quinto año que prácticamente conocía todos los conceptos de Data Structures y que ni siquiera había dedicado ningún esfuerzo adicional para aprenderlos, al menos no desde el punto de vista de retroceder e intentar comprender específicamente. Estructuras de datos, si eso tiene sentido.

Sin ningún esfuerzo real terminé escribiendo una pila de listas enlazadas con plantillas y haciendo cola para un par de tareas en Sistemas Operativos y las entendí. Me impactó. Estoy seguro de que será lo mismo para ti. Dale tiempo y concéntrate en otras clases y todo hará clic. Pareció que pasaría una eternidad para que todo hiciera clic para mí, pero lo hizo.

Espero que ayude.

Para mí, el mejor libro que he encontrado (hasta ahora) para comprender las estructuras de datos es The Algorithm Design Manual de Steven Skiena.
Aparte de la primera parte que cubre análisis de algoritmos, algoritmos y estructuras de datos, la segunda parte es absolutamente invaluable para encontrar (o al menos reducir) la estructura / algoritmo de datos adecuado para resolver un problema.

Práctica práctica práctica.

El primer consejo que tengo para ti es llegar a ser lo más competente posible en C ++.

Las estructuras de datos y la programación son dos temas muy diferentes. Si te encuentras luchando con la programación, es poco probable que puedas comprender las estructuras de datos.

¿Cómo te vuelves competente en C ++? Práctica práctica práctica. Programa todo Aprenda todo lo que pueda al respecto. Escribe docenas de pequeños programas. Cualquier cosa que pueda hacer para sentirse cómodo con C ++.

Si adquiere dominio en C ++, entonces le aseguro que las estructuras de datos serán más fáciles. (Tenga en cuenta que no dije fácil, dije más fácil :))

Puedo recordar mi primer curso de estructuras de datos. Recuerdo que estaba un poco abrumado al principio.

Yo era más un aprendiz visual. Para captar mejor el material, realmente ayudó a ver imágenes. Solía ​​dibujar los pasos de insertar, borrar e iterar a través de estructuras de datos como una lista enlazada o una cola. Tomó mucho papel antes de que terminara, pero valió la pena.

Una vez que comencé a dibujar el proceso de inserciones y lo que no, la transición a la programación de la estructura de datos fue mucho más fácil.

Ser capaz de visualizar lo que estaba sucediendo en la memoria realmente me ayudó. Y, como otros mencionaron antes que yo: ¡practica, practica, practica!

Que hay una gran parte del éxito.

¡Buena suerte!

Si eres un aprendiz visual, pregúntale a tu instructor por más diagramas. Puede preguntar a otros estudiantes si puede estudiar con ellos. Tal vez uno de ellos puede explicarte las cosas de una forma que puedas captar más fácilmente

Si puede visualizar la implementación de estructuras de datos en la vida real o resolver problemas de la vida real, entonces puede que le resulte más fácil de entender.

Aquí hay algunos

  1. Lista enlazada FIFO: esta es la unidad en McDonalds
  2. Lista ligada de LIFO - Una pila de platos de comida
    • Búsqueda y clasificación: un rolodex (si eres viejo y has visto alguna de estas cosas)

Si tiene problemas con la notación O, entonces ''Introducción a los algoritmos'' de Cormen et.al. introduce estos conceptos teóricos en un estilo fácil de entender. Bueno, este libro es básicamente la biblia de las estructuras de datos básicos. Las pruebas de límites de tiempo de ejecución / espacio siempre se presentan de una manera muy instructiva.

Como siempre, si estudias tal libro, no solo lo leas, sino que trates de trabajar en la mayoría de los ejercicios. Usualmente, hacer esto es muy efectivo para aprender cosas.

Otra técnica general: intente unirse a un grupo de estudio local de otros dos o tres estudiantes; por lo general, discutir el material con otros (cara a cara) y al tratar de explicar el material autoestudiado a sus compañeros, le da muchos consejos, que cosas que necesitas cubrir más.

Para dominar C ++ para los ejercicios, ''The C ++ Programming Language'' de Stroustrup ofrece una buena introducción y referencia a los diversos conceptos de lenguaje. Dado que C ++ es un lenguaje de paradigmas múltiples, los principiantes a menudo se confunden con los conceptos que realmente se deben usar en la práctica para resolver ciertos problemas. Para ayudar con ese ''Effective C ++'' de Scott Myers es un buen comienzo.

Si su curso hace un uso intensivo del STL, entonces también existe el ''STL efectivo''. El estilo de escritura de Scott Myers generalmente se considera muy apropiado para los principiantes.

Un buen recurso es The NIST Dictionary of Algorithms and Data Structures . No te vas a sentar y memorizar toda esta información, y no deberías usarla para evitar codificar tus propias estructuras, eso anularía por completo el valor de la clase, pero este sitio sirve como una gran referencia porque enlaza las estructuras de datos con los algoritmos que las utilizan y también muestra algunas variantes, que proporcionan información sobre cómo puede modificar las estructuras para otros usos.

Espero que ayude. Buena suerte.

Una cosa que siempre debe recordar es que las estructuras de datos no existen. Fueron inventados para satisfacer una necesidad, lo que significa que son buenos por algunos motivos, pero no por otros.
Averigüe cuáles son esas razones, para qué sirve la estructura de datos, intente descubrir el Big O para las operaciones antes de que se lo digan.
Siempre compare las estructuras de datos. Incluso con el más simple de ellos: una matriz. Tómela como punto de partida y compare cada estructura de datos que encuentre con una matriz. A veces encontrarás pequeños trucos que te ayudarán a evitar el uso de la estructura de big data por completo.
Para mí, lo que me ayudó a entender muchas estructuras de datos y algoritmos fue el applet aquí, y espero que también te ayude: Applet

Ya has recibido algunos enlaces e ideas interesantes. Espero poder proporcionar un punto de vista diferente:

Aprendí a visualizar y "me gusta" las estructuras de datos al enseñarme que la memoria de la computadora es como una lista realmente larga. Las estructuras tienen un diseño diferente en la memoria. Al visualizar las estructuras en la memoria, me resultó obvio (e interesante) cómo funcionan. Conocer el diseño de los datos en la memoria es increíblemente importante para un programador ya que las máquinas en crecimiento continuo de hoy en día a menudo se detienen por el acceso a la memoria. Un buen diseño de la memoria facilita la carga de la CPU para recuperar los datos de la memoria, de modo que la CPU no tenga que esperar a que lleguen los datos.

Estructuras de datos es el diseño de los datos en una memoria. Considere la memoria como una lista larga, como una lista de compras pero sin las entradas.

0... 1... 2... 3... 4... 5... 6...

Cuando colocas estructuras en la memoria, esencialmente llenan estas ranuras en la memoria.

Una lista es muy simple, simplemente llena la lista de memoria desde arriba y abajo:

0 Element 0 1 Element 1 2 Element 2 3 Element 3

Aunque a veces quiera cambiar el elemento 2 por otra cosa, quizás sea cero. Así funcionan las listas. Puede acceder a los datos en la estructura conociendo su índice (en este caso, 0 .. 3).

Las pilas son diferentes. Solo puede acceder a la "parte superior" de una pila "empujando" un elemento hacia la parte superior de la misma o "haciendo saltar" un elemento desde la parte superior. Empujar significa agregar otro elemento y la parte superior vieja se vuelve invisible. Poping significa eliminar el elemento superior y el que está debajo se vuelve visible.

0 [ Hidden data ] . [ Hidden data ] . [ Hidden data ] . [ Hidden data ] n [ Hidden data ] n+1 Element 4

Las listas enlazadas son diferentes. Una lista vinculada contiene un puntero (índice en la lista de memoria) a los datos, y un puntero al siguiente elemento:

0 Data: Memory index 0x00000100 1 Next: Memory index 6 2 3 4 5 6 Data: Memory index 104 7 Next: Memory index 8 ... 100 Data pointed to from first member 101 102 103 104 Data pointed to from second member

Queue es como una pila más poderosa, tienes acceso tanto a la parte inferior como a la superior. Solo puede insertar elementos en la parte superior y solo puede abrir elementos desde abajo.

0 (bottom) Element (ready to be popped) 1 [ Hidden data ] 2 [ Hidden data ] 3 [ Hidden data ] . . . n (top) (empty, ready to be pushed / be given data)

Al visualizar el diseño de cada estructura de datos, se hicieron mucho más obvios para mí en cuanto a cómo requieren memoria y cómo funcionan realmente ( también en la memoria ). Espero que mis ejemplos te hayan brindado un breve conocimiento inicial para que puedas basar tus futuros estudios en. Como ejemplo final sobre estructuras de datos, le daré un árbol binario desequilibrado que ha tenido el siguiente orden de inserción de elementos: 3, 2, 1, 10, 9, 8, 6, 5, 4, 7

El árbol comienza en la dirección de memoria 100, ya que la dirección de memoria 0 no es válida y la usaré como "sin puntero".

100 Value: "3" 101 Left ptr: 103 102 Right ptr: 109 103 Value: "2" 104 Left ptr: 106 105 Right ptr: 0 106 Value: "1" 107 Left ptr: 0 108 Right ptr: 0 109 Value: "10" 110 Left ptr: 112 111 Right ptr: 0 112 Value: "9" 113 Left ptr: 115 114 Right ptr: 0 115 Value: "8" 116 Left ptr: 118 117 Right ptr: 0 118 Value: "6" 119 Left ptr: 121 120 Right ptr: 127 121 Value: "5" 122 Left ptr: 124 123 Right ptr: 0 124 Value: "4" 125 Left ptr: 0 126 Right ptr: 0 127 Value: "7" 128 Left ptr: 0 129 Right ptr: 0

¡Espero que ayude!

Yo recomendaría obtener un buen libro sobre algoritmos (''Introducción a los algoritmos'' de Cormen et al. Sería mi recomendación). A través del libro, desarrollarán y pondrán en práctica diferentes estructuras de datos y probablemente se den cuenta de para qué sirve cada estructura. Las estructuras de datos solo son útiles como medio para lograr un objetivo diferente: resolver un problema en particular.

Dependiendo de cuánto tiempo tenga o desee gastar en él, puede tratar de obtener problemas de diferentes concursos de programación como el ACM ICPC. La mayoría de los problemas requerirán que ejercites este conocimiento. Tenga en cuenta que tanto los algoritmos como las estructuras de datos son independientes del idioma, por lo que si tiene un buen conocimiento de cualquier otro idioma, simplemente úselo.