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.

...