elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ordenar lista doblemente enlazada con insertion sort
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ordenar lista doblemente enlazada con insertion sort  (Leído 6,015 veces)
mari2diaz

Desconectado Desconectado

Mensajes: 24


Ver Perfil
Ordenar lista doblemente enlazada con insertion sort
« en: 26 Marzo 2022, 18:53 pm »

Cuando esta ordenando el programa se queda pegado sin hacer nada, me podrian decir q estoy haciendo mal al ordenar

Código
  1. void Curso::InsertionSort(){
  2. // Nodo puntero sera igual al siguinte de primer
  3. Curso* puntero = primer->ptrSig;
  4. // Nodo siguiente sera igual al siguiente de puntero
  5. Curso* siguiente = puntero->ptrSig;
  6. Curso* auxiliar;
  7. // Mistras puntero sea distinto de nullptr ordena la lista
  8. while(puntero != nullptr){
  9.  
  10. while(puntero->ptrAnt->t_prioridad > puntero->t_prioridad && puntero->ptrAnt != nullptr){
  11. if(puntero->ptrAnt == primer){
  12. // El siguiente de primer sera el siguiente de puntero
  13. primer->ptrSig = puntero->ptrSig;
  14. // El anterior del siguinte de puntero sera primer
  15. puntero->ptrSig->ptrAnt = primer;
  16. // El siguiente de puntero sera primer
  17. puntero->ptrSig = primer;
  18. // El anterior de primer sera puntero
  19. primer->ptrAnt = puntero;
  20. // primer sera igual a puntero
  21. primer = puntero;
  22. }else if(puntero == ultimo){
  23. // ultimo sera igual al anterior de puntero
  24. ultimo = puntero->ptrAnt;
  25. // El anterior de puntero sera el anterior del ultimo
  26. puntero->ptrAnt = ultimo->ptrAnt;
  27. // El siguiente del anterior del ultimo sera puntero
  28. ultimo->ptrAnt->ptrSig = puntero;
  29. // El siguiente de puntero sera el ultimo
  30. puntero->ptrSig = ultimo;
  31. // El anterior del ultimo sera puntero
  32. ultimo->ptrAnt = puntero;
  33. }else{
  34. auxiliar = puntero->ptrAnt;
  35. auxiliar->ptrSig = puntero->ptrSig;
  36. puntero->ptrSig->ptrAnt = auxiliar;
  37. auxiliar->ptrAnt->ptrSig = puntero;
  38. puntero->ptrAnt = puntero->ptrAnt;
  39. puntero->ptrSig = auxiliar;
  40. auxiliar->ptrSig = puntero;
  41. }
  42. }
  43. puntero = siguiente;
  44. siguiente = siguiente->ptrSig;
  45. }
  46. }
  47.  


En línea

MAFUS


Desconectado Desconectado

Mensajes: 1.603



Ver Perfil
Re: Ordenar lista doblemente enlazada con insertion sort
« Respuesta #1 en: 27 Marzo 2022, 20:26 pm »

Sí, es un quebradero de cabeza. Mucho más sencillo cuando se usa un array.

Una solución que he conseguido es la siguiente. En C. Esas cosas modernas de C++ se me escapan :D

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. typedef struct node {
  6.    int data;
  7.    struct node* prev;
  8.    struct node* next;
  9. } node;
  10.  
  11. void print(node *list) {
  12.    node *pointer = list;
  13.    while(pointer) {
  14.        printf("%d ", pointer->data);
  15.        pointer = pointer->next;
  16.    }
  17.    putchar('\n');
  18. }
  19.  
  20. void insertion_sort(node **head) {
  21.    // evito una lista vacía
  22.    if(!*head) {
  23.        return;
  24.    }
  25.  
  26.    // se recorre la lista de izquierda a derecha
  27.    for(node *pointer=(*head)->next; pointer; pointer=pointer->next) {
  28.        // nodo auxiliar para recorrer la lista al revés en busca de datos menores
  29.        node *aux = pointer;
  30.        // flag para mantener pointer en su sitio
  31.        bool flag = true;
  32.        // ordenando de forma ascendente
  33.        while(aux->prev && aux->data < aux->prev->data) {
  34.            // se inicia el intercambio de nodos, el actual por el anterior a este ----------------
  35.            // se empieza por hacer que los nodos en los extremos de la pareja actual apunten
  36.            // a la pareja actual de forma intercambiada. Por ejemplo: sean los cuatro nodos
  37.            // A B [C] D
  38.            // C es el nodo actual a comparar
  39.            // A->next apunta a B
  40.            // D->prev apunta a C
  41.            // en el intercambio
  42.            // A->next debe apuntar a C
  43.            // D->prev debe apuntar a B
  44.            // para que esto sea así se debe comprobar que A y D existan para poder operar
  45.  
  46.            // contiene la dirección del nodo previo al previo del actual: siendo el actual C, A
  47.            node *app = aux->prev->prev;
  48.            // si dicho nodo existe, el siguiente a este deberá ser el actual. A->next apunta a C.
  49.            if(app) {
  50.                aux->prev->prev->next = aux;
  51.            }
  52.            // si existe un nodo que sea siguiente al actual, su previo debe apuntar al nodo anterior al actual. D->prev apunta a B.
  53.            if(aux->next) {
  54.                aux->next->prev = aux->prev;
  55.            }
  56.  
  57.            // intercambio entre la pareja de nodos.
  58.            // B->prev apunta a C
  59.            aux->prev->prev = aux;
  60.            // B->next apunta a D
  61.            aux->prev->next = aux->next;
  62.            // C->next apunta a B
  63.            aux->next = aux->prev;
  64.            // C->prev apunta a A
  65.            aux->prev = app;
  66.  
  67.            // el primer intercambio se hará lo más a la derecha de la sublista
  68.            // por lo tanto cuándo se efectua el primer intercambio se debe actualizar
  69.            // pointer para que apunte al nodo intercambiado. El flag va a evitar que
  70.            // si se va hacia la izquierda pointer también vaya a la izquierda.
  71.            if(flag) {
  72.                pointer = aux->next;
  73.                flag = false;
  74.            }
  75.  
  76.            // la cabeza de la lista se debe actualizar si hay algún nodo que ha caído en
  77.            // esa posición
  78.            if(!aux->prev)
  79.                *head = aux;          
  80.        }
  81.    }
  82. }
  83.  
  84. bool add(node **head, int data) {
  85.    node *new = malloc(sizeof(node));
  86.    if(!new) {
  87.        return false;
  88.    }
  89.  
  90.    new->data = data;
  91.    new->next = NULL;
  92.  
  93.    if(*head) {
  94.        node *pointer = *head;
  95.        while(pointer->next) {
  96.            pointer = pointer->next;
  97.        }
  98.        pointer->next = new;
  99.        new->prev = pointer;
  100.    } else {
  101.        new->prev = NULL;
  102.        *head = new;
  103.    }
  104.  
  105.    return true;
  106. }
  107.  
  108. void drop(node **head) {
  109.    node *aux;
  110.    if(!*head) {
  111.        return;
  112.    }
  113.  
  114.    while(*head) {
  115.        aux = *head;
  116.        *head = (*head)->next;
  117.        free(aux);
  118.    }
  119. }
  120.  
  121. int main() {
  122.    node *list = NULL;
  123.    add(&list, 5);
  124.    add(&list, 2);
  125.    add(&list, 4);
  126.    add(&list, 1);
  127.    add(&list, 3);
  128.    add(&list, 0);
  129.  
  130.    print(list);
  131.  
  132.    insertion_sort(&list);
  133.    print(list);
  134.  
  135.    drop(&list);
  136. }


« Última modificación: 27 Marzo 2022, 21:06 pm por MAFUS » En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.348


Ver Perfil
Re: Ordenar lista doblemente enlazada con insertion sort
« Respuesta #2 en: 27 Marzo 2022, 23:53 pm »

Es deseable a la hora de programar, hacerse un sencillo esquema de como ha de funcionar el algoritmo, precisamente para luego ver que si falla, qué punto puede estar mal programado.

Primero procede una descripción del algoritmo, simple y clara... obviando que se trata de una lista enlazada (es más sencillo de entender si se aplica a un array) cuando se esté seguro que la descripción es correcta, se hace un pseudocódigo del mismo y luego se programa con el tipo de estructura que se haya solicitado...

Una descricpción simple podría ser:
Algoritmo de ordenación por inserción:
1 - Comenzando por el segundo elemento (en la lista) y siguiendo hasta el último, se toma como actual y se aparta.
2 - Luego el actual se va comparando con los que le preceden, mientras el precedente sea menor que él (y no se alcance el primero).
3 - En dicho caso el precedente cambia de posición colocándose detrás del puesto que ocupa el actual y el puesto del actual se reduce en 1 (sigue apartado).
4 - Cuando ya no hay más precedentes menor que él, se ubica en tras ese precedente.
5 - Volvemos al paso 1

Hay que entender la descripción. De otro modo, el código que le siga fracasará.
Lo siguiente es un pequeño pseudocódigo, todavía pòdemos obviar que se trata de listas enlazadas, resolvámoslo primero con arrays y luego se tratará con listas enlazadas...
Código:
funcion InsertionSort(array de enteros Array)
    entero min, max, n, j, k, temp

    min = 0
    max = Array.length
    j = (min +1)
    bucle para k desde j hasta max   // 1              
        temp = Array(k)
        hacer mientras (temp < Array(j))   // 2
            Array(j+1) = Array(j)   // 3
            j -=1    
            Si (j<0) salir del bucle        // 2 ***
        repetir
        Array(j +1) = temp   // 4
        j = k
    siguiente    // 5

*** En según que lenguajes puede ponerse como primera condición del bucle, porque solo se evalua la segunda condición si la primera falla, en lenguajes que no 'cortocircuitan' incurre en un error, que se solventa colocando al final del bucle dicha condición (como se observa).

Nota que si los valores 'min' y 'max' se pasaran como parámetros, en vez de tenerlos internamente en la función, podría ordenarse cualquier subsección del array en vez del array entero que se toma por defecto de este modo.

Puede hacerse una ligera mejora al algoritmo. Es fácil darse cuenta que el elemento apartado, se asigna tras el bucle incluso aunque el precedente no sea menor. Si se hace una comprobación previa al bucle interno, y solo si se cumple dicha condición la asignación (del elemento siendo comparado) siempre será aplicable, si no, no se precisa... a su vez dado que esa condición ya examina dicha posibilidad, el bucle interno, puede mudar su condición a la parte baja (algunos lenguajes no toleran cambiar la condición al final del bucle):
Código:
funcion InsertionSort(array de enteros Array)
    entero min, max, n, j, k, temp

    min = 0
    max = Array.length
    j = (min +1)
    bucle para k desde j hasta max   // 1              
        temp = Array(k)
        Si (temp < Array(j))            // 2
            hacer                          //mientras (Array(j) < temp)   // 2
                Array(j+1) = Array(j)   // 3
                j -=1    
                Si (j<0) salir del bucle        // 2
            repetir mientras (temp < Array(j))   // 2
            Array(j +1) = temp   // 4
        Fin si
        j = k          
    siguiente    // 5
Es importante notar la diferencia entre este y el pseudocódigo anterior.
Esta ligera mejora, ya que evita hacer asignaciones innecesarias, será aún más notable en la lista doblemente enlazada.

Como se puede seguir en el pseudocódigo (aplicado a un array) es bastante sencillo y podría pasarse a programar ya en cualquier lenguaje. Como se requiere aplicarlo sobre una lista doblemente enlazada, conviene pasarlo a una estructura de tal tipo antes de programarlo. Básicamente es copiar y pegar el pseudocódigo y luego hacer remplazos para referirse a los ítems de una lista doblemente enlazada. Suele requerirse a veces (este es el caso), tener algún elemento auxiliar, para no perder referencias del curso del actual.
 
Lo primero a notar es como cambiaremos las variable del tipo entero al tipo 'nodo' que son los elementos de la lista, y que la función recibe como parámetro el odo raíz.
Código:
estructura nodo
    entero Valor
    nodo Anterior
    nodo Siguiente
fin estructura

funcion InsertionSort(nodo Raiz)
    nodo  j, k, temp  //min, max,
 
    temp  = Raiz.Siguiente
    hacer mientras temp no sea nulo  // 1 Supone que hay más de 1 elemento y que no está más allá del último.                
        j = temp.Anterior
        k = temp.siguiente
        si (temp.Valor < j.Valor)    // 2
            // Aislamos temp de la lista reconectando sus extremos entre sí.
            // Esto además nos permite, no tener necesidad de hacer intercambios contínuamente en el bucle que sigue.
            Si (temp.Siguiente no es nulo)
               temp.Siguiente.Anterior = j      // el anterior al siguiente a temp, será ahora el anterior a temp (no temp)
            fin si
            j.Siguiente = temp.Siguiente    // el siguiente del previo a temp, ahora será el siguiente de temp, incluso si es nulo (el último)
            
            hacer    // 2        
                Si (j.Anterior es nulo ) salir del bucle        // 2                        
                j = j.Anterior                              // 3  
            repetir mientras  (temp.Valor < j.Valor)
            // Ahora conectamos temp entre medios del que es manor o igual que él (aún siendo el primero) y el mayor que él (aún siendo el último)
            // 4
            si (j.Anterior es nulo)
                temp.Anterior = j.Anterior   // nulo
                temp.siguiente = j
                j.Anterior = temp
                Raiz = temp
            sino
                j.siguiente.Anterior = temp  
                temp.Anterior = j
                temp.siguiente = j.siguiente
                j.siguiente = temp
            fin si
        Fin si
        temp = k
    repetir    // 5
fin funcion
El código no es mucho más largo que la versión que opera sobre un array.
Nota como al desenlazar el nodo siendo examinado (y una vez vimos que debe cambiar de sitio, merced a la mejora introducida), podemos hacer un recorrido hacia atrás más sencillo y elegante.
También debes notar, como las precauciones tomadas preguntando cuando interesa si no es nulo, hace que no tengamos que hacer asignaciones más complejas...

Para probarlo, puede recurirse a crear una lista, ordenarla y luego imprimirla:
Código:
funcion CrearOrdenarYProbar
    nodo j, k, temp, Raiz
    entero n, valores[]
    
    // 1 Creamos una lista doblemente enlazada de nodos
    valores = Array(6, 4, 7, 8, 2, 5, 5, 1, 7, 3, 6, 8, 4, 9, 2)
    Raiz = nuevo nodo
    Raiz.Valor = valores(0)
    k = Raiz
    bucle para n desde 1 hasta valores.length
        j = nuevo nodo
        j.Valor = valore[n]
        j.Anterior = k
        k.siguiente = j
        k = j
    siguiente

    // 2 ordenamos la lista.
    llamada a InsertionSort(raiz)

    // 3 mostramos el resultado.
    temp = Raiz
    hacer mientras temp no sea nulo
        imprimir temp.Valor
        temp = temp.siguiente
    repetir
fin funcion

Resultado:
 1
 2
 2
 3
 4
 4
 5
 5
 6
 6
 7
 7
 8
 8
 9

« Última modificación: 27 Marzo 2022, 23:58 pm por Serapis » En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
ayuda...Lista doblemente enlazada
Java
goll9d 2 3,611 Último mensaje 22 Enero 2012, 04:50 am
por goll9d
ayuda con lista doblemente enlazada
Programación C/C++
gibi77 3 3,674 Último mensaje 7 Marzo 2012, 07:47 am
por nirvguy
Ayuda con lista doblemente enlazada
Programación C/C++
falconez 2 8,992 Último mensaje 16 Diciembre 2013, 01:35 am
por falconez
Ordenar strings de analisis de fechas en lista doblemente enlazada.
Programación C/C++
falconez 1 2,413 Último mensaje 16 Junio 2014, 09:21 am
por eferion
lista doblemente enlazada
Programación C/C++
d91 1 1,906 Último mensaje 19 Octubre 2015, 04:06 am
por d91
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines