C++ - sortowanie listy jednokierunkowej cyklicznej

Odpowiedz Nowy wątek
2016-11-27 21:25

Rejestracja: 3 lata temu

Ostatnio: 3 lata temu

0

Cześć,

Mam problem z posortowaniem listy jednokierunkowej cyklicznej. Z acykliczną nie miałem problemu. Ważne jest to, że sortowanie ma dotyczyć adresów, a nie samych wartości.

Doszedłem to tego, że potrzebuje znać 4 adresy występujące po sobie i dwa środkowe zamieniać z uwzględnieniem zamiany 3 pierwszych adresów na to co będą wskazywać.

Przykładowa lista: A ( 10 ) -> B ( 20 ) -> C ( 11 ) -> D ( 30 ).
Zamiana: A ( 10 ) -> C ( 11 ) -> B ( 20 ) -> D ( 30 ).

Po zamianie lub nie ( jeśli B nie jest większe od C ) to wówczas A = B, B=C, C=D, D=E.

Taka zamiana zadziała dla minimum 4 wartości.

Szukałem rozwiązań, próbowałem sam. Straciłem sporo czasu i nie jestem wstanie tego rozwiązać znając jakby możliwe rozwiązanie. Będę wdzięczny za pomoc.

Aktualna sortowanie samych wartości:

    for (int i = 0; i < count; i++)
    {
        for (int j = 0; j < count - 1; j++)
        {
            current = current->next;
            do
            {
                previous = current;
                current = current->next;
                if (previous->data.Value > current->data.Value)
                {
                    swap(current->data.Value, previous->data.Value);
                    sorted = 1;
                }
            } while (current != end);
        }

        if (sorted == 1)
        {
            return;
        }
    }

Pozostało 580 znaków

2016-11-28 17:17

Rejestracja: 14 lat temu

Ostatnio: 3 lata temu

Przy (sensownym), założeniu, że taka cykliczna lista musi miec jakiś początek, gdzie nie zwracamy uwagę na porządek elementów (tzn. 1, 2, 3 oraz 2, 3, 1 to te same cykliczne listy, ale jeśli będziemy patrzeć na to, że "początkiem" jest pierwszy element w obu wypadkach, to pierwsza jest posortowana, a druga nie).

Twierdzisz, że nie masz problemów z listą acykliczną, to nie możesz po prostu "zerwać" cyklu, posortować listy, a potem ten cykl przywrócić?

Pozostało 580 znaków

2016-11-28 19:57

Rejestracja: 3 lata temu

Ostatnio: 3 lata temu

0
Kele napisał(a):

Przy (sensownym), założeniu, że taka cykliczna lista musi miec jakiś początek, gdzie nie zwracamy uwagę na porządek elementów (tzn. 1, 2, 3 oraz 2, 3, 1 to te same cykliczne listy, ale jeśli będziemy patrzeć na to, że "początkiem" jest pierwszy element w obu wypadkach, to pierwsza jest posortowana, a druga nie).

Twierdzisz, że nie masz problemów z listą acykliczną, to nie możesz po prostu "zerwać" cyklu, posortować listy, a potem ten cykl przywrócić?

Aż wstyd, rozwiązanie pod nosem. Dzięki Ci wielkie za podpowiedź. Przekształciłem to na odpowiedni kod i jest oczekiwany efekt!

Pozostało 580 znaków

Odpowiedz

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