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

Zakładamy że elementy list mają całkowite pole 'licznik'. Dla dwu zadanych list (równej długości) stworzyć nową listę, której pola 'licznik' są sumami pól 'licznik' z list wejściowych (n-ty element wyniku zawiera sumę z n-tych elementów obu list wejściowych).

Zadanie 2

Zakładamy że elementy listy mają całkowite pola 'klucz' i 'licznik'. Powiększyć pole 'licznik' o 1 dla tych elementów listy które mają zadaną wartość klucza.

Zadanie 3

Napisać funkcję, która mając daną listę liczb całkowitych i liczbę, usunie pierwsze (albo każde) wystąpienie tej liczby na liście. Dokładniej, zrobić kopię listy pomijając zbędne elementy.

Zadanie 4

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 5

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

Zrobić dwie wersje, jedną która modyfikuje elementy (wskaźniki), i taką któraś kopiuje listy zamiast modyfikacji.

Zadanie 6

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

Zadanie 7

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 8

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.

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 źró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' za wyjątkiem być może pierwszej listy 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.