Orice algoritm lucrează cu date (numere întregi, reale, şiruri de caractere etc.). Referitor la acestea, în informatică, s-au cristalizat anumite concepte fundamentale, pe care le voi prezenta în continuare. Definiţie: Printr-un tip de dată înţelegem o mulţime cu elemente numite valori. De sxemplu:{-32768, -32767,…0,1, …32767} este omulţime de numere întregi. Atunci cînd nu există posibilatea de confuzie, putem nota mulţimea de mai sus astfel: [-32768,32767]. În Turbo Pascal un astfel de tip se numeşte integer şi este predefinit. Pe mulţimea valorilor unui tip se definesc operaţiile asociate tipului. De exemplu, pentru tipul integer se definesc operaţiile de adunare, scădere, înmulţire etc. Pentru fiecare tip se defineşte modul în care se memorează valorile sale. De exemplu, pentru tipul integer valorile se memorizează utilizînd codul complementar şi se folosesc 2 octeţi consecutivi. Pentru a lucra cu date de un anumit tip se folosesc variabile. O variabilă se caracterizează prin: tip (natura datelor şi modul de memorare), nume (prin care aceasta se adresează) şi adresă (număr de ordine al primului octet în care se reţin datele, memoria internă fiind privită ca o succesiune de octeţi numerotaţi). Tipurile de date pot fi simple şi structurate. Limbajele de programare evoluate utilizează din plin tipurile de date. Mai mult, unele din ele permit programului, folosind tipurile existente, să definească noi tipuri de date. Noţiunea de tip de date este strînsă legată de un anumit limbaj de programare. În situaţia în care se renunţă la această legătură, se ajunge la o altă noţiune mult utilizată şi anume cea de structură de date. De exemplu, mulţimea este o structură de date. În limbajul Turbo Pascal există tipul mulţime (set). Alte limbaje (de exemplu C) nu cunosc acest tip. Aceasta nu înseamnă că în C nu vom putea lucra cu mulţimi. Variabilele declarate în secţiunea var a unui program sau subprogram se numesc variabile statice. Numărul variabilelor statice se satabileşte în momentul scrierii programului şi nu poate fi schimbat în timpul execuţiei. Există însă situaţii în care numărul necesar de variabile nu este cunoscut din timp. De exemplu, presupunem că este necesară prelucrarea datelor referitoare la persoanele care formează o listă de aşteptare (o coadă) la o casă de bilete. Lungimea cozii este nedefinită. De fiecare dată cînd apare o persoană nouă, trebuie să se creeze o variabilă de tipul respectiv. După ce persoana pleacă – variabile evine inutilă. Variabilele care sunt create şi eventual distruse în timpul execuţiei programului se numesc variabile dinamice O structură de date este formată din datele propriu-zise şi relaţiile dintre ele. În funcţie de modul de organizare, o structură de date poate fi implicită sau explicită. Tablourile, şirurile de caractere, articolele, fişierele şi mulţimile sunt structuri implicite de date. Relaţiile dintre componentele acestor structuri sînt predefinite şi nemodificabile. De exemplu, toate componentele unui şir de caractere au un nume comun, iar caracterul s[i+1] este succesorul caracterului s[i] în virtutea poziţiei ocupate. Structurile de date se clasifică în două mari categorii: statice şi dinamice. Criteriul de clasificare este dat de modul de alocare a memoriei interne. Întrucît structura tablourilor, şirurilor de caractere, articolelor, mulţimilor, fişierelor nu se modifică în timpul execuţiei oricărul program sau subprogram, structurile respective reprezintă structuri statice de date.
§1. Tabloul
Fie Ani={1,2,….ni} mulţimea primelor ni numere naturale. Fie M=An1 x An2 x…..x Ank produsul cartezian a k astfel de mulţimi. Definiţie: Se numeşte tablou o funcţie f:M→T, unde T este o mulţime oarecare. Numărul k este dimensiunea tabloului. Dacă k=1 tabloul se mai numeşte şi vector. Vectorul are n1 componente. Dacă k=2 tabloul se mai numeşte şi matrice. Matricea are n1xn2 elemente. Majoritatea limbajelor de programare evoluate au implementat tipul tablou (array în Turbo Pascal). Pentru a identifica elementele unui tablou se folosesc indicii. Exemplul 1: Distanţa dintre două mulţimi în plan se consideră distanţa dintre două puncte ale acestor mulţimi, situate cel mai aproape unul de altul. Aflaţi distanţa dintre două mulţimi de puncte date. (pr.38, §5, [1])
