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
Każdy wspólny element list jest tak samo odległy od końca list. Jeśli więc obliczymy długości list to możemy iść po nich równocześnie w takiej samej odległości od końca i sprawdzać czy trafiliśmy już na wspólny element czy nie.
Rozwiązanie
function PierwszyWspólny(l1, l2:lista):lista;
//Listy l1 i l2 maja wspólny element; szukamy pierwszego elementu wspólnego tych list
var dl1, dl2, i: integer;
pom1, pom2: lista;
begin
dl1:=0; pom1:=l1;
while pom1 <> nil do begin //liczymy długość l1
dl1:=dl1+1;
pom1:=pom1^.nast;
end;
dl2:=0; pom2:=l2;
while pom2 <> nil do begin //liczymy długość l2
dl2:=dl2+1;
pom2:=pom2^.nast;
end;
for i:=1 to dl1-dl2 do l1:=l1^.nast; //wyrównujemy odległość od końców list
for i:=1 to dl2-dl1 do l2:=l2^.nast;
while l1 <> l2 do begin //szukamy elementu wspólnego
l1:=l1^.nast;
l2:=l2^.nast;
end;
PierwszyWspólny:=l1;
end;
Koszt czasowy: liniowy względem sumy długości list
Koszt pamięciowy: stały
Ćwiczenie
Skąd wiadomo, że w ostatnim while'u l1 i l2 sa zawsze różne od nil ?
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
Wystarczy poruszać sie po liście dwoma wskaźnikami o dwóch różnych względnie pierwszych prędkościach; wtedy albo trafimy szybszym wskaźnikiem na nil albo oba wskaźniki się zejdą.
Rozwiązanie
function ListaZCyklem(l:lista):boolean;
//Sprawdzamy czy lista l jest listą z cyklem, czy tez kończy się nilem
var pom1, pom2: lista;
begin
pom1:=l;
pom2:=l^.nast;
while (pom2 <> nil) and (pom2 <> pom1) do begin
pom1:=pom1^.nast;
pom2:=pom2^.nast;
if pom2 <> nil then pom2:=pom2^.nast;
end;
ListaZCyklem:=(pom1=pom2);
end;
Koszt czasowy: liniowy względem długości listy
Koszt pamięciowy: stały
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
Można poruszać sie po liście dwoma wskaźnikami tak jak w zadaniu poprzednim; gdy wskaźniki sie zejdą to znaczy, że jesteśmy na cyklu; wystarczy zatrzymać jeden wskaźnik a drugim obejść cykl i obliczyć jego długość.
Rozwiązanie 1
function DługośćCyklu1(l:lista):integer;
//Obliczamy długość cyklu dla listy z cyklem
var pom1, pom2: lista;
dl: integer;
begin
pom1:=l;
pom2:=l^.nast;
while pom2 <> pom1 do begin
pom1:=pom1^.nast;
pom2:=pom2^.nast;
pom2:=pom2^.nast;
end;
pom2:=pom1^.nast;
dl:=1;
while pom2 <> pom1 do begin
dl:=dl+1;
pom2:=pom2^.nast;
end;
DługośćCyklu1:=dl;
end;
Koszt czasowy: liniowy względem długości listy
Koszt pamięciowy: stały
Wskazówka 2
Jeśli przechodząc po liście z cyklem będziemy ją odwracać to dojdziemy do początku; odwiedzimy przy tym 2m+n elementów gdzie n to długość cyklu a m to liczba elementów poza cyklem. Wtedy (2m+n div 2)-ty element leży na cyklu i poczynając od niego można obliczyć długość cyklu.
Rozwiązanie 2
function DługośćCyklu2(l:lista):integer;
//Obliczamy długość cyklu dla listy z cyklem
var poprz, akt, pom1, pom2: lista;
dl: integer;
begin
poprz:=nil;
akt:=l;
dl:=0;
while akt <> nil do begin //odwracamy listę i liczymy ile kroków zajmuje dojście do nil
pom1:=akt^.nast;
akt^.nast:=poprz;
poprz:=akt;
akt:=pom1;
dl:=dl+1;
end; //dl to 2m+n, gdzie n to długosć cyklu a
pom1:=l; //m to liczba elementów poza cyklem
for i:=1 to (dl div 2) do pom1:=pom1^.nast;
pom2:=pom1^.nast; //pom1 i pom2 leżą na cyklu
dl:=1; //liczymy długość cyklu
while pom2 <> pom1 do begin
dl:=dl+1;
pom2:=pom2^.nast;
end;
DługośćCyklu2:=dl;
end;
Koszt czasowy: liniowy względem długości listy
Koszt pamięciowy: stały
