structuri de date abstracte
în informatică, un tip de date abstract (ADT) este un model matematic pentru tipurile de date în care un tip de date este definit punctul de vedere al unui utilizator al datelor, în special în ceea ce privește valorile posibile, operațiile posibile asupra datelor de acest tip și comportamentul acestor operațiuni. Acest lucru contrastează cu structurile de date, care sunt reprezentări concrete ale datelor și sunt punctul de vedere al unui implementator, nu al unui utilizator.
formal, un ADT poate fi definit ca o „clasă de obiecte al căror comportament logic este definit de un set de valori și un set de operații”; acest lucru este analog cu o structură algebrică din matematică. Ceea ce se înțelege prin „comportament” variază în funcție de autor, cele două tipuri principale de specificații formale pentru comportament fiind specificație axiomatică (algebrică) și un model abstract; acestea corespund semanticii axiomatice și, respectiv, semanticii operaționale a unei mașini abstracte. Unii autori includ, de asemenea, complexitatea computațională („cost”), atât în termeni de timp (pentru operații de calcul), cât și spațiu (pentru reprezentarea valorilor).
motivul pentru care folosim structuri abstracte este pentru că folosesc eficient memoria bazată pe proiectarea datelor stocate în ele. Cu cantități foarte mari de date sau date care se schimbă foarte frecvent, structura datelor poate face o diferență uriașă în eficiența (timpul de rulare) al programului dvs. de computer.
într-un limbaj mai comun, o structură abstractă a datelor este doar un aranjament de date pe care l-am construit într-un aranjament ordonat.
o imagine de ansamblu perfect minunat
unele tipuri de structuri de date abstracte
evaluate de IB
- structura de date statice și dinamice
- matrice
- matrice bidimensionale
- stivă
- coadă
- lista legate
- copac
- binar arborele
- colecții
- recursivitate
nu este evaluat de Ib, dar ar trebui să le cunoașteți
- liste
- dicționare
- seturi
- tuplu
operații de bază ale structurilor de date
am găsit acest diapozitiv excelent de la Simon allardice.
compararea diferitelor structuri de date
| structura de date | puncte forte | puncte slabe |
| matrice | inserarea și ștergerea elementelor, iterarea prin colecția | sortarea și căutarea, inserarea și ștergerea – mai ales dacă introduceți și ștergerea la începutul sau la sfârșitul matrice |
| lista legat | indexare directă, ușor de a crea și de a folosi | acces direct, căutarea și sortarea |
| stivă și coadă | proiectat pentru LIFO / FIFO | acces direct, căutarea și sortarea |
| arbore binar | viteza de inserare și ștergere, viteza de acces, menținerea ordine sortate | unele aeriene |
- structurile fixe sunt mai rapide / mai mici
- când vă gândiți dacă ar trebui să utilizați o structură de date abstractă, ar trebui să vă întrebați: ce conține cele mai multe date și ce conține cele mai frecvent modificate date?
Compararea structurilor de date statice vs dinamice
această comparație este utilizată din manualul nostru de informatică.
| structură statică de date | structură dinamică de date |
| ineficientă deoarece este alocată memorie care poate să nu fie necesară. | eficient deoarece cantitatea de memorie variază în funcție de necesități. |
| acces rapid la fiecare element de date ca locația de memorie este fixat atunci când programul este scris. | acces mai lent la fiecare element ca locația de memorie este alocată la run-time. |
| adresele de memorie alocate vor fi contigue atât de rapid de accesat. | adresele de memorie alocate pot fi fragmentate atât de lent pentru a accesa. |
| structurile sunt de dimensiuni fixe, ceea ce le face mai previzibile pentru a lucra cu. De exemplu, ele pot conține un antet. | structurile variază ca mărime, deci trebuie să existe un mecanism pentru cunoașterea dimensiunii structurii curente. |
| relația dintre diferitele elemente ale datelor nu se schimbă. | relația dintre diferitele elemente de date se va schimba pe măsură ce programul este rulat. |
alegerea structurii de date pentru a utiliza
Acest grafic este folosit cu recunoștință extraordinară de la Departamentul de Informatică Dartford Grammar School.
standardele
- identifică o situație care necesită utilizarea gândirii recursive.
- identificați gândirea recursivă într-o soluție de problemă specificată.
- Trace un algoritm recursiv pentru a exprima o soluție la o problemă.
- descrie caracteristicile unei matrice bidimensionale.
- construi algoritmi folosind matrice bidimensionale.
- descrieți caracteristicile și aplicațiile unei stive.
- construi algoritmi folosind metodele de acces ale unei stive.
- descrieți caracteristicile și aplicațiile unei cozi.
- construi algoritmi folosind metodele de acces ale unei cozi.
- explicați utilizarea matricelor ca stive statice și cozi.
- descrieți caracteristicile și caracteristicile unei structuri de date dinamice.
- descrieți modul în care listele legate funcționează logic.
- schițează liste legate (simple, duble și circulare).
- descrieți caracteristicile și aplicațiile unei colecții.
- construi algoritmi folosind metodele de acces ale unei colecții.
- discutați necesitatea subprogramelor și colecțiilor în cadrul soluțiilor programate.
- construi algoritmi folosind pre-definite subprograme, matrice unidimensionale și / sau colecții.
- descrie modul în care copacii funcționează logic (atât binar, cât și non-binar).
- definiți termenii: părinte, stânga-copil, dreapta-copil, subarborele, rădăcină și frunze.
- Stat rezultatul inorder, postorder și preorder copac traversal.
- schițează copaci binari.
- definiți termenul structură dinamică de date.
- comparați utilizarea structurilor de date statice și dinamice.
- sugerează o structură adecvată pentru o anumită situație.
Leave a Reply