Struktury danych, drzewa i grafy
Tablice, listy, stos, kolejka, drzewa, grafy; reprezentacja hierarchii przez tablicę przełożonych.
Teoria, wzory i przykłady
Podstawowe struktury
- stos (LIFO) — push/pop, np. nawiasowanie, rekurencja,
- kolejka (FIFO) — enqueue/dequeue, np. BFS,
- lista, tablica, słownik (mapa) — dostęp po kluczu w średnim .
Drzewa
Drzewo ukorzenione: każdy wierzchołek poza korzeniem ma dokładnie jednego rodzica. Hierarchię (np. korporacja) zapisujemy jako tablicę rodziców: rodzic[i] = numer bezpośredniego przełożonego pracownika i.
Typowe obliczenia na tablicy rodziców:
- liczba bezpośrednich podwładnych pracownika x = ile razy x występuje w tablicy rodziców,
- pracownicy niebędący przełożonymi to liście = numery, które nie występują w tablicy rodziców,
- liczba przełożonych pracownika (głębokość w drzewie): — jeśli rodzic zawsze ma mniejszy numer, wystarcza jeden przebieg od w górę,
- wszyscy podwładni — suma po poddrzewie (przebieg od końca: dodajemy rozmiar dziecka do rodzica).
Przykładowa korporacja z 8 pracownikami: pracownik 2 ma 3 bezpośrednich podwładnych (3, 5, 6) i 4 wszystkich (dodatkowo 7).
Grafy
Graf = wierzchołki + krawędzie. Reprezentacja: macierz sąsiedztwa lub listy sąsiedztwa. Przeszukiwanie DFS (stos/rekurencja) i BFS (kolejka) w ; BFS znajduje najkrótsze ścieżki w grafie nieważonym.
Średnie zadania
Informacja do zadań 4.2–4.4. Plik korpo.txt zawiera liczb opisujących korporację. W pierwszym wierszu jest 0 (prezes nie ma przełożonego), a w -tym wierszu () — numer bezpośredniego przełożonego pracownika . Pliki z danymi (Dane-NF-2605.zip) pobierzesz na stronie arkusza. (Do dyspozycji jest też korpo_przyklad.txt.)
Podaj, ilu pracowników nie jest przełożonym żadnego pracownika. Dla korpo_przyklad.txt odpowiedź to .
Podaj, który pracownik z pliku korpo.txt ma najwięcej bezpośrednich podwładnych: numer tego pracownika oraz liczbę jego bezpośrednich podwładnych. Dla korpo_przyklad.txt odpowiedź to 3 49997.
Wpisz dwie liczby oddzielone spacją: numer liczba.