Lista jednokierunkowa - sortowanie bąbelkowe

[wawek91]

Kod: Zaznacz cały

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

#define N 20

struct Lista
{
 struct Lista *next;
 int wartosc;       
};

typedef struct Lista Lista;

void wypisz(Lista *lista)
{
 Lista *wsk = lista;
 while(wsk)
 {
  printf("%d ", wsk->wartosc);
  wsk = wsk->next;    
 }
}

void dodaj(Lista *lista, int liczba)
{
 Lista *wsk, *nowy;
 wsk = lista;
 
 while(wsk->next)
       wsk = wsk->next;
       
 nowy = malloc(sizeof(Lista));
 nowy->wartosc = liczba;
 nowy->next = NULL;
 wsk->next = nowy;           
}

void sortuj(Lista *lista)
{
 Lista *wsk;
 wsk = lista;
 int pomoc;

 
 while(wsk)
 {
  if(wsk->wartosc > wsk->next->wartosc)
  {
   pomoc = wsk->wartosc;
   wsk->wartosc = wsk->next->wartosc;
   wsk->next->wartosc = pomoc;                
  } 
  wsk = wsk->next;          
 }     
}

main()
{
  Lista *pierwszy;
  int i;
  
  srand(time(NULL));
  
  pierwszy = malloc(sizeof(Lista));
  pierwszy->wartosc = rand()%10;
  pierwszy->next = NULL;
  
  for(i = 0; i < N; i++)
        dodaj(pierwszy, rand()%10);
  
  wypisz(pierwszy);
  sortuj(pierwszy);
  wypisz(pierwszy);
    
  printf("\n");
  system("PAUSE");	
  return 0;
}

Oto kod mojego programu. Problem pojawia sie przy sortowaniu listy. Wszystko wydaje mi sie ok choc jedyne co przychodzi mi do glowy to to ze do ktoregos wskaznika na koncu trzeba przypisac null'a. Prosiłbym o jakieś wskazowki co dodać do funkcji sortującej lub jak w najprostszy sposob posortowac liste (nie musi byc bąbelkowo, ale ten algorytm wydał mi sie najłatwiejszy). Z góry dziękuję.

[Afish]

To nie jest sortowanie bąbelkowe, brakuje jednej pętli. Zerknij na wikipedię w poszukiwaniu pseudokodu. Poza tym co zrobisz, gdy w tym kodzie

Kod: Zaznacz cały

if(wsk->wartosc > wsk->next->wartosc)

wsk->next będzie wskazywał na nulla?

[wawek91]

No wlaśnie wiem jak bąbelkowo sortować tablicę ale z listą mam problem bo nie mam jej poindeksowanej i nie wiem jak ta druga pętla ma wyglądać.

Poza tym co zrobisz, gdy w tym kodzie

Kod: Zaznacz cały

if(wsk->wartosc > wsk->next->wartosc)

wsk->next będzie wskazywał na nulla?

Wiem tutaj się później zorientowałem, ze za daleko wyjezdzam.

[Afish]

Algorytm można rozbudować tak, by czas optymistyczny był lepszy. Najłatwiejsze jest dodanie flagi informującej czy w danej iteracji doszło do zmiany. Flaga jest zerowana na wejściu w przebiegu pętli, w przypadku natrafienia na zmiane jest podnoszona. A po wykonaniu przejścia jest sprawdzana. Jeśli nie było zmian to sortowanie jest zakończone

[mcbob]

Hmm, jeśli nie musisz tego sortować bąbelkowo to proponuję sortowanie przez wybór (selection sort), na listach jednokierunkowych chyba najprostszy do zaklepania.

PS Radzę napisać sortowanie w którym zamieniasz wskaźniki, a nie wartości. Dla inta to się nie opłaca, ale gdyby kluczem w node były jakieś duże obiekty już tak.

[wawek91]

Wciąż nie mogę sobie z tym poradzić. Spróbowałem przez selection sort i moja funkcja wygląda tak:

Kod: Zaznacz cały

void sortuj(Lista *lista)
{
 Lista *i, *j, *min, *pom;
 
 for(i = lista; i->next != NULL; i = i->next)
 {
  min = i;
  for(j = i->next; j->next != NULL; j= j->next)
  {
   if(j->wartosc < min->wartosc) min = j;      
  } 
   pom = min;
   min = i;
   i = pom; 
 }
}

Wzorowałem się na kodzie z wikipedii tylko tak jak mówie tam jest sortowana tablica która ma indeksy i to bym potrafił natomiast wskaźników przecież nie mogę poindeksować więc mam z tym juz większy problem. Gdzie robie bład? Wydaje mi sie, że to moje swap'owanie to jakaś lipa jest.

[mcbob]

Kilka wskazówek:
Nie możesz tak zamieniać wskaźników bo lista ci się przerwie w tym miejscu. Załóżmy że mamy element b w liście, a jego poprzednikiem jest a. Aby usunąć element b z listy należy połączyć jego poprzednika z następnikiem a->next=b->next. Stąd prosty wniosek, że dla danego elementu w liście będziesz też potrzebował jego poprzednika. Gdy już usuniemy element minimalny z listy to wpinamy go do innej listy (nie ma sensu tego robić na jednej bo nic na tym nie zyskujemy, a komplikuje to lekko zapis). Na samym końcu musisz nowy head albo zwrócić returnem albo listę mieć przekazaną przez referencję bądź wskaźnik na wskaźnik do funkcji sort.