Lista jednokierunkowa. Mikołaj: Lista jednokierunkowa. Wiem,że to forum matematyczne, ale na pewno są też tutaj informatycy i tych prosiłbym o pomoc. Nie do końca czuję wskaźniki i mam problem z zadaniami z list. Czy ktoś mógłby mnie nakierować jak zrobić takie zadanie? Ogólnie mam jakieś podstawy i przedstawię swój pomysł na rozwiązanie, jeśli tylko ktoś napisze, że jest w stanie pomóc Dana jest lista liniowa jednokierunkowa o adresie pierwszego elementu h zawierająca liczby całkowite o niepowtarzających się wartościach. Podaj algorytm usuwający element zawierający wartość x podaną przez użytkownika.

jakubs: http://edu.i-lo.tarnow.pl/inf/alg/001_search/0086.php#P9

Saris: no to zapewne masz dana jakas strukture z polami wartosci i przejscia dalej. no to zrob funkcje o 2 argumentach node *&h, int x − gdzie node to jest ta twoja struktura budujaca listę wejściową , h wskaźnik na 1 element. Przekazujemy przez referencje, bo chcesz coś usunąć i mieć nową listę poza funkcją. x to wartosc usuwana. Wczesniej zrob sobie funkcje usun gdzie podajesz po prostu x i wywulujesz w niej tą która usuwa wlasnie od tego x'a). No funkcja główna wygląda tak, że poruszasz się po tej liście i porównujesz wartość x z wartością wagonika, na który patrzysz, jak są równe to usuwasz. I teraz masz kilka opcji, bo żeby coś usunąć w liście jednokierunkowej musisz mieć wskazanie na wcześniejszy wagonik, żeby go móc przepiąć dalej. Mianowicie, stworzenie wartownika na początku, i iterowanie się po jakimś znaczniku p−>next, że element, na który patrzysz jest za elementem na który wskazuje znacznik p. (to jest tylko przykładowa nazwa) albo robisz 2 znaczniki jeden za drugim iterujesz się oboma naraz, ale tu musisz wyifować sytuację na początku, bo nie wiadomo czy ten wcześniejszy np nie wskazuje już na dobrą wartośc, także polecam raczej wartownika. Uwagi: nie przekroczyć listy przesuwając się po niej, jak usuwasz element pierwszy musisz przepiąć wskaźnik h albo stworzyć jakiś tymczasowy, który trzyma początek listy, w ogóle to na początku sprawdzić czy lista nie jest pusta. Trochę na szybko pisałem, więc może być chaotyczne.

Mikołaj: Dzięki jakubs za linka. Oczywiście korzystam z tej strony przy nauce Zadanie jest bardzo podobne, tylko nie wiem co w moim przypadku dać w pętli while, jak ją zapisać... Nie potrafię zapisać jak dojść do poprzednika elementu o wartości x.

Mikołaj: Dziękuję Saris. Postaram się zrozumieć, ale czuję, że najpierw będę musiał sięgnąć do lektury, bo kilka zwrotów było dla mnie nieznanych, np. lista z wartownikiem. Kolega przesłał mi takie rozwiązanie: p=h; if (h−>dane == x) { h = h−>nast; delete p; } else { w = h−>nast; while (w != NULL AND w−>dane != x) { w = w−>nast; p = p−>nast; } if ( w != NULL) { p−>nast = w−>nast; delete w; } }

Mikołaj: I szczerze powiedziawszy nie rozumiem tego rozwiązania. Saris, według Ciebie jest ono poprawne?

Dziadek Mróz: Mówisz o liście list<int>? Czy własnej zdefiniowanej?

Mikołaj: Nie rozumiem pytania Słabo znam się na listach...dla mnie jest to po prostu zwykła lista jednokierunkowa.

Dziadek Mróz: Informacji o tym jest pełno, co jakiś czas zaglądam na stronę: http://www.p-programowanie.pl/cpp/lista-jednokierunkowa-c/ Tu ładnie jest wszystko wyjaśnione.

Saris: dobrze. W sumie to jest dość klarowne, ja trochę pogmatwałem, bo myślałem, o usuwaniu niewiadomej liczby elementów. Działa to tak: tworzysz wskaźnik, który wskazuje tam gdzie h. Jeśli już pierwszy element to ten szukany przesuwasz wskaźnik h dalej i usuwasz p (który wskazuje tam gdzie wczesniej był h − tj. 1 element) i koniec. Jeśli to nie szukany element to tworzysz w i przypinasz go za h. Tak, więc teraz masz kolejno wskazania p i na następny element w. Jeśli w nie wskazuje na koniec listy i w nie jest szukanym elementem przesuwasz te wskaźniki, aż któryś warunek zacznie być false. po wyjściu z pętli sprawdzasz czy to nie koniec listy, jeśli nie to znaczy, że znalazłeś element do usunięcia (w na niego wskazuje) p przepinasz za w, a w usuwasz. koniec brakuje return; na końcu i inicjalizacji, chyba, że masz wyżej. i dopisz sobie na początku if(!h) return; (lub if(h==NULL) return; (sprawdzisz czy lista jest pusta i wyjdziesz od razu jeśli jest) bo w sumie jak rozumiem, masz tylko usunąć element bez zwracania? Także funkcją jest typu void tylko pamiętaj o referencji, bo tak to usuniesz tylko kopię elementu w funkcji, a poza nią lista będzie nie zmieniona.

Mikołaj: Dzięki Saris jeszcze raz. Bardzo mi pomogło Twoje wyjaśnienie. Jeszcze nie wszystko rozumiem tak jakbym chciał, ale z czasem może będzie lepiej

asdf: lecisz po liscie jesli aktualny−>next−>id == x, to aktualny−>next = aktualny−>next−>next i dalej bajeruejsz z przypadkami, polecam nie korzystac z gotowcow, jest troche z tym łamigówek przy innych strukturach i nie jest to takie proste Ale fajnie sie przy tym idzie rozwinąć i ogarnąć temat programowania.

Dziadek Mróz: A no, tylko pamiętać trza o zwalnianiu pamięci

Mikołaj: Intuicyjnie to złapałem (chyba) Teraz mam usunąć element przed elementem zawierającym wartość x. Gdyby ktoś sprawdził poprawność byłbym mega wdzięczny Zakładam, że lista ma co najmniej dwa elementy. p = h−>nast if ( p−>dane ==x) { h = h−>nast; delete p; } else { w=h; z=p−>nast; while ( z != NULL AND z−>nast != x) { z = z −> nast; p = p −> nast; w = w −> nast; } if (z != NULL) { w −>nast = p−>nast; delete p; } }

Trivial: Uruchamiasz w ogóle te programy, czy tak sobie piszesz?

asdf: najprosciej: while(p−>next−>next−>id != x) { p=p−>next; } d = p; k = p−>next; d−>next = k−>next; delete p−>next; przetestuj to, tak z glowy.

Mikołaj: Na razie tylko piszę sobie na kartce taki pseudokod... Dlaczego nie uruchamiam? Bo w poniedziałek muszę to zaliczyć, a jeszcze nigdy nie uruchamiałem listy i pewnie trochę czasu by mi to zajęło. W przyszłym tygodniu na spokojnie sobie zobaczę czy te programy działają w realu, teraz po prostu nie zdążę.

Trivial: Napisałem kiedyś program do sprawdzania wycieków pamięci w prostych programach. Można sprawdzić czy wszystko jest dobrze usuwane. Jeśli chcesz mogę podesłać.

Trivial: Przecież z uruchamianiem jest prościej. Sam sobie utrudniasz.

asdf: ogarnij listy, bez zrozumienia tego nie da się programować są gotowe "biblioteki", ale dobrze jest rozumieć czemu to tak działa, powodzenia.

Saris: nie rozpatrujesz sytuacji kiedy musisz usunąć 1 element, chyba, że p wskazuje na wartownika wtedy to jest ok + jak nie będzie elementu do usunięcia "wpadniesz" do NULLa .

Mikołaj: Dzięki asdf. Czyli wygląda na to, że to co napisałem ma jakiś sens, bo Twoje jest podobne. Trivial, pewnie masz rację, bo uruchamiam i widzę czy działa...tylko jak mówię − nie potrafię w tym momencie tego uruchomić. Jeśli możesz podesłać ten program, to nie pogardzę, przyda się na pewno w przyszłości

Saris: Sprawdzanie list jest o tyle problematyczne, że musisz napisać osobne funkcje do tworzenia listy no i w zależności od zadania posortowaną albo nie, jak tak to czy rosnącą czy malejące + funkcje do wypisywania. Plus jest taki, że jak sobie zrobisz algorytm, w którym uwzględniasz każdą opcję to będziesz miał na przyszłość + to jest dobre ćwiczenie.

Saris: albo korzystać z biblioteki, ale jak Trivial napisał, możesz korzystać z jej funkcji, ale wcale nie wiedzieć co one robią i jak działają . Ten komentarz byl do posta asdf.

Mikołaj: Saris, napisałeś " jak nie będzie elementu do usunięcia "wpadniesz" do NULLa", czyli co mam u siebie poprawić i w którym momencie?

asdf: im zna się więcej tym lepiej − można to sobie później dostosować do własnych potrzeb − a już nie raz jak pobierałem bibliotekę to musiałem sobie coś do niej dopisać − bo nigdy nie jest wszystko napisane na gotowe. Omijanie czegoś, bo coś jest trudne mija się z chęcią nauki programowania...

Dziadek Mróz: Lista: − obiekt obecny − wskaźnik na kolejną listę Gdy ostatni element na liście to wskaźnik na kolejną listę jest NULL.

Trivial: https://www.sendspace.com/file/d1m4b4 Kompilujemy tak (w zależności od architektury): http://pastebin.com/nQb0Lnxc g++ test.cpp libmemchkr−win32.a lub g++ test.cpp libmemchkr−win64.a

Trivial: A wynik dla programu testowego jest taki: Memory leaks! (1 detected). test.cpp:6: 0x6467d0 (1.23 kB): 58 01 64 00 00 00 00 00 b0 71 4c 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ...

Mikołaj: Dziękuję Trivial. Teraz mam chwilę, to popróbuję uruchomić te listy