Duomenų struktūra yra duomenų organizavimo ir saugojimo atmintyje būdas, kuris leidžia efektyviai pasiekti ir modifikuoti duomenis. Abstraktusis duomenų tipas (ADT) yra loginis modelis — operacijos ir jų elgsena — nepriklausančios nuo to, kaip jis yra diegiamas.
ADT aprašo operacijos egzistuoja; duomenų struktūra nusprendžia jos saugomos ir kokiu greičiu jos veikia.
ADT: Stack → push, pop, peek (LIFO behavior)
Implementations: → array-backed OR linked-list-backed
ADT: List → get(i), insert, remove
Implementations: → dynamic array OR linked list
# Both satisfy the "Stack" ADT, but have different cost profiles
stack = [] # list-backed stack
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Apsvarstymas | Klausimas, kurį reikia padaryti |
|---|---|
| Prieigos šablonas | Atsitiktine prieiga ar nuosekli? |
| Mutacijos | Dažnas įterpimas/šalinimas viduryje? |
| Sutvarkytumas | Surūšiuota, FIFO, LIFO, ar nėra? |
| Paieškai | Pagal indeksą ar pagal raktą? |
Teisingas pasirinkimas yra tas, kurio įprastos operacijos yra pigios jūsų darbui.
Pasirinkę netinkamą struktūrą O(1) operacija paverčiama į O(n), o tai gali padaryti kodą tūkstančius kartų lėtesnį dirbant su dideliais duomenimis.
Galvodami ADT sąlygomis, galite pirmiausia protauti apie elgseną, o vėliau pakeisti diegimą iš naujo neparašydami šaukėjų.
IT pokalbių klausimų biblioteka su išsamiais atsakymais — nuo Junior iki Senior.
Paaukoti