Wikipedysta:Thorlak/brudnopis3: Różnice pomiędzy wersjami

Usunięta treść Dodana treść
Thorlak (dyskusja | edycje)
Thorlak (dyskusja | edycje)
wstępny szkic
Linia 1:
==Stos=Grafy=
'''Graf''' to doskonała struktura danych do reprezentowania zależności pomiędzy różnymi obiektami.
Stos jest dobrym rozwiązaniem, gdy gromadząc jakieś dane przeprowadzamy operacje najpierw na tych najnowszych (ostatnio dodanych), a gdy te nie są nam już potrzebne, to zabieramy się za te nieco starsze.
Składa się on z dwóch zbiorów: pierwszego - zbioru wierzchołków oznaczanego przez '''V''' (ang. ''Verices'') oraz drugiego - zbioru krawędzi oznaczanego przez '''E''' (ang. ''Edges'').
Jeżeli pomiędzy dwoma wierzchołkami zachodzi jakaś zależność określona przez jakąś konkretną relację to istnieje krawędź łącząca te dwa wierzchołki.
Mniej więcej tak może brzmieć uproszczona definicja matematyczna.
 
Jak można wykorzystać tą strukturę w praktyce?
Dobrym przykładem jest tu stos talerzy, ułożonych jeden na drugim, które - załóżmy - przypadło nam zmywać. W pierwszej kolejności zabierzemy się za talerz na samej górze. Gdy już go wyczyścimy to odłożymy na bok i weźmiemy następny - tak do ostatniego który jest na samym dnie stosu.
Powiedzmy, że chcielibyśmy zareprezentować w jakiś użyteczny sposób mapę drogową Polski, ponieważ będziemy potrzebować jej do programu, który będzie zainstalowany w nawigacji GPS.
 
W takim wypadku w zbiorze V znalazłyby się nazwy miejscowości, a w zbiorze E wszystkie istniejące połączenia drogowe pomiędzy tymi miastami.
===Opis===
Dzięki takiej reprezentacji oraz przy wykorzystaniu odpowiednich algorytmów, które służą do znajdowania najkrótszych ścieżek w grafie będzie można ustalić najbardziej optymalną trasę prowadzącą z jednego miasta do drugiego.
Zważywszy na kolejność dodawania i usuwania elementów ze stosu, struktura ta określana jest jako '''LIFO''' (ang. '''''L'''''ast '''''I'''''n '''''F'''''irst '''''O'''''ut - ''Ostatni na wejściu, Pierwszy na wyjściu'').
===Podstawowe pojęcia===
 
====Graf prosty====
[[Grafika:Stack_data_structure.gif|thumb|150px|right|Schemat<br>(element 1 dodany został jako pierwszy, następnie dodano 2, 3 .. n]]
====Ścieżka w grafie====
 
===Reprezentacja grafu===
{{Struktury danych:ADT|Stos|
====Lista sąsiedztwa====
* ''PUSH(d:Data)'' - wrzuca nowy element ''d'' na szczyt stosu
====Macierz sąsiedztwa====
* ''POP()'' - zdejmuje element ze szczytu stosu zwracając jego wartość
====Analiza obu reprezentacji====
}}
 
===Implementacja===
Do implementacji stosu o stałym rozmiarze ''n'' wystarczy ''n''-elementowa tablica i jedna zmienna, która będzie przetrzymywać aktualną liczbę elementów.
 
 
===Dodatkowe informacje===
* [[/Przykładowe implementacje| Przykładowe implementacje stosu w różnych językach programowania]]
 
===Ćwiczenia===