Informatyka dla klas II

Algorytmy listowe

Wyszukiwanie elementu na liście

Problem jest następujący:

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) ((pdata) ≠ v), wykonuj p ← (pnext) ; 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.

 

Usuwanie duplikatów z listy

Mamy za zadanie usunąć z listy wszystkie duplikaty (powtórki) elementów. Dla przykładu na poniższej liście kolorem czerwonym zaznaczono elementy powtarzające się:

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

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(n2), 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
head  –  adres pierwszego elementu listy
Wyjście:

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

Elementy pomocnicze:
p,r  –  wskaźniki elementu listy
pc  – wskaźnik elementu bieżącego
Lista kroków:
K01: pchead; ; jako element bieżący przyjmujemy pierwszy element listy
K02: Dopóki pc ≠ NULL, wykonuj K03...K11  
K03:     ppc ; zawsze będziemy testowali następnik
K04:     Dopóki (pnext) ≠ NULL, wykonuj K05...K10 ; dopóki istnieje następnik
K05:         Jeśli ((pnext)→data) ≠ (pcdata), to idź do K10 ; sprawdzamy, czy jest duplikatem
K06:         r ← (pnext) ; zapamiętujemy adres następnika
K07:         (pnext) ← (r→next) ; wyłączamy następnik z listy
K08:         Usuń z pamięci element o adresie r ; zwalniamy pamięć zajętą przez element
K09:         Kontynuuj pętlę z kroku K04  
K10:         p ← (pnext) ; przesuwamy się do następnika
K11     pc ← (pcnext) ; kolejny element bieżący
K12: Zakończ  

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.

 

Odwracanie elementów listy

Naszym zadaniem jest takie przekształcenie listy, aby jej elementy znalazły się w kolejności odwrotnej. Na przykład listę:

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
head  –  adres pierwszego elementu listy
Wyjście:

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

Elementy pomocnicze:
p  –  wskaźniki elementu listy
pc  – wskaźnik elementu bieżącego
Lista kroków:
K01: Jeśli head = nil, to zakończ ; jeśli lista jest pusta, kończymy.
K02: pchead ; zapamiętujemy adres pierwszego elementu
K03: Dopóki (pcnext) ≠ nil, wykonuj K04...K07 ; dopóki istnieje następnik zapamiętanego elementu
K04:     p ← (pcnext) ; zapamiętujemy adres następnika
K05:     (pcnext) ← (pnext) ; wyjmujemy następnik z listy
K06:     (pnext) ← head ; i wstawiamy go na jej początek
K07:     headp  
K08: Zakończ  

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.

 

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.