program Benny: #include <iostream> using namespace std; struct el_listy { int klucz; el_listy* nast; }; class lista { el_listy* glowa; public: lista(); void sortowanie(); void zamien(el_listy*, el_listy*); void zamien2(el_listy*, el_listy*); void wypisz(); void wstaw(el_listy*, int); el_listy* zwroc_glowe(); }; el_listy* lista::zwroc_glowe() { return glowa; } void lista::sortowanie() { el_listy *pomi, *pomj, *pomk; pomi=glowa; int min; while (pomi−>nast!=NULL) { min=pomi−>nast−>klucz; pomk=pomi; pomj=pomi−>nast; while(pomj−>nast!=NULL) { if (pomj−>nast−>klucz<min) { min=pomj−>nast−>klucz; pomk=pomj; } pomj=pomj−>nast; } zamien2(pomi, pomk); pomi=pomi−>nast; } } void lista::zamien(el_listy* pomi, el_listy* pomk) { int y; y=pomi−>nast−>klucz; pomi−>nast−>klucz=pomk−>nast−>klucz; pomk−>nast−>klucz=y; } void lista::zamien2(el_listy* poz1, el_listy* poz2) { if (poz1!=poz2) { if (poz2==poz1−>nast) { el_listy* pom3; pom3=poz2−>nast; poz1−>nast=pom3; poz2−>nast=pom3−>nast; pom3−>nast=poz2; } else { el_listy *pom3, *pom4; pom3=poz1−>nast; pom4=poz2−>nast−>nast; poz1−>nast=poz2−>nast; poz2−>nast−>nast=pom3−>nast; poz2−>nast=pom3; pom3−>nast=pom4; } } } void lista::wstaw(el_listy* poz, int x) { el_listy* pom; pom=new el_listy; if (pom!=NULL) { pom−>klucz=x; pom−>nast=poz−>nast; poz−>nast=pom; } } lista::lista() { glowa=new el_listy; if (glowa!=NULL) glowa−>nast=NULL; } void lista::wypisz() { el_listy* pom; pom=glowa−>nast; while(pom!=NULL) { cout << pom−>klucz << " "; pom=pom−>nast; } cout << endl; } main() { lista A; A.wstaw(A.zwroc_glowe(), 5); A.wstaw(A.zwroc_glowe(), 7); A.wstaw(A.zwroc_glowe(), 8); A.wstaw(A.zwroc_glowe(), 8); A.wstaw(A.zwroc_glowe(), 9); A.wstaw(A.zwroc_glowe(), 1); A.wstaw(A.zwroc_glowe(), 0); A.wypisz(); A.sortowanie(); A.wypisz(); } Mógłby ktoś prześledzić program i opisać jego działanie?

Mariusz: Co do sortowania to proponuję przez scalanie lub napisać procedurę wstawiającą tak aby dane były posortowane zależnie od tego jak często potrzebujemy sortować

Mariusz: // funkcje do obsługi stosu i kolejki Funkcja sprawdzają czy lista jest pusta Funkcja dodająca węzeł na początek listy Funkcja dodająca węzeł na koniec listy Funkcja zdejmująca pierwszy węzeł listy // funkcje dodające i usuwające węzły Funkcja dodająca węzeł za węzłem o danym kluczu Funkcja dodająca węzeł przed węzłem o danym kluczu Funkcja dodająca węzeł tak aby dane były posortowane według klucza Funkcja usuwająca węzeł o danym kluczu Funkcja usuwająca wszystkie węzły z listy // funkcje dodatkowe Funkcja zwracająca liczbę węzłów Funkcja wyszukująca węzeł o danym kluczu Funkcja sortująca listę przez scalanie Funkcja wypisująca dane zawarte w węzłach listy Musisz pisać obiektowo ? Jeśli tak użyj szablonów Jeśli nie typem danych powinien być void* Nie używasz referencji tam gdzie funkcja powinna zmodyfikować listę ?

Mariusz: Referencja czy drugi wskaźnik to do podejścia strukturalnego Twoje sortowanie wygląda tak w jednej pętli while przechodzisz listę W drugiej pętli szukasz minimum po znalezieniu minimum wychodzisz z najbardziej zagnieżdżonej pętli i zamieniasz element znaleziony element z iterowanym w zewnętrznej pętli Złożoność twojego algorytmu to O(n²) a można było uzyskać lepszy czas Niektórzy mogą się przyczepić do tego że strukturę węzła masz na zewnątrz klasy Poza tym brak funkcji usuń może powodować wycieki pamięci O twoim kodzie będzie mógł trochę napisać Dziadek o ile będzie mu się chciało czytać kod

Benny: To nie jest mój kod, dlatego pytałem o jego działanie.

Mariusz: Benny na razie dodałem szablony Złym nawykiem jest pisanie konstruktorów bez destruktorów i funkcji wstawiających bez funkcji usuwających // to nie Java że mamy odśmiecacza tzw garbage collectora Powyższym trzeba się teraz zająć Pomyśl nad funkcją wstawiającą węzeł w sposób aby dane były posortowane według klucza Na youtube jest do tego filmik , ciebie powinna zainteresować procedura InsertarOrdenado(var cabeza: PNodo;clave:integer); Po polsku jest taka strona gdzie koleś podaje łatwe do przepisania pseudokody w postaci listy kroków a nawet podaje przykładowe kody Niestety nie uzwględnia on obsługi błędów http://eduinf.waw.pl/inf/alg/001_search/0083.php Jeżeli chodzi o przyspieszenie sortowania to sortowanie rozbijasz na trzy funkcje 1. Funkcje rozdzielająca listę na dwie podlisty Dla parzystej liczby węzłów podlisty będą miały tyle samo elementów Dla nieparzystej liczby węzłów jedna podlista będzie miała o jeden element więcej 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ść NULL węzła znalezionego w punkcie 2., 5) zwrócić wskaźnik na węzeł zapamiętany w punkcie 1., jako wskaźnik na głowę pierwszej listy docelowej, 6) zwrócić wskaźnik na węzeł zapamiętany w punkcie 3., jako wskaźnik na głowę drugiej listy docelowej; Jak znaleźć węzeł z punktu 2 Ustawić dwa wskaźniki pomocnicze na głowę, jeden z nich iterować o jedno pole a drugi iterować o dwa pola Gdy ten wskaźnik iterowany o dwa pola osiągnie NULL ten iterowany o jedno pole osiągnie węzeł po którym listę należy rozdzielić Scalanie dwóch posortowanych list Tutaj są różne podejścia: rekurencyjne, iteracyjne z wartownikiem, iteracyjne bez wartownika 1. Sprawdzasz czy któraś z list jest pusta jeśli tak to zwracasz drugą listę 2. Jeśli obydwie listy nie są puste porównujesz wartości kluczy w węzłach będących głowami list i zachowujesz tę o mniejszym kluczu 3. Porównujesz w pętli pozostałe elementy list dopóki obydwie listy są niepuste 4. Gdy jedna z porównywanych list będzie pusta dopisujesz do wyniku elementy z tej drugiej listy Sortowanie Gdy lista ma więcej niż jeden element to (sprawdzasz to używając wskaźnika na głowę i jego następnika) Dzielisz listę na dwie podlisty Sortujesz rekurencyjnie obydwie podlisty Łączysz dwie posortowane podlisty

Mariusz: W konstruktorze nie inicjuje głowy na węzeł tylko allokuje pamięć na węzeł i jeżeli głowa wskazuje na jakiś węzeł przypisuje następnikowi wartość NULL Ogólnie trochę dziwna ta klasa i nie wiem czy jest sens przyspieszać to sortowanie Tylko napisać tę klasę od nowa a jeśli nie jesteś w tym dobry to może zacząć od podejścia strukturalnego jak w C #include <iostream> using namespace std; template <class T> struct el listy { T klucz; el listy<T>* nast; }; template <class T> class lista { el listy<T>* glowa; public: lista(); ~lista(); void sortowanie(); void zamien(el listy<T>*, el listy<T>*); void zamien2(el listy<T>*, el listy<T>*); void wypisz(); el_listy<T>*znajdz(T); // void odwroc(); void wstaw(el listy<T>*, T); void usun pierwszy(); void usun(el listy<T>*); el listy<T>* zwrocglowe(); }; template <class T> el listy<T>* lista<T>::zwrocglowe() { return glowa; } template <class T> void lista<T>::sortowanie() { el listy<T> *pomi, *pomj, *pomk; pomi=glowa; T min; if(glowa!=NULL&&glowa−>nast!=NULL) { while (pomi−>nast!=NULL) { min=pomi−>nast−>klucz; pomk=pomi; pomj=pomi−>nast; while(pomj−>nast!=NULL) { if (pomj−>nast−>klucz<min) { min=pomj−>nast−>klucz; pomk=pomj; } pomj=pomj−>nast; } zamien2(pomi, pomk); pomi=pomi−>nast; } } } template <class T> void lista<T>::zamien(el listy<T>* pomi, el_listy<T>* pomk) { T y; y=pomi−>nast−>klucz; pomi−>nast−>klucz=pomk−>nast−>klucz; pomk−>nast−>klucz=y; } template <class T> void lista<T>::zamien2(el listy<T>* poz1, el listy<T>* poz2) { if (poz1!=poz2) { if (poz2==poz1−>nast) { el listy<T>* pom3; pom3=poz2−>nast; poz1−>nast=pom3; poz2−>nast=pom3−>nast; pom3−>nast=poz2; } else { el listy<T> *pom3, *pom4; pom3=poz1−>nast; pom4=poz2−>nast−>nast; poz1−>nast=poz2−>nast; poz2−>nast−>nast=pom3−>nast; poz2−>nast=pom3; pom3−>nast=pom4; } } } template <class T> void lista<T>::wstaw(el listy<T>* poz, T x) { el listy<T>* pom; pom=new el listy<T>; if (pom!=NULL) { pom−>klucz=x; pom−>nast=poz−>nast; poz−>nast=pom; } } template <class T> lista<T>::lista() { glowa=new el listy<T>; if (glowa!=NULL) glowa−>nast=NULL; } template <class T> void lista<T>::wypisz() { el listy<T>* pom=NULL; if(glowa!=NULL) pom=glowa−>nast; while(pom!=NULL) { cout << pom−>klucz << " "; pom=pom−>nast; } cout << "NULL"<<endl; } template <class T> el listy<T>* lista<T>::znajdz(T wartosc) { el listy<T> *p; p=glowa; while((p!=NULL)&&(p−>klucz!=wartosc)) p=p−>nast; return p; } /*template <class T> void lista<T>:: odwroc() { el listy<T> *p=NULL; el listy<T> *pc=NULL; if(glowa!=NULL) { pc=glowa; while(pc−>nast!=NULL) { p=pc−>nast; pc−>nast=p−>nast; p−>nast=glowa; glowa=p; } } }*/ template <class T> void lista<T>::usun pierwszy() { el_listy<T> * p=glowa; if(p!=NULL) { glowa = p−>nast; // nowy początek delete p; // usuń element z pamięci } } template <class T> void lista<T>::usun(el listy<T> * e) { el listy<T> * p; if(glowa == e&&e!=NULL) { usun pierwszy(); } else if(e!=NULL) { p=glowa; while((p!=NULL)&&(p−>nast != e)) p = p−>nast; if(p!=NULL) { p−>nast = e−>nast; delete e; } } } template <class T> lista<T>::~lista() { while(glowa!=NULL) { usun pierwszy(); } } int main() { lista<int> A; A.wstaw(A.zwrocglowe(), 5); A.wstaw(A.zwrocglowe(), 7); A.wstaw(A.zwrocglowe(), 8); A.wstaw(A.zwrocglowe(), 8); A.wstaw(A.zwrocglowe(), 9); A.wstaw(A.zwrocglowe(), 1); A.wstaw(A.zwrocglowe(), 0); /* A.wstaw(A.zwrocglowe(),'z'); A.wstaw(A.zwrocglowe(),'s'); A.wstaw(A.zwrocglowe(),'u'); A.wstaw(A.zwrocglowe(),'i'); A.wstaw(A.zwrocglowe(),'r'); A.wstaw(A.zwrocglowe(),'a'); A.wstaw(A.zwrocglowe(),'M'); */ A.wypisz(); A.sortowanie(); A.wypisz(); //A.odwroc(); // A.wypisz(); //A.usun(A.znajdz(8)); //A.wypisz(); A.~lista(); cin.get(); return 0; }