Compendio de estructura de datos

2. ¿Qué es una estructura?
3. Pila simple, Pila circular, Pila doble
4. Cola simple, cola circular, cola doble
5. Lista
6. Árboles binarios
7. Los métodos de ordenamiento
8. Conclusión

Introducción

En la clase de estructura de datos programamos 3 proyectos, vimos árboles y 8 métodos de ordenamiento que serán explicados mas adelante.

Los proyectos son:

• Pilas
• Colas
• Listas

Los árboles son:

• Binarios

Los métodos de ordenamiento son:

• Selección directa
• Bubble sort
• Shell sort
• Quick sort
• Merge sort
• Radix sort
• Heap sort
• Tournament

Varios de estos proyectos son muy extensos y se describirá cada punto y código con algo de detalle para un mejor entendimiento.

El lenguaje de los proyectos es c++.

Los métodos de ordenamiento de explicaran en tablas de Excel y también se con algo de detalle.

Qué es una estructura?

La estructura es una manera de conectar los valores y de manera automática conectarlos de manera que tengan algo en común, en estos proyectos utilizamos apuntadores, para no perder rastro de los valores ya agregados.

Un ejemplo de una estructura en C++ seria:

Los que están adentro de la estructura de "nodos" son los valores o apuntadores dentro del nodo. Los apuntadores por dentro del nodo son los que ayudan a conectarse unos con otros.

Los que se encuentran afuera son los apuntadores que ayudaran a mantener record del último y el primer valor que entro.

Pila simple, Pila circular, Pila doble.

Lenguaje: C++

Acciones a una pila simple, pila circular y pila doble:

• Push
• Pop

Que es pila simple?

Pila simple significa el primero en entrar es el ultimo en salir. Es una estructura donde puedes agregar valores y retirarlos. Teniendo solo un apuntador por dentro que ayuda a conectarse con los demás.

Push- Sirve para ingresar valores y agregarlos a la estructura pila dejando el ultimo valor que ingreso arriba con el apuntador externo "top".

Algoritmo:

1. inicio manda a llamar push

    Vacía =3

   

   Sino =8

2. estado de pila?

   

3. crear nodo

   

4. asignación de valor

   

5. los apuntadores externos "bottom" y "top" apuntan al nuevo nodo

   

6. el apuntador interno "next" del nuevo nodo apunta a nulo
7. fin

   

8. crear nodo

   

9. asignación de valor

   

10. el apuntador externo "top" asigna al apuntador interno "next" apuntar al nuevo nodo

     

11. el apuntador externo "top" se actualiza moviéndose al nuevo nodo

    

12. el apuntador externo "top" asigna al apuntador interno "next" apuntar a nulo
13. fin

Para el algoritmo #7 el diseño de la estructura seria:

Para el algoritmo #13 el diseño de la estructura seria:

Y así se podrán agregar mas valores hasta que el usuario desee:

Se debe de tomar en cuenta que los dibujos solo muestran como se mueven los apuntadores y los valores no tienen que ver con los movimientos. El primero que entre se queda con el apuntador externo "bottom" y el ultimo que entre se queda con el apuntador externo "top".

Pop- Sirve para sacar el ultimo valor que fue ingresado. Si hay solo un valor en la estructura, simplemente ya no hay mas valores en la pila. Si se intenta sacar un valor cuando no hay valores se avisara que no hay valores.

Algoritmo:

1. inicio manda a llamar a pop

    Vacía =3

   Solo 1 valor =5

   Sino =7

2. estado de pila?

   

3. mensaje "no hay valores en la pila
4. fin

   

5. se muestra el valor por borrar y los apuntadores externos "top" y "botton" serán nulos
6. fin

   

7. se muestra el valor por borrar y se inicializa un ciclo para desconectar el último valor y hacer el penúltimo como ultimo.

   

8. el apuntador externo "top" asigna al apuntador interno "next" apuntar a nulo
9. fin

Para el algoritmo #6 el diseño de la estructura seria:

En el algoritmo #7 el ciclo sirve para recorrer l estructura de abajo hacia arriba y encontrarse con el penúltimo, y de esa manera poder desconectar el ultimo y actualizar el apuntador externo "top" hacia abajo con la ayuda del auxiliar.

Para el algoritmo #9 el diseño de la estructura seria:

El penúltimo que este se queda con el apuntador externo "top" y el último valor, antes de que se hiciera el pop, se desconecta de la estructura.

Que es una pila doble?

Esta se trata de que cada valor tenga doble conexión o dos apuntadores internos "next" y "prev", que ayudara a este valor a tener comunicación con el valor que entro antes que el y el valor que entro después que el.

Y se lleva acabo de la misma manera en la acción push pero agregando el apuntador interno "prev", puedes comparar con el código que se ve a continuación:

Cuando se trata del primer valor y la pila esta vacía:

Cuando la pila tiene más de un valor:

Que es pila circular?

Este tipo de pila no tiene mucha diferencia a la pila doble, lo único que tiene de diferente es que las conexiones en los apuntadores internos "prev" y "next" Nunca apuntan a nulo, solo cuando no existe ningún valor en la pila, sino es como o veremos a continuación:

Cuando solo tiene un solo valor:

Cuando solo tiene más de un valor:

Cola simple, cola circular, cola doble

Lenguaje C++

Acciones a una pila simple, pila circular y pila doble:

• In
• Out

Su estructura en código se formara de la siguiente manera "estándar" para mejor explicación:

Que es una cola simple?

Esta significa el primero en llegar es el primero en salir. La estructura de este es como cualquier tipo de fila como: la cola que tienes que hacer en un lugar esperando a ser atendido y como todos sabemos, el primero en llegar estará en frente de la cola y será el primero en salir.

In- Sirve para ingresar los valores que se van agregando, este valor será el primero en la cola y se quedara con el apuntador externo "front", los demás serán parte de la cola y el ultimo que este en la cola será apuntado por el apuntador externo "end".

Algoritmo:

1. inicio manda a llamar in

   Vacía =3

   sino =8

2. estado de cola?

   

3. crear nodo

   

4. asignación de valor

   

5. los apuntadores externos "end" y "front" apuntan al nuevo nodo

   

6. el apuntador interno "next" del nuevo nodo apunta a nulo
7. fin

   

8. crear nodo

   

9. asignación de valor

   

10. el apuntador externo "nuevo" asigna al apuntador interno "next" del nodo del nuevo valor apuntar al nodo que esta apuntando el apuntador externo "end".

    

11. el apuntador externo "end" se actualiza moviéndose al nuevo nodo

    

12. el apuntador externo "end" asigna al apuntador interno "next" apuntar a nulo
13. fin

Para el algoritmo #7 el diseño de la estructura seria:

Para el algoritmo #13 el diseño de la estructura seria:

Out- Sirve para sacar el primer valor que fue ingresado. Si hay solo un valor en la estructura, simplemente ya no hay mas valores en la pila. Si se intenta sacar un valor cuando no hay valores se avisara que no hay valores.

Algoritmo:

1. inicio manda a llamar a out

   Vacía =3

   Solo 1 valor =5

   Sino =7

2. estado de cola?

   

3. mensaje "no hay valores en la pila
4. fin

   

5. se muestra el valor por borrar y los apuntadores externos "end" y "front" serán nulos
6. fin

   

7. se muestra el valor por borrar y se inicializa un ciclo para desconectar el primer valor y hacer el segundo como primero.

   

8. y para eso el apuntador externo "front" se actualiza con al ayuda del apuntador externo "aux" y asigna al apuntador interno "next" apuntar a nulo
9. fin

Para el algoritmo #6 el diseño de la estructura seria:

Para el algoritmo #7 el diseño de la estructura seria:

Para el algoritmo #9 el diseño de la estructura seria:

El segundo que este se queda con el apuntador externo "front" y el primer valor, antes de que se hiciera el pop, se desconecta de la estructura.

Todo esto es un proceso de programación muy delicada ya que con cualquier mal asignación de apuntadores, tanto internos como externos, puede arruinar la estructura de los valores y hasta perder la información.

Que es cola doble?

Esta se trata de que cada valor tenga doble conexión o dos apuntadores internos "next" y "prev", que ayudara a este valor a tener comunicación con el valor que entro antes que el y el valor que entro después que el.

Y se lleva acabo de la misma manera en la acción in pero agregando el apuntador interno "prev", puedes comparar con el código que se ve a continuación:

Cuando se trata del primer valor y la cola esta vacía:

Cuando se trata de más de un valor:

Que es una cola circular?

Este tipo de cola no tiene mucha diferencia a la cola doble, lo único que tiene de diferente es que las conexiones en los apuntadores internos "prev" y "next" nunca apuntan a nulo, solo cuando no existe ningún valor en la pila, sino, es como o veremos a continuación:

Y su código seria:

Para el primer valor y la cola vacia:

Para el resto de los valores que entren con la cola con mas de una valor;

Lista

Lenguaje C++

Acciones a una pila simple, pila circular y pila doble:

• Up
• Down

Su estructura en código se formara de la siguiente manera "estándar" para mejor explicación:

Que es una lista?

Esta se refiere a las listas que están organizadas por orden alfabético o numérico, dependiendo de la necesidad. La diferencia de esta lista a la de Pilas y Colas, es que esta tiene que estar organizada de alguna manera y mientras los datos se van agregando la lista tiene sus reglas de cómo ordenar los datos.

Up- Sirve para ingresar los datos e irlos organizando. El valor que entre tiene que ser comparado con los demás para saber cual es su posición en la orden en que este diseñada.

Algoritmo:

1. inicio manda a llamar up

   Vacía =3

   Solo 1=8

   Sino =16

2. estado de lista?

   

3. crear nodo

   

4. asignación de valor

   

5. los apuntadores externos "last" y "first" apuntan al nuevo nodo

   

6. el apuntador interno "next" y "prev" del nuevo nodo apunta a nulo
7. fin

   

8. crear nodo

   

9. asignación de valor

   

10. el apuntador interno "next" y "prev" del nuevo nodo apunta a nulo

    =14

11. =12

    

12. el apuntador externo "nuevo" asigna al apuntador interno "next" apuntar al apuntador externo "first". el apuntador externo "first" asigna al apuntador interno "prev" apuntar al apuntador externo "nuevo". se actualiza el apuntador externo "first" con el apuntador externo "nuevo".
13. fin

    

14. el apuntador externo "last" asigna al apuntador interno "next" apuntar al apuntador externo "nuevo". el apuntador externo "nuevo" asigna al apuntador interno "prev" apuntar al apuntador externo "last". se actualiza el apuntador externo "last" con el apuntador externo "nuevo".
15. fin

    

16. crear nodo

    

17. asignación de valor

    

18. el apuntador interno "next" y "prev" del nuevo nodo apunta a nulo

    =22

19. =20

    

20. el apuntador externo "nuevo" asigna al apuntador interno "next" apuntar al apuntador externo "first". el apuntador externo "first" asigna al apuntador interno "prev" apuntar al apuntador externo "nuevo". se actualiza el apuntador externo "first" con el apuntador externo "nuevo".
21. fin

    

    

22. se inicializa un ciclo para buscar el lugar en el orden y meterlo entre los valores o datos.
23. fin

Para el algoritmo #7 el diseño de la estructura seria:

Para el algoritmo #13 tomando en cuenta que el valor nuevo es menor, el diseño de la estructura seria:

Para el algoritmo #15 tomando en cuenta que el valor nuevo es mayor, el diseño de la estructura seria:

Para el algoritmo #21 tomando en cuenta que el valor nuevo es menor, el diseño de la estructura seria:

Para el algoritmo #23 tomando en cuenta que el valor nuevo es mayor, el diseño de la estructura seria:

Down- Sirve para sacar el valor que el usuario decidió retirar. Si hay solo un valor en la estructura, simplemente ya no hay mas valores en la pila. Si se intenta sacar un valor cuando no hay valores se avisara que no hay valores. Si no se halla el valor se avisa que no se encontró el valor.

Algoritmo:

1. Inicio manda llamar down

   =5

2. =3

   

3. mensaje "no hay valores en la lista
4. fin

   

5. asignación de valor

   =12

6. =7

   =10

7. =8

   

8. se manda el mensaje "el valor a sido retirado" y los apuntadores externos "last" y "first" apuntaran a nulo
9. fin

   

10. se manda el mensaje "ese valor no existe en la lista"
11. fin

    =15

12. =13

    

13. se manda el mensaje "el valor a sido retirado" y el apuntador externo "auxa" apunta al apuntador externo "first". el apuntador externo "first" se mueve con el valor anterior y asigna al apuntador interno "prev" apuntar a nulo y el apuntador externo "auxa" ayuda a desconectar finalmente al valor sugerido
14. fin

    

    

15. se empieza un ciclo recorriendo la lista hasta encontrar el valor y si no lo encuentra se manda el mensaje "el valor no se encuentra"
16. fin

Todo esto es un proceso de programación muy delicada ya que con cualquier mal asignación de apuntadores, tanto internos como externos, puede arruinar la estructura de los valores y hasta perder la información.

Para el algoritmo #9 el diseño de la estructura seria:

Para el algoritmo #14 el diseño de la estructura seria:

Para el algoritmo #16 el diseño de la estructura seria:

Árboles binarios

Los árboles tienen sus diferentes conceptos dependiendo de sus integrantes:

Árbol-

Estructura dinámica

Nodo-

Elemento de la estructura

Padre-

Cuando tiene descendientes

Hijo-

Descendiente del padre

Hermano-

Compañero del hijo

Grado-

No. de hijos

Nivel-

La jerarquía desde raíz

Nodo Terminal-

Hola o hijo solo sin hermanos

Raíz-

Primer nodo

Arco-

Enlace entre nodos

Recorridos en un árbol binario

1. Preorder padre—hijo izq—hijo der
2. Inorder hijo izq—padre—hijo der
3. Postorder hijo izq—hijo der—padre

Ejemplo:

1. Preorder

D-C-H-J-A-E-M-G-K-I-F-B-L

2. Inorder

H-J-C-E-A-M-D-K-I-G-B-F-L

3. Postorder

J-H-E-M-A-C-I-K-B-L-F-G-D

Los métodos de ordenamiento

Estos se refieren la manera de ordenar valores, arios de estos métodos fueron creados por personas entradas en la matemática pero ahora tenemos la facilidad de hallar información sobre estas y como aplicarlas. Aquí se mostraran algunos de los métodos:

Selección directa

Esta se refiere a ir ordenando una lista de valores, agarrando el primer valor de izquierda a derecha y comparándola hacia la derecha, preguntando si el valor de la derecha es menor, si se cumple esa condición entonces el valor que ahora sabemos que es menor seguirá preguntando y así sucesivamente hasta hallar el ultimo valor y el valor que este como el menor de la lista en esa primera pasada, intercambiara posiciones con el primer valor de la lista que comparo, sino hay ninguno menor a la derecha con el primer numero que escogimos ese se queda en el primer lugar y avanzamos con el siguiente numero hasta que se termine toda la lista de comparar.

Ejemplo:

Bubble sort

Este es muy diferente a la selección directa. Las reglas de este son:

• Se comparan los primeros dos de derecha a izquierda
• Si el de la izquierda es mayor se intercambian lugares sino le cede el lugar al menor en ir preguntando hacia la izquierda y de esa manera los menores se van a ir filtrando hasta tenerlos todos en orden

Ejemplo:

La lista 12 3 57 5 22

Quick sort

Este tiene muchas reglas y es muy delicado:

• Primero agarramos el primer valor de izquierda a derecha y lo nombramos pivote
• Luego buscamos el primer mayor de izquierda a derecha y el primer menor de derecha a izquierda
• Cuando estos valores se hayan sin haber cruzado entonces se intercambien entre ellos y cuando se crucen, se encuentra con el valor menor después de la cruzada con el valor mayor y el menor se intercambia con el valor pivote
• Y así cuando ya este el pivote en medio de estos
• El valor pivote tendrá sus mayores a la derecha y sus menores a la izquierda
• Y el pivote dividirá la lista y se hará, por separado en las dos listas el mismo método hasta que todo este organizado

Ejemplo:

Shell sort

Este método no tiene mucha dificultad y sus reglas son muy claras:

• Se divide el total de valore entre dos y el resultado se redondea hacia abajo
• Entonces el resultado de la división serán los saltos que se hará para comparar los datos
• Cuando ya no hay cambios se divide el resultado que tienes de salto entre dos y se le sigue hasta que ya no haya cambios
• Y así sucesivamente hasta que llegues a 1 brinco ósea compararlos directamente y sin problema

Ejemplo:

Lista: 12 3 56 2 16 9 33 22

Merge sort

La imagen tiene te resuelve todas las preguntas……..

Radix sort

En este tipo de ordenamiento se pediran las siguientes reglas:

• Que los acomodes por unidades, de izquierda a derecha
• Luego por decenas, de izquierda a derecha
• Luego por centenas, de izquierda a derecha
• Hasta que ya no tengas mas
• Luego de la ultima lista que sacaste de rriva hacia abajo acomodalas de izquierda a derecha para tenerlas de menor a mayor

Lista: 10 22 30 56 44 3 7 73 2 3 28 4 12 55 78 87 45 18 81

Ejemplo:

Primera pasada: 10 30 81 22 2 12 3 73 3 44 4 55 45 56 7 87 28 78 18

Segunda pasada: 2 3 4 7 10 12 18 22 28 30 44 45 55 56 78 81 87

Todo en orden….

Heap

Este lleva el proceso de un recorrido de un árbol binario:

• Inorder

La orden seria: 7 8 10 11 12 15

Tournament

Este y como su nombre lo dice es como una liguilla donde van avanzando y se van dividiendo y haciendo en menos pero cuando este en lo mas mínimo se vuelve a hacer grande y con los valores ordenados.

Lista 23 12 41 2 5 8 13 4

No se termino porque no me acuerdo como era ……. Pero búsquenlo en el Internet

Conclusión

La clase de estructura de datos me dejo mucho, desde la programada, lo cual ya mejore un poco más, hasta la lógica de entender y ver las cosas de otra manera. Todo esto que acabo de explicar es un repaso de mi clase estructura de datos y simplemente puedo decir que si pudiera volverla a tomar, tenlo por seguro que volveré a decir esto tantas veces sea un arte para mi programar.

END OF FILE;

EXIT;

Referencias:

No hay……

Nunca se leyó un solo libro…..

Eso es lo bueno del asunto…….No?

Autor:

Christian Medrano De los Santos