Metody programowania / Ćwiczenia 2

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