După cum rezultă din definiția de mai sus, structurarea datelor presupune existența (sau stabilirea) unor relații (legături) între ele. În funcție de natura acestor relații, se pot distinge câteva caracteristici de clasificare a structurilor de date.
Primul dintre acestea este relația de ordine. În ordinea structurilor de date sunt împărțite în ordine și neordonate.
Un exemplu de structuri dezordonate sunt seturile - ele nu definesc ordinea elementelor; singurul lucru care poate fi setat pentru orice date specifice este că aparțin (sau nu aparțin) setului selectat.
Următoarea caracteristică de clasificare a structurilor este omogenitatea. Omogene includ structuri care conțin date elementare de un singur tip. Structurile incompetente combină date de diferite tipuri. Exemple de structuri omogene sunt: matrice, seturi, stive. Structurile independente includ înregistrări.
Un alt semn este natura relației dintre elemente. Prin subordonarea reciprocă a elementelor, structurile de date sunt împărțite în liniare și neliniare.
În structurile liniare, toate elementele sunt egale. Acestea includ o matrice, un set, un stiva, o coadă.
În structurile neliniare există relații de subordonare între elemente sau pot fi conectate prin condiții logice. Acestea includ copaci, grafice, cadre.
Pe baza caracteristicilor de clasificare identificate, vom lua în considerare și caracteriza unele structuri de date.
Un solid este o colecție liniară ordonată de date omogene.
· Termenul "ordonat" înseamnă că elementele matricei sunt numerotate;
· Termenul "liniar" indică egalitatea tuturor elementelor;
· Termenul "omogen" înseamnă următoarele: în cazul în care o matrice este formată din date elementare, aceasta poate fi doar una de un anumit tip, de exemplu o serie de numere sau o serie de simboluri; Cu toate acestea, este posibil ca elementele matricei să fie date complexe (structurale), de exemplu, o serie de matrice - în acest caz "omogenă" înseamnă că toate elementele au aceeași structură și dimensiune.
Numărul de indici care determină poziția unui element într-o matrice se numește dimensionalitatea matricei.
Deci, dacă indicele este unic, matricea este denumită unidimensională; adesea o astfel de matrice este denumită și un vector, un rând sau o coloană. Pentru a scrie elemente dintr-o matrice unidimensională, utilizați notația mi; în limbile de programare, notația m (i) sau m [i] a fost adoptată.
O matrice a cărei elemente au doi indici este numită matrice bidimensională sau matrice. Exemplu de desemnare: G [3,5]; primul indice este numărul liniei, iar al doilea indice este numărul coloanei, la intersecția căruia se află acest element.
Arrays cu trei indici se numesc matrice tridimensionale, etc. Dimensiunile maxime ale unei matrice pot fi limitate la sintaxa unor limbi de programare sau nu pot avea astfel de limitări.
Valoarea maximă a indexului determină dimensiunea matricei. Dimensiunea matricei este indicată în blocul de descriere a programului, deoarece cantitatea necesară de memorie este rezervată executării programului pentru stocarea elementelor matrice. Dacă în timpul execuției programului mărimea matricei nu se modifică (sau nu poate fi schimbată), atunci în acest caz se vorbește despre matrici de dimensiune fixă; dacă determinarea dimensiunii matricei sau a modificării acesteia are loc în cursul programului, atunci astfel de rețele se numesc dinamice (descrise dinamic).
Un set de operații permise pe elementele unei matrice este determinat de tipul de date (elementar sau structurat) din care se formează matricea. În unele limbi de programare, o operație de atribuire M este definită pe o matrice ca întreg: = <выражение> - In acest caz, toate elementele de matrice se atribuie aceeași valoare, egală cu valoarea calculată a expresiei; operațiune de atribuire este de asemenea posibil ca doua identice tip, mărime și dimensiune matrice M2 = M1 - atribuirea valorii se efectuează element înțelept (M2 (i, j, k): = M1 (i, j, k) ..).
Un loc special este ocupat de matrice de caractere - ele sunt numite siruri de caractere sau date de sir (de exemplu, String type in PASCAL'e). Cu ei, este posibil un întreg set de operațiuni, nedefinit pentru date de caracter unic. Mai întâi de toate, aceasta este operația de concatenare (combinare) șiruri de caractere cu formarea unei linii noi. În plus, există operațiuni pentru înlocuirea unei părți a liniei, precum și determinarea caracteristicilor sale numerice.
Diferența dintre o coadă și o teanc este că informațiile sunt extrase în ordinea "first-in-out-out", adică din partea de jos a stivei.
Astfel, datele au un ordin de localizare și sunt egale în drepturi - prin urmare, structura este ordonată și liniară. Cu toate acestea, în cazul general, celulele stivei pot conține date de diferite tipuri - în conformitate cu această caracteristică structura nu este omogenă.
Metoda descrisă de organizare a datelor este convenabilă atunci când lucrați cu subrutine, întrerupeți întreținerea și rezolvând multe sarcini.
Un arbore sau o ierarhie este un exemplu de structură neliniară. În el, elementul fiecărui nivel (cu excepția celei mai înalte) intră într-un singur element al nivelului următor (mai mare). Elementul celui mai înalt nivel se numește rădăcină, iar cel mai mic nivel se numește frunze.
O diagramă a unei astfel de structuri este prezentată în figură. Elementele individuale pot fi omogene sau nu. Un exemplu al unei astfel de organizații este structurile de fișiere de pe dispozitivele de stocare externe ale computerului.
Adesea, relația dintre date este reprezentată ca un grafic - o colecție de puncte și linii în care fiecare linie conectează două puncte. În domeniul informaticii, punctul primește semnificația elementului de structură (sistem, date etc.), iar liniile sunt semnificația relației dintre elemente. Să facem cunoștință cu un număr de termeni legați de utilizarea graficelor.
Punctele sunt numite nodurile graficului, liniile sunt numite margini. Dacă o margine se unește cu două vârfuri, atunci spunem că o margine este incidentă cu aceste vârfuri, iar vârfurile se consideră a fi adiacente. Numărul de muchii care intră în contact cu un vârf este numit gradul unui vârf. Dacă două margini intră în contact cu aceeași pereche de vârfuri, ele sunt numite multiple. O margine care coincide cu ambele vârfuri se numește o buclă.
În Fig. 6.3, a. graficul 1 este dat de o listă de vârfuri și o listă de margini în care pentru fiecare margine este indicată o pereche de vârfuri incidente: a (1,2); b (1,4); cu (2, .4); 6 (2,3); e (3.4); f (2,3); g (4.4).
Două perechi adiacente de vârfuri: (2,3), (2,4), (1,2), (1,4), (3,4). Marginea q este o buclă; Marginile d și f sunt multiple. Gradele de puncte 2 și 4 sunt 4; vârfurile sunt 3 -3; vârfuri 1 - 2.
Marginea care unește vârfurile poate avea o direcție - atunci se numește orientată și este reprezentată de o săgeată. Un grafic în care toate laturile sunt orientate se numește orientat; Marginile sale sunt deseori numite arce. Arcurile sunt numite multiple dacă conectează aceleași vârfuri și coincid în direcție. În desemnarea unui arc, vârful de la care începe, de exemplu, în Fig. 6.3, b (2.3).
O rută este o secvență de margini în care sfârșitul marginii precedente coincide cu începutul următorului, de exemplu, a. c, e pe graficul 1. Un traseu în care vertexul terminal coincide cu vârful inițial se numește un ciclu, de exemplu c. e, d pe graficul 2. Se spune că un grafic este conectat dacă există un traseu între oricare dintre cele două vârfuri. Un grafic conectat cu n noduri conține cel puțin η-1 margini.
Conform clasificărilor considerate anterior, graficul este o structură ordonată, neliniară, neomogenă. Conceptul graficului, datorită clarității sale și a generalității ridicate în informatică, servește drept principalul mijloc de descriere a structurilor de date, a sistemelor, a ordinii de executare a acțiunilor. Un exemplu este diagrama bloc a programului.
Din punct de vedere al utilizării practice, un alt tip de date care reprezintă o structură comandată, liniară, neomogenă este de mare interes. O astfel de structură poate fi considerată ca o serie de date structurate eterogene.
O structură este numită tabelă, iar linia sa individuală este o înregistrare (înregistrare logică). Având în vedere importanța deosebită a acestei structuri, aceasta va fi analizată în detaliu.
Înapoi la cuprins: Fundamentele teoretice ale informaticii
Articole similare
Trimiteți-le prietenilor: