Lista jednokierunkowa usuwanie elementu

pytanie zadane 15 stycznia 2017 w Algorytmy przez Mariusz M Obywatel (1,640 p.)

Przypuśćmy że chcemy napisać procedurę do usuwania węzłów na liście
przy danym wskaźniku na głowę i wskaźniku na usuwany element
Jak wyglądałby algorytm usuwania węzłów z uwzględnieniem możliwych błędów

komentarz 15 stycznia 2017 przez operator Stary wyjadacz (10,920 p.)

Było na forum przynajmniej kilka razy.

komentarz 15 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)

Tak to podaj gdzie.
Jakie były dane tej procedury
Czy były w niej obsłużone błędy ?

1 odpowiedź

odpowiedź 15 stycznia 2017 przez mbabane Szeryf (79,280 p.)

http://eduinf.waw.pl/inf/alg/001_search/0086.php#P9

komentarz 16 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)

Właśnie widziałem algorytmy tego kolesia
Byłyby całkiem niezłe gdyby uwzględniały też sytuacje błędne
np podanie wskaźnika nie pokazującego na węzeł listy
lub podanie wskaźnika nil

komentarz 16 stycznia 2017 przez mbabane Szeryf (79,280 p.)

to sobie to dodaj samemu,
przed wejsciem w szukanie sprawdz adres czy jest ten sam i czy nie jest nilem

komentarz 18 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)

Ciekawy jestem czy nie wystąpią jakieś inne błędy

Jakie twoim zdaniem mogą wystąpić błędy

komentarz 18 stycznia 2017 przez mbabane Szeryf (79,280 p.)

Jak dla mnie to te błędy ze złym wskaźnikiem są raczej niemożliwe (ale sprawdzenie tego jest szybkie wiec ok, no chyba ze do funkcji przekażemy wskaźnik np. na tablice, a nie na strukturę danych, ale to będzie błąd programisty i przy testach to wyjdzie, a przy normalnym użytkowaniu programu nie ma możliwości żeby do tego doszło), ponieważ kolejka i inne struktury służą przede wszystkim do przechowywania danych w postaci rekordów np. imię, nazwisko pracownika i przeszukując taka listę w celu znalezienia jakiegoś elementu nie podajemy adresu do pamięci tylko jakąś wartość, która albo jest albo jej nie ma w strukturze np. znajdź pracownika o danych Jan Kowalski - nie obchodzi nas to pod jakim adresem jest przechowywany Jan Kowalski tylko czy tam jest.

komentarz 23 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)

Załóżmy że chcemy posortować linie w pliku który może nie zmieścić się w pamięci
Listę można by wykorzystać do wstępnego posortowania fragmentów pliku które zmieszczą
się w pamięci a następnie trzeba by dokończyć sortowanie przez scalanie
Jakie procedury obsługujące listę według ciebie wystarczyłyby do tego

komentarz 23 stycznia 2017 przez mbabane Szeryf (79,280 p.)
edycja 23 stycznia 2017 przez mbabane

Dokładnie to nie wiem jakby to można zrealizować.

Jeśli chodzi o sama listę to chyba nic nowego się tutaj nie wymyśli i trzeba wykorzystać standardowe procedury czyli dodająca (najlepiej od razu z sortowaniem), usuwającą (z tym że chyba to by trzeba od razu z zapisem do pliku, żeby zrobić miejsce na kolejna porcje danych).

komentarz 23 stycznia 2017 przez Mariusz M Obywatel (1,640 p.)

Sortowanie linii miało przyśpieszyć wyszukiwanie linii wg zadanego kryterium
więc wstawianie z sortowaniem może być jednak zbyt wolne
Jak to jest z pamięciową złożonością sortowania listy przez scalanie

Sortując listę wystarczy przestawiać wskaźniki więc na pierwszy rzut oka wydawałoby się
że zapotrzebowanie na pamięć jest stałe jednak mamy rekurencję która może zabierać pamięć

komentarz 23 stycznia 2017 przez mbabane Szeryf (79,280 p.)

Sortowanie listy (juz istniejacej) jest bardzo niewygodne (nie jest to takie proste jak z tablica ze robie sobie podmianke), dlatego czesto robi sie wstawinie od razu z sortowaniem, zeby uniknac tych wszytkich gimnastyk z przestawianiem nextow.