Vodič · Algoritmi · Strukture podataka
Strukture podataka – vodič kroz lekcije
Struktura podataka je način na koji su podaci smešteni u memoriji. Od izbora strukture zavisi koliko brzo se element dodaje, briše ili pronalazi – zato isti zadatak može da traje sekundu ili sat.
Vodič ide od niza, stringa i matrice, preko steka, reda i skupova, do struktura koje se koriste na državnom takmičenju i SIO: Fenwick i segmentno stablo.
- 6–8. razred i srednja škola
- C++
- Priprema za takmičenja
1 Osnovne strukture
Niz, string, matrica, strukture i vektori – temelj svih ostalih.
2 Linearne strukture
Elementi poređani jedan za drugim, sa različitim pravilima dodavanja i uklanjanja.
3 Skupovi, mape i red sa prioritetom
Gotove strukture iz C++ biblioteke koje rade u O(log n).
4 Napredne strukture
Strukture za državno takmičenje i SIO.
Predloženi redosled
Korisni spoljni resursi
- VisuAlgo – animacije steka, reda, heap-a, DSU, Fenwick i segmentnog stabla
- CSES Problem Set – odeljak „Sorting and Searching“, zadaci sa automatskom proverom
- cp-algorithms – Data Structures – detaljni članci o naprednim strukturama (engleski)
Mapa učenja — Strukture podataka
Ova stranica predstavlja mapu učenja i vodič kroz najvažnije strukture podataka
koje se koriste u algoritmima i takmičarskom programiranju.
Strukture podataka su temelj za razumevanje brzih, efikasnih i optimizovanih algoritama.
Kroz ovu mapu možeš videti:
- koje strukture podataka treba učiti
- kojim redosledom ih je preporučljivo savladati
- kako su povezane sa algoritmima kao što su BFS, DFS, pretrage i sortiranja
Preporučeno za pripremu za: SIO, okružno i državno takmičenje, kao i za učenike koji žele da steknu čvrstu osnovu iz algoritama.
□ Osnovne linearne strukture
- Nizovi (Arrays)
- Povezane liste (Linked List)
- Stek (Stack)
- Red (Queue)
- Deque (Double-ended queue) — u izradi
Ove strukture su prvi i najvažniji korak u učenju struktura podataka i koriste se u skoro svakom programu i algoritmu.
□ Prioritetne i pomoćne strukture
- Prioritetni red (Priority Queue)
- Heap (min-heap / max-heap) – u lekciji o redu sa prioritetom
- Set i Map (STL) — u izradi
- Unordered Set / Map — u izradi
Ove strukture se koriste za optimizaciju algoritama, naročito u algoritmima kao što su Dijkstra, greedy strategije i razne simulacije.
□ Drvolike strukture podataka
- Binarno stablo — u izradi
- Binarno pretraživačko stablo (BST) — u izradi
- Segmentno stablo
- Fenwick (BIT) stablo
⭐ Ovo su ključne strukture podataka za rešavanje problema sa opsegom (range queries), kao i za optimizaciju složenih algoritama.
□ Specijalne strukture podataka
- Disjoint Set Union (Union-Find)
- Trie (prefiksno stablo) — u izradi
- Hash strukture i kolizije — u izradi
DSU je neizostavan u algoritmima za minimalno razapinjuće stablo (Kruskal), dok se Trie često koristi u problemima sa stringovima i prefiksima.
□ Predložen redosled učenja
- Nizovi i povezane liste
- Stek i red
- Deque i priority queue
- Heap struktura
- Set / Map (STL)
- DSU (Union-Find)
- Binarna stabla i BST
- Fenwick i segmentno stablo
- Trie i hash strukture
□ Uči postupno — svaka nova struktura se oslanja na prethodne.
Ključne reči: strukture podataka, stek, red, heap, DSU, segmentno stablo, algoritmi, C++, takmičarsko programiranje
| Prethodno |<Brzo stepenovanje |
Sledeće Uvod u strukture i unije>| |
Mapa učenja — Strukture podataka
- Disjoint Set Union (DSU) – teorija i osnovne operacije
- Fenwick stablo (BIT) – zbirovi uz izmene
- Mapa učenja — Strukture podataka
- OSNOVNE STRUKTURE PODATAKA
- Povezane liste
- Red (Queue)
- Red sa prioritetom (priority_queue) u C++
- Segmentno stablo – upiti na intervalu
- Skupovi i mape u C++: set, multiset i map
- Stek (Stack) – osnovna struktura podataka
- Uvod u strukture i unije
- Uvod u vektore