SoloCodigo

Programación General => Pascal => Mensaje iniciado por: thot_ohm en Sábado 3 de Diciembre de 2005, 21:06

Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Sábado 3 de Diciembre de 2005, 21:06
Buenas.

Ante todo, como siempre, gracias al que se tome su tiempo en leer y tratar de ayudarme en ésta duda que paso a explicar.

Tengo una lista enlazada creada con punteros cuya estructura es:
Código: Text
  1.  
  2. type
  3.   TipoNombre = String[15];
  4.         TipoClave = string[3];
  5.   TipoSector = String[2];
  6.   TipoHabitantes = integer;
  7.   PunteroLista = ^NodoLista;
  8.         NodoLista = record
  9.     Nombre : TipoNombre;
  10.                 Clave : TipoClave;
  11.                 Sector : TipoSector;
  12.                 Habitantes : TipoHabitantes;
  13.                 Sig : PunteroLista;
  14.         end;
  15.         TipoListaEnlazada = PunteroLista;
  16.  
  17. var
  18.         Lista : TipoListaEnlazada;
  19.  
  20.  
Sé que los campos de datos del puntero los puedo meter en un solo tipo record, pero quise postearlo así, pues para ver si quedaba más claro.

Ok. Creo mi lista y empiezo a meter datos como un degenerado  :comp: . La muestro en pantalla y perfecto, se muestran en orden inverso en el que yo los introduje ya que el procedimiento de inserción lo hace al principio de la lista (deliberadamente).

Seguidamente, se me pide ordenar la lista generada mediante diferentes métodos (inserción, selección, burbuja...). Ahora estoy con el procedimiento de selección y es acá donde tengo el problema. He revisado el código, y hasta donde me llegan mis conocimientos, parece estar bien, pero cuando imprimo la lista después de haber ejecutado el procedure, ésta sigue estando igual de desordenada. Éste es el procedure:

Código: Text
  1.  
  2. procedure Seleccion (var Lista : TipoListaEnlazada);
  3.  
  4. var
  5.   Ref, Next : PunteroLista;
  6.  
  7. begin
  8.   if not ListaVacia(Lista) then
  9.   begin
  10.     Ref := Lista;
  11.     repeat
  12.       Next := Ref^.Sig;
  13.       while Next <> nil do
  14.       begin
  15.         if Ref^.Nombre > Next^.Nombre then Cambiar(Ref, Next);
  16.         Next := Next^.Sig;
  17.       end;
  18.       Ref := Ref^.Sig;
  19.     until Ref = nil;
  20.   end
  21.   else
  22.   begin
  23.     writeln ('La lista esta vac¡a. No hay elementos para ordenar');
  24.     readln;
  25.   end;
  26. end;
  27.  
  28.  

El procedure Cambiar es este:

Código: Text
  1.  
  2. procedure Cambiar (var Mayor, Menor : PunteroLista);
  3.  
  4. var
  5.   Aux : PunteroLista;
  6. begin
  7.   new(Aux);
  8.   Aux^.Sig := Mayor^.Sig;
  9.   Mayor^.Sig := Menor^.Sig;
  10.   Menor^.Sig := Aux^.Sig;
  11.   dispose(Aux);
  12. end;
  13.  
  14.  

El campo clave para ordenar, como puede verse, es el nombre de la ciudad. Yo estoy haciendo las comparaciones directas ya que leí por ahí que pascal reconoce a>b o luis<diana.

No sé si estoy pasando bien la lista por valor (si es que esto se puede) o es que debo crear una nueva lista con los nuevos valores ordenados (cosa que me parece que carece de valor), o no estoy haciendo correctamente el intercambio de los nodos en el procedimiento Cambiar.

Estoy nuevo en esto de los punteros y estoy bastante enredado. El procedimiento Selección está adaptado de un procedimiento de ordenación por selección creado para arrays unidimensionales y aunque ustedes probablemente lo vean fácil, a mi me costó bastante debido a mi inexperiencia y debido a ella, no me extrañaría que tuviera algo malo  :rolleyes: .

Bueno, creo que eso es. Gracias, de nuevo, a todos por su atención y perdón por el ladrillito.
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Sábado 3 de Diciembre de 2005, 21:35
Ya comprobé que Pascal permite comparaciones directas sobre los tipos string (tenía duda en eso. Acá está el código con el que probé esto:

Código: Text
  1.  
  2. program ordenacadena;
  3.  
  4. var
  5.   a, b : string;
  6.  
  7. begin
  8.   writeln('primera cadena: ');
  9.   readln(a);
  10.   writeln('segunda cadena: ');
  11.   readln(b);
  12.         if a &#60; b then writeln(a, ' est  antes en el abecedario que ', b);
  13.         if a &#62; b then writeln(b, ' est  antes en el abecedario que ', a);
  14.   readln;
  15. end.
  16.  
  17.  
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Domingo 4 de Diciembre de 2005, 14:46
Modifiqué el procedimiento de ordenación por selección usando bucles for.

Código: Text
  1.  
  2. procedure Seleccion (var Lista : TipoListaEnlazada);
  3.  
  4. var
  5.   Ref, Next : PunteroLista;
  6.   N, J, I : byte;
  7.  
  8. begin
  9.   if not ListaVacia(Lista) then
  10.   begin
  11.     Ref := Lista;
  12.     N := Longitud(Lista);
  13.     for I := 1 to N-1 do
  14.     begin
  15.       Next := Ref^.Sig;
  16.       for j := I + 1 to N do
  17.       begin
  18.         if Ref^.Datos.Nombre &#62; Next^.Datos.Nombre then Cambiar(Lista, Ref, Next);
  19.         Next := Next^.Sig;
  20.       end;
  21.       Ref := Ref^.Sig;
  22.     end;
  23.    
  24.         end
  25.   else
  26.   begin
  27.     writeln ('La lista est  vac¡a. No hay elementos para ordenar');
  28.     readln;
  29.   end;
  30.         ImprimeLista(Lista);
  31. end;
  32.  
  33.  

Longitud es una función que devuelve el número de nodos de la lista enlazada. Acá está el código:

Código: Text
  1.  
  2. function Longitud (Lista: TipoListaEnlazada): byte;
  3.   var
  4.     n: PunteroLista;
  5.     i: word;
  6.   begin
  7.     n := Lista;
  8.     i := 0;
  9.     while n &#60;&#62; nil do
  10.       begin
  11.         n := n^.sig;
  12.         i := i + 1
  13.       end;
  14.     Longitud := i
  15.   end;
  16.  
  17.  

Ok. Sigo teniendo el mismo error: La lista sigue desordenada. Intuyo que el error, proviene del procedimiento cambiar. Probando, lo cambié por éste:

Código: Text
  1.  
  2. procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
  3.  
  4. var
  5.   Aux : PunteroLista;
  6. begin
  7.   new(Aux);
  8.   Aux := Mayor;
  9.   Mayor := Menor;
  10.   Menor := Aux;
  11.   dispose(Aux);
  12. end;
  13.  
  14.  

pero sigue estando la lista desordenada.

Por favor, alguna sugerencia?
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Martes 6 de Diciembre de 2005, 14:21
Nadie me puede sugerir nada?

He estado dándole vueltas a la cosa. Supongamos que mi lista enlazada es esta:

rosa->alberto->luis->nil

Queremos intercambiar rosa con alberto. Debería asignar a rosa la dirección a la que apunta alberto. Esto sería: rosa^.sig := alberto^.sig y a alberto asignarle la dirección que tiene rosa ahora y alberto pasaría a ser la cabecera de la lista. Ok, no estoy seguro de cómo hacer esto.

Sugerencias???
Título: Re: Ordenacion Por Selección
Publicado por: Enko en Martes 6 de Diciembre de 2005, 23:34
Citar
Queremos intercambiar rosa con alberto. Debería asignar a rosa la dirección a la que apunta alberto. Esto sería: rosa^.sig := alberto^.sig y a alberto asignarle la dirección que tiene rosa ahora y alberto pasaría a ser la cabecera de la lista. Ok, no estoy seguro de cómo hacer esto.

Citar
rosa->alberto->luis->nil
Supongo que ser'ia como intercambiar variables>

punteroTemporal := rosa.sig;
rosa.sig := alberto.sig;
alberto.sig := punteroTemporal;
punteroTemporal := nil;
Título: Re: Ordenacion Por Selección
Publicado por: Alpha_ en Miércoles 7 de Diciembre de 2005, 15:46
Primero, disculpen si me equivoco, pero ese método es el de burbujeo. El de selección hasta donde yo sabía consistía en recorer la lista N veces y en cada iteración seleccionar el mayor/menor de la lista y ubicarlo donde corresponda.

Segundo. La lista no se te ordenará nunca porque estás cambiando los lugares en memoria donde están los nodos de la lista, pero tenés que actualizar también los enlaces. Lógicamente dentro de la lista, no hubo un solo cambio.

Cambiar debería ser

Código: Text
  1. procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
  2. var
  3.   Aux : PunteroLista;
  4. begin
  5.   Aux := mayor^.sig;
  6.   Mayor^.sig := Menor^.sig;
  7.   Menor^.sig := Aux;
  8. end;
  9.  

Ni hace falta cambiar los datos en memoria. Sólo los enlaces.

Saludos Zorrinescos. xD
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Jueves 8 de Diciembre de 2005, 19:23
Gracias Enko, gracias Alpha. Por lo que deduzco ambos tienen razón.

Todo emocionado voy a compilar y va y me sale "Error while linking" y se situa en la última línea de código, al lado del último end. Que es eso?  :(
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Jueves 8 de Diciembre de 2005, 20:28
Se me olvidaba Alpha. Burbuja, creo, es el que compara los datos de una lista de a dos de forma consecutiva y si el primero es mayor que el segundo se intercambian. Es decir:

5->4->8->2

Suponiendo que es un array (olvidémonos de los punteros un rato :blink: ), primero compara 5 y 4, como 5 es más mayor, los intercambia:

4->5->8->2

Ahora compara 5 y 8, quedaría igual. Luego Compara 8 y 2 y como se cumple la condición:

4->5->2->8

Y así iterativamente hasta que lo ordena. Suponiendo que el array (A)sea de 4 elementos el código sería algo así:

Código: Text
  1.  
  2. for j:=1 to 3 do
  3.          for i:=1 to 3 do
  4.              if (A[i] &#62; A[i+1]) then Cambiar(A[i],A[i+1])
  5.  
  6.  

Selección compara un elemento con el resto de los elementos del array. Es decir:

5->4->8->2

Compara 5 con 4, los cambia:

4->5->8->2

Ahora compara 4 con 8 (el tercer elemento) y queda igual. Por último compara el 4 con el 2, y por supuesto, los intercambia:

2->5->8->4

El código es algo así:

Código: Text
  1.  
  2. for Recorrido:= 1 to N-1 do
  3.          for J :=Recorrido+1 to N do
  4.              If (A[Recorrido]&#62;A[J]) then Cambiar(A[Recorrido],A[J])
  5.  
  6.  

Es decir la idea de éste último método de ordenación es ubicarse en la primera posición del array, seleccionar el elemento de menor tamaño y ponerlo en la primera posición, luego se ubica en la segunda posición y busca el siguiente elemento más pequeño y lo pone en ésta segunda posición etc...

Vamos, según tengo yo entendido. Como yo estoy aprendiendo, es muy probable que éste equivocado en algún punto. La idea no es dármela de listillo, si no de aprender. Si estoy errado, por favor díganme donde. Gracias.
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Viernes 9 de Diciembre de 2005, 16:15
Probé en otra computadora y no me daba el "error while linking". Ahora puedo ejecutar el programa, pero en plena ejecucion me da un error. Exitcode =216. Que es esto??
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Viernes 30 de Diciembre de 2005, 14:53
Rescatando un poco este post y para dejar la solución al problema que planteaba para futuras consultas.

Lo del "error while linking" y el "exitcode=216" al parecer lo provocaba el compilador (FreePascal), probé con TurboPascal y corre sin problemas.

El procedimiento cambiar quedó definitivamente de la siguiente manera:

Código: Text
  1.  
  2. procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
  3.  
  4. var
  5.   Aux : PunteroLista;
  6. begin
  7.         new(Aux);
  8.   Aux^.Datos := Mayor^.Datos;
  9.   Mayor^.Datos := Menor^.Datos;
  10.   Menor^.Datos := Aux^.Datos;
  11. end;
  12.  
  13.  

Lo que hice fué simplemente cambiar los datos contenidos en los punteros sin cambiar sus enlaces. No se si será medio chapucera esta forma, pero así funciona.

Agradecería cualquier sugerencia, pero como digo, funciona.
Título: Re: Ordenacion Por Selección
Publicado por: Amilius en Viernes 30 de Diciembre de 2005, 16:46
Cita de: "thot_ohm"
Rescatando un poco este post y para dejar la solución al problema que planteaba para futuras consultas.

Lo del "error while linking" y el "exitcode=216" al parecer lo provocaba el compilador (FreePascal), probé con TurboPascal y corre sin problemas.

El procedimiento cambiar quedó definitivamente de la siguiente manera:

Código: Text
  1.  
  2. procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
  3.  
  4. var
  5.   Aux : PunteroLista;
  6. begin
  7.         new(Aux);
  8.   Aux^.Datos := Mayor^.Datos;
  9.   Mayor^.Datos := Menor^.Datos;
  10.   Menor^.Datos := Aux^.Datos;
  11. end;
  12.  
  13.  

Lo que hice fué simplemente cambiar los datos contenidos en los punteros sin cambiar sus enlaces. No se si será medio chapucera esta forma, pero así funciona.

Agradecería cualquier sugerencia, pero como digo, funciona.
Pues estas dejando muchos nodos huerfanos de padre y madre...  :lol:

Normalmente la cosa funciona asi:

Código: Text
  1.  
  2. procedure Cambiar (var Mayor, Menor : PunteroALosDatos);
  3. var
  4.   Aux : PunteroALosDatos;
  5. begin
  6.   Aux := Mayor;
  7.   Mayor := Menor;
  8.   Menor := Aux;
  9. end;
  10.  
  11.  

Y luego tienes que asegurarte que sus punteros de enlace al anterior y siguiente apunten a donde quieres. Complicacion que te ganaste por el tipo de estructura de datos que estas usando. Una forma más comoda es usar 3 punteros: al anterior, al actual y al siguiente, asi cuando quieres intercambiar valores de los nodos solo intercambias los indices a ese gran arreglo estatico llamado ram guardados en los punteros "actuales", sin tener las complicaciones de evitar que tu lista quede fragmentada.

P.D. "Datos" no figura en los tipos que definiste, es simplemente una forma de abreviar o efectivamente Datos ahora es una variable del tipo puntero a los datos de tu nodo?
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Viernes 30 de Diciembre de 2005, 17:11
Hola Amilus:

He probado así como dices tú, incluso acabo de modificar el procedimiento para probar la forma que me indicas, pero la lista no se ordena.

No entiendo cuando dices que dejo un montón de nodos huérfanos  <_< . Simplemente cambio la información de un nodo a otro, pero no toco la estructura de la lista. Si te refieres al Aux que queda siempre por ahí pues con un dispose lo arreglo, no?

Bueno, tu me dices en que me estoy equivocando. Gracias.
Título: Re: Ordenacion Por Selección
Publicado por: Amilius en Viernes 30 de Diciembre de 2005, 19:38
Cita de: "thot_ohm"
Hola Amilus:

He probado así como dices tú, incluso acabo de modificar el procedimiento para probar la forma que me indicas, pero la lista no se ordena.

No entiendo cuando dices que dejo un montón de nodos huérfanos  <_< . Simplemente cambio la información de un nodo a otro, pero no toco la estructura de la lista. Si te refieres al Aux que queda siempre por ahí pues con un dispose lo arreglo, no?

Bueno, tu me dices en que me estoy equivocando. Gracias.
Si, efectivamente me referia al Aux. Si Datos es un registro y no un puntero no hay problema, pero no es eficiente por que mueves toda la memoria del registro en lugar de sólo modificar los punteros. (De todas formas un codigo que funciona es mejor que uno que no funciona aunque en teoria si funcionara fuera mas eficiente  :P ) Si Datos es un puntero el new() esta demás por que sólo necesitas intercambiar las posiciones de memoria que contienen.

Finalmente si no utilizas: var Lista : TipoListaEnlazada , seria bueno que lo quites para no desperdiciar tiempo de cpu al pasar ese parametro.

P.D.

Para asegurarte que todo marcha bien seria bueno que al reservar memoria y al liberarla pusieras en pantalla algun mensaje y mejor si tienes un contador en alguna variable global para saber cuantas veces reservaste memoria para un nodo y cuantas veces liberaste la memoria de un nodo.
Título: Re: Ordenacion Por Selección
Publicado por: thot_ohm en Viernes 30 de Diciembre de 2005, 20:35
Gracias Amilus.

Cuando llamo al procedimiento cambiar, me llevo los parámetros que viste, Lista, mayor y menor. Lo que no estoy seguro es si esto esta bien o no. La verdad es que me ha costado bastante hacer el programita y eso ha sido leyendo de un lado y de otro y adaptando código. Voy a adjuntar el código completo del programa a ver si le puedes echar un vistazo y me dices si voy bien.

Gracias por tu tiempo.