Informatyka dla klas II

Mamy daną listę jednokierunkową. Szukamy na niej elementu o określonych własnościach. Jeśli go znajdziemy, zwracamy adres elementu w pamięci. Jeśli elementu nie znajdziemy, zwracamy adres NULL.

Algorytm polega na przechodzeniu listy od jej głowy do ogona. Każdy kolejno napotkany węzeł sprawdzamy pod katem kryterium. Jeśli element spełnia to kryterium, zwracamy jego adres. W przeciwnym razie kontynuujemy przeszukiwanie listy aż do momentu, gdy wyjdziemy poza jej ostatni element. Wtedy zwracamy adres NULL.

Każdy element listy jest strukturą o postaci:

struct slistEl
{
  slistEl * next;
  typ_danych data;
};

Algorytm wyszukiwania na liście elementu o wartości v

Wejście

p	–	wskazanie elementu listy, od którego rozpocznie się poszukiwanie
v	–	poszukiwana wartość

Wyjście:

Adres elementu, który w polu data przechowuje wartość v  lub NULL, jeśli na liście nie ma takiego elementu.

Lista kroków:

K01:	Dopóki (p  ≠ nil) ((p→data) ≠ v), wykonuj p  ← (p→next)	; w pętli przechodzimy przez kolejne elementy listy
K04:	Zakończ z wynikiem p

Wykorzystując powyższy algorytm, napisz program, który umieści na liście 1000 elementów pseudolosowych z zakresu od 1 do 9, a następnie zliczy kolejno elementy o wartości 1, 2,..., 9.

1 → 5 → 4 → 7 → 2 → 8 → 9 → 3 → 1 → 2 → 5 → 6 → 3 → 1

Po usunięciu duplikatów na liście pozostaną elementy unikalne:

1 → 5 → 4 → 7 → 2 → 8 → 9 → 3 → 6

Zadanie można rozwiązać w sposób następujący. Jeśli lista nie jest pusta, rozpoczynamy przeglądanie od pierwszego elementu. Nazwijmy go elementem bieżącym. Dla każdego kolejnego elementu bieżącego przechodzimy listę wzdłuż jego następników. Jeśli natrafimy na element, który w polu data zawiera tę samą daną co element bieżący, to usuwamy ten element i kontynuujemy przeglądanie. Po przeglądnięciu całej listy zostaną z niej usunięte wszystkie duplikaty elementu bieżącego. Operację kontynuujemy z następnym elementem bieżącym, aż wykorzystamy wszystkie elementy listy. Algorytm ma klasę złożoności obliczeniowej O(n²), gdzie n  oznacza liczbę elementów listy.

Każdy element listy jest strukturą o postaci:

struct slistEl
{
  slistEl * next;
  typ_danych data;
};

Algorytm usuwania duplikatów z listy jednokierunkowej

Wejście

Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:

Lista kroków:

Wykorzystując powyższy algorytm napisz program, który utworzy listę 15 wartości pseudolosowych z zakresu od 1 do 9 i usunie z niej wszystkie duplikaty.

5 → 7 → 8 → 3 → 2 → 1 → 4

musimy przekształcić w listę:

4 → 1 → 2 → 3 → 8 → 7 → 5

Zadanie wykonujemy następująco. Jeśli lista jest pusta, kończymy. W przeciwnym razie zapamiętujemy adres pierwszego elementu listy. Następnie dopóki istnieje następnik zapamiętanego elementu, wyjmujemy go z listy i dodajemy na jej początek. W efekcie elementy na liście zmienią swoją kolejność, a element pierwszy stanie się ostatnim.

Każdy element listy jest strukturą o postaci:

struct slistEl
{
  slistEl * next;
  typ_danych data;
};

Algorytm odwracania kolejności elementów na liście jednokierunkowej

Wejście

Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:

Lista kroków:

Wykorzystując powyższy algorytm napisz program, który utworzy 20 elementową listę liczb pseudolosowych o wartościach od 1 do 9, a następnie odwróci jej elementy.