12  Listy jednokierunkowe

Wykorzystaj z zadaniach konwencją omawianą na wykładzie.

12.1 Bez funkcji

1. W main stwórz listę bez głowy o trzech elementach 4,5,-12. Następnie w kolejnych wierszach wyświetl elementy znajdujące się na liście. Wykorzystaj strukturę:

struct element {
    int x;
    struct element * next;
};

2. W main stwórz listę z głową o trzech elementach 4,5,-12. Następnie w kolejnych wierszach wyświetl elementy znajdujące się na liście. Wykorzystaj strukturę:

struct element {
    int x;
    struct element * next;
};

12.2 Wyświetlanie

3. Napisz funkcję printListWithoutHead, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma wyświetlić kolejne elementy listy w kolejnych wierszach lub wyświetlić komunikat, że lista jest pusta. Stwórz przypadek testowy.

4. Napisz funkcję printListWithHead, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma wyświetlić kolejne elementy listy w kolejnych wierszach lub wyświetlić komunikat, że lista jest pusta. Stwórz przypadek testowy.

5. Napisz funkcję printPos, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma wyświetlić te elementy listy, które są dodatnie. Stwórz przypadek testowy.

6. Napisz funkcję printOdd, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma wyświetlić te elementy listy, które są nieparzyste. Stwórz przypadek testowy.

12.3 Tworzenie listy

7. Napisz bez-argumentową funkcję createNoHead, która zwraca wskaźnik na “nowo-utworzoną” pustą listę bez głowy. Stwórz przypadek testowy. Wykorzystaj strukturę:

struct element {
    int x;
    struct element * next;
};

8. Napisz bez-argumentową funkcję createWithHead, która zwraca wskaźnik na “nowo-utworzoną” pustą listę z głową. Stwórz przypadek testowy. Wykorzystaj strukturę:

struct element {
    int x;
    struct element * next;
};

12.4 Dodawanie na początek

9. Napisz funkcję addFirst, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma dodać na początek listy nowy element o wartości a. Stwórz przypadek testowy.

10. Napisz funkcję addFirst, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma dodać na początek listy nowy element o wartości a. Stwórz przypadek testowy.

12.5 Dodawanie na koniec

11. Napisz funkcję addLast, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma dodać na koniec listy nowy element o wartości a. Stwórz przypadek testowy.

12. Napisz funkcję addLast, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma dodać na koniec listy nowy element o wartości a. Stwórz przypadek testowy.

12.6 Wyszukiwanie/liczniki

13. Napisz funkcję find, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma zwrócić 1, jeśli co najmniej jeden element listy jest równy a oraz ma zwrócić 0 w pozostałych wypadkach. Stwórz przypadek testowy.

14. Napisz funkcję find, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

oraz liczbę całkowitą a. Funkcja ma zwrócić 1, jeśli co najmniej jeden element listy jest równy a oraz ma zwrócić 0 w pozostałych wypadkach. Stwórz przypadek testowy.

15. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma zwrócić sumę elementów nieparzystych znajdujących się na liście. Stwórz przypadek testowy.

16. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma zwrócić sumę elementów ujemnych znajdujących się na liście. Stwórz przypadek testowy.

17. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma zwrócić adres ostatniego elementu parzystego lub NULL gdy takie elementu nie ma lub lista jest pusta. Stwórz przypadek testowy.

18. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma zwrócić adres ostatniego elementu dodatniego lub NULL gdy takie elementu nie ma lub lista jest pusta. Stwórz przypadek testowy.

12.7 Usuwanie pojedynczych elementów

19. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć początkowy element na liście (o ile lista nie jest pusta). Stwórz przypadek testowy.

20. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć początkowy element na liście (o ile lista nie jest pusta). Stwórz przypadek testowy.

21. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć ostatni element na liście (o ile lista nie jest pusta). Stwórz przypadek testowy.

22. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć ostatni element na liście (o ile lista nie jest pusta). Stwórz przypadek testowy.

23. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć przedostatni element na liście (o ile lista ma co najmniej dwa elementy). Stwórz przypadek testowy.

24. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć przedostatni element na liście (o ile lista ma co najmniej dwa elementy). Stwórz przypadek testowy.

12.8 Usuwanie całej listy

25. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć całą listę (ręcznie element za elementem). Po usunięciu upewnij się, że lista jest pusta zgodnie z konwencją. Stwórz przypadek testowy.

26. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct element {
    int x;
    struct element * next;
};

Funkcja ma usunąć całą listę (ręcznie element za elementem). Po usunięciu upewnij się, że lista jest pusta zgodnie z konwencją. Stwórz przypadek testowy.

12.9 Zadania różne

27. Napisz funkcję, która otrzymuje jako argument listę bez głowy o elementach typu:

struct node {
    int i;
    struct node * next;
};

Funkcja ma wyświetlić na konsoli w kolejnych wierszach wartości elementów na liście będących kwadratami liczb całkowitych. Stwórz przypadek testowy.

Przykład. Jeśli lista składa się z elementów 4,5,6,-34,0,25,11, to ma być wyświetlone w kolejnych wierszach: 4,0,25.

28. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct node {
    double x;
    struct node * next;
};

i zwraca najmniejszą z liczb znajdujących się na liście. W przypadku pustej listy, funkcja ma zwrócić zero. Stwórz jeden przypadek testowy.

29. Napisz funkcję, która otrzymuje jako argument listę bez głowy o elementach typu:

struct node {
    int i;
    struct node * next;
};

Funkcja ma zdublować wartość ostatniego elementu, o ile lista jest nie pusta. W przypadku pustej listy, funkcja ma nic nie robić. Stwórz przypadek testowy.

Przykład: Dla listy 3,4,5 ma być zdublowana 5, więc po modyfikacji lista ma być postaci 3,4,5,5.

30. Napisz funkcję, która otrzymuje jako argument listę z głową o elementach typu:

struct elem {
    int a;
    struct elem * next;
};

Funkcja ma zdublować wartość ostatniego elementu, o ile lista jest nie pusta. W przypadku pustej listy, funkcja ma nic nie robić. Stwórz przypadek testowy.

Przykład: Dla listy 3,4,5 ma być zdublowana 5, więc po modyfikacji lista ma być postaci 3,4,5,5.

31. Napisz funkcję, która porównuje dwie listy z głową o elementach typu:

struct node {
    int i;
    struct node * next;
};

i zwraca 1 jeśli ostatnie elementy na liście są równe oraz 0 w pozostałych przypadkach (także wtedy gdy któraś z list lub obie są puste). Stwórz jeden przypadek testowy.

32. Napisz funkcję, która porównuje dwie listy bez głowy o elementach typu:

struct node {
    int a;
    struct node * next;
};

i zwraca 1 jeśli listy są takiej samej długości oraz 0 w pozostałych przypadkach (także wtedy, gdy któraś z list lub obie są puste). Stwórz przypadek testowy.

33. Napisz funkcję, która przyjmuje dwie listy z głową o elementach typu:

struct node {
    int value;
    struct node * next;
};

i zwraca 1 jeśli suma wszystkich elementów nieparzystych w obu listach jest taka sama oraz 0 w przeciwnym przypadku (także wtedy, gdy któraś z list lub obie są puste). Stwórz przypadek testowy.

34. Napisz funkcję, która przyjmuje dwie listy bez głowy o elementach typu:

struct node {
    int w;
    struct node * next;
};

i zwraca 1 jeśli suma wszystkich elementów parzystych w obu listach jest taka sama oraz 0 w przeciwnym przypadku (także wtedy, gdy któraś z list lub obie są puste). Stwórz przypadek testowy.

35. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct node {
    int x;
    struct node * next;
};

Funkcja ma zwrócić sumę elementów nieparzystych z listy. Stwórz jeden przypadek testowy.

36. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct elem {
    int x;
    struct elem * next;
};

Funkcja ma podwoić wszystkie elementy dodatnie na liście (o ile istnieją). Stwórz jeden przypadek testowy.

37. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct node {
    int y;
    struct node * next;
};

oraz dwie liczby całkowite a i b. Funkcja ma dodać na początek listy dwa nowe elementy i ich wartości ustawić odpowiednio z podanych argumentów. Stwórz jeden przypadek testowy.

38. Napisz funkcję, która przyjmuje jako argument listę bez głowy o elementach typu:

struct node {
    int a;
    struct node * next;
};

oraz dwie liczby całkowite a i b. Funkcja ma dodać na początek listy dwa nowe elementy i ich wartości ustawić odpowiednio z podanych argumentów. Stwórz jeden przypadek testowy.

39. Napisz funkcję, która otrzymuje jako argument listę bez głowy o elementach typu:

struct element {
    float value;
    struct element * next;
};

Funkcja ma zamienić wartości każdego elementu na jego wartość bezwzględną. Dla listy pustej funkcja ma nic nie robić. Stwórz przypadek testowy.

40. Napisz funkcję, która otrzymuje jako argument listę z głową o elementach typu:

struct node {
    int val;
    struct node * next;
};

Funkcja ma zamienić wartości każdego elementu na jego wartość bezwzględną. Dla listy pustej funkcja ma nic nie robić. Stwórz przypadek testowy.

41. Napisz funkcję, która przyjmuje jako argument listę z głową o elementach typu:

struct node {
    int x;
    struct node * next;
};

oraz liczbę całkowitą d. Funkcja ma zwrócić ile na liście jest elementów równych d. Stwórz jeden przypadek testowy.