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 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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 1

{{{3}}}

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 1

{{{3}}}

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 1

{{{3}}}

Rozwiązanie 1

{{{3}}}

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}}}

Ćwiczenie 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}}}