ANÁLIS DE ALGORITMO

ESTRUCTURA DE DATOS

FELIPE EDUARDO FAUNDEZ AGUILAR

ANÁLIS DE ALGORITMO

Instituto IACC

Ponga la fecha aquí

Desarrollo

1. De acuerdo a lo visto en los contenidos de la semana y al hecho de que las estructuras de datos pueden ser implementadas utilizando otras estructuras de datos, ¿cómo sería una estrategia para contar los elementos existentes en una pila? (Es decir, ¿cómo sería una forma eficiente de construir la función Count?).

Respuesta: Con la información entregada en el contenido de la semana uno y lo comprendido, pasaremos a describir cada una de las estructuras de datos mencionadas en dicho control las cuales son:

• Lista: Las listas son un conjunto de nodos unidos entre sí, formando de esta manera una cadena de nodos las cuales se relacionan con una o dos referencias al nodo anterior, estas se pueden implementar a otras estructuras de datos.

[pic 1]

• Cola: La cola es muy similar a la pila, pero ocupa una forma inversa a la de la pila  para recuperar la información. Esta es llamada FIFO (First In, First Out), el primero en entrar es el último en salir, esta característica obliga y asegura que los elementos sean procesados en el orden que fueron insertados.

[pic 2]

• Pila: La pila es una estructura de datos que nos permite almacenar y rescatar información almacenada en ella, a este tipo de datos se les conoce como LIFO (Last in, First Out, en español seria “El último en entrar, primero en salir”), dentro de sus operaciones básicas de esta estructura de datos es la operación PUSH, la cual agrega un elemento al tope de la pila, y POP, el cual saca un elemento de la pila.

[pic 3]

Respuesta en Pseudocodigo:

Inicio

        ENTERO PILA[3], tope = 0

        FUNCION Apilar (ENTERO dato)

            SI( NO( pilaLLENA() ) ) entonces

                tope = tope + 1

                pila[tope]= dato

             SINO

                Imprimir "La pila esta llena"

           FIN SI

        FIN FUNCION

        FUNCION ENTERO DESAPILAR (ENTERO PILA[])

           ENTERO dato

           SI ( NO ( pilaVacia() ) ) ENTONCES

                dato = pila[tope]

                tope = tope -1

            SINO

                IMPRIMIR "LA PILA ESTA VACIA"

            FIN SI

        FIN FUNCION

        PILA.Apilar[3]

        ENTERO C = 0

        MIENTRAS ( NO (pilaVacia() ) )

                pila.DESAPILAR

                C = C + 1

        FIN MIENTRAS

FIN        

1. La empresa ferroviaria ABC-Ferrocarriles está en proceso de remodelación de algunos de sus terminales de trenes y necesita mover un tren completo (locomotora y 4 vagones) desde el terminal A al terminal C, como muestra la figura. La dificultad en esta operación es que el tren debe quedar en el terminal C en el mismo orden del que salió del terminal A, frente a esta situación se le ha pedido a Ud. que ayude con una estrategia para cumplir con el objetivo. Entonces, ¿qué tipo de estructura de datos utilizaría para resolver el  problema? Genere la estrategia para mover el tren y escriba cómo lo haría (puede usar el terminal B para apoyarse).

• Desarrollo: Creo que en el caso planteado y con los conocimientos adquiridos en esta semana ocuparía la estructura de datos de pilas, empesando con la operacion o funcion POP  (desapilar)  para poder  desapilar el tren desde la locomotora hasta el vagón número 4 y posteriormente utilizamos la función u operacion PUSH (apilar) lo cual nos permitirá apilar desde locomotora hasta vagón número 4 en la estación B. Con estas operaciones se dejaría al tren mirando en dirección contraria a la que estaba inicialmente el tren (estación A). Una vez posicionado el tren en la estación B se volvería a realizar las mismas funciones antes realizadas para pasar el tren a la siguiente estación, pero esta vez se empezaría del vagón número 4 a la locomotora al realizarlo de esta forma  dejaría al tren posicionado en la misma dirección a la que cuando estaba ubicado en la estación A.

...