STUDIUM PRZYPADKU — IMPLEMENTACJA LISTY WSKAŹNIKOWEJ 149 } int main () { unsigned long i = 3; /* szukamy liczb pierwszych w zakresie od 3 do 1000 */ const unsigned long END = 1000; first = malloc (sizeof(el_listy)); first-val = 2; first-next = NULL; for (;i!=END;++i) { if (jest_pierwsza(first, i)) dodaj_do_listy (first, i); } wypisz_liste(first); return 0; } Możemy jeszcze pomyśleć, jak można by wykonać usuwanie elementu z listy. Najprościej byłoby zrobić: wsk-next = wsk-next-next ale wtedy element, na który wskazywał wcześniej wsk- next przestaje być dostępny i zaśmie- ca pamięć. Trzeba go usunąć. Zauważmy, że aby usunąć element potrzebujemy wskaźnika do elementu go poprzedzającego (po to, by nie rozerwać listy). Popatrzmy na poniższą funk- cję: void usun_z_listy(el_listy *lista, int element) { el_listy *wsk=lista; while (wsk-next != NULL) { if (wsk-next-val == element) /* musimy mieć wskaźnik do elementu poprzedzającego */ { el_listy *usuwany=wsk-next; /* zapamiętujemy usuwany element */ wsk-next = usuwany-next; /* przestawiamy wskaźnik next by omijał 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 programie nie ma to miejsca, ale lista jest zrobiona tak, że może trzymać dowol- ne 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ło- wę” — 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 list, np. lista jednokierunkowa cykliczna, lista dwukierunko- wa oraz dwukierunkowa cykliczna. Różnią się one od siebie tylko tym, że:
... zobacz całą notatkę
Komentarze użytkowników (0)