Metody programowania / Ćwiczenia 2

To są zadania na listy.

W poniższych zadaniach będziemy używać następujących typów:

type el_listy = record 
                  w: integer;
                  nast: ^el_listy;
                end;
     lista = ^el_listy;

Zadanie 1 (Odwracanie listy)

Napisz procedurę Odwróć(var l:lista) odwracającą listę l.

Rozwiązanie 1

{{{3}}}

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 1

{{{3}}}

Ćwiczenie 1

{{{3}}}

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ą posortowanych 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ść elelmentó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 funkcje 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 funkcje 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}}}