Szuakm algorytmu na zwalnianie grupy wybranych elementów listy podczas
iteracji po liście. Są to podstawy Algorytmów i Struktur danych, problem
wydaje się łatwy, ale jest parę kruczków, które utrudniają zadanie.
Lista jest jednokierunkowa co właśnie robi problem(ik) trudniejszym.
Bieżaca niedziałająca wersja w pseudokodzie wygląda tak:

item = Tab[index];
prevItem = nil;
while item <> nil do
{
if item.marked then
{
if prevItem=nil then
Tab[index]=item.next
else
prevItem.next=item.next;
Free(item);
}
else prevItem=item;
item = item.next;// 1)
//2)
};

W miejscu 1) jest błąd po zwolnienieniu itema bo nie mamy dostępu do
item.next, choć niestety wyjątek nie wystęuje w tym miejscu ale dopiero
później.
W miejscu 2) można wstawić assert że prevItem napewno nie jest zaznaczony.
Mamy mnóstwo przypadków, chociażby:
- lista pusta
- w liscie jeden i to będący "marked"
- lista z samych oznaczonych do skasowania, długość 2 i więcej
- zaczyna się od niezaznaczonego, potem same zaznaczone
- lista z samych nieozanczaonych do skasowania, długość 2 i więcej
- i wiele różnych kombinacji, gdy oznaczony jest miedzy nieoznaczonymi sam
lub jest ich więcej, i tak samo gdy nieoznaczony jest między oznaczonymi lub
jest ich więcej.

do góry

Użytkownik "Ignacy" <n...@s...ignacy> napisał w wiadomości
news:jp4qt5$j30$1@inews.gazeta.pl...
> Bieżaca niedziałająca wersja w pseudokodzie wygląda tak:

Poprawiona :
item = Tab[index];
prevItem = nil;
while item != nil do
{
if item.marked then
{
nextItem=item.next;
if prevItem=nil then
Tab[index]=item.next
else
prevItem.next=item.next;
Free(item);
item:=nextItem;
}
else
{
prevItem=item;
item= item.next;
}
//2)
};

Rozwiązanie, t wprowadzenie nowej zmiennej nextItem oraz rozbicie item=
item.next
na item= item.next i item:=nextItem
Czy wszystko będzie dobrze działało?

do góry