C/Typy złożone: Różnice pomiędzy wersjami
Usunięta treść Dodana treść
m →Listy: gallery |
|||
Linia 291:
{{wikipedia|Lista}}
rodzaje list:
Studium przypadku - implementacja listy wskaźnikowej▼
* '''lista jednokierunkowa''' – w każdym elemencie listy jest przechowywane odniesienie tylko do jednego sąsiada (następnika lub poprzednika)
* '''lista dwukierunkowa''' – w każdym elemencie listy jest przechowywane odniesienie zarówno do następnika, jak i poprzednika elementu w liście. Taka reprezentacja umożliwia swobodne przemieszczanie się po liście w obie strony
* '''lista cykliczna''' – następnikiem ostatniego elementu jest pierwszy element. Po liście można więc przemieszczać się cyklicznie. Nie ma w takiej liście charakterystycznego ogona (ani głowy), często rozpoznawanego po tym, że jego następnik jest pusty (NULL)
* '''lista z wartownikiem''' – lista z wyróżnionym elementem zwanym wartownikiem. Jest to specjalnie oznaczony element niewidoczny dla programisty wykorzystującego listę. Pusta lista zawiera wtedy tylko wartownika. Zastosowanie wartownika znacznie upraszcza implementację operacji na listach.
<gallery perrow=1 mode=nolines widths="500px">
Singly-linked-list.svg
Doubly-linked-list.svg
Circularly-linked-list.svg
</gallery>
▲=== Studium przypadku - implementacja listy wskaźnikowej===
Rozważmy teraz coś, co każdy z nas może spotkać w codziennym życiu. Każdy z nas widział kiedyś jakiś przykład listy (czy to zakupów, czy też listę wierzycieli). Język C też oferuje listy, jednak w programowaniu listy będą służyły do czegoś innego. Wyobraźmy sobie sytuację, w której jesteśmy autorami genialnego programu, który znajduje kolejne liczby pierwsze. Oczywiście każdą kolejną liczbę pierwszą może wyświetlać na ekran, jednak z matematyki wiemy, że dana liczba jest liczbą pierwszą, jeśli nie dzieli się przez żadną liczbę pierwszą ją poprzedzającą, mniejszą od pierwiastka z badanej liczby. Mniej więcej chodzi o to, że moglibyśmy wykorzystać znalezione wcześniej liczby do przyspieszenia działania naszego programu. Jednak nasze liczby trzeba jakoś mądrze przechować w pamięci. Tablice mają ograniczenie - musimy z góry znać ich rozmiar. Jeśli zapełnilibyśmy tablicę, to przy znalezieniu każdej kolejnej liczby musielibyśmy:
| |||