To są zadania na listy.
Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__
W poniższych zadaniach będziemy używać następujących typów:
type lista = ^el_listy;
el_listy = record
w: integer;
nast: lista;
end;
Zadanie 1 (Odwracanie listy)
Napisz procedurę Odwróć(var l:lista) odwracającą listę l.
Rozwiązanie 1
procedure Odwróć(var l:lista);
//Odwracamy listę l
var poprz, akt, pom : lista;
begin
if l <> nil then begin
poprz:=nil;
akt:=l;
while akt<>nil do begin
pom:=akt^.nast;
akt^.nast:=poprz;
poprz:=akt;
akt:=pom;
end;
end;
l:=poprz;
end;
Koszt czasowy: liniowy względem długości listy
Koszt pamięciowy: stały
Wizualizacja
Zadanie 2 (Scalanie dwóch posortowanych list)
Napisz funkcję Scal(l1,l2:lista):lista scalającą dwie posortowane niemalejąco listy l1 i l2, tak aby wynikowa lista również była posortowana niemalejąco.
Rozwiązanie
function Scal(l1,l2:lista): lista;
//Listy l1 i l2 są posortowane niemalejąco; scalamy je do jednej listy również posortowanej niemalejąco
var atrapa, akt : lista;
begin
new(atrapa);
atrapa^.nast:=nil;
akt:=atrapa;
while (l1 <> nil) and (l2 <> nil) do
if l1^.w < l2^.w then begin //jeśli l1^.w < l2^.w
akt^.nast:=l1;
akt:=akt^.nast;
l1:=l1^.nast;
end
else
if l1^.w > l2^.w then begin //jeśli l1^.w > l2^.w
akt^.nast:=l2;
akt:=akt^.nast;
l2:=l2^.nast;
end
else begin //jeśli l1^.w = l2^.w - ten else można sobie darować, i tak będzie dobrze
akt^.nast:=l1;
akt:=akt^.nast;
l1:=l1^.nast;
akt^.nast:=l2;
akt:=akt^.nast;
l2:=l2^.nast;
end;
if l1 = nil then //obsługa końcówki listy która nie jest pusta
akt^.nast:=l2
else
akt^.nast:=l1;
Scal:=atrapa^.nast;
dispose(atrapa);
end;
Koszt czasowy: liniowy względem sumy długości list
Koszt pamięciowy: stały
Wizualizacja
Ćwiczenie
Czy instrukcja atrapa^.nast:=nil jest potrzebna? W jakich przypadkach ?
Zadanie 3 (Usuwanie elementów zadanych listą)
Napisz procedurę Usuń(var l1:lista; l2:lista) która usunie z listy l1 wszystkie elementy z listy l2. Zakładamy, że listy l1 i l2 są posortowane niemalejąco.
Rozwiązanie
procedure Usuń(var l1:lista; l2:lista);
//Usuwamy z listy l1 wszystkie elementy z listy l2; zakładamy, że listy l1 i l2 są posortowane niemalejąco
var atrapa, poprz: lista;
begin
new(atrapa);
atrapa^.nast:=l1;
poprz:=atrapa;
while (l1 <> nil) and (l2 <> nil) do
if l1^.w < l2^.w then begin //jeśli l1^.w < l2^.w
l1:=l1^.nast;
poprz:=poprz^.nast;
end
else
if l1^.w > l2^.w then //jeśli l1^.w > l2^.w
l2:=l2^.nast
else begin //jeśli l1^.w = l2^.w
poprz^.nast:=l1^.nast;
dispose(l1);
l1:=poprz^.nast;
end;
l1:=atrapa^.nast;
dispose(atrapa);
end;
Koszt czasowy: liniowy względem sumy długości list
Koszt pamięciowy: stały
Wizualizacja
Ćwiczenie
Czy lista l1 musi być przekazywana przez zmienną ? W jakich przypadkach jest to konieczne ?
Zadanie 4 (Uporządkowanie elementów w liście)
Napisz procedurę Uporządkuj(var l:lista) która przestawi elementy w liście l tak by najpierw były elementy w których pole w jest ujemne, potem równe zero, a na końcu dodatnie. Dodatkowo względna kolejność elementów jednego rodzaju (dodatnich, równych zero i ujemnych) powinna być zachowana.
Rozwiązanie
procedure Uporządkuj(var l:lista);
//Ustawiamy elementy listy l tak by najpierw były elementy ujemne, potem równe zero, a na końcu dodatnie
//Osobno zbieramy elementy ujemne, dodatnie i równe zero i potem je łączymy
var atrapau, atrapaz, atrapad, u, z, d : lista;
begin
new(atrapau); u:=atrapau;
new(atrapaz); z:=atrapaz;
new(atrapad); d:=atrapad;
while l <> nil do begin
if l^.w < 0 then begin //dołączamy l do listy u
u^.nast:=l;
u:=u^.nast;
end
else
if l^.w = 0 then begin //dołączamy l do listy z
z^.nast:=l;
z:=z^.nast;
end
else begin //dołączamy l do listy d
d^.nast:=l;
d:=d^.nast;
end;
l:=l^.nast;
end; //while
d^.nast:=nil;
z^.nast:=atrapad^.nast;
u^.nast:=atrapaz^.nast;
l:=atrapau^.nast;
dispose(atrapad);
dispose(atrapaz);
dispose(atrapau);
end;
Koszt czasowy: liniowy względem długości listy
Koszt pamięciowy: stały
Wizualizacja
Zadanie 5 (Problem Józefa Flawiusza)
Napisz procedurę Flawiusz(var l:lista; k:integer), która dla danego
k > 0 i niepustej cyklicznej listy l, cyklicznie usuwa co k-ty element listy l, aż pozostanie w niej tylko jeden element. Liczenie rozpoczynamy od elementu wskazywanego przez l.
Rozwiązanie
procedure Flawiusz(var l:lista; k:integer);
//Usuwamy z listy l cyklicznie co k-ty element dopóki nie zostanie jeden element; k>0, l niepusta cykliczna
var poprz, pom: lista;
begin
poprz:=l^.nast;
while poprz^.nast <> l do poprz:=poprz^.nast; //poprz wskazuje na element poprzedzający l
while poprz <> poprz^.nast do begin //dopóki lista ma więcej niz jeden element
for i:=1 to k-1 do poprz:=poprz^.nast;
pom:=poprz^.nast;
poprz^.nast:=pom^.nast;
dispose(pom);
end;
l:=poprz;
end;
Koszt czasowy: rzędu n*k, gdzie n to długość listy
Koszt pamięciowy: stały
Zadanie 6 (Listy łączące się)
Dane są dwie listy proste (kończące się nilami). Napisz funkcję stwierdzającą czy te listy mają jakiś wspólny element (nie wartość typu integer, a element typu el_listy).
Wskazówka
Jeśli listy mają wspólny element to ostatni niepusty element l1 i ostatni niepusty element l2 muszą być takie same.
Rozwiązanie
function Wspólny(l1, l2:lista):boolean;
//Sprawdzamy czy listy proste l1 i l2 maja wspólny element
var pom1, pom2: lista;
begin
if l1=nil or l2=nil then Wspólny:=false
else begin
pom1:=l1;
while pom1^.nast <> nil do pom1:=pom1.^nast;
pom2:=l2;
while pom2^.nast <> nil do pom2:=pom2.^nast;
Wspólny:=(pom1=pom2);
end;
end;
Koszt czasowy: liniowy względem sumy długości list
Koszt pamięciowy: stały
Zadanie 7 (Pierwszy wspólny element list łączących się)
Dane są dwie listy proste (kończące się nilami) i takie że maja one element wspólny (funkcja Wspólny z poprzedniego zadania dałaby wynik true). Napisz funkcję odnajdującą pierwszy element wspólny tych list.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Zadanie 8 (Listy z cyklem)
Napisz funkcję która sprawdzi czy dana l typu lista jest listą prostą czy też listą z cyklem.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Zadanie 9 (Długość cyklu w liście z cyklem)
Napisz funkcję która dla danej listy z cyklem obliczy długość cyklu.
Wskazówka 1
{{{3}}}
Rozwiązanie 1
{{{3}}}
Wskazówka 2
{{{3}}}
Rozwiązanie 2
{{{3}}}
