Single-Linked list sortowanie

Single-Linked list sortowanie
SQ
  • Rejestracja:ponad 8 lat
  • Ostatnio:ponad 8 lat
  • Postów:7
0

Witam
interesuje mnie funkcja w postaci void (); sortujaca. zamieniająca wyłącznie next'y.
W pewnym momencie źle sortuje najprawdopodobniej w głowie.
Nie mogę znaleźć tego momentu. Jakieś pomysły ?

Kopiuj
void sortLista()
{
    struct lista *pointer = head;
    struct lista *temp1,*temp2,*temp3;
    if (head == NULL)
    {
        printf("There is nothing to sort my friend go add some elements by using addLista...");
    }
    else
    {
        while (pointer->next->next!=NULL)
        {
            if (head->freq>head->next->freq)
            {
               temp3 = head->next->next;
               temp2 = head->next;
               temp1 = head;
               head = temp2;
               head->next = temp1;
               head->next->next = temp3;
            }
            if (pointer->next->freq>pointer->next->next->freq)
            {
                temp1=pointer->next;
                temp2=pointer->next->next;
                temp3=pointer->next->next->next;
                pointer->next=temp2;
                pointer->next->next=temp1;
                pointer->next->next->next=temp3;
                pointer = head;
            }
            else
            {
                pointer=pointer->next;
            }

        }
    }
}

Będę wdzięczny za pomoc.

carlosmay
  • Rejestracja:prawie 9 lat
  • Ostatnio:około 5 lat
  • Lokalizacja:Pabianice
2

debugger i do dzieła.


kq
Moderator C/C++
  • Rejestracja:prawie 12 lat
  • Ostatnio:4 minuty
  • Lokalizacja:Szczecin
4

Niezbyt rozumiem to podejście.

  1. Raz używasz head, raz pointer, które oryginalnie jest równe head.
  2. Przez listę przechodzisz raz, więc nie jest to sortowanie
  3. Dlaczego nie użyjesz std::forward_list?
  4. Funkcja globalna, head to też zmienna globalna. Co zrobisz jak będziesz chciał mieć dwie listy jednocześnie?
  5. temp1, temp2, temp3 - nicniemówiące nazwy zmiennych.

twonek
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 2 lata
  • Postów:2500
3

Po pierwsze program się wywali gdy lista ma 2 elementy, tj. gdy pointer->next jest nullem.
Po drugie w pierwszym ifie nie modyfikujesz elementu, który poprzedzał temp1, więc po tych zmianach jego next nadal będzie wskazywać na temp1 zamiast na temp2.
Po trzecie jaki sens ma ten drugi if? Przecieć po jednym obiegu pętli ten przypadek będzie obsługiwany przez pierwszy if.

SQ
  • Rejestracja:ponad 8 lat
  • Ostatnio:ponad 8 lat
  • Postów:7
0

Dziękuję za odpowiedź.

  1. ok. dam odpowiednie warunki. Wywala.
  2. Jakoś nie mogę tego zauważyć. Nadal nie wiem o co chodzi.
    Zastanowie się jeszcze .

coś srogo pomieszałem z tymi ifami. Przejrze jeszcze kilka razy.

Macie może jakiś inny lepszy pomysł z tym forwardingiem np. ?

edytowany 2x, ostatnio: Sqrl
twonek
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 2 lata
  • Postów:2500
1

Ok punkty 2 i 3 razem mają jakiś sens, choć nie tak się robi. Najprostszym rozwiązaniem, by móc obsłużyć przypadek z głową, jest dodanie jeszcze jednego węzła przed głową. Wtedy wszystko się sprowadza do 1 przypadku.
Natomiast problem z sortowaniem jest to, że tak jak wspomniał @kq, wcale nie sortujesz. Implementujesz bubble-sort, więc po jednokrotnym przejściu przez listę jedynie ostatni element będzie na dobrym miejscu.

SQ
  • Rejestracja:ponad 8 lat
  • Ostatnio:ponad 8 lat
  • Postów:7
0

trochę się poddałem :D
jaki jest najłatwiejszy(do napisania) sposób sortowania wymieniając tylko wskaźniki next ?
czy łatwiej byłoby usuwać aktualnie zaalokowane i dodawać nowe ?

SQ
ok dzieki za pomoc
grzesiek51114
grzesiek51114
  • Rejestracja:ponad 11 lat
  • Ostatnio:ponad 4 lata
  • Postów:2442
1

Po staremu to tak: http://4programmers.net/Forum/C_i_C++/264087-sortowanie_listy_jednokierunkowej_c?p=1211784#id1211784
Przykład wzięty z C ale przerobić to do C++ to nie problem.

Możesz zamieniać klucze (prościej) albo całe wskaźniki (trudniej). Jak wolisz.

edytowany 2x, ostatnio: grzesiek51114
SQ
dzięki grzesiek !!!! o to właśnie mi chodziło.

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.