Struktury danych — jak ułożyć informacje
Wstęp do działu
Przez cały dział o sortowaniu i szukaniu (6) trzymałeś dane w liście — i czasem lista zawadzała. W jednostce 6.4 odkryłeś, że wstawienie elementu w środek tablicy kosztuje przesunięcie całego ogona; w 8.6, że k-NN dławi się, licząc odległości do wszystkich. Za każdym razem problem był ten sam: narzędzie nie pasowało do operacji. Ten dział jest o dobieraniu naczynia do zawartości — bo to, jak ułożysz dane, decyduje o tym, co da się z nimi zrobić tanio.
Poznasz struktury, które są dla informatyki tym, czym dla stolarza różne uchwyty: stos (ostatni wchodzi, pierwszy wychodzi — jak sterta talerzy), kolejkę (kto pierwszy, ten pierwszy — jak w sklepie), listę wiązaną (elementy trzymające się za ręce), kopiec (błyskawiczny dostęp do najważniejszego) i graf — najogólniejszą strukturę świata, którą da się opisać sieci dróg, znajomości, stron internetowych i zależności. Zobaczysz stos w akcji przy odwrotnej notacji polskiej, kolejkę przy problemie Flawiusza, a grafy jako uniwersalny model, do którego redukuje się zaskakująco wiele problemów. Podstawa rozszerzona wymienia każdą z tych struktur z nazwy.
Mapa pojęć działu
STRUKTURA DANYCH = układ + dozwolone operacje
|
┌──────────┬───────────┬───┴───────┬─────────────┬──────────────┐
tablica stos kolejka lista kopiec graf
(indeks, (LIFO: (FIFO: wiązana (najważniejszy (wierzchołki
szybki ostatni pierwszy (giętka zawsze na + krawędzie;
dostęp) wchodzi, wchodzi, w środku) wierzchu) model WSZYSTKIEGO)
[R] sumy pierwszy pierwszy | |
prefiksowe wychodzi) wychodzi) Flawiusz, kolejka
| | | leksyko- priorytetowa
dobór struktury do ONP, graficzne
operacji, nie odwrotnie cofanie
Jednostki w tym dziale
- 9.1 Tablica i jej granice (w rozszerzeniu: sumy prefiksowe)
- 9.2 Stos — i odwrotna notacja polska (rozszerzenie)
- 9.3 Kolejka i lista — Flawiusz i porządek leksykograficzny (rozszerzenie)
- 9.4 Kopiec — kolejka ważności (rozszerzenie)
- 9.5 Grafy i drzewa — modelowanie świata (rozszerzenie)