Sortowanie listy za pomocą wskaźników.

Odpowiedz Nowy wątek
2015-01-23 19:54
0

Witam wszystkich forumowiczów.
Mam problem z sortowaniem listy, w którym muszę zamienić wskaźniki elementów.
Mam oto taką strukturę:

typedef struct lista {
       int liczba;
       struct lista *next;      
} element;

Stworzyłem do tego funkcję sortującą, która zamienia wartości zmiennej 'liczba' i wszystko działa poprawnie.

void sortowanie2(element *adres) {
    element *tmp,*tmp2;
    tmp=adres;
    int p=1; // zmienna, ktora pilnuje czy byla zamiana w liscie
    while(p!=0) {
        p=0; // wyzerowanie zmiennej pomocniczej
        while(tmp->next!=NULL) {
            if(tmp->liczba > tmp->next->liczba){
                p=1; // ustawienie zmiennej na 1, znaczy ze zamiana nastapila
                tmp2=tmp->liczba;
                tmp->liczba=tmp->next->liczba;
                tmp->next->liczba=tmp2; 
            }
            tmp=tmp->next;  
        }
        tmp=adres;
    }
}

Jednak struktura może mieć wiele danych i łatwiej po prostu zamienić elementy listy 'miejscami', tzn. zamienić im wskaźniki, jednak, gdy spróbowałem cały czas wywala mi program.

void sortowanie2(element *adres) {
    element *teraz,*prev,*tmp2;
    teraz=adres;
    prev=NULL;
    int p=1;
    while(p!=0) {
        p=0;
        while(teraz->next!=NULL) {
            if(teraz->liczba > teraz->next->liczba){
                p=1;
                if(prev!=NULL) prev=teraz->next;
                tmp2=teraz;
                teraz->next=teraz->next->next;
                teraz->next->next=tmp2; 
            }
            prev=teraz;
            teraz=prev->next;  
        }
        teraz=adres;
    }
}

Próbowałem robić na różne sposoby i już nie mam pomysłu co może być nie tak. Proszę o pomoc.

edytowany 2x, ostatnio: dami, 2015-01-24 02:58

Pozostało 580 znaków

2015-01-24 02:51
1

Jak dla mnie to prev od początku do końca jest NULLem.

Pozostało 580 znaków

2015-01-24 02:57
0

Tak, mój błąd. Zły kod wkleiłem. Problem występuje pomimo tego :/

Pozostało 580 znaków

2015-01-24 03:05

Wszystko Ci się pomieszało. Np.

// jest powiedzmy  1 -> 2 -> 3 - 4
teraz->next=teraz->next->next;
// no to jest 1 -> 3, 2 - > 3
teraz->next->next=tmp2;
// 4 -> 1, 2 -> 3

Rozrysuj sobie na kartce i przy każdej operacji gumką ścieraj stare połączenie i narysuj nowe.

Pozostało 580 znaków

2015-01-24 03:36
0

Tak, masz rację, tutaj przekombinowałem. Użyję swojego pierwotnego kodu:

//przy twoim założeniu 1 -> 2 -> 3 -> 4   i teraz = 1
tmp2=teraz->next->next; //tmp2 = 3
teraz->next->next=teraz; // 2 -> 1
teraz->next=tmp2; // 1 -> 3
//wynik: 1 -> 3 -> 4

Wypadł nam z listy element "2", dlatego stworzyłem wskaźnik "prev".
Jednak po poprawce dalej wywala programik:

void sortowanie2(element *adres) {
    element *teraz,*prev,*tmp2;
    teraz=adres;
    prev=NULL;
    int p=1;
    while(p!=0) {
        p=0;
        while(teraz->next!=NULL) {
            if(teraz->liczba > teraz->next->liczba){
                p=1;
                    if(prev!=NULL) prev->next=teraz->next; // jezeli istnieje poprzedni element nakierowywuje go na element kolejny po aktualnym
                    if(teraz==adres) adres=teraz->next; // jezeli zamieniamy pierwszy element listy ustawiam kolejny element jako poczatek
                tmp2=teraz->next->next;
                teraz->next->next=teraz;
                teraz->next=tmp2;
            }
            prev=teraz;
            teraz=teraz->next;  
        }
        teraz=adres;
    } 
    poczatek=adres; //zmienilismy kolejnosc elementow, zmieniamy poczatek listy
}

Pozostało 580 znaków

2015-01-24 04:09
1

Wywala się, bo sięgasz za daleko.

//1 -> 2 -> null, teraz == 1
while (teraz->next != NULL) // 2 != NULL, przechodzimy przez całą pętlę
{
    // w następnym obiegu teraz == 2
    ...
    teraz->next->next   // co to jest null->next?
}

Zresztą nie wiem po co, skoro do zamiany są potrzebne tylko 3 elementy, prev, teraz i teraz->next.

No i przydatny trik, żeby nie bawić się w przypadki brzegowe:

element atrapa;
atrapa->next = adres;   // głupia nazwa parametru BTW
element* prev = &atrapa;

Pozostało 580 znaków

2015-01-26 17:40
0

Już poprawiłem kod i działa.
Przy Twoim założeniu "1 -> 2 -> null" pętla działała dobrze, bo skoro "teraz->next->next null->next" to "teraz->next = null", a więc nie wejdzie do pętli, bo jest warunek "while (teraz->next != NULL) // czyli while(NULL!=NULL) -> wychodzi z pętli".
Napisałem sobie zestaw 5 liczb odpowiednio: 312,123,987,654,789. Liczby są w różnej kolejności i program odpowiednio sortuje. Uważam, że działa on prawidłowo :) . Sprawdziłem na różnych ilościach liczb i różnych kolejnościach, wpisywane losowo i wszystko działa jak należy :D.

void sortowanie(kierowca *adres) {
    printf("\n\n\tSortowanie danych:\n");
    kierowca *teraz,*dalej,*prev,*tmp,*start;
    teraz=adres;
    start=adres;
    dalej=teraz->next;
    prev=NULL;
    int p=1;
    while(p){
        p=0;
        while(dalej!=NULL) {
            if(strcmp(teraz->imie, dalej->imie)>0) {
                if(prev!=NULL) prev->next=dalej;
                if(start==teraz) start=dalej;
                tmp=dalej->next;
                dalej->next=teraz;
                teraz->next=tmp;
                prev=dalej;
                dalej=teraz->next;
                p++;
            }else{
                prev=teraz;
                teraz=dalej;
                dalej=teraz->next;
            }
        }
        teraz=start;
        dalej=teraz->next;
        prev=NULL;
    }
    poczatek=start;
}

Dzięki wielkie za pomoc. Gdyby nie Twoje wskazówki męczyłbym się z tym o wiele dłużej.

edytowany 1x, ostatnio: dami, 2015-01-26 19:26

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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