2do Parcial 2011 - EJ 2

2do Parcial 2011 - EJ 2

de Alejandro Barreiro Deminco -
Número de respuestas: 7
Hola tenia una pregunta sobre como definir el TYPE de ListaEsperaAviones del 2do parcial 2011

En la solución separa los aviones en 2 listas (normales, urgentes)
TYPE
   NodoAvion = POINTER TO RECORD
      avion : Avion;
      sig : NodoAvion;
   END;
   ColaAviones = RECORD
      primero : NodoAvion;
      ultimo  : NodoAvion;
   END;
   ListaEsperaAviones = POINTER TO RECORD
      urgentes : ColaAviones; (* estructura FIFO para aviones “urgentes” *)
      normales : ColaAviones; (* estructura FIFO para aviones “normales”, que
                                 permite supresión de elementos arbitrarios *)
END;

Me queda alguna duda de como definen eso del "POINTER TO RECORD"
Yo cuando lei este ejercicio lo pensé como una cola de prioridad, donde la prioridad era si el avión era "urgente" o "normal"
y el TYPE pensaba definirlo asi:
ListaEsperaAviones = POINTER TO Cabezal;
Lista=POINTER TO Nodo;
     Nodo = RECORD
        a:Avion;
        sig:Lista;
        prioridad: (normal,urgente);
     END;
    Cabezal=RECORD;
      primero,ultimo:Lista;
    END;
Es aceptable una solución con este type?
En respuesta a Alejandro Barreiro Deminco

Re: 2do Parcial 2011 - EJ 2

de Carlos Luna -
Deberías ver si con esta estructura lográs cumplir las restricciones establecidas para las operaciones (parte b del ejercicio).

Saludos, Carlos
InCo
En respuesta a Carlos Luna

Re: 2do Parcial 2011 - EJ 2

de Alejandro Barreiro Deminco -
VaciaListaEsperaAviones también es solo de O(1) solo creo el cabezal y le asigno nil al primero y al ultimo.
InsertarAvion es de O(1) por que tengo el cabezal con puntero al principio y al ultimo (voy insertando al final con avion^.prioridad:=normal) 
ObtenerSigAvion también es de O(1), ya que seria solo devolver el primero, si eventualmente hay aviones que tengan prioridad urgente van a estar al principio de la cola 

Yo pienso que si se puede hacer, solo que costo un poco mas de trabajo hacer PromoverAvion (PromoverAvion, permite promover un avión de “Normales” a “Urgentes”, si el avión no está presente o
ya está entre los “Urgentes”, entonces la ListaEsperaAviones no se ve modificada. Al promover un avión
de “Normales” a “Urgentes”, dicho avión será considerado último en el orden FIFO entre los “Urgentes”.
Esto es, será el último de los “Urgentes” en el orden de selección para aterrizar.)


En respuesta a Carlos Luna

Re: 2do Parcial 2011 - EJ 2

de Santiago Andres Diaz Pereira -
el ejercicio 2 parte b) dice : " Implemente   el   TAD  ListaEsperaAviones  ,  donde  todas   las   operaciones   tengan   O(1)  de   tiempo   de  
    ejecución en el peor caso, excepto PromoverAvion y DestruirListaEspera. Escriba la representación del  
    TAD y el código de las operaciones  VaciaListaEsperaAviones  , InsertarAvion , ObtenerSigAvion  y  
    PromoverAvion. No utilice TADs auxiliares. " 
Mi duda es, con la forma que se declara 'ListaEsperaAviones' en la solución del parcial, no se supone que la operación 'EstaEnListaEsperaAviones'  no cumple la restricción de ser O(1)?  O cuando dice "todas   las   operaciones" no se refiere a todas las definidas para el TAD, sino solo las que se pide implementar que son : "las operaciones  VaciaListaEsperaAviones  , InsertarAvion , ObtenerSigAvion  y   PromoverAvion."

En respuesta a Santiago Andres Diaz Pereira

Re: 2do Parcial 2011 - EJ 2

de Yasim Zeballos Rodríguez - INCO -
No cumple con la restricción, pero creo que no leíste bien la letra:
"todas  las  operaciones  tengan  O(1) (...) excepto PromoverAvion, EstaEnListaEsperaAviones y DestruirListaEspera."
En respuesta a Yasim Zeballos Rodríguez - INCO

Re: 2do Parcial 2011 - EJ 2

de Alvaro Jose Callero Umpierre -
Yo tengo una duda, en el procedimiento ObtenerSigAvion yo implemente el código pensando en que lo que tenia que devolver era el avión en si, osea el nodo, pero cuando veo la solución lo que se devuelve es el identificador del avion, no tendria que ser un poco mas especifica la letra?? Por ejemplo en el laboratorio siempre que se pedía devoler algo de una determinada estructura siempre era el nodo entonces como que es medio entreverado. 
En respuesta a Alvaro Jose Callero Umpierre

Re: 2do Parcial 2011 - EJ 2

de Yasim Zeballos Rodríguez - INCO -
No me queda del todo clara tu duda.
En particular en la solución un avion es un CARDINAL, al devolver un número estás devolviendo un avión, porque en este caso es una estructura muy simple.

Si devolvieras un nodo de la solución (con el siguiente a nil) no estaría bien porque estarías devolviendo un nodoLista, no un avion.