Sortowanie bąbelkowe listy dwukierunkowej

Odpowiedz Nowy wątek
Biały Pomidor
2015-06-09 14:16
Biały Pomidor
0

Witam wszystkich mam problem z posortowaniem listy dwukierunkowej za pomocą sortowania bąbelkowego. Mój kod wygląda tak:

struct node {
     int key;
     struct node *left;
     struct node *right;
}; 

void sort(int count, struct node *t_node)
{
    struct node *tmp,*nextnode, *node1, *node2;
    node2 = t_node;

    do{
         while(node2->right){
            if (node2->key > node2->right->key) {
                // zamiana B z C w liście A<->B<->C<->D na listę A<->C<->B<->D
                // B = node2
                nextnode = node2->right; // C
                tmp = node2->left; // A 

                if (tmp) 
                    tmp->right = nextnode; // A->right = C

                if (nextnode->right)
                    nextnode->right->left = node2; //D->left = B
                node2->right = nextnode->right; //B->right = D
                node2->left = nextnode->left; //B->left = C
                nextnode->right = node2; //C->right = B
                nextnode->left = tmp; //C->left = A
            }
            node2 = node2->right;
        }
         count = count -1;
    }while(count > 1);

}

Problem polega na tym, że dla przykładowych danych przed sortowaniem mam

Node value: 15
Node value: 3
Node value: 1
Node value: 10 

A po sortowaniu:


Node value: 15
Node value: 1
Node value: 10

Gdzie mam błąd w kodzie proszę o pomoc.

Pozostało 580 znaków

2015-06-09 14:27
Moderator

Rejestracja: 16 lat temu

Ostatnio: 1 godzina temu

0

Debuger w dłoń i klikaj, nikt tego za ciebie nie zrobi.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2015-06-09 15:10

Rejestracja: 6 lat temu

Ostatnio: 11 godzin temu

0

Wersja na kompletnego lenia:
Lista dwukierunkowa posiadająca gałęzie prev i next, traktowana kodem z internetu jak lista jednokierunkowa.

Pozostało 580 znaków

2015-06-09 15:11

Rejestracja: 4 lata temu

Ostatnio: 12 godzin temu

Lokalizacja: Hong Kong

2015-06-11 22:27

Rejestracja: 6 lat temu

Ostatnio: 8 miesięcy temu

0

Trochę stary temat ale pomyślałem sobie: "A napiszę sobie to!"

Do posortowania takiej listy jak napisał autor (z intem jako klucz) wcale nie jest potrzebny wskaźnik na poprzedni element.

#include <stdio.h>
#include <stdlib.h>

struct Liczba{
    int wartosc;
    struct Liczba *nastepny;
    struct Liczba *poprzedni;
    struct Liczba *ostatni;
};

void dodaj(struct Liczba **glowa, int wartosc){
    struct Liczba *element = (struct Liczba*)malloc(sizeof(struct Liczba));
    element->wartosc = wartosc;
    element->nastepny = element->poprzedni = element->ostatni = NULL;

    if((*glowa) == NULL){
        (*glowa) = element;
        (*glowa)->nastepny = (*glowa);
        (*glowa)->poprzedni = (*glowa);
        (*glowa)->ostatni = (*glowa);
    }
    else{
        (*glowa)->ostatni->nastepny = element;
        element->poprzedni = (*glowa)->ostatni;
        element->nastepny = (*glowa);
        (*glowa)->poprzedni = element;
        (*glowa)->ostatni = element;
    }
}

void wypisz(struct Liczba *glowa){
    struct Liczba *temp = glowa;
    while(temp != glowa->ostatni){
        printf("%d ", temp->wartosc);
        temp = temp->nastepny;
    }
    printf("%d ", temp->wartosc);
    printf("\n");
}

void sortuj(struct Liczba *glowa){
    struct Liczba *iter_1 = NULL;
    struct Liczba *iter_2 = NULL;
    int temp = 0;

    for(iter_1 = glowa; iter_1 != glowa->ostatni; iter_1 = iter_1->nastepny){
        for(iter_2 = glowa; iter_2 != glowa->ostatni; iter_2 = iter_2->nastepny){
            if(iter_1->wartosc > iter_2->wartosc){
                temp = iter_1->wartosc;
                iter_1->wartosc = iter_2->wartosc;
                iter_2->wartosc = temp;
            }
        }
    }
}

void zniszcz(struct Liczba **glowa){
    struct Liczba *temp = (*glowa);
    struct Liczba *doZniszczenia = NULL;
    while(temp != (*glowa)->ostatni){
        doZniszczenia = temp;
        temp = temp->nastepny;

        free(doZniszczenia);
        doZniszczenia = NULL;
    }
}

int main(void)
{
    struct Liczba *tab = NULL;
    dodaj(&tab, 10);
    dodaj(&tab, 2);
    dodaj(&tab, -3);
    dodaj(&tab, 41);
    dodaj(&tab, 98);
    dodaj(&tab, 3);
    dodaj(&tab, -11);
    printf("\nPrzed sortowaniem:\n");
    wypisz(tab);
    sortuj(tab);
    printf("\nPo posortowaniu:\n");
    wypisz(tab);
    zniszcz(&tab);
    return 0;
}

https://ideone.com/DB48Ks

edytowany 1x, ostatnio: grzesiek51114, 2015-06-11 22:29

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0