Intercalación por MERGE

En las clases de Laboratorio, de la Comisión 1 (Profesora Mariela Vanesa Burghardt), trabajamos con el Ejercicio 3 de los complementarios de Guía Nº:7.

 Consigna: Se tiene en dos listas las notas obtenidas de aprobación por los alumnos en la asignatura AEDII. En la primera se encuentra los alumnos que se presentaron en la primera instancia, en la segunda lista, los alumnos que se presentaron en la segunda instancia.

Se desea obtener una sola lista, para ello deberá mezclar los elementos de ambas listas.

Ej.: Lista Primera Instancia Lista Segunda Instancia

N.L.U         Nota                     N.L.U.                Nota

5963           9                           5933                   10

6012           7                           6010                   6

5873           7                           ………               ..

……..         ..                           5898                   6

6011           6

** (Se entiende que no habrá ningún desaprobado en ambas listas, ni tampoco N.L.U repetidas, es decir, si rindió en primera instancia no rinde en segunda y viceversa -- Este ejercicio lo implementamos con punteros, no con arreglo)

Codificado en Geany (Free Pascal)

{

Ordenar A y B usando Merge Sort

Mezclar las ordenaciones de A y B para generar el vector ordenado.

}

program g7_ej1_c1_intercalacion;

uses

  crt, alumnosNotaListaDinamica, ordenarLista;

var

  vLista1, vLista2, vListaResultante: alumnosNotaListaDinamica.tLista;

  vOpcion: integer;

// Modificacion a 1. Para que sea un procedimiento.

// Este procedimiento recibe dos listas independientes (lista1, lista2) ordenadas cada una de manera creciente segun un campo clave (la libreta universitaria). Actualiza por referencia una tercer lista creciente (lista3), que es el resultado de intercalar las dos listas de entrada.

procedure merge(x1: alumnosNotaListaDinamica.tLista; x2: alumnosNotaListaDinamica.tLista; var x3: alumnosNotaListaDinamica.tLista);

var

  cola, t: alumnosNotaListaDinamica.tLista;

begin

  cola := nil;

  x3 := nil;  // El vector resultante apunta nil.

  while x2 <> nil do  // Mientras la lista2 no termine, es decir no apunte a nil, entra al while. Si la segunda se termina, el ultimo nodo de lista3 debe apuntar a donde apunta la lista1.

  begin

    if x1 = nil then  // Se intercabian las listas, para que la lista2 siempre sea mas corta o se termine antes.

    begin

      x1 := x2;

      x2 := nil;

    end

    else

    begin

      if x2^.lu > x1^.lu  then  // La lista que tiene el campo LU mas chico se guarda en t, y se actualiza la cabecera de la lista correspondiente al siguiente.

      begin

        t := x1;

        x1 := x1^.siguiente;

      end

      else

      begin

        t := x2;

        x2 := x2^.siguiente;

      end;

      t^.siguiente := nil;  // El siguiente de t pasa a apuntar a nil.

      if x3 = nil then x3 := t  // En la primera "vuelta" se guarga el primer nodo de la lista3 que es t.

      else cola^.siguiente := t;  // Si lista3 ya tiene algun nodo, es decir, ya paso por la primera "vuelta" se hace que el ultimo de lista3 apunte a donde apunta t (que contiene el nodo mas chico de los que se compararon).

      cola := t;  // Se guarda el ultimo nodo de la lista3, que va a ser el ultimo que se guardo en t.

    end;

  end;

  if x3 = nil then x3 := x1  // Si lista3 todavia apunta a nil, es por que lista2 no tenia nada, entonces lista3 := lista1.

  else cola^.siguiente := x1; // Si no, lista3 ya tiene nodos, pero lista2 se acabo entonces el ultimo nodo de lista3 debe apuntar a lo que resta de lista1.

end;

procedure menu();

begin

  writeln('Que desea hacer');

  writeln('1. Agregar alumno en lista 1');

  writeln('2. Agregar alumno en lista 2');

  writeln('3. Mostrar lista 1');

  writeln('4. Mostrar lista 2');

  writeln('5. Eliminar ultimo alumno agregado en lista 1');

  writeln('6. Eliminar ultimo alumno agregado en lista 2');

  writeln('7. Ordenar y mostrar lista 1');

  writeln('8. Ordenar y mostrar lista 2');

  writeln('9. Ordenar y mostrar lista resultante');

  writeln('10. Salir');

  writeln();

  readln(vOpcion);

  case vOpcion of

    1:

    begin

      alumnosNotaListaDinamica.leerElemento(vLista1);

      readkey;

      clrscr;

      menu();

    end;

    2:

    begin

      alumnosNotaListaDinamica.leerElemento(vLista2);

      readkey;

      clrscr;

      menu();

    end;

    3:

    begin

      writeln('Lista primera instancia (Lista1): ');

      alumnosNotaListaDinamica.mostrarLista(vLista1);

      readkey;

      clrscr;

      menu();

    end;

    4:

    begin

      writeln('Lista segunda instancia (Lista2): ');

      alumnosNotaListaDinamica.mostrarLista(vLista2);

      readkey;

      clrscr;

      menu();

    end;

    5:

    begin

      alumnosNotaListaDinamica.eliminarElemento(vLista1);

      readkey;

      clrscr;

      menu();

    end;

    6:

    begin

      alumnosNotaListaDinamica.eliminarElemento(vLista2);

      readkey;

      clrscr;

      menu();

    end;

    7:

    begin

      ordenarLista.ordenar(vLista1);

      writeln('Lista primera instancia (Lista1): ');

      alumnosNotaListaDinamica.mostrarLista(vLista1);

      readkey;

      clrscr;

      menu();

    end;

    8:

    begin

      ordenarLista.ordenar(vLista2);

      writeln('Lista segunda instancia (Lista2): ');

      alumnosNotaListaDinamica.mostrarLista(vLista2);

      readkey;

      clrscr;

      menu();

    end;

    9:

    begin

      merge(vLista1, vLista2, vListaResultante);

      writeln('Lista resultante: ');

      alumnosNotaListaDinamica.mostrarLista(vListaResultante);

      readkey;

      clrscr;

      menu();

    end;

    10:

    begin

      readkey;

      clrscr;

    end;

    else

    begin

      readkey;

      clrscr;

      menu();

    end;

  end;

end;

begin

  crearLista(vListaResultante);

  menu();

end.

IMPORTANTE: Este .pas trabaja con dos TDA, aquí sus LINKS;

alumnosNotaListaDinamica                                 ordenarLista

INICIO