Autor Tema: Re: Ordenacion Por Selección (Leído 4339 veces)

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

 
type
  TipoNombre = String[15];
        TipoClave = string[3];
  TipoSector = String[2];
  TipoHabitantes = integer;
  PunteroLista = ^NodoLista;
        NodoLista = record
    Nombre : TipoNombre;
                Clave : TipoClave;
                Sector : TipoSector;
                Habitantes : TipoHabitantes;
                Sig : PunteroLista;
        end;
        TipoListaEnlazada = PunteroLista;
 
var
        Lista : TipoListaEnlazada;
 
 

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

. 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

 
procedure Seleccion (var Lista : TipoListaEnlazada);
 
var
  Ref, Next : PunteroLista;
 
begin
  if not ListaVacia(Lista) then
  begin
    Ref := Lista;
    repeat
      Next := Ref^.Sig;
      while Next &#60;&#62; nil do
      begin
        if Ref^.Nombre &#62; Next^.Nombre then Cambiar(Ref, Next);
        Next := Next^.Sig;
      end;
      Ref := Ref^.Sig;
    until Ref = nil;
  end
  else
  begin
    writeln ('La lista esta vac¡a. No hay elementos para ordenar');
    readln;
  end;
end;
 
 

El procedure Cambiar es este:

Código: Text

 
procedure Cambiar (var Mayor, Menor : PunteroLista);
 
var
  Aux : PunteroLista;
begin
  new(Aux);
  Aux^.Sig := Mayor^.Sig;
  Mayor^.Sig := Menor^.Sig;
  Menor^.Sig := Aux^.Sig;
  dispose(Aux);
end;
 
 

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

.

Bueno, creo que eso es. Gracias, de nuevo, a todos por su atención y perdón por el ladrillito.

thot_ohm

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

 
program ordenacadena;
 
var
  a, b : string;
 
begin
  writeln('primera cadena: ');
  readln(a);
  writeln('segunda cadena: ');
  readln(b);
        if a &#60; b then writeln(a, ' est  antes en el abecedario que ', b);
        if a &#62; b then writeln(b, ' est  antes en el abecedario que ', a);
  readln;
end.
 
 

thot_ohm

Modifiqué el procedimiento de ordenación por selección usando bucles for.

Código: Text

 
procedure Seleccion (var Lista : TipoListaEnlazada);
 
var
  Ref, Next : PunteroLista;
  N, J, I : byte;
 
begin
  if not ListaVacia(Lista) then
  begin
    Ref := Lista;
    N := Longitud(Lista);
    for I := 1 to N-1 do
    begin
      Next := Ref^.Sig;
      for j := I + 1 to N do
      begin
        if Ref^.Datos.Nombre &#62; Next^.Datos.Nombre then Cambiar(Lista, Ref, Next);
        Next := Next^.Sig;
      end;
      Ref := Ref^.Sig;
    end;
    
        end
  else
  begin
    writeln ('La lista est  vac¡a. No hay elementos para ordenar');
    readln;
  end;
        ImprimeLista(Lista);
end;
 
 

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

Código: Text

 
function Longitud (Lista: TipoListaEnlazada): byte;
  var
    n: PunteroLista;
    i: word;
  begin
    n := Lista;
    i := 0;
    while n &#60;&#62; nil do
      begin
        n := n^.sig;
        i := i + 1
      end;
    Longitud := i
  end;
 
 

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

 
procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
 
var
  Aux : PunteroLista;
begin
  new(Aux);
  Aux := Mayor;
  Mayor := Menor;
  Menor := Aux;
  dispose(Aux);
end;
 
 

pero sigue estando la lista desordenada.

Por favor, alguna sugerencia?

thot_ohm

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???

Enko

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;

Alpha_

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

procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
var
  Aux : PunteroLista;
begin
  Aux := mayor^.sig;
  Mayor^.sig := Menor^.sig;
  Menor^.sig := Aux;
end;
 

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

Saludos Zorrinescos. xD

thot_ohm

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?

thot_ohm

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

), 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

 
for j:=1 to 3 do
         for i:=1 to 3 do
             if (A[i] &#62; A[i+1]) then Cambiar(A[i],A[i+1])

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

 
for Recorrido:= 1 to N-1 do
         for J :=Recorrido+1 to N do
             If (A[Recorrido]&#62;A[J]) then Cambiar(A[Recorrido],A[J])

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.

thot_ohm

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??

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

 
procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);
 
var
  Aux : PunteroLista;
begin
        new(Aux);
  Aux^.Datos := Mayor^.Datos;
  Mayor^.Datos := Menor^.Datos;
  Menor^.Datos := Aux^.Datos;
end;
 
 

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.

Amilius

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

procedure Cambiar (var Lista : TipoListaEnlazada; var Mayor, Menor : PunteroLista);

var
Aux : PunteroLista;
begin
new(Aux);
Aux^.Datos := Mayor^.Datos;
Mayor^.Datos := Menor^.Datos;
Menor^.Datos := Aux^.Datos;
end;

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

Normalmente la cosa funciona asi:

Código: Text

 
procedure Cambiar (var Mayor, Menor : PunteroALosDatos);
var
  Aux : PunteroALosDatos;
begin
  Aux := Mayor;
  Mayor := Menor;
  Menor := Aux;
end;
 
 

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?

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.

Amilius

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

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

thot_ohm

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.