[ Foro de Pascal ]

problema con ordenamiento de lista simple

16-Aug-2012 12:39
carlos lopez
13 Respuestas

hola gente, tengo un problema con el ordenamiento de una lista simple a partir de las fechas(string) de manera descendente, no puedo encontrar cual es el error, el algoritmo de ordenamiento lo utilice en otro programas y funciona bien. El programa es el siguiente, por favor que alguien me indique el error que estoy cometiendo, si es posible en el programa. Desde ya muchas gracias.

uses crt;



type puntero=^nodo;

    nodo=record

    fecha:string;

    nro_cta:integer;

    monto:real;

    tipo:char;

    sig:puntero

end;



var opc,nro:integer;

   list1,list2,aux,x,p,a:puntero;

   date:string;

   cant:real;

   tipot:char;

   label 0,1,2,3,7;





begin

clrscr;

list1:=nil;

aux:=nil;



0:

writeln('Elija una opcion:');

writeln('1)insertar');

writeln('2)mostrar');

writeln('3)ordenar');

writeln('7)salir');

readln(opc);

case opc of

1: goto 1;

2: goto 2;

3: goto 3;

7: goto 7;

end;



1:

writeln('ingrese nro de cuenta:');

readln(nro);

writeln();

writeln('ingrese fecha:');

readln(date);

writeln();

writeln('ingrese monto:');

readln(cant);

writeln();

writeln('ingrese tipo tramite(deposito(d)/extraccion(e)):');

readln(tipot);

new(x);

x^.nro_cta:=nro;

x^.fecha:=date;

x^.monto:=cant;

x^.tipo:=tipot;



if list1=nil then

  list1:=x

else

  aux^.sig:=x;



x^.sig:=nil;

aux:=x;

goto 0;



2:

x:=list1;

writeln();

writeln();

writeln('la lista es:');

while (x<>nil) do

begin

writeln('Nro de cuenta: ',x^.nro_cta);

writeln('Fecha de la transaccion: ',x^.fecha);

writeln('Monto: ',x^.monto:0:2);

if (x^.tipo='D') or (x^.tipo='d') then

  writeln('tipo de tramite: deposito')

else

  writeln('tipo de tramite: extraccion');

writeln();

writeln();

x:=x^.sig;

end;

goto 0;



3:

x:=list1;

list2:=nil;



while (x<>nil) do

begin

p:=list2;

new(a);

a^.nro_cta:=x^.nro_cta;

a^.fecha:=x^.fecha;

a^.monto:=x^.monto;

a^.tipo:=x^.tipo;





while (p<>nil) and (p^.fecha > x^.fecha) do

begin

   aux:=p;

   p:=p^.sig

end;



if p=list2 then

  begin

  a^.sig:=p;

  list2:=a;

  end

else

  begin

  aux^.sig:=a;

  a^.sig:=p

  end;

x:=x^.sig

end;

list1:=list2;

goto 0;



7:

end.


16-Aug-2012 23:46
Antonio P.G.

¡Hola!

¿Puedes describir más o menos qué es lo que obtienes?¿Poner unos (al menos uno) casos de prueba?

Por cierto, es la primera vez que veo instrucciones "goto" en código de Pascal realmente aplicadas. Interesante.

He visto tu código por encima, y no he sido capaz de encontrar el error, tal vez si pones unos casos de prueba... ;-)

Te recomiendo el uso de TAD's (Tipos Abstractos de Datos) en casos de uso de punteros; se vuelve todo más sencillo, como un "LEGO".

¡A ver si el profe encuentra la respuesta!

Un saludo.


17-Aug-2012 00:12
carlos lopez

Gracias Antonio por responder. El problema es que al ordenar, no lo hace completamente, por ej al ingresar las siguientes fechas a ordenar(puse cualquier numero ya que escribir las fechas de forma dd/mm/aaaa era tedioso para la prueba):

73-5-29-6-81

el resultado de ordenamiento me daba:

81-73-6-5-29

y ahi estas el error, no lo ordena al 29, el algoritmo de ordenamiento lo utilice en otros programas sin probles, no se que ocurre en este.


17-Aug-2012 16:19
Nacho Cabanes (+31)

Primero un consejo, Carlos: Cuando te enfrentes a un problema difícil, o al menos a un problema nuevo, simplifica tanto como te sea posible.

En este caso, eso afecta a varias cosas:

- Usa estructuras tan sencillas como te sea posible: si aún no sabes ordenar, no uses un struct con muchos campos, sino un único campo.

- Intenta que el código sea legible: bien estructurado y con comentarios que ayuden a seguir lo que hace (o pretende hacer) cada parte del programa. De hecho, es muy recomendable escribir primero los comentarios que explican la lógica del programa y luego "rellenar" el programa entre los comentarios.

- Que los nombres de variables sean claros. Piensa que un programa se escribe una vez pero se lee muchas, cada vez que haya que ampliarlo o corregirlo. En ese sentido, ¿por qué el último ficha se llama "aux" en vez de "ultimo"? ¿y el dato actual "x" en vez de "actual"? ¿que hacen "p" y "a"?

- Intenta agrupar las secuencias lógicas. Esta interrupción en la asignación de valores al dato actual, para cambiar datos que corresponden al comienzo de la lista, es desconcertante y propensa a despistes:

new(x);
x^.nro_cta:=nro;
x^.fecha:=date;
x^.monto:=cant;
x^.tipo:=tipot;
if list1=nil then
 list1:=x
else
 aux^.sig:=x;
x^.sig:=nil;
aux:=x;

- El uso de variables globales y de "goto" puede dar lugar a muchos errores difíciles de rastrear. Intenta descomponer el programa en funciones, y que tantos datos como sea posible estén en variables locales.

- Si te ves forzado a usar "goto" y etiquetas, aprovecha que las etiquetas pueden ser palabras: "goto ordenar" es más legible que "goto 3".

En este caso, tendrás además la dificultad de que para ordenar por fecha, tendrás que compararlas en formato aaaa-mm-dd, no en el dd-mm-aaaa que presumiblemente introducirá el usuario.

En el próximo post te incluyo una versión "casi idéntica" de tu fuente, ligeramente retocada para que sea más fácil de leer, y comentamos a partir de ella...


17-Aug-2012 16:51
Nacho Cabanes (+31)

Aquí va una versión ligeramente reescrita, más a mi gusto.

La parte de añadir y la de mostrar datos están correctas. La opción de ordenar no tengo claro cómo pretendes plantearla, así que le he dado nombres un tanto arbitrarios a las variables. Cuéntanos cómo quieres lograrlo, para ver qué no estás haciendo bien. (La forma más sencilla es ir ordenando a medida que se inserta, en vez de añadir siempre al final; si quieres hacerlo a posteriori, no hace falta crear nuevos nodos con "new" sino recolocar los punteros "sig").

{ Lista ordenada - versión 1a (con menos datos, "while" por "goto") }
uses crt;

type
   puntero=^nodo;
   nodo=record
       dato:string;
       sig:puntero
   end;

var
   opcion: integer;
   comienzoLista,ultimoDato,datoActual: puntero;
   listaAlternativa,posicionListaAlternativa,
       datoListaAlternativa: puntero;
   texto: string;
   salir: boolean;
   
begin
   comienzoLista := nil;
   ultimoDato := nil;
   salir := false;

   repeat
       writeln('Elija una opcion:');
       writeln('1)insertar');
       writeln('2)mostrar');
       writeln('3)ordenar');
       writeln('7)salir');
       readln(opcion);
       case opcion of
       1: { --- Insertar un dato nuevo al final --- }
           begin
           writeln('ingrese dato:');
           readln(texto);
           new(datoActual);
           
           datoActual^.dato:=texto;   { Reservo espacio }
           datoActual^.sig:=nil;

           if comienzoLista=nil then  { si no hay datos, sera el primero }
             comienzoLista:=datoActual
           else
             ultimoDato^.sig:=datoActual;
           ultimoDato:=datoActual;    { y queda en ultimo lugar }
           end;
           
       2: { --- Ver toda la lista --- }
           begin
           datoActual:=comienzoLista;  { Desde el principio hasta nil }
           writeln();
           writeln('la lista es:');
           while (datoActual<>nil) do
               begin
               writeln('Dato: ',datoActual^.dato);
               writeln();
               datoActual := datoActual^.sig;
               end;
           end;

       3: { --- Ordenar segun campo "dato" --- }
           begin
           datoActual:=comienzoLista;
           listaAlternativa:=nil;

           while (datoActual<>nil) do
           begin
           posicionListaAlternativa:=listaAlternativa;
           new(datoListaAlternativa);
           datoListaAlternativa^.dato:=datoActual^.dato;

           while (posicionListaAlternativa<>nil)
               and (posicionListaAlternativa^.dato > datoActual^.dato) do
           begin
               ultimoDato:=posicionListaAlternativa;
               posicionListaAlternativa:=posicionListaAlternativa^.sig
           end;

           if posicionListaAlternativa=listaAlternativa then
             begin
             datoListaAlternativa^.sig:=posicionListaAlternativa;
             listaAlternativa:=datoListaAlternativa;
             end
           else
             begin
             ultimoDato^.sig:=datoListaAlternativa;
             datoListaAlternativa^.sig:=posicionListaAlternativa
             end;
           datoActual:=datoActual^.sig
           end;
           comienzoLista:=listaAlternativa;
           end;

       7: { --- Salir --- }
           salir := true;
           
       end;

   until salir;
end.


18-Aug-2012 02:58
Luis Torres (+12)

Diculpen que me meta, pero me gustaría saber ¿cuál método de ordenación utilizó el prof. Nacho Cabanes?.
Muchos saludos.


18-Aug-2012 03:45
carlos lopez

ya habia solucionado la parte del ordenamiento especificando efectivamente que se ingrese la fecha en formato (aaaa/mm/dd). Lo que sigue fallando, y falla todavia en la version que me dio usted, es que despues del ordenamiento, si ingreso un nuevo dato, y vuelvo a ordenar, al mostrar veo que me ha eliminado un nodo, o dos, depende de la cantidad de datos nuevos que ingreso, y no veo en que parte falla. Intente con procedure, pero en la parte de ordenamiento no me funciona correctamente, me ha funcionado todo, sin embargo si hago el programa de forma lineal, pero no puedo volver a repetir nada, tengo que cargar de una sola vez.


19-Aug-2012 02:02
Nacho Cabanes (+31)

Pero insisto, Carlos: no entiendo cómo estás ordenando. Cuéntanos qué idea estás aplicando, para ver dónde está el fallo. Una forma que recuerda a lo que tú haces, que resulta relativamente sencilla, pero es lenta y un tanto engorrosa, es volcar a una segunda lista, en la que los datos se ordenen en el momento de introducirlos, pero esto tiene dos problemas:

a) Tienes que acordarte de liberar la memoria que ocupaban los datos de la lista original, para no ir colapsando la memoria del sistema sin necesidad.

b) Si quieres que los datos estén ordenados, ¿realmente es necesario ordenarlos a petición?  ¿No sería más "amigable" para el usuario que estuvieran ordenados continuamente? (y en ese caso, se trataría de una lista ordenada).

Explícanos cómo lo quieres hacer, para ver qué está fallando en tu idea.


19-Aug-2012 04:34
carlos lopez

Hola Sr. Nacho Cabanes, el ordenamiento que estoy utilizando es por inserción, es un tanto intuitivo, estoy aprendiendo por mi cuenta a programar, no soy un experto. La verdad es que si el programa es utilizado, no hace falata ordenarlo, ya que van a ser ingresados de manera ordenada, creo que se entiende esta parte. Y sí, no hace falta que se ordene a petición, pero, de ordenarse a penas se ingresa el elemento habria que usar un algoritmo de ordenamiento similar o mas complicado, pero un algoritmo de ordenamiento en fin, ya que podria ingresar, por ej, primero un 3, luego un 1, si es de menor a mayor, va a ordenar el 3-1 en 1-3, pero si despues pongo un dos va a tener que comparar que sea mayor que el 1 y no mayor que el 3, y para esto voy a tener que recorrer la lista anterior como lo hago en mi algoritmo. Reconozco que no hace falta ordenarlo en otra lista, sí, se puede ordenar en la misma, pero el proceso sigue siendo el mismo creo yo. La cuestión por la que la ordeno es que después me simplifica otras tareas estando ordenada, como calcular la cantidad de dinero extraido en un cierto periodo de fechas, o la cuenta de un usuario en un determinado año. Me disculpo si soy un poco molesto, y si hay una forma de ordenar mas simple, hagamenla saber. Muchas gracias.


19-Aug-2012 04:49
carlos lopez

Por cierto, el problema que estoy haciendo es este:

Un banco tiene guardado los registros de los movimientos en una lista (lista ligada simple). Los movimientos estan ordenados primero por fecha y luego por numero de cuenta.

El tipo de elemento de la lista es:

TElemLista

         Fecha (Clave de ordenamiento 1)
         Numero de cuenta (Clave de ord. 2)
         Monto
         Tipo(deposito/extraccion)

realizar los siguientes procedimientos para este TDA:

-Permita calcular la cantidad de depósitos hechos realizados entre por ej el 01/01/2003 y el 27/04/2007

-Permita calcular el total depositado y extraido en el año por ej: 2003

-permita calcular el saldo de la cuenta 453 en el año 2003, por ej.

el ordenamiento por numero de cuenta si las fechas son iguales no lo implante aun, ya que me encontre con el problema de que se corta la lista al ordenar.


19-Aug-2012 12:54
carlos lopez

Bueno, revisando mi programa y el que me sugirió usted con las respectivas modificaciones, encontré donde fallaba al querer insertar otro elemento después de ordenar, y lo resolví de la siguiente forma:

{ Lista ordenada - versión 1a (con menos datos, "while" por "goto") }
uses crt;

type
   puntero=^nodo;
   nodo=record
       dato:string;
       sig:puntero
   end;

var
   opcion: integer;
   comienzoLista,ultimoDato,datoActual: puntero;
   listaAlternativa,posicionListaAlternativa,
       datoListaAlternativa: puntero;
   texto: string;
   salir: boolean;
   
begin
   comienzoLista := nil;
   ultimoDato := nil;
   salir := false;

   repeat
       writeln('Elija una opcion:');
       writeln('1)insertar');
       writeln('2)mostrar');
       writeln('3)ordenar');
       writeln('7)salir');
       readln(opcion);
       case opcion of
       1: { --- Insertar un dato nuevo al final --- }
           begin
           writeln('ingrese dato:');
           readln(texto);
           new(datoActual);
           
           datoActual^.dato:=texto;  { Reservo espacio }
           datoActual^.sig:=nil;

           if comienzoLista=nil then  { si no hay datos, sera el primero }
             comienzoLista:=datoActual
           else
             ultimoDato^.sig:=datoActual;
           ultimoDato:=datoActual;    { y queda en ultimo lugar }
           end;
           
       2: { --- Ver toda la lista --- }
           begin
           datoActual:=comienzoLista;  { Desde el principio hasta nil }
           writeln();
           writeln('la lista es:');
           while (datoActual<>nil) do
               begin
               writeln('Dato: ',datoActual^.dato);
               writeln();
               datoActual := datoActual^.sig;
               end;
           end;

       3: { --- Ordenar segun campo "dato" --- }
           begin
           datoActual:=comienzoLista;
           listaAlternativa:=nil;

           while (datoActual<>nil) do
           begin
           posicionListaAlternativa:=listaAlternativa;
           new(datoListaAlternativa);
           datoListaAlternativa^.dato:=datoActual^.dato;

           while (posicionListaAlternativa<>nil)
               and (posicionListaAlternativa^.dato > datoActual^.dato) do
           begin
               ultimoDato:=posicionListaAlternativa;
               posicionListaAlternativa:=posicionListaAlternativa^.sig
           end;

           if posicionListaAlternativa=listaAlternativa then
             begin
             datoListaAlternativa^.sig:=posicionListaAlternativa;
             listaAlternativa:=datoListaAlternativa;
             end
           else
             begin
             ultimoDato^.sig:=datoListaAlternativa;
             datoListaAlternativa^.sig:=posicionListaAlternativa
             end;
           datoActual:=datoActual^.sig
           end;
           comienzoLista:=listaAlternativa;

{--- Pone el ultimo dato de la lista ordenada para que se pueda ligar al proximo dato ingresado ---}
           datoActual:=listaAlternativa;
           while datoActual<>nil do
                 begin
                 if datoActual^.sig=nil then  
                    ultimoDato:=datoActual;
                 datoActual:=datoActual^.sig;
                 end;
{---------------------------------------------------------------------------------------------------}
           end;

       7: { --- Salir --- }
           salir := true;
           
       end;

   until salir;
end.

ya se aclararon mis dudas, gracias por ayudarme.


19-Aug-2012 22:39
Nacho Cabanes (+31)

Si hablas de que estás usando "ordenación por inserción", me temo cual es el problema: lo estás intentando hacer como si fuera un arrauy. No intentes tratar una estructura dinámica como si fuera una estructura estática, porque son distintas, cada una tiene sus ventajas y sus inconvenientes.

Primero, una comparación: si primero aprendes a conducir un coche y luego aprendes a conducir una motocicleta, verás que muchas de las "cosas" que haces en coche no las podrás hacer en moto: no puedes tomar las curvas girando el volante... ni siquiera girando el manillar, tendrás que inclinar la moto. Si giras el manillar, será porque vas muy despacio... o te matarás.

Aquí pasa algo parecido: cuando ordenas un array, intercambias un elemento por otro, preparas espacio para un elemento auxiliar, te despreocupas del espacio que ocupa ese elemento porque se liberará automáticamente en cuanto esa variable (estática) deje de existir, etc. En cambio, con estructuras dinámicas, es (o debería ser) totalmente distinto: no reservas espacio para nuevos nodos, sino que basta con cambiar el "orden de los enlaces"; si reservas espacio para algún dato auxiliar, tendrás que acordarte de liberarlo después. De hecho, insertar datos en orden en un array es "costoso" porque puedes tener que mover muchos datos, pero insertar en orden en una lista enlazada es simple y rápido: basta comenzar por el principio y avanzar hasta llegar a "nil" o a un dato mayor que el nuevo.

Insisto: cambia el chip, ordenar una lista enlazada es algo totalmente distinto a ordenar un array, y deberías atacarlo de forma distinta.

Había un ejemplo al final del apartado 13.3, que mostraba cómo insertar datos en orden en una lista, pero me acabo de dar cuenta de que estaba partido, así que lo he movido a un nuevo apartado. Échale un vistazo. Lo tienes en:

http://www.aprendeaprogramar.com/mod/resource/view.php?id=483


23-Aug-2012 00:39
Luis Torres (+12)

Acabo de correr el programa, pero no ordena correctamente los números introducidos.
Saludos.


23-Aug-2012 01:15
Nacho Cabanes (+31)

Era de temer. Ya te decía yo que lo estabas haciendo de una forma muy rebuscada...  ;-)






(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.)