"Nu pe ansamblu, să caute unitate, ci în uniformitatea împărțirii."
Kozma Prutkov.
O serie de pointeri ca tip de date și ca structură de date
Un șir de indicatori (MU) este cea mai simplă structură de date, în care se face o distincție între ordinea fizică și logică a elementelor. Modul în care sunt organizate datele este deja clar din definiția însăși: este o matrice, fiecare element al căruia conține un pointer la o variabilă (obiect).
Fig. 62,1. Diferența dintre o serie de indicatori este tipul și structura datelor
Dacă aceasta este scrisă în termenii unei definiții contextuale a variabilelor, atunci ajungem, de exemplu
Variabila p trebuie interpretată ca o matrice (operație []), fiecare element al căruia este un pointer la o variabilă de tipul double (operație *). Variabila p este o serie de pointeri ca tip de date, dar nu este o structura de date. Pentru a fi transformată într-o structură de date, aceasta trebuie să fie completată cu variabile identificabile și indicatori (link-uri).
Varietatea opțiunilor pentru implementarea rețelelor pointerilor apare din mai multe motive:
· Deoarece o serie de pointeri, variabile specificate și link-uri (pointeri) pot fi specificate static (în textul programului) sau create dinamic în timpul executării;
· Interpretarea Twofold a indicatorului ca un pointer la o variabilă separată și o variabilă matrice (un șir de caractere), puteți crea LED-uri unidimensionale - matrici de pointeri la variabile și bidimensionale - matrici de indicii pentru matrice (rândurile) ale variabilelor;
· Variabilele specificate pot fi "proprietatea" structurii de date, dar matricea de pointeri se poate referi la variabilele (obiectele) care sunt componente ale altor structuri de date.
Principala dificultate este că în toate cazurile se utilizează aceleași tipuri de date, iar tipul specific de structuri de date este determinat de contextul utilizării lor în textul programului.
Tipuri de date utilizate la lucrul cu tablouri de indicatori
Un tip de date pe care am menționat deja este o serie de indicatori, o variabilă a formulei int * p []. În plus, este utilizat un alt tip de tip int ** pp. care poate fi definită în formă generală ca un pointer la un pointer.
Fig. 6 2 .2. Varietatea interpretărilor tipului de date int ** pp
Reamintim că în C există două interpretări ale pointerului, care pot fi diferențiate numai în textul programului de tipul operațiilor aplicate pe pointer (adică numai în contextul utilizării acestuia):
· Interpretarea tradițională a indicatorului ca referință la o singură variabilă corespunde funcționării adresării indirecte cu pointerul * pp;
Pointerul la pointer permite astfel maximum patru interpretări. În același timp, pentru fiecare dintre ele trebuie să fie creată (inițializată) propria sa structură de date. Situația este agravată de faptul că programatorul trebuie să urmărească structura de date și operațiunile de pe ea (compilatorul nu face acest lucru).
int a = 5, b = 10; int * p = a; int ** pp = p;
int a [10] = 5, b [10] = 10; int * p = a; int ** pp = p;
pentru (int i = 0; i<10;i++) (*pp)[i]=0;
A doua opțiune este, de asemenea, destul de exotică - un pointer la un pointer la o gamă liniară de variabile. În expresiile utilizate în această structură de date există paranteze prioritare, deoarece operația indirectă din primul nivel precede operația de indexare a celei de-a doua.
În alte cazuri, tipul de date int ** este folosit pentru a lucra cu arrays of pointers. Interpretarea clasică - un pointer către o serie de pointeri către obiecte individuale folosește ordinea naturală a operațiilor * p [i] pentru a accesa obiectele ce urmează a fi arătate.
pentru (int s = 0, i = 0; i<10;i++) s=s+*pp[i];
O serie de indicatori pentru rețelele liniare ale variabilelor este o structură de date bidimensională și utilizează indexarea dublă. Funcțional, este echivalentul unei matrice bidimensionale.
pentru (int s = 0, i = 0; i<3;i++)
pentru (int j = 0;<4;j++) s=s+pp[i][j];
Ansambluri statice și dinamice de indicatori
O altă sursă de diversitate este modul în care se formează aceste structuri de date. O matrice statică de indicii generate în timpul traducerii: variabilele (indicii de matrice și variabile ukazuemye) sunt definite ca un mod static variabilele numite convenționale și indicii sunt inițializate. Structura datelor este inclusă direct în codul programului și este "gata de funcționare".
pentru (i = 0; i<19; i++) pd[i] = &d[i];
În cele din urmă, dacă se formează o serie de pointeri ca structură de date dinamică, în timpul funcționării programului se creează o matrice dinamică dinamică. Noua operație returnează un pointer în zona de memorie care conține indicii, ca rezultat. tip int **. care este stocată într-o variabilă de același tip.
pp = newint * [20]; // memorie pentru o serie de pointeri
pentru (i = 0; i<19; i++)
pp [i] = p; // poate fi pp [i] = int int; * pp [i] = i;
O serie de pointeri. Ordinea fizică și logică
Când lucrați cu o serie de indicii, se folosesc două contexte:
- pp [i] -i-pointer în matrice;
- * pp [i] -valoarea variabilei i specificate.
Algoritmii pentru lucrul cu o serie de indicatori și o matrice obișnuită sunt foarte asemănătoare în aspect. Diferența este că plasarea datelor într-o matrice convențională corespunde ordinea lor fizică în memoria de secvență, și o serie de indicii permite generarea ordinea logică a elementelor în conformitate cu indicii pentru a le localiza. Apoi, schimbarea secvenței (includere, excludere, prin care se dispune de permutare), care, în matrice normală este de a muta elementele însele, într-o serie de indicii trebuie să fie însoțite de operațiuni pe indicii pentru ele. Avantaje evidente apar atunci când ukazuemye variabile în sine sunt suficient de mari sau mutați-le imposibil pentru orice motiv (de exemplu, acestea sunt menționate la alte părți ale programului). Pentru comparație, oferim funcțiile de sortare a unei matrice și a unei game de indicii.
// --- Sortarea unui matrice și a unui șir de indicii
void sort1 (dublu d [], int sz)
pentru (k = 0, i = 0; i void sort2 (dublu * pd [])
pentru (k = 0, i = 0; pd [i + 1] 1 = NULL; i ++) dacă (* pd [i]> * pd [i +1]) // Comparați variabilele care vor fi specificate c = pd [i]; pd [i] = pd [i + 1]; pd [i + 1] = c; k = 1;> Dacă o matrice dinamică de indicatori se referă la un set de "deja cunoscut", adică nu este creată și nu este deținută de variabile (obiecte), este oportună considerarea acesteia ca fiind o colecție care are propria sa ordine logică. De exemplu, luați în considerare o funcție care creează o serie de indicatori pentru valori pozitive ordonate pozitiv, luate dintr-o matrice. În ceea ce privește orice matrice dinamică, toate concluziile privind dimensiunea sa sunt valabile pentru o gamă de indicatori: în acest caz, aceasta poate fi calculată în avans. Rezultatul funcției este de tip double ** - un pointer într-o matrice dinamică de pointeri creată în interiorul funcției. // -------- O matrice dinamică de indicatori // pe elementele pozitive ordonate ale matricei originale dublu ** crea (dublu în [], int n)
int i. j. m; // Calculați dimensiunea pentru (i = 0, m = 0; i dublu ** pp = dublu nou * [m + 1]; // Creați DMU pentru (i = 0, j = 0; i dacă (în [i]> 0) pp [j ++] = în [i]; // element pozitiv // --- Matricea dimensiunii arbitrare - o serie de pointeri la matrice încărcarea dublă ** (char nm [], int n. int m)
dacă (fd == NULL) returnați NULL; fscanf (fd, "..", n, m); // Citirea dimensiunilor dublu ** pp = dublu nou * [n]; // Crearea DMU din prima dimensiune pp [i] = nou dublu [m]; // Creați DM-uri liniare (șiruri de caractere) pentru (int j = 0;
O matrice dinamică a variabilelor (obiecte)
O matrice dinamică de indicatori pentru tablouri de variabile
Fig. 6 2 .3. Reprezentarea unei matrici cu dimensiuni variabile în formă de DMU pe rânduri
Articole similare
Trimiteți-le prietenilor: