Listas En Estructura De Datos

Compendio de estructura de datos

1. Introducción

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

2. estado de pila?

Vacía =3

Sino =8

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

2. estado de pila?

Vacía =3

Solo 1 valor =5

Sino =7

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

2. estado de cola?

Vacía =3

sino =8

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

2. estado de cola?

Vacía =3

Solo 1 valor =5

Sino =7

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

...