[Algorytmy] Wstawianie i usuwanie węzłów na liście

[Mariusz M]

Niedawno znalazłem opis algorytmu wstawiania i usuwania węzłów na liście uporządkowanej

Kod: Zaznacz cały

List-Insert(L,x)
	if head[L]=NIL then
		head[L]:=x; next[x]:=NIL;
	else 
		y:=head[L];z:=NIL;
		while(y!=NIL)and(key[x]>key[y]) do 
			z:=y;
			y:=next[y];
		end while
		next[x]:=y;
		next[z]:=x;
	end if

List-Del(L,x)
	if head[L]!=NIL then
		if head[L]=x then 
			head[L]:=next[x];
		else 
			y:=head[L];
			while(next[y]!=x) do 
				y:=next[y];
			end while
			next[y]:=next[x];
		end if
	end if

Okazało się jednak że jest in błędny

Gdzie są błędy i jak je poprawić ?

[qwertghjio]

Operacja usuwania jest cała źle napisana. Można na wiele sposobów usuwać element z listy, rozumiem że ty chcesz usunąć z listy jeden raz element o kluczu x tak? Cały algorytm radziłbym usunąć i napisać od nowa, bo nie wiem nawet od czego zacząć, dosłownie wszystko jest źle.
A co do operacji insert, to nie powinno być L.head.next , zamiast x.next ?

[Mariusz M]

Taki opis algorytmu znalazłem w pdf z wykładu
Osoba która prowadziła wykład nazywa się
Bożena Woźna-Szcześniak
Ja z nią nie miałem wykładów ale pdf nadal krąży po sieci
Przypuśćmy że w procedurze usuwającej mamy dany wskaźnik na głowę i wskaźnik na usuwany element
Jak wyglądałby wtedy taki algorytm oczywiście z uwzględnieniem błędów jakie mogą się pojawić

[qwertghjio]

Dodam, że zapis L.head jest równoważny zapisowi head[L] z tego co wiem, aczkolwiek dobrze by było gdybyś się upewnił.
Algorytm, który szuka elementu o kluczu x i usuwa go z listy(jeżeli jest kilka to usunie tylko ten pierwszy na liście):

Kod: Zaznacz cały

Remove(L,x)
p:=L.head
if(p.key=x) then
{
L.head:=p.next
return L
}
else
{
while p!= NIL do 
{
z:=p
p:=p.next
if(p.key==x) then 
{
z:=p.next.next
return L
}
}
return Nie znaleziono x
}

Opis działania algorytmu:
Funkcja dostaje od nas listę L oraz wartość klucza do usunięcia oznaczamy ją przez x.
Przypisujemy do zmiennej p głowę naszego programu.
Sprawdzamy, czy nasza głowa jest szukaną, jeżeli tak to: głową naszej listy zostanie kolejny element na liście, czyli drugi, jeżeli drugiego elementu nie ma, to traktujemy to jako NIL, a więc zostanie przypisana do głowy wartość NIL. return L - kończy program i zwraca listę.
Jeżeli jednak głowa nie jest naszą szukaną to:
w pętli while wykonujemy czynności:
sprawdź czy p nie jest NIL, jak jest to kończ program i wypisz komunikat, że nie ma elementu o kluczu x. W przeciwnym wypadku, jak nie jest NIL to:
Do z przypisz p, p przypisz p.next , czyli element następny (jeżeli p.next jest NIL to nic złego się nie wydarzy, bo program porówna NIL z x i nie wejdźie to if'a , a przy następnym obiegu przerwie się pętla while). Jeżeli program napotka element o kluczu równym x, wtedy wchodzi do if'a i do zmiennej z(czyli do elementu poprzedniego względem elementu szukanego) przypisuje element następny, który jest po elemencie , który usuwamy.(Tutaj analogicznie jak poprzednio jak jest NIL to nic się złego nie stanie).

[Mariusz M]

Kod: Zaznacz cały

procedure deleteNode(var L:PNode;x:PNode);
var p:PNode;
begin
p:=L;
if(L=x) then 
begin
L:=L^.next;
dispose(p);
end
else
begin
while((p<>nil)and(p^.next<>x)) do 
p:=p^.next;
if(p<>nil) then
begin
p^.next:=x^.next;
dispose(x);
end;
end;
end;

Co może być nie tak z tym kodem
W razie problemów ze sprawdzaniem warunków w pętli można dać dyrektywę {$B+/-}
chociaż we Free Pascalu chyba zrezygnowano z dyrektyw
Do takiego rozwiązania przydatna będzie funkcja wyszukująca
ale napisanie jej nie powinno sprawić problemów

[qwertghjio]

Mógłbyś powiedzieć co konkretnie jest nie tak? Kompilator wywala ci jakiś błąd, czy po prostu procedura robi coś czego nie powinna.

[Mariusz M]

Dobra te błędy co zauważyłem to poprawiłem
Teraz ciekawi mnie jak zapisać algorytm sortowania linii w pliku w takim języku jak Pascal czy C
(na kod w języku C nałożone są pewne ograniczenia)