Sortowanie listy za pomocą wskaźników.

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.

1

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

0

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

1

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.

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

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