[ Foro de Pascal ]

Sobre el ejercicio de ordenamiento usando listas que está en el curso.

21-Aug-2012 03:08
Luis Torres (+18)
13 Respuestas

Estuve leyendo el hilo sobre ordenamiento usando listas, específicamente el código cuyo link es el siguiente:
http://www.aprendeaprogramar.com/mod/resource/view.php?id=483
Hay una parte que, la verdad, no entiendo nada y, es a la referente a la recursividad. La parte del código que no entiendo es la referente al procedimiento InsertarLista.

Entiendo bien hasta la parte de InsertarLista(1,2), pero, estoy desesperado porque no entiendo nada en la parte de InsertarLista(1,6):
Allí se producen una serie de llamadas recursivas, por el hecho de que 6 es mayor que cualquier valor apuntado por Lista. Así, se producirían las siguientes llamadas al mismo procedimiento:

InsertarLista(Lista(apunta a 2), 6);
___InsertarLista(Lista(apunta a 3), 6);
________InsertarLista(Lista(apunta a 5), 6);
_______________InsertarLista(Lista(apunta a nil), 6);

                    Como Lista apunta a nil, entonces                   entraríamos al siguiente else:


  else                                { Si no hay lista }
    begin                             {   deberá crearla }
    new(r);                           {   reserva espacio }
    r^.numero := valor;               {   guarda el dato }
    r^.sig := nil;                    {   no hay nada detrás y }
    lista := r  



por lo que se reserva espacio para un nuevo elemento, el campo número será igual a 6, y el campo sig igual a nil. Pero, ESTO NO LO ENTIENDO, lista se hace igual a la dirección de esa dirección. Yo me pregunto ¿no se perdería la lista al apuntar la variable lista a 6 y no al primer elemento que debería ser aquel cuyo campo número vale 2?. POR FAVOR, PROFESOR, ESTOY MUY CONFUNDIDO, LE PIDO QUE ME EXPLIQUE.

Muchos saludos.


22-Aug-2012 18:40
Luis Torres (+18)

Le pido al prof. Nacho Cabanes que me de una explicación de lo que hace el programa cuando se llama al procedimiento InsertaLista(l,6). Porque, haciendo el seguimiento del programa, a mí me da como resultado que lista termina apuntando a 6, y sig apunta a nil. El resultado debería ser que el nodo cuyo valor es 5 apunte a al nodo de valor 6 y, lista apunte al nodo de valor 2. Pero mi seguimiento del procedimiento no me da así.

Por favor, prof., explíqueme, es que estoy trabado en ese punto y, de esto depende que entienda otras cosas en cuanto al punto de Recursividad.

Un gran saludo.


23-Aug-2012 01:55
Nacho Cabanes (+83)

Los programas que manejan memoria dinámica son los más difíciles de analizar. Si quieres entender el funcionamiento, hay dos alternativas:

- La más efectiva, pero más trabajosa, es hacer la traza del programa a mano: coger un lápiz y un papel, ir "imitando la ejecución" línea a línea y apuntando el estado de la lista (o la estructura que sea) en cada paso.

- La alternativa "mala" es hacer exactamente lo mismo, pero de forma automática: ampliar el programa para que sea él mismo quien te muestre por dónde va pasando y qué valores tiene cada variable.

El problema es que mostrar el valor de un puntero es algo que no permiten todos los compiladores. Por ejemplo, si intentas mostrar un puntero con Free Pascal obtendrás un error "Error: Can’t read or write variables of this type".

Aun así, intento crearte mañana una versión que muestre parte de su avance, por si te ayuda a seguirlo mejor.

El matiz más importante, que tienes que tener en cuenta: en la llamada recursiva "lista" no se refiere al principio de la lista sino a la posición actual en la que estás insertando o comprobando.


23-Aug-2012 02:29
Nacho Cabanes (+83)

Aquí tienes un ejemplo con el fuente "ampliado con write" para que muestre por dónde va pasando. He tenido que hacer un par de trucos para conseguir que muestre la dirección de memoria en la que se encuentra: "write(ofs(lista^))" en vez de "write(lista)"

---

program EjemploDeListasRetocado;

type
 puntero = ^TipoDatos;
 TipoDatos = record
   numero: integer;
   sig:    puntero
 end;


function CrearLista(valor: integer): puntero;  {Crea la lista, claro}
var
 r: puntero;                 { Variable auxiliar }
begin
 new(r);                     { Reserva memoria }
 r^.numero := valor;         { Guarda el valor }
 r^.sig := nil;              { No hay siguiente }
 CrearLista := r             { Crea el puntero }
end;


procedure MuestraLista ( lista: puntero );
begin
 if lista <> nil then               { Si realmente hay lista }
   begin
   write(lista^.numero, ' - ');          { Escribe el valor }
   MuestraLista (lista^.sig )       { Y mira el siguiente }
   end;
 writeln;
end;


procedure InsertaLista( var lista: puntero; valor: integer);
var
 r: puntero;                         { Variable auxiliar }
begin
 writeln('Insertando valor: ',valor, ' Desde: ', ofs(lista^));
 write('Parte restante de la lista: ');
 MuestraLista(lista);
 
 if lista <> nil then                { Si hay lista }
   if lista^.numero<valor            {   y todavía no es su sitio }
     then                            {   hace una llamada recursiva: }
     begin
     writeln('Mayor: Llamada recursiva');
     InsertaLista(lista^.sig,valor);  {   mira la siguiente posición }      
     end
   else                              { Caso contrario: si hay lista }
     begin                           {   pero hay que insertar ya: }
     new(r);                         {   Reserva espacio, }
     r^.numero := valor;             {   guarda el dato }
     r^.sig := lista;                {   pone la lista a continuac. }      
     lista := r;                      {   Y hace que comience en }
     writeln('Menor: guardado en ', ofs(r^))
     end                             {     el nuevo dato: r }
 else                                { Si no hay lista }
   begin                             {   deberá crearla }
   new(r);                           {   reserva espacio }
   writeln('Creando lista: pos ',ofs(r^));
   r^.numero := valor;               {   guarda el dato }
   r^.sig := nil;                    {   no hay nada detrás y }
   lista := r;                       {   hace que la lista comience }
   end                               {     en el dato: r }
end;


var
 l: puntero;             { Variables globales: la lista }

begin
 l := nil;
 InsertaLista(l, 5);     { Crea una lista e introduce un 5 }  
 writeln('Creada la lista en: ', ofs(l^) );
 
 InsertaLista(l, 3);     { Inserta un 3 }
 writeln('Ahora la lista comienza en: ', ofs(l^) );
 
 InsertaLista(l, 2);     { Inserta un 2 }
 writeln('Ahora la lista comienza en: ', ofs(l^) );
 
 InsertaLista(l, 6);     { Inserta un 6 }
 writeln('Ahora la lista comienza en: ', ofs(l^) );
 
 MuestraLista(l)         { Muestra la lista resultante }
end.

-----------------

El resultado sería algo como (ligeramente retabulado)

Insertando valor: 5 Desde: 0
Parte restante de la lista:
Creando lista: pos 22276752
Creada la lista en: 22276752

Insertando valor: 3 Desde: 22276752
Parte restante de la lista: 5 -
Menor: guardado en 22276768
Ahora la lista comienza en: 22276768

Insertando valor: 2 Desde: 22276768
Parte restante de la lista: 3 - 5 -
Menor: guardado en 22276784
Ahora la lista comienza en: 22276784

Insertando valor: 6 Desde: 22276784
Parte restante de la lista: 2 - 3 - 5 -
Mayor: Llamada recursiva

Insertando valor: 6 Desde: 22276768
Parte restante de la lista: 3 - 5 -
Mayor: Llamada recursiva

Insertando valor: 6 Desde: 22276752
Parte restante de la lista: 5 -
Mayor: Llamada recursiva

Insertando valor: 6 Desde: 0
Parte restante de la lista:
Creando lista: pos 22276800
Ahora la lista comienza en: 22276784

2 - 3 - 5 - 6 -

-----------------

A partir de ahí puedes ampliar el cuerpo del programa para hacer pruebas con más datos y ver cómo influyen los cambios en la traza de la ejecución.


23-Aug-2012 05:11
Luis Torres (+18)

Muchas gracias por la respuesta. Gracias por tomarse el tiempo de realizar todo ese seguimiento del programa, pero lamentablemente no responde a mi pregunta.
Todo el seguimiento que usted hizo es similar al que yo había hecho. Pero vamos a tomar los resultados que obtuvo para plantear mi duda con más claridad.
Estamos claros en que la lista comienza en el valor 2 cuya dirección es 22276784. Pero vamos a trasladarnos a la parte en la que se realiza la última llamada recursiva, la cual es:
      insertaLista(nil, 6); acá entramos a la parte del procedimiento que dice así:


  else 
    begin  
    new(r);     
    writeln('Creando lista: pos ',ofs(r^));
    r^.numero := valor;
    r^.sig := nil;
    lista := r;  
    end



Ahora, si examinamos un poco lo que hace esta parte, vemos que la lista se crea en la posición:
22276800
r^.numero = 6
r^.sig = nil
lista = 22276800  ESTO ES LO QUE NO ENTIENDO.

¿CÓMO LLEGA LISTA A TENER EL VALOR 22276784, SI COMO VIMOS, LISTA FINALIZA CON EL VALOR 22276800?

¿EN QUÉ MOMENTO SE LE ASIGNÓ A LISTA EL VALOR 22276784?

POR FAVOR, EXPLÍQUEME. ES QUE ESTOY ESTUDIANDO RECURSIVIDAD Y YO CREÍA QUE HABÍA APRENDIDO ALGO, PERO AL VER LO QUE SUCEDE EN ESTE CÓDIGO ME DEJÓ DESCONCERTADO.

Agradezco todo el interés y el tiempo que ha tomado en la explicación.
Un gran abrazo y muchos saludos.


24-Aug-2012 01:57
Luis Torres (+18)

Le pido al prof. que me ayude a aclarar este último punto, que considero crucial en mi aprendizaje sobre recursividad.

¿Qué compilador usó para presentar las direcciones de memoria?. Lamentablemente Turbo Pascal no presenta las direcciones de memoria.

La parte que no tendiendo es la última. Fíjese que los resultados que usted obtuvo fueron los siguientes:

Insertando valor: 6 Desde: 0
Parte restante de la lista:
Creando lista: pos 22276800
Ahora la lista comienza en: 22276784


O sea que Lista es igual a 22276800. Lo que no entiendo es cómo finalmente Lista llegó a valer 22276784, dirección que se corresponde con el nodo de valor 2, es necesario que Lista tenga la dirección de memoria de este nodo para que en el procedimiento MostrarLista se puedan ver todos los valores (2- 3- 5- 6-). Además, no llego a comprender cómo se establece el enlace entre el nodo de valor 5 y el último nodo de valor 6.

Por favor, ayúdeme a comprender.

Un abrazo y muchos saludos.
24-Aug-2012 17:47
Nacho Cabanes (+83)

Ten en cuenta que, al ser una llamada recursiva, "lista" no es lo mismo que "l": ya no estás en la "cabeza" de la pila, sino mucho más abajo, de modo que no modificas el valor de la "cabeza".

Esa es la parte dificil de recursividad: entender que en cada pasada estás trabajando con datos distintos, aunque la variable se llame igual. Por ejemplo, en este caso si insertas 2 y luego 3, el 3 no lo estás guardando en "l" sino en "l^.sig", porque ya has avanzado por la estructura.

Prueba a hacer la traza de alguno de los ejemplos clásicos de recursividad, como el del factorial. Te ayudará a entenderlo. Piensa cómo se calcular el factorial de 4 de forma recursiva y qué pasos intermedios supone eso, porque en cada nueva pasada se generan datos temporales intermedios, en variables que "aparentemente se llaman igual" pero que no están en la misma posición de memoria, sino que son "nuevas copias".


25-Aug-2012 02:36
Luis Torres (+18)

Nuevamente muchas gracias por responder.

Me alarmé tanto, de no entender este código, precisamente porque creía que había entendido perfectamente el ejercio del Factorial en forma recursiva.

Esto último ha aclarado en mucho mis dudas, aunque no todas. Ahora tengo claro el por qué la variable lista conserva la posición de memoria del nodo cuyo valor es 2 (el primero de todos). Ahora tengo la mayor parte del camino recorrido. Pero, lo que aún no logro entender es, en qué comento el campo sig del nodo de valor 5 se le asigna la dirección del último nodo (de valor 6).

Antes de hacerse las llamadas recursivas, el campo sig del nodo de valor 5 guardaba la dirección nil. Pero al finalizar todo el proceso de meter los datos, este campo debe apuntar al nodo de valor 6, no logro comprender en qué parte de la ejecución de las llamadas recursivas se le asigna esta dirección.

Prof. no me respondió la pregunta del compilador que usó para ver la direcciones de la variable I.

Muchos saludos, y perdone tanta molestia.
28-Aug-2012 16:13
Nacho Cabanes (+83)

Como compilador, he usado FreePascal, pero quizá funcione también en TurboPascal, que también tiene la función "ofs", que dice la posición de memoria ("offset") en que se encuentra una variable, con la diferencia de que en MsDos la memoria estaba dividida en segmentos, así que para conocer la posición de memoria hay que saber a qué segmento pertenece, "seg(variable)", además del desplazamiento dentro de ese segmento, "ofs(variable)"

En cuanto al paso del nodo 5 al nodo 6: cuando se inserta el 6, se va avanzando hasta llegar al último nodo, y se ve que su campo "siguiente" es "nil", de modo que se pasa al fragmento:

 else                                { Si no hay lista }
   begin                            {  deberá crearla }
   new(r);                          {  reserva espacio }
   writeln('Creando lista: pos ',ofs(r^));
   r^.numero := valor;              {  guarda el dato }
   r^.sig := nil;                    {  no hay nada detrás y }
   lista := r;                      {  hace que la lista comience }
   end                              {    en el dato: r }

Es decir, se reserva espacio, se guarda el valor, se apunta que no tiene siguiente (su siguiente es nil), y se hace que el valor desde el que se ha llamado, que era "el siguiente de 5" ya no sea "nil" sino "r", es decir, la posición de memoria que el compilador nos ha reservado para el dato "6".


29-Aug-2012 01:02
Luis Torres (+18)

Gracias por la respuesta, pero...

"y se hace que el valor desde el que se ha llamado, que era "el siguiente de 5" ya no sea "nil" sino "r""

Esa parte no la veo por ningún lado, porque al hacer que lista:= r , lo que veremos es que lista sea igual a la dirección reservada para el elemento de valor 6. O sea que lista será igual a 22276800.

Por favor, deme otra explicación, es lo único que me falta para entender este código.
29-Aug-2012 01:32
Nacho Cabanes (+83)

Recuerda que en este fuente, "lista" (posición actual) no es lo mismo que "l" (lista resultante). Al ser una llamada recursiva, el valor de "lista" va cambiando (posición actual), y al llegar a este punto no es la cabecera la toda la lista, sino la posición en la que insertamos ese último dato.

En este fuente, el nombre "lista" no es muy afortunado. Sería mejor "sublista", o "posicionActual", "posicionDeInsercion", "posicionDePartidaDelAnalisis", pero cuanto más detallemos con el nombre de las variables, más largas quedan las líneas y puede acabar resultando incómodo de leer y ser contraproducente. Tómalo como "sublista" si quieres, pero sobre todo, recuerda que es un valor "cambiante".


29-Aug-2012 03:31
Luis Torres (+18)

"Recuerda que en este fuente, "lista" (posición actual) no es lo mismo que "l" (lista resultante). Al ser una llamada recursiva, el valor de "lista" va cambiando (posición actual), y al llegar a este punto no es la cabecera la toda la lista, sino la posición en la que insertamos ese último dato."

Ok, eso lo entiendo perfectamente y responde a mi primera duda sobre el comienzo de la lista enlanzada. Ya entiendo el por qué la varible l guarda la primera posición de la lista. Eso ya lo entiendo.

Lo que no logro entender es en qué momento el campo sig del nodo de valor 5 guarda la dirección del último nodo insertado, el cual es de valor 6. No entiendo esto, porque la última llamada es
insertarLista(nil,6);

Vamos a hacer un seguimiento a esto último:
new(r);
writeln('Creando lista: pos ',ofs(r^));
r^.numero := valor;
r^.sig := nil;
lista := r;


r^.numero := 6;
r^.sig := nil;

y, la última sentencia que se ejecuta sería:
lista:= 22276800; la cual corresponde al nodo de valor 6

siendo ésta la última sentencia, ¿cuándo, en qué momento se pone al campo sig del nodo 5 a apuntar al nodo de valor 6?

Esto es lo único que me falta por entender.

Mil gracias por tanta paciencia para conmigo. Un gran saludo.
30-Aug-2012 01:47
Nacho Cabanes (+83)

Tu problema está aquí:

Lo que no logro entender es en qué momento el campo sig del nodo de valor 5 guarda la dirección del último nodo insertado, el cual es de valor 6. No entiendo esto, porque la última llamada es
insertarLista(nil,6);

Cuidado con eso. No es

insertarLista(nil,6);

sino

insertarLista(posicionActual,6);

donde posicionActual valía nil y ahora va a cambiar de valor, para pasar a ser la posición del dato recién creado.


01-Sep-2012 00:39
Luis Torres (+18)

¡Wow!!!. Estoy super agradecido con su explicación, la verdad es que dio en el clavo, eso era precisamente lo que no había entendido. De todas maneras déjemelo explicárselo con mis propias palabras y, usted me responde si es lo correcto o no:

Al haber declarado el parámetro formal "lista" como un parámetro por referencia, cualquier cambio de "lista" se reflejará en el parámetro real, o sea al que llama al procedimiento. En el caso que estamos considerando, la última llamada al procedimiento insertaLista(lista^.sig,valor), le pasa los siguientes valores:
lista^sig(del nodo 5) valdrá nil (al igual que lista del nuevo nodo) y
valor valdrá 6;
esto provoca que se ejecute la última parte del código del procedimiento (o sea el bloque del último else).
Allí, se reserva espacio en memoria para el registro y su dirección se almacena en r.

Ahora, el campo "numero" de r^ se le asignará el valor 6 y,
al campo "sig" de la misma variable dinámica se le asigna "nil".

POR ULTIMO, HACEMOS QUE lista SE LE ASIGNE LA DIRECCION DE r. PERO, COMO SE TRATA DE UN PARAMETRO POR REFERENCIA, ESE VALOR TAMBIÉN LO TENDRÁ LA LLAMADA AL PROCEDIMIENTO insertaLista(lista^.sig,valor).
lista^.sig, PARA LA ÚLTIMA LLAMADA, ESTABA RELACIONADA CON EL NODO CUYO VALOR ES 5, POR LO QUE AHORA DICHO NODO TENDRÁ LA DIRECCIÓN DEL NODO DE VALOR 6, A CAUSA DE ESTA ÚLTIMA LLAMADA Y POR TRATARSE DE VARIABLES POR REFERENCIA.

¿Estoy en lo cierto, sí o no?.

Muy agradecido por su ayuda. Le debo mucho!!!.
Abrazos y saludos.






(No se puede continuar esta discusión porque tiene más de dos meses de antigüedad. Si tienes dudas parecidas, abre un nuevo hilo.)