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