Dlaczego dokładnie potrzebujemy" okrągłej listy połączonej " (pojedynczo lub podwójnie) struktury danych?
Dlaczego dokładnie potrzebujemy "okrągłej listy połączonej" (pojedynczo lub podwójnie) struktury danych?
Jaki problem rozwiązuje, który jest widoczny przy prostych listach linkowanych (pojedynczo lub podwójnie)?
8 answers
Prostym przykładem jest śledzenie, czyja to kolej w wieloosobowej grze planszowej. Umieść wszystkich graczy na okrągłej liście połączonej. Gdy gracz wykonuje swoją kolej, przejdź do następnego gracza na liście. Spowoduje to, że program będzie się obracał w nieskończoność wśród graczy.
Aby przejść przez okrągłą listę połączoną, Zapisz wskaźnik do pierwszego elementu, który widzisz. Gdy zobaczysz ten element ponownie, przejechałeś całą listę.
void traverse(CircularList *c) {
CircularList start = c;
do {
operateOnNode(c);
c = c->next;
} while(c != start);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-28 16:04:37
Dwa powody, dla których warto z nich korzystać:
1) niektóre domeny problemowe są z natury okrągłe.
Na przykład, kwadraty na planszy monopolisty mogą być reprezentowane w okrągłej liście połączonej, aby odwzorować ich nieodłączną strukturę.
2) niektóre rozwiązania mogą być mapowane do listy kołowo połączonych dla wydajności.
Na przykład bufor jitter jest rodzajem bufora, który pobiera ponumerowane pakiety z sieci i umieszcza je w kolejności, tak aby (na przykład) odtwarzacz wideo lub audio można odtwarzać je w kolejności. Pakiety, które są zbyt wolne (opóźnione), są odrzucane.
Może to być reprezentowane w okrągłym buforze, bez konieczności ciągłego przydzielania i dealokacji pamięci, ponieważ gniazda mogą być ponownie używane po ich odtworzeniu.
To Może być zaimplementowane z linked-list, ale będą stałe dodawania i usuwania do listy, zamiast zastępowania stałych (które są tańsze).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-28 07:06:36
Aplikacje
1) Możemy użyć okrągłej listy linkowanej dowolnej aplikacji, w której wpisy pojawiają się w sposób rotacyjny.
2) Circular linked list jest podstawową ideą algorytmu szeregowania round robin.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-08-09 17:20:32
Coś znalazłem z google.
Singly linked circular list jest listą połączoną, w której ostatni węzeł na liście wskazuje na pierwszy węzeł na liście. Lista okrągła nie zawiera wskaźników NULL.
Dobrym przykładem aplikacji, w której powinna być używana okrągła lista powiązana, jest problem współdzielenia czasu rozwiązany przez system operacyjny.
W środowisku współdzielenia czasu system operacyjny musi utrzymywać listę obecnych użytkowników i musi na przemian pozwól każdemu użytkownikowi na użycie małego kawałka czasu procesora, jednego użytkownika na raz. System operacyjny wybierze użytkownika, pozwoli mu / jej wykorzystać niewielką ilość czasu procesora, a następnie przejść do następnego użytkownika, itp.
Dla tej aplikacji nie powinno być żadnych wskaźników NULL, chyba że absolutnie nikt nie żąda czasu procesora.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-11 02:47:15
Okrągła lista linkowana może być efektywnie użyta do utworzenia kolejki (FIFO) lub deque (efektywnie wstawiaj i usuwaj z przodu iz tyłu). Zobacz http://en.wikipedia.org/wiki/Linked_list#Circularly-linked_vs._linearly-linked
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-08-28 06:54:48
Dobrym przykładem aplikacji, w której powinna być używana okrągła lista powiązana, jest problem współdzielenia czasu rozwiązany przez system operacyjny.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-12-30 20:42:05
Lista okrągła jest prostsza niż normalna lista podwójnie połączona. Append jest tylko prepend i przesuń do przodu raz, Pop back jest tylko Przesuń do tyłu raz i pop front . Łącząc oba końce razem, otrzymujesz listę zakończoną podwójnie za koszt tylko wdrożenia operacji listy zakończonej.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-11-10 16:25:26
W poolingu zasobów Możemy użyć listy łączonej cyklicznie. Jeśli wielu użytkowników chce korzystać ze współdzielonego zasobu, możemy przydzielić ten zasób za pomocą listy połączonej kołowo.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-11-01 05:41:46