MERGE DE LISTAS

Explicación Práctica 11

Algoritmos Datos y Programas 2014Facultad de Informática - UNLP

LISTAS – MERGE

Se dispone de dos listas simples de enteros ordenadas en forma ascendente.Se pide implementar un algoritmo que combine ambas listas y genere una tercer lista ordenada también por el mismo criterio.

L1

nil

20

100

17

200

nil

L2

5

100

17

200

L3

20

5

nil

Ejemplo

LISTAS – MERGE

nil

20

100

L1

17

200

nil

L2

5

L3

5

nil

17

nil

20

nil

100

nil

200

nil

Pensar:

¿Sabemos cuántos datos debemos

agregar a L3? ¿Cuándo termina el

algoritmo?

¿Cómo se selecciona el mínimo

dato en cada paso? Módulo. Casos

¿De qué manera tengo que

agregar en L3?

LISTAS – MERGE

Program MERGE_DE_LISTAS;CONST VALOR_CORTE = 9999;Type lista = ^nodo; nodo=record datos: integer; sig: lista; end;

{Acá van declarados los módulos a utilizar}

Var L1,L2,L3: lista;Begin CrearListaOrdenada (L1); {Se dispone}

CrearListaordenada (L2); {Se dispone}

L3:= nil; Merge(L1, L2, L3);end.

LISTAS – MERGE

Procedure merge (l1,l2: lista; var l3:lista);

Var

min: integer; ultL3: lista;

Begin

minimo(l1, l2, min);

while (min <> VALOR_CORTE) do begin {mientras no se terminen las

listas}

agregarAtras (l3, ultL3,min);

minimo (l1, l2, min);

end;

end;

Procedure MINIMO ( … )- Si ambas l1 y l2 están vacías, devuelve MIN = VALOR_CORTE- Caso contrario devuelve en min el valor mínimo de la cabecera de l1 ó l2 y avanza en la lista correspondiente

Procedure agregarAtras (var pri: lista; var ult: lista;

dato:integer); var nue: lista;Begin new (nue); nue^.sig := nil; nue^.datos := dato; if (pri = nil) then {La lista esta vacía} pri := nue; {NUE es el primero} else ult^.sig := nue; { El ult pasa a tener como sig al nuevo ult}

ult := nue; {El ult es el que acabo de agregar}end;

LISTAS – MERGE

PseudocódigoProcedure minimo( var L1:lista; var L2: lista; var min: integer);Begin {las dos listas están vacías, devuelvo VALOR_CORTE para terminar el algoritmo} if (l1 y l2 están vacías) then min:= VALOR_CORTE; else {si las dos listas tienen elementos, obtengo el menor} if (l1 no está vacía) and (l2 no está vacía) then elijo el número más chicos de los dos (lo copio en min) avanzo el puntero de la lista del número elegido else {una de las dos listas no tiene elementos} if (l1 no está vacía) then {sólo l1 tiene elementos} el min es de l1 y avanzo l1 else {sólo l2 tiene elementos} el min es de l2 y avanzo l2

¿Por qué paso L1 y L2 por referencia?

LISTAS – MERGE

Procedure minimo (var l1:lista; var l2: lista; var min:integer);Begin if (l1 = nil) and (l2=nil) then min:= VALOR_CORTE; else if (l1<> nil) and (l2<> nil) then if (l1^.datos <= l2^.datos) then begin min:= l1^.datos; l1:= l1^.sig; end else begin min:= l2^.datos; l2:= l2^.sig; end else if (l2 = nil) then begin {L2 vacía, L1 <> nil} min:= l1^.datos; l1:= l1^.sig; end else begin {L1 vacía, L2 <> nil} min:= l2^.datos; l2:= l2^.sig end;end;

Type lista = ^nodo; nodo=record datos: integer; sig: lista; end;

¿Qué ocurre con el

algoritmo si hay números

repetidos en L1 y L2?

Ejemplo

Se dispone de dos listas simples de enteros ordenadas en forma ascendente (l1 y l2). Un mismo número entero puede aparecer varias veces en una o ambas listas.Implementar un algoritmo que combine ambas listas y genere una tercer lista ordenada por el mismo criterio, donde por cada número que aparece en las listas de entrada se tenga la cantidad de ocurrencias.

1 2 2 5

1 3 6 6

NIL

NIL

l2

l1

12

22

31

63

NIL

l3

6

51

1 2 2 5 6

1 3 6 6

NIL

NIL

12

22

31

51

63 N

IL

L3

l2

l1

Llevar min, actual y cantidad de ocurrencias de actual

Program MERGE_DE_LISTAS2;CONST VALOR_CORTE = 9999;Type lista = ^nodo; nodo=record datos: integer; sig: lista; end;

Tdatos3= record num: integer; ocurrencias: integer; end;

lista3 = ^nodo; nodo=record datos: Tdatos3; sig: lista3; end;

{ Acá van los módulos }Procedure merge2 (l1,l2: lista; var l3:lista3); => MODIFICAR Procedure minimo( var L1:lista; var L2: lista; var min: integer); => NO SE MODIFICAProcedure agregarAtras (var pri: lista3; var ult: lista3; dato:Tdatos3); => SÓLO CAMBIAN LOS TIPOS DE DATO

Var L1,L2: lista; L3: lista3;

Begin CrearListaOrdenada (L1); {Se dispone} CrearListaordenada (L2); {Se dispone} L3:= nil; Merge2(L1, L2, L3);End.

Procedure Merge2 (l1,l2: lista; var l3:lista3);Var min : integer; ultL3: lista; actual, ocurrencias: integer; dato: Tdatos3;Begin minimo(l1, l2, min); while (min <> VALOR_CORTE) do begin {mientras no se terminen las listas} actual:= min; {cuento las veces que aparece el número “actual”} ocurrencias:= 0; while (actual = min ) do begin {mientras “min” no cambia respecto a “actual”} ocurrencias:= ocurrencias + 1; minimo (l1, l2, min); end; {termine de procesar todas las apariciones de “actual”} dato.num:= actual; dato.ocurrencias:= ocurrencias; agregarAtras (l3, ultL3, dato); end;end;

Por qué NO pongo “min”

Por qué NO vuelvo a sacar el mínimo

Procedure agregarAtras (var pri: lista3; var ult: lista3; dato:Tdatos3); var nue: lista3;Begin new (nue); nue^.sig := nil; nue^.datos := dato; if (pri = nil) then {La lista esta vacía?} pri := nue; {NUE es el primero} else ult^.sig := nue; { El último pasa a tener como siguiente al nuevo último }

ult := nue; {El último es el que acabo de agregar}end;