39026

STUDIUM PRZYPADKU IMPLEMENTACJA LISTY WSKAŹNIKOWEJ 119 int main ()

{

unsigned long i = 3; /• szukany liczb pierwszych w zakresie od 3 do 1000 •/ const unsigned long END * 1000; first » malloc (sizeof(el.listy));

£irst->val - 2;

£irst->next ■ NULL; for (;i!=END;++i) {

if (jest_piervsza(first, i)) dodaj_do_listy (first, i);

>

vypisz_liste(first); return 0;

Możemy jeszcze pomyśleć, jak można by wykonać usuwanie elementu z listy. Najprościej byłoby zrobić:

vsk->next = vsk->next->next

ale wtedy element, na który wskazywał wcześniej wsk->next przestaje być dostępny i zaśmieca pamięć. Trzeba go usunąć. Zauważmy, że aby usunąć element potrzebujemy wskaźnika do elementu go poprzedzającego (|x> to. by nie rozerwać listy). Popatrzmy na poniższą funkcję:

void usun_z_listy(el_listy *lista, int element)

{

el.listy ‘wsk-lista; while (wsk->next !* NULL)

{

if (wsk->next->val == element) /• musimy nieć wskaźnik do elenentu poprzedzającego */

{

el.listy *usuwany»wsk->next; /• zapamiętujemy usuwany element •/

wsk->next ■ usuwany->next;    /• przestawiany wskaźnik next by onijal usuwany element */

free(usuwany);    /• usuwamy z pamięci */

> else

{

wsk * wsk->next;    /» idziemy dalej tylko wtedy kiedy nie usuwaliśmy »/

>    /• bo nie chcemy zostawić duplikatów */

}

>

Funkcja ta jest tak napisana, by usuwała z listy wszystkie wystąpienia danego elementu (w naszym |)rogramie nie ma to miejsca, ale lista jest zrobiona tak, że może trzymać dowolne liczby). Zauważmy, że wskaźnik wsk jest przesuwany tylko wtedy, gdy nie kasowaliśmy.

Gdybyśmy zawsze go przesuwali, przegapilibyśmy element gdyby występował kilka razy pod rząd.

Funkcja ta działa poprawnie tylko wtedy, gdy nie chcemy usuwać pierwszego elementu.

Można to poprawić dodając instrukcję warunkową do funkcji lub dodając do listy “głowę" pierwszy element nie przechowujący niczego, ale upraszczający operacje na liście.

Zostawiamy to do samodzielnej pracy.

Cały powyższy przykład omawiał tylko jeden przypadek listy — listę jednokierunkową.

Jednak istnieją jeszcze inne typy Ust, np. lista jednokierunkowa cykliczna, lista dwukierunkowa oraz dwukierunkowa cykliczna. Różnią się one od siebie tylko tym. że: