Sortowanie listy przez łączenie naturalne z użyciem klas Mariusz: https://pastebin.com/Dz9B8KMa Próbowałem dopisać sortowanie listy dwukierunkowej przez łączenie naturalne do klasy ale chyba gdzieś popełniłem błąd

Pytający: Zastanów się, co robią destruktory zmiennych lokalnych po zakończeniu funkcji DoublyLinkedList<T>::MergeSort.

Mariusz: Tak ale co z tym zrobić próbowałem dopisać listę do argumentów funkcji i przekazać przez referencję Próbowałem też zwrócić listę i nic to nie dało

Mariusz: Rzeczywiście musi być coś z destruktorami bo jak przeniosłem zmienne lokalne do argumentów funkcji to już zaczęło działać chociaż to niezbyt eleganckie rozwiązanie

Pytający: W linii 459 masz sytuację: L1.first == A // niech A oznacza głowę posortowanej listy L1.last == B // niech B oznacza głowę posortowanej listy L2.first == nullptr L2.last == nullptr this−>first == nullptr this−>last === nullptr Po linii 461 (przed wyjściem z funkcji) masz sytuację: L1.first == A L1.last == B L2.first == nullptr L2.last == nullptr this−>first == A this−>last == B Po zakończeniu funkcji kończy się zakres zmiennych L1, L2, więc są wywoływane ich destruktory, a te wyglądają przecież tak: while(!isEmpty()) // isEmpty sprawdza, czy głowa jest nullem { deleteFirst(); } Czyli destruktor L2 nie zrobi w zasadzie nic, ale destruktor L1 usunie wszystkie węzły z listy. Są to oczywiście te same węzły, na które wskazują wskaźniki z aktualnego obiektu (wskazywanego przez this). Czyli po linii 462 masz sytuację: this−>first == invalid pointer value this−>last == invalid pointer value // to co było wskazywane przez te wskaźniki zostało zwolnione przez odpowiednie wywołania delete, więc odwoływanie się do wskazań tych wskaźników jest niezdefiniowane // https://stackoverflow.com/a/44182938 // L1, L2 już nie są zdefiniowane Wystarczy jedna linijka na koniec funkcji i będzie hulać (destruktor L1 nie usunie żadnego węzła): L1.setFirst(nullptr); // ogon w teorii też wypadałoby wyzerować, ale nie jest to niezbędne przy takiej implementacji Jako tako elegancko byłoby pewnie przeciążyć kopiujący operator przypisania listy (i tam podmienić wskaźniki) i wywołać go po posortowaniu: *this = std::move(L); ale to chyba za dużo...

Mariusz: https://eduinf.waw.pl/inf/alg/001_search/0097.php Co dzieje się w tym kodzie ? Tutaj koleś nie ustawia zmiennym lokalnym wartości NULL choć destruktor wygląda podobnie a mimo to jego kod działa

Pytający: "jest jeszcze taka dość ważna umiejętność jak czytanie kodu" "Koleś" zawsze wywołuje merge po split, Ty zawsze wywołujesz Merge o 1 raz mniej niż Split (i po ostatnim wywołaniu Split masz listę w L1, nie w *this). Poza tym u niego merge_sort jest wywoływany rekurencyjnie, więc masz wiele różnych (*this), ale na koniec każdego wywołania merge_sort listy h1, h2 są u niego puste, a "cała" lista (aktualnie przetwarzana w kroku rekurencyjnym) jest w *this.

Mariusz: Może udałoby się wyrugować funkcje headdel, tailins lub w nazewnictwie jakie zaproponowałeś ListInsertNodeTail ,ListDetachHead mając funkcje takie jak SplitAfter, SplitBefore , Concat SplitAfter − rozdziela listę za wybranym węzłem SplitBefore − rozdziela listę przed wybranym węzłem Concat − proste łączenie list tzw konkatenacja Jeden zaproponował taki spis kroków dla funkcji SplitAfter 1 zapamiętać wskaźnik na głowę listy wejściowej, 2 znaleźć węzeł, który będzie ostatnim węzłem pierwszej listy docelowej, 3 zapamiętać wskaźnik na Next węzła znalezionego w punkcie 2., 4 wpisać do Next wartość nil węzła znalezionego w punkcie 2., 5 wpisać do Prev wartość nil węzła zapamętanego w punkcie 3., 6 zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej, 7 zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej; Jednak tak jak podejrzewałem nie uwzględnia on przypadków brzegowych https://ideone.com/ed5S4j Ja tutaj próbowałem zapisać funkcję na podstawie tej listy kroków Nie wiem czy uwzględniłem wszystkie przypadki brzegowe Dlaczego po usunięciu list L1 oraz L2 wskaźniki głowy i ogona listy L nie pokazują na null Czy ustawienie głowy i ogona listy L na null nie spowoduje wycieków pamięci

Pytający: "Dlaczego po usunięciu list L1 oraz L2 wskaźniki głowy i ogona listy L nie pokazują na null " A dlaczego miałyby pokazywać? Przecież nigdzie nie modyfikujesz tych wskaźników. Masz sytuację podobną do tej wyżej opisanej − to na co wskazują odpowiednio głowa i ogon listy L usunąłeś poprzez wywołania delete.

Mariusz: Lista zawiera już między innymi sortowanie i operacje na stosie Jak zrealizować na niej następujący pseudokod otoczki https://imgur.com/a/Q4eYWns Ten pseudokod jest w książce CLRS Introduction to Algorithms http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_11 A tutaj mniej więcej ten sam pseudokod po polsku

Mariusz: Gdybyśmy scalali do dwóch list zamiast do jednej to funkcję rozdzielającą można by było wywołać tylko raz Ten pomysł widziałem w książce Diksa i Ryttera 2.10.1 Scalanie wielofazowe z 4 plikami Załóżmy że bloki zostały rozłożone na pliki P₀ i P₁ Pliki P₂ i P₃ są początkowo puste i₁ = 0; i₂ = 1; // numery plików wejściowych , tzn otwartych do czytania j₁ = 2; j₂ = 3; // numery plików wyjściowych , tzn otwartych do pisania while jest wiecej niz jeden blok do (a) scal pierwszy blok na P_i1 z pierwszym blokiem na P_i2 i powstający blok zapisz na P_j1 (b) scal następny blok na P_i1 z następnym blokiem na P_i2 i powstający blok zapisz na P_j2 (c) powtarzaj kroki (a) i (b) (kładąc powstające bloki na przemian na pliki P_j1 i P_j2) aż zostanie osiągnięty koniec plików P_i1 i P_i2 (d) przewiń wszystkie pliki do początku; dodaj liczbę 2 mod 4 do i₁,i₂,j₁,j₂ odwracając w ten sposób rolę plików wejściowych