C++ - sortowanie listy jednokierunkowej cyklicznej

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

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ć?

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!

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