Metody Programowania - Lista 2

W zadaniach zakładamy że listy są zadane (reprezentowane) poprzez wskaźnik do pierwszego elementu, zaś ostatni element ma zerowy wskaźnik do następnego. Listy są jednokierunkowe, chyba że napisano inaczej.

Zadanie 1

Napisać funkcję, która mając daną listę, (taką jak któraś z list z zadania 4 z listy 1) i wskaźnik do elementu na liście znajdzie poprzedni element.

Zadanie 2

Rozdzielić zadaną listę na dwie,

pierwsza z nieparzystych elementów, druga z parzystych
zakładamy że elementy mają całkowite pole klucz. Pierwsza lista ma mieć elementy z kluczem większym od zadanej wartości, druga pozostałe
to samo, ale dla list dwukierunkowych
to samo co w poprzednich punktach, ale kopiując listy zamiast modyfikacji

Zadanie 3

Napisać funkcję, która odwróci daną listę dwukierunkową (tzn. zmieni wskaźniki tak by elementy były w odwrotnej kolejności).

Zadanie 4

Napisać funkcję:

która wypisze elementy zadanej listy
zbuduje listę zadanej długości wypełniając pola 'klucz' kolejnymi (albo losowymi) wartościami

Jak można użyć takie funkcje do sprawdzenia czy funkcje z poprzednch zadań działają poprawnie.

Zadanie 5

Napisać wersję funkcji `mape' (z programu przykładowego listy-pr.c ) która kończy iterację gdy funkcja `fun' zwraca 0. Wykorzystać ją do alternatywnego rozwiązania zadania 1.

Zadanie 6

Zakładamy że elementy meta-listy (listy list) mają następującą deklarację:

struct ls { struct ls *nastepny; int wartosc;}
struct mls { struct mls *nastepny; struct ls *lwartosc;};

Obliczyć (stworzyć) listę sum pól wartość poszczególnych list na meta-liście. Podać rozwiązanie bezpośrednie jak i bazujące na `map' lub `mape'.

Zadanie 7

Spróbować rozwiązać zadania o listach z listy 1 używając do przechodzenia listy funkcji `map' (lub `mape'). W których zadanich są z tym trudności .

Zadanie 8

Napisać funkcję, która mając daną listę liczb całkowitych i kryterium obliczy sumę liczb spełniających kryterium. Kryterium jest zadane jako wskaźnik do funkcji która bierze jako argument wskaźnik do elementu listy i zwraca 1 jeśli element spełnia kryterium, zaś 0 w przeciwnym razie. Podać rozwiązanie bezpośrednie jak i bazujące na `map' lub `mape'.

Zadanie 9

Napisać funkcję, która mając dane dwie listy liczb całkowitych równej długości stworzy listę par liczb całkowitych.

Zadanie 10

Napisać funkcję, która mając dane dwie listy liczb całkowitych zlepi je, tzn. wyprodukuje listę na której są wszyskie elementy pierwszej listy, a po nich wszystkie elementy drugiej listy (tu należy zmodyfikować ostani węzeł pierwszej listy).
Podobnie, ale nie modyfikująć węzłów list zródłowych (w razie potrzeby tworząc kopie węzłów).
Napisać funkcję, która mając daną listę list liczb całkowitych zlepi wszystkie składowe listy (destruktywnie).
Podobnie, ale nie modyfikująć węzłów list zródłowych (w razie potrzeby tworząc kopie węzłów).

Zadanie 11

Napisać funkcję, która mając daną listę liczb całkowitych 'l' i liczbę 'a' rozbije 'l' na odcinki zaczynające się od 'a'. Dokładniej, funkcja ma stworzyć listę list 'ml' taką że:

każdy element (lista) na liście 'ml' zaczyna się od 'a'
elementy 'ml' nie zawierają 'a' na innych pozycjach niż pierwsza
zlepienie (konkatenacja) elementów listy 'ml' da z powrotem listę 'l'

Funkcja nie ma odyfikować węzłów list zródłowych (w razie potrzeby tworzyć kopie węzłów).

Zadanie 12

Napisać funkcję, która mając dany łańcuch znaków wyprodukuje listę wchodzących w niego słów. Dla celów tego zadania słowo to maksymalny ciąg znaków nie zawierający spacji.