06. Algoritmi de Prelucrare a Fisierelor Binare

6 Algoritmi de prelucrare a fişierelor binare

Din punct de vedere al operaţiilor de gestiune solicitate de diverse aplicaţii, fişierele binare se pot grupa în: fişiere care nu sunt actualizate (ţinute la zi) şi fişiere care sunt actualizate. De obicei, fişierele din prima grupă se regăsesc în aplicaţii matematice sau ca fişiere temporare şi de tranzacţii în aplicaţii de gestiune economică. Fişierele din cea de-a doua grupă sunt, de obicei, fişiere permanente (principale) în aplicaţii de gestiune economică şi au particularităţi de proiectare, referitoare, în special, la asigurarea ştergerii şi adăugării de articole.

6.1 Caracteristici generale ale algoritmilor de prelucrare a fişierelor

Organizarea datelor în fişiere memorate pe medii magnetice externe presupune proiectarea unor algoritmi specifici operaţiilor de gestiune a acestora, denumiţi generic algoritmi de prelucrare a fişierelor de date. Datorită complexităţii aplicaţiilor care prelucrează fişiere este recomandată aplicarea metodei modularizării algoritmilor şi programelor. Modularizarea presupune ca, pe baza analizei problemei, să se descompună rezolvarea ei în părţi distincte, numite module, astfel încât fiecare dintre acestea să îndeplinească anumite funcţii. Descompunerea se poate realiza în mai multe faze (pe mai multe niveluri), prin metoda top-down. Criteriile de descompunere în module depind, în mare măsură, de experienţa programatorilor. Ele se referă, în principal, la: omogenizarea funcţiilor; utilizarea diverselor structuri de date; separarea funcţiilor de intrare/ieşire de funcţiile de prelucrare; utilizarea unor module deja existente; utilizarea eficientă a resurselor calculatorului (timp UC, memorie internă, periferie) etc. Modulele se implementează în program prin subprograme interne sau externe. De cele mai multe ori, o aplicaţie necesită existenţa mai multor fişiere

Algoritmi de prelucrare a fişierelor binare

active simultan, cu rol diferit (de intrare, de ieşire, de intrare/ieşire). Indiferent de numărul fişierelor utilizate, în marea majoritate a algoritmilor, logica prelucrării este coordonată, la un moment dat, de un singur fişier, obligatoriu de intrare, parcurs secvenţial, numit fişier conducător (sau director). Fişierul conducător are proprietatea că articolele lui pot fi citite logic independent de prelucrarea altor fişiere. Altfel spus, un fişier nu este conducător dacă prelucrarea articolelor sale este dependentă de existenţa (de citirea) articolului altui fişier. Accesul la datele memorate în fişierul conducător se realizează la nivel de articol. De aceea, algoritmii de prelucrare, indiferent de operaţia de gestiune, necesită utilizarea unei structuri repetitive pentru parcurgerea (parţială sau integrală) a fişierului respectiv. Algoritmii de prelucrare cu fişier conducător pot fi reprezentaţi prin schema logică generalizată, concepută modularizat, redată în figura 6.1.

Figura 6.1 Schema logică generală a unui algoritm

de prelucrare cu fişier conducător

Modulul ÎNCEPUT se realizează o singură dată, înaintea prelucrării primului articol al fişierului conducător şi cuprinde următoarele grupe de operaţii:

Operaţii iniţiale standard, obligatorii oricărui algoritm şi care includ: punerea în corespondenţă a fişierelor logice cu fişiere fizice, deschiderea fişierelor, şi, pentru anumite variante, iniţializarea unei variabile logice pentru sfârşit de fişier (SF) şi citirea primului articol.

Operaţii iniţiale specifice, facultative, existenţa lor depinzând de particularităţile problemei abordate şi care includ, în principal: iniţializări de variabile de total, afişări ale antetului, titlului şi/sau a capului de tabel pentru situaţii de ieşire etc.

Modulul PRELUCRARE se execută repetitiv şi cuprinde, pe de o parte,

Programarea calculatoarelor

totalitatea operaţiilor de prelucrare a articolului curent al fişierului conducător - operaţii specifice fiecărei probleme - şi, pe de altă parte, citirea unui articol din fişierul conducător. Ordinea celor două operaţii (citire şi prelucrare) depinde de varianta de algoritm aleasă.

Modulul SFÎRŞIT se execută o singură dată, după prelucrarea ultimului articol al fişierului conducător şi include următoarele grupe de operaţii: operaţii finale standard, corespunzând închiderii fişierelor implicate în prelucrare; operaţii finale specifice, care depind de natura problemei şi includ, de regulă: afişarea variabilelor de total, a statisticilor privind operaţiile de gestiune executate, închiderea situaţiilor de ieşire etc. Modalitatea de detectare/tratare a sfârşitului de fişier conduce la existenţa mai multor variante ale schemei generale de prelucrare cu fişier conducător, prin forme particulare ale condiţiei sfîrşit_de_prelucrare. În funcţie de variantele alese, se pot construi scheme logice valabile pentru toate tipurile de fişiere sau numai pentru fişierele binare.

Scheme valabile pentru toate tipurile de fişiere Detectarea sfârşitului de fişier, cu macrodefiniţia feof, caz în care testarea sfârşitului de fişier trebuie să urmeze după o operaţie de citire a unui articol. Algoritmul trebuie să conţină o citire iniţială în modulul ÎNCEPUT şi o citire curentă la sfârşitul modulului PRELUCRARE - (figura 6.2). Acest algoritm se poate aplica fişierelor vide sau nevide.

Figura 6.2

Scheme logice valabile numai pentru fişiere binare

r.ariadna

Text Box

Operatii initiale

r.ariadna

Text Box

Operatii finale


Detectarea sfîrşitului de fişier prin operaţia de citire, verificând rezultatul întors de funcţia de citire (fread). Dacă rezultatul este mai mic decât numărul de blocuri de date care trebuie citite, înseamnă că s-a ajuns la sfârşitul fişierului. Întrucât, uzual, la o operaţie de citire se citeşte un articol întreg, în cazul atingeri sfârşitului de fişier, rezultatul întors de funcţia fread va fi 0. Rezultatul poate fi preluat într-o variabilă pentru a fi folosit în condiţia de terminare a prelucrării (figura 6.3) sau poate fi verificat direct, folosind apelul funcţiei fread în expresia (condiţia) care controlează sfârşitul prelucrării (figura 6.4). În ambele variante fişierul conducător este binar, vid sau nevid.

START

STOP

Da

SF = fread (…)

SF != 0

Operaţii finale

Nu

Operaţii iniţiale

Prelucrare articol

SF = fread (…)

Figura 6.3

Figura 6.4

r.ariadna

Text Box

Operatii initiale

r.ariadna

Text Box

Operatii finale

r.ariadna

Text Box

Operatii initiale

r.ariadna

Text Box

Operatii finale

r.ariadna

Text Box

Operatii initiale

r.ariadna

Text Box

Operatii finale


Prelucrarea unui număr cunoscut de articole, prin determinarea în modulul ÎNCEPUT a numărului de articole din fişierul conducător se regăseşte în figura 6.5. Limbajul C nu oferă o funcţie standard pentru calcularea numărului de articole dintr-un fişier binar, deoarece, din punctul de vedere al limbajului, fişierele nu conţin articole. Din punctul de vedere al utilizatorului, cunoscând dimensiunea unui articol, se poate calcula numărul de articol de fişier, împărţind lungimea acestuia la lungimea unui articol (ambele măsurate în număr de octeţi). Lungimea fişierului este egală cu poziţia curentă, atunci când pointerul de citire se află la sfârşitul fişierului. Pentru aflarea numărului de articole, se foloseşte secvenţa următoare:

p=ftell(f); fseek(f,0,SEEK_END); l=ftell(f); nr=l/sizeof(tip_articol); fseek(f,p,SEEK_SET);

unde: variabila p, de tip long reţine poziţia curentă în fişier; f este fişierul a cărui lungime trebuie calculată; variabila l reţine poziţia curentă (în număr de octeţi faţă de începutul fişierului, deci lungimea fişierului măsurată în octeţi); variabila nr va primi ca valoare numărul de articole din fişier; tip_articol este tipul articolelor din fişier (din punctul de vedere al utilizatorului). Împărţirea se face exact, deoarece fişierul conţine un număr întreg de articole – utilizarea acestei secvenţe asupra unui fişier care conţine articole de alt tip (sau are conţinut de altă natură) va duce la rezultate incorecte.

Figura 6.5

r.ariadna

Text Box

Operatii initiale

r.ariadna

Text Box

Operatii finale


Caracteristica generală a algoritmilor de prelucrare cu fişier conducător este parcurgerea secvenţială a fişierului conducător şi efectuarea unor prelucrări în funcţie de fiecare articol citit din acesta. Problema care se pune este detectarea sfârşitului de fişier. În C, macrodefiniţia feof nu face decât să furnizeze valoarea indicatorului de sfârşit de fişier, care este setat de operaţia de citire; în program, citirea trebuie să apară înaintea verificării sfârşitului de fişier. Forma generală a algoritmului este:

<citire articol> while(!feof(f)) { <prelucrare articol citit> <citire articol> }

Exemplu:

Crearea şi consultarea unui fişier text care memorează elemente întregi, folosind funcţia feof pentru gestionarea sfârşitului de fişier. La crearea fişierului, fişier conducător este fişierul standard de intrare. La afişare, conducător este fişierul f.

#include<stdio.h> #include<conio.h> void main() { FILE *f; int x; long dim; clrscr(); f=fopen("numere.dat","w+"); scanf("%d",&x); while(!feof(stdin)) {fprintf(f,"%d\n",x); scanf("%d",&x);} fseek(f,0,SEEK_SET); fscanf(f,"%d",&x); while(!feof(f)) {printf("%d\t",x); fscanf(f,"%d",&x);} fclose(f); getch();}

Acelaşi exemplu, folosind fişier binar:

#include<stdio.h> #include<conio.h> void main() { FILE *f; int x,g; long dim; clrscr(); f=fopen("numere.dat","wb+"); scanf("%d",&x); while(!feof(stdin)) {fwrite(&x,sizeof(x),1,f); scanf("%d",&x);} fseek(f,0,SEEK_SET); fread(&x,sizeof(x),1,f); while(!feof(f)) {printf("%d\t",x); fread(&x,sizeof(x),1,f);} fclose(f); c=getch();}


Fişierele utilizate într-o aplicaţie informatică au rol diferit în procesul prelucrării, în funcţie de scopul lor: de intrare, de ieşire, de intrare/ieşire, temporare, de tip listă etc. Aceste caracteristici conduc la algoritmi specifici fiecărei operaţii de gestiune în parte (creare, populare, consultare şi actualizare), fiind însă variante derivate din schema generală a unui algoritm de prelucrare cu fişier conducător. Deoarece aplicaţiile informatice din domeniul economic, social, administrativ etc. utilizează, cu predilecţie, fişiere cu articole de aceeaşi structură (sau un număr mic de structuri diferite), alegând limbajul C, se poate aprecia că cele mai performante sunt fişierele binare, ale căror articole sunt date declarate ca structuri (folosind tipul de date struct). Această alegere este motivată din următoarele puncte de vedere:

descrierea articolelor este apropiată atât descrierii naturale a structurii unei entităţi din lumea reală (formată din câmpuri cu nume, lungime, reprezentare internă proprie, semnificaţie şi factor de repetabilitate diferite), cât şi descrierii din alte limbaje;

există posibilitatea de a descrie explicit mai multe structuri pentru articolele aceluiaşi fişier (articole cu structură variabilă);

operaţiile de acces la înregistrări se realizează cu viteză mare, datorită lipsei conversiilor la transferul între memoria principală şi memoria externă. Fişierele cu conţinut de tip text sunt recomandate a fi utilizate ca fişiere de ieşire, pentru realizarea de liste, situaţii finale, rapoarte etc., fiind rezidente pe disc, în general, până la listarea lor la imprimantă. Fişierele cu conţinut de tip text pot constitui şi sursa de creare a fişierelor binare, dacă acestea au fost populate cu date, fie prin editoare de texte, fie prin alte limbaje (Cobol, Fortran, Basic, Pascal), sisteme de gestiune a bazelor de date (DBase, FoxPro, Oracle etc.), constituind unicul mijloc de compatibilitate directă.

6.2 Algoritmi de prelucrare a fişierelor binare care nu necesită actualizare

Asupra fişierelor binare care nu necesită actualizare se realizează, de obicei, operaţiile de creare (populare) şi consultare. Dintre operaţiile de actualizare pot fi realizate, fără mari complicaţii, modificarea şi adăugarea densă de articole.

Popularea fişierelor se realizează prin preluarea datelor fie din alte fişiere primare (cu conţinut binar sau de tip text), fie de la tastatură (popularea interactivă). În ultimul caz, cel mai des întâlnit în practică, fişierul conducător corespunde mulţimii datelor introduse de la tastatură. Articolele sunt preluate câmp cu câmp, neexistând posibilitatea citirii unei variabile de tip articol şi, în plus, introducerea unei date este adesea însoţită de proceduri de validare specifice, cu reintroducerea ei în cazul unei erori. Sfârşitul introducerii datelor de la tastatură (şi implicit al procesului de populare a fişierului) poate fi:

De tip chestionar, prin consultarea utilizatorului, privind continuarea sau nu a introducerii articolelor. Pentru un volum mare de date, varianta prezintă dezavantajul


măririi timpului de prelucrare. Convenţional, prin introducerea pentru primul câmp din articol a unei valori

prestabilite, cu semnificaţie de sfârşit de prelucrare. Standard, prin introducerea caracterului CTRL-Z, cu rol de sfârşit de fişier

text. Schema logică a algoritmului de prelucrare este similară celei din figura 6.2., cu următoarele particularităţi:

• modulul ÎNCEPUT are ca ultime operaţii, afişarea numelui primului câmp din articol şi citirea valorii sale;

• modulul PRELUCRARE începe cu citirea următorului câmp, urmată de citirea celorlalte câmpuri (eventual cu validările stabilite) şi se termină cu afişarea numelui primului câmp şi cu citirea valorii acestuia (pentru articolul următor) (similar operaţiei din modulul ÎNCEPUT). O altă problemă a populării fişierelor binare o reprezintă aşezarea articolelor pe suportul extern. Din acest punct de vedere se întâlnesc două modalităţi:

Populare densă, prin care articolele se scriu unul după altul, în ordinea în care au fost furnizate, fără a se lăsa locuri libere (acces secvenţial). Pentru fişierele care nu necesită actualizare acesta este tipul recomandat.

Populare aleatoare, prin care articolele sunt scrise în casetele (virtuale) ale căror numere relative sunt furnizate explicit de utilizator (acces direct). Scrierea unui articol se realizează după poziţionarea pe numărul relativ dorit. La populare, nr_relativ nu este limitat decât de spaţiul existent pe suportul extern. Metoda are dezavantajul că necesită evidenţa "articolelor vide". În cazul fişierelor care nu necesită actualizare, popularea aleatoare se recomandă numai dacă, după creare, fişierul este dens.

Pentru poziţionarea pe articolul cu numărul relativ n se foloseşte funcţia fseek astfel:

fseek(f, n*sizeof(tip_articol), SEEK_SET);

unde n este numărul relativ al articolului iar tip_articol este tipul de dată care îi corespunde. Exemplu: 1. Să se creeze cu populare densă un fişier PRODUSE.DAT cu informaţii despre producţia cantitativă într-un an, la o societate comercială. Articolele au următoarea structură logică:

Cod produs

Denumire Produs

Preţ Mediu Cantităţi lunare

1 2 ... 12

Articolele sunt introduse de la terminal, câmp cu câmp. Terminarea introducerii datelor este marcată standard, prin introducerea caracterului CTRL-Z.


#include <stdio.h> typedef struct { int cod; char denumire[20]; float pret_mediu; int cant[12]; } PRODUS; void main() { FILE* f; PRODUS x; char nume_fisier[20]; int i; //---INCEPUT--- printf("\n\nNumele fisierului: "); gets(nume_fisier); if(!(f=fopen(nume_fisier,"wb"))) printf("\n\nNu poate fi creat fisierul cu numele %s",nume_fisier); else { printf("\nCod produs: "); scanf("%d",&x.cod); //---Aici se termina operatiile initiale--- while(!feof(stdin)) { //---PRELUCRARE ARTICOL--- printf("Denumire produs: "); fflush(stdin); gets(x.denumire); printf("Pret mediu: "); scanf("%f",&x.pret_mediu); printf("Cantitate lunara:\n"); for(i=0;i<12;i++) { printf(" - luna %d: ",i+1); scanf("%d",&x.cant[i]); } fwrite(&x,sizeof(PRODUS),1,f); //---Aici se incheie prelucrarea articolului--- printf("\nCod produs: "); scanf("%d",&x.cod); } //---SFIRSIT--- fclose(f); } } Observaţii: Dacă se doreşte crearea fişierului de date cu populare în acces direct, programul este similar, cu următoarele diferenţe:

câmpul COD indică numărul relativ al articolului în fişier şi nu va fi memorat (nu va face parte din declaraţia tipului PRODUS), fiind redundant;

scrierea articolului va fi precedată de apelul funcţiei fseek(f,codt*sizeof(PRODUS),SEEK_SET);

unde codt este o variabilă independentă în care se citeşte codul de la terminal. Consultarea fişierelor are numeroase variante, în funcţie de scopul

prelucrării. După modul de regăsire a articolelor în cadrul fişierului, ea poate fi secvenţială, directă sau mixtă.


Consultarea secvenţială presupune regăsirea articolelor în ordinea în care au fost scrise pe suportul tehnic de informaţii. După numărul articolelor prelucrate, consultarea secvenţială poate fi: integrală, când se prelucrează toate articolele fişierului, începând cu primul şi terminând cu ultimul; cu selecţie, când se prelucrează numai acele articole care au una sau mai multe caracteristici comune (valori identice pentru acelaşi câmp). După numărul de caracteristici, selecţia poate fi simplă, dublă, multiplă. Pentru consultarea secvenţială se poate utiliza oricare din tipurile de algoritmi prezentaţi anterior. Exemplu: 2. Să se afişeze pe ecran conţinutul fişierului creat la exemplul 1. #include <stdio.h> typedef struct { int cod; char denumire[20]; float pret_mediu; int cant[12]; } PRODUS; void main() { FILE* f; PRODUS x; char nume_fisier[20]; int i; //---INCEPUT--- printf("\n\nNumele fisierului: "); gets(nume_fisier); if(!(f=fopen(nume_fisier,"rb"))) printf("\n\nNu poate fi deschis fisierul cu numele %s",nume_fisier); else { fread(&x,sizeof(PRODUS),1,f); //---Aici se termina operatiile initiale--- while(!feof(f)) { //---PRELUCRARE ARTICOL--- printf("\n\nCod produs:\t\t%d",x.cod); printf("\nDenumire produs:\t%s",x.denumire); printf("\nPret mediu:\t\t %7.2f",x.pret_mediu); printf("\nCantitati lunare:\t"); for(i=0;i<12;i++) printf("%3d ",x.cant[i]); //---Aici se incheie prelucrarea articolului--- fread(&x,sizeof(PRODUS),1,f); } //---SFIRSIT--- fclose(f); } }

3. Obţinerea unei situaţii cu mai multe grade de total. Pentru aceasta se stabilesc câmpuri asociate gradelor de total, numite caracteristici de grupare sau caracteristici de control. O caracteristică de control este un câmp al articolului din fişierul de date, care are aceeaşi valoare pentru mai multe înregistrări. Astfel, articolele care au valoare comună pentru o caracteristică de grupare se pot ordona pe submulţimi, formând o grupă de control. Fişierul poate constitui, în ansamblul său, caracteristica


de grupare de cel mai înalt nivel, pentru care se poate calcula totalul general. Numărul maxim de grade de total este superior cu unu numărului de

caracteristici de control stabilite. Între caracteristicile de grupare se stabileşte o relaţie de ordine ierarhică. Pentru prelucrarea fişierului, cu utilizare minimă de memorie, articolele trebuie sortate după caracteristicile de control. Acest tip de prelucrare intră în categoria consultărilor secvenţiale integrale şi urmează algoritmul de principiu din figurile 6.2 sau 6.3. Prelucrarea unui fişier sortat după criteriile enunţate, presupune existenţa unor operaţii standard, executate la schimbarea valorii fiecărei caracteristici de control stabilite:

operaţii iniţiale ale unei grupe de control prin care se iniţializează variabila de total specifică grupei; se salvează valoarea caracteristicii primului articol din grupă; alte operaţii iniţiale specifice grupei;

operaţii finale ale unei grupe de control prin care se afişează totalul calculat pentru caracteristica ce se schimbă; se cumulează totalul grupei curente la totalul grupei ierarhic superioare; alte operaţii finale specifice grupei;

condiţia de prelucrare a unei grupe de control conţine, pe lângă condiţia specifică, toate celelalte condiţii din amonte. Raportul final este listat la imprimantă, fie direct, ca fişier de ieşire, fie creat pe suport magnetic, ca fişier text, în vederea imprimării ulterioare. Structura unei pagini a raportului şi controlul trecerii la o nouă pagină trebuie asigurate de programator. În continuare (figura 6.6) se prezintă structura de principiu a unui program de obţinere a unui raport final, cu control după două caracteristici şi trei grade de total, unde cîmp_1 şi cîmp_2 sunt caracteristicile de control (câmpuri din articol), v1 şi v2 sunt variabile de lucru pentru salvarea caracteristicilor, val_art e valoarea care interesează din fiecare articol (câmp al articolului sau valoare calculată pe baza unor câmpuri ale articolului), iar TOTG, TOT1 şi TOT2 sunt variabile pentru calculul gradelor de total. Analog, se poate extinde pentru oricâte caracteristici şi grade de total.


START

STOP

Da

Citeşte articol

!feof(f)

Citeşte articol

Nu

Operaţii iniţialegenerale

Operaţii finalegenerale

Operaţii iniţialeGrupa 1

TOTG=0

TOT1=0v1=cîmp_1

! feof(f) şi v1==cîmp_1 Da

TOT2=0v2=cîmp_2

! feof(f) şi v1==cîmp_1 şi v2==cîmp_2

Operaţii iniţialeGrupa 2

Prelucrare articol

Da

TOT2+=val_artOperaţii finale

Grupa 2

TOT1+=TOT2

TOTG+=TOT1

Operaţii finaleGeupa 1

Nu

Nu

Figura 6.6 Schema logică – problema cu grade de total

Consultarea în acces direct presupune regăsirea articolului după numărul

relativ. Întrucât fişierele sunt considerate ca fluxuri de octeţi, trebuie calculată poziţia articolului dorit în fişier ca produs între numărul său relativ şi dimensiunea unui articol în octeţi (nr*sizeof(tip_articol)). Secvenţa care realizează acest lucru este:

fseek(f,nr*sizeof(tip_articol), SEEK_SET); fread(&art,sizeof(tip_articol), 1, f);


Numărul relativ este furnizat de utilizator şi trebuie să aparţină domeniului 0..dimensiune fişier-1 (dimensiunea calculată ca număr de articole). Pentru evitarea situaţiilor în care numărul relativ se află în afara acestui domeniu, se va include în program validarea apartenenţei numărului relativ la intervalul acceptat. Algoritmul de consultare în acces direct a unui fişier are un alt fişier conducător (de exemplu tastatura). Exemplu: 4. { // citire nume fisier extern f=fopen(nume_fisier, "rb"); // calculare numar de articole din fisier printf("\nNr. relativ: "); scanf("%d",&r); //citirea numarului relativ al articolului while(!feof(stdin)) { if(r>=nr_art) printf("\n Articol inexistent !"); else { fseek(f,r*sizeof(tip_articol),SEEK_SET); fread(&art,sizeof(tip_articol),1,f); // ------------------------ //PRELUCRARE ARTICOL //------------------------ } printf("\nNr. Relativ (sau CTRL-Z): "); scanf("%d",&r); } fclose(f); }

Consultarea în acces mixt utilizează o combinaţie între accesul direct şi cel secvenţial, în vederea prelucrării unui grup de articole, memorate contiguu în fişier şi selectabile printr-o condiţie. Pentru fişierele binare, metoda poate fi aplicată dacă se doreşte selectarea articolelor dintre două limite ale numerelor relative (limita inferioară - li şi limita superioară - ls). Algoritmul trebuie să verifice relaţia 0≤li≤ls≤dimensiune fişier, după care parcurgerea fişierului poate fi realizată prin orice tip de structură repetitivă. Exemplu: 5. { // citire nume fisier extern f=fopen(nume_fisier, "rb"); // calculare numar articole din fisier printf("\nLimita inferioara: "); scanf("%d",&li); // citirea nr. relativ al primului articol // din secventa printf("\nLimita superioara: "); scanf("%d",&ls); // citirea nr. relativ al ultimului articol // din secventa if((0<li)&&(li<=ls)&&(ls<=nr_art)) { fseek(f,li*sizeof(tip_articol),SEE_SET); for(i=li;i<=ls;i++)


{ fread(&art,sizeof(tip_articol),1,f); // ----------------------- // Prelucrare articol // ----------------------- } } else printf(" Nu este indeplinita conditia de limite"); fclose(f) }

Adăugarea de articole se realizează, în general, cu tranzacţii de la terminal,

similar operaţiei de populare. Pentru o corectă exploatare ulterioară, adăugarea trebuie să fie densă. Acest lucru poate fi realizat astfel:

Adăugare la sfârşit (extindere), după ultimul articol scris. Operaţia se realizează similar populării în acces secvenţial, după poziţionarea pe marcatorul de sfârşit de fişier, apelând funcţia fseek:

fseek(f,0,SEEK_END); Exemplu: 6. { // citire nume fisier extern f=fopen(nume_fisier, "rb"); fseek(f,0,SEEK_END); // pozitionare dupa ultimul // articol scris printf("Cimp 1: "); scanf("%d ",&art.cimp_1); while(!feof(stdin)) { // ----------------------------------------------- // Preluare de la tastatura a celorlalte // campuri din articol // ----------------------------------------------- printf("Cimp 1: "); scanf("%d ",&art.cimp_1); } fclose(f) }

Inserarea unor articole. Se aplică în cazul în care articolele sunt scrise în

fişier în ordinea crescătoare (descrescătoare) a valorilor unui anumit câmp. În acest caz, noul articol va fi inserat între două articole, astfel:

se caută (cu un algoritm secvenţial, binar etc.) poziţia k în care trebuie inserat noul articol;

se copiază, glisând cu o poziţie spre dreapta, toate articolele de la sfârşitul fişierului până la articolul cu numărul relativ k;

se scrie în acces direct noul articol, în poziţia k.


Exemplu: 7. { // articolele fisierului sunt in ordinea // crescatoare a valorii campului 1 // citire nume fisier extern *) f=fopen(nume_fisier, "rb+ "); // calculare numar de articole din fisier printf("\nCimp 1: "); // introducerea campului dupa care // sunt sortate articolele scanf("%d ",&art_nou.cimp_1); while(!feof(stdin)) // adaugarea mai multor articole { // ----------------------------------- // Preluare de la tastatura a celorlalte // campuri din articolul de adaugat // ----------------------------------- // secventa de cautare a pozitiei //in care se va insera articolul } fseek(f,0,SEEK_SET); // pozitionare pe inceput de fisier fread(&art_existent,sizeof(tip_articol),1,f); while((!feof(f))&&(art_existent.cimp_1<art_nou.cimp_1) fread(&art_existent,sizeof(tip_articol),1,f); if(!feof(f)) { k=ftell(f)-sizeof(tip_articol); //articolul se va // insera in pozitia k for(i=nr_art-1;i>=k;i--) { fseek(f,i*sizeof(tip_articol),SEK_SET); fread(&art_existent,sizeof(tip_articol),1,f); fwrite(&art_existent,sizeof(tip_articol),1,f); } } else k=nr_art; // articolul se adauga la sfirsitul // fisierului fseek(f,k*sizeof(tip_articol),SEK_SET); fwrite(&art_nou,sizeof(tip_articol),1,f); printf("\nCimp 1: "); // introducerea campului dupa care // sunt sortate articolele scanf("%d ",&art_nou.cimp_1);rite('Camp 1: ') } fclose(f); }

Modificarea valorii unor câmpuri din articol se realizează în mai multe

etape: se citeşte articolul care se modifică (fseek şi fread); se modifică (în zona articol din memoria principală) câmpurile cu valorile

dorite, introduse, în general, de la tastatură; se repoziţionează pe articolul respectiv cu fseek(f,ftell(f)-sizeof(tip_articol),SEEK_SET);

se scrie articolul modificat, cu funcţia fwrite. O problemă importantă rămâne selectarea câmpurilor care se modifică, pentru fiecare articol în parte. O variantă simplă este afişarea vechii valori, urmată de introducerea noii valori, în variabile independente de tip şir de caractere. În cazul în care şirul introdus este vid (s-a apăsat numai ENTER), respectivul câmp, prin convenţie, nu se modifică.


Altfel, câmpului respectiv i se va atribui valoarea citită în variabila independentă, eventual prin conversie, pentru câmpurile numerice. Exemplu: 8. // ------------------------------ // cautare articol de modificat // ------------------------------ *) fread(&art,sizeof(tip_articol),1,f); printf("Codul: %d - ",art.cod); //afisare vechea valoare fflush(stdin); gets(cods); // citire noua valoare; cods este de tip sir if(strlen(cods)) { art.cod=atoi(cods); // conversie din ASCII in binar printf("Denumire: %s - ",art.den); // afisare vechea // valoare gets(dens); // citire noua valoare if(strlen(dens) strcpy(dens,art.den); // copiere noua valoare // ---------------------------------- // Introducerea celorlalte campuri // din articol // ---------------------------------- // repozitionare pe articol feek(f,ftell(f)-sizeof(tip_articol),SEEK_SET); // rescriere articol modificat fwrite(&art,sizeof(tip_articol),1,f); } O altă variantă se poate realiza prin folosirea unei machete de ecran în care se afişează valorile actuale ale fiecărui câmp de modificat, se poziţionează succesiv cursorul la începutul fiecărui câmp, cu două răspunsuri posibile ale utilizatorului: <ENTER>, caz în care se menţine actuala valoare, respectiv o tastă diferită de <ENTER>, reprezentând primul caracter al noii valori.

6.3 Algoritmi de prelucrare a fişierelor binare care necesită actualizare

Prelucrarea fişierelor binare care necesită actualizare trebuie să asigure posibilitatea ştergerii articolelor şi să elimine riscul de suprascriere a articolelor adăugate. Pentru aceasta, trebuie proiectate structuri particulare de articole şi concepute operaţii de gestiune specifice. Fără a epuiza multitudinea soluţiilor de rezolvare a problemelor de gestiune a fişierelor care necesită actualizare, în continuare, se prezintă câteva soluţii posibile. În orice situaţie, limitările de regăsire prin acces secvenţial sau relativ a articolelor în fişier reduc aria folosirii limbajului în probleme de gestiune. Marele inconvenient îl constituie lipsa accesului după cheie, cel care corespunde cel mai bine gestiunii în sistemele reale.


În cele ce urmează se analizează trei tipuri de probleme: probleme în care se utilizează asocierea externă a numărului relativ la articolul corespunzător (codificare prin număr relativ); probleme în care se utilizează asocierea internă a numărului relativ la articolul corespunzător, iar acesta poate emana extern (se generează nomenclatoare după fiecare actualizare de fişier); probleme în care se utilizează extern coduri (chei) şi intern numere relative.

6.3.1 Probleme care utilizează codificarea externă prin numere relative Nomenclatorul de articole conţine numărul relativ al fiecăruia dintre ele. Nomenclatorul este elaborat extern (automat sau neautomat). Orice operaţie de regăsire în acces relativ presupune introducerea din exterior a numărului relativ. La crearea iniţială, fiecare articol este înscris la numărul său relativ predefinit. Asigu-rarea ştergerii şi adăugării controlate poate fi făcută în diverse moduri:

Extinderea articolelor logice cu un indicator de stare (un octet), ajungându-se la forma din figura 6.8.

IS Articol propriu-zis

Figura 6.8 Structura articolului care include indicatorul de stare

Indicatorul de stare (notat IS) poate lua una din cele două valori posibile (de exemplu 0 pentru articol inactiv – inexistent sau şters, 1 pentru articol prezent). Cu această convenţie, operaţiile de acces la articole se realizează în următoarele condiţii: scrierea în fişier este permisă numai pentru articolele cu IS=0; citirea din fişier este permisă numai pentru articolele cu IS=1.

Preformarea presupune deschiderea fişierului ca nou (crearea unui fişier nou) şi scrierea unui număr de articole (la limită, zero) cu IS=0. Includerea operaţiei de preformare conduce la dispariţia distincţiei dintre populare şi adăugare. Datorită faptului că fişierul se deschide ca existent, orice operaţie de scriere a unui nou articol se tratează ca adăugare. Într-un sistem de programe, deschiderea cu modul wb a unui fişier se realizează o singură dată, în procedura de preformare.

Scrierea în acces direct presupune furnizarea numărului relativ (nr) al artico-lului. În funcţie de valoarea lui nr se disting următoarele situaţii: - dacă nr<dimensiune fişier, se citeşte articolul respectiv din fişier şi adăugarea este permisă numai dacă IS=0; - dacă nr>=FileSize(f), are loc extinderea fişierului cu preformarea articolelor cu numerele relative cuprinse în domeniul dimensiune fişier..nr-1. Noul articol se scrie pe poziţia nr. Se remarcă faptul că scrierea în acces direct permite preformarea iniţială cu zero articole.

Scrierea în acces secvenţial se face fără verificare de existenţă. Scrierea are


loc în poziţia dată de pointerul curent. Procedura face IS=1. Utilizarea ei se recomandă numai la popularea densă.

Citirea în acces direct presupune furnizarea numărului relativ (nr). Ea verifică dacă IS=1.

Citirea în acces secvenţial analizează articolele începând cu cel de la pointerul curent. Articolele cu IS=0 sunt ignorate, până la întâlnirea primului articol cu IS=1 sau până se ajunge la sfârşit de fişier.

Ştergerea se realizează în acces direct. Ea presupune citirea articolului şi, dacă ştergerea este permisă (IS=1), se modifică indicatorul de stare (IS=0) şi se scrie articolul pe vechiul loc.

Rescrierea realizează scrierea unui articol în poziţia ftell(f)-sizeof(tip_articol), dacă vechiul articol din această poziţie are IS=1.

Folosirea articolului zero ca tabelă de ocupare în fişier. Fiecărui articol din fişier îi corespunde câte un octet în primul articol: articolului cu numărul relativ i îi corespunde octetul a[i]. Primul articol are structura char a[max], unde max este o constantă care indică numărul maxim de articole pe care le poate avea fişierul pe durata existenţei sale. Dacă articolul i este prezent, a[i]=1; dacă articolul i este inactiv (inexistent sau şters), a[i]=0. Cu această structură, operaţiile de acces la articole se realizează în următoarele condiţii: scrierea în fişier a articolului cu numărul relativ i este permisă numai dacă a[i]=0; citirea din fişier a articolului cu numărul relativ i este permisă numai dacă a[i]=1. Ştergerea articolului i presupune verificarea existenţei sale (a[i]=1) şi realiza-rea operaţiei a[i]=0. Adăugarea unui articol i presupune verificarea inexistenţei lui (a[i]=0), înscrierea articolului şi realizarea operaţiei a[i]=1. Utilizarea acestei modalităţi necesită încărcarea iniţială în memoria principală a articolului cu numărul relativ zero. În programele care realizează ştergeri sau/şi adăugări, înainte de închiderea fişierului trebuie rescris articolul zero în fişier. Datorită restricţiei impuse pentru numărul de articole din fişier, acest model de gestiune a articolelor este ineficient pentru multe probleme. Se pot concepe algoritmi prin care în tabela de ocupare în fişier fiecărui articol îi corespunde un bit, în loc de un octet. În acest fel numărul maxim de articole ce pot fi adăugate în fişier se măreşte de 8 ori.

6.3.2 Probleme care utilizează codificarea internă prin numere relative Înscrierea articolelor în fişiere, chiar cea iniţială, se face în primele articole inactive, asociindu-se astfel intern un număr relativ fiecărui articol. Deosebirea esenţială între această soluţie şi cea prezentată anterior, constă în modul de realizare a adăugării secvenţiale. După fiecare sesiune de actualizare va trebui listat nomenclatorul de coduri interne (numere relative). Articolelor din fişier li se asociază structura din figura 6.8. Preformarea, consultarea, modificarea şi ştergerea sunt similare celor prezentate în §6.3.1. Adăugarea unui articol se realizează în


condiţii diferite, după cum această operaţie are loc printre articolele existente, respectiv după ultimul articol (extindere). În ambele situaţii, condiţiile de realizare sunt determinate de modul de acces folosit: secvenţial sau direct.

Adăugarea în acces secvenţial se bazează pe presupunerea că utilizatorul nu impune o corespondenţă prestabilită între conţinut şi numărul articolului, adică în alţi termeni, că se acceptă o codificare automată. Adăugarea în acces secvenţial poate fi utilizată în două variante:

Cu verificarea existenţei de articole libere, caz în care se adaugă noul articol în prima poziţie găsită disponibilă (IS=0), eventual la sfârşit (extindere), dacă nu mai există articole libere în interior. Această variantă presupune existenţa unei soluţii de gestiune a articolelor libere (în urma preformării sau a ştergerii logice). Dintre soluţiile posibile pot fi menţionate:

Folosirea articolului zero pentru colectarea numărului articolelor libere, într-o structură de forma celei din figura 6.9.

nal al[1] al[2] ... al[nal] Articolul 0

WORD WORD WORD ... WORD

Figura 6.9 Structura articolului zero, pentru gestiunea articolelor libere În această soluţie, nal este numărul articolelor libere şi al[i], cu i=1..nal, reprezintă poziţiile relative ale articolelor libere. Soluţia prezintă avantajul timpului redus de căutare şi de atribuire a unei poziţii pentru noul articol. Numărul de articole libere ce pot fi gestionate în acest mod este limitat de descrierea articolelor principale ale fişierului. De exemplu, dacă articolul principal are 128 de octeţi, această soluţie permite gestionarea a 63 de articole libere (dacă se impune pentru articolul zero aceeaşi lungime ca şi pentru celelalte articole; pentru primul articol se poate accepta şi o dimensiune diferită – mai mare – dar nu cu mult mai mare şi oricum este o dimensiune stabilită de la început, care nu mai poate fi mărită la nevoie). La ştergerea logică a unui articol se realizează incrementarea valorii lui nal, iar al[nal] primeşte ca valoare numărul relativ al articolului şters.

Folosirea articolului zero ca început al unei liste simple (sau dublu) înlănţuite a articolelor libere, într-o structură de principiu de forma celei din figura 6.10.

pal ual

0 au 0 au 0 au ... ...

Figura 6.10 Gestionarea articolelor libere prin liste


În această soluţie, articolul zero punctează pe primul (pal) şi pe ultimul (ual) articol liber, iar fiecare articol punctează pe următorul (au). Numărul articolelor libere care pot fi gestionate în acest mod este oarecare. La adăugarea unui nou articol, se verifică dacă există articole libere (pal<>0) şi dacă există, se atribuie primul articol din listă articolului de adăugat, actualizându-se componenta articolului zero. La ştergerea unui articol, trebuie asigurată includerea sa în lista articolelor libere, operaţia fiind posibilă la oricare din capetele listei.

Căutarea secvenţială a primului articol liber, fără organizarea unei gestiuni a acestora. Deşi mai costisitoare ca timp de căutare, aceasta este soluţia cea mai simplă sub aspectul programării, eliminând necesitatea unei structuri distincte a articolului zero şi operaţiile legate de întreţinerea colecţiei sau listei articolelor libere. În concluzie, este de preferat ultima variantă atunci când timpul de căutare nu este prohibitiv.

Fără verificarea existenţei de articole libere, caz în care articolul este adăugat direct la sfârşit (extindere). Această variantă este avantajoasă când are loc introducerea de la început a majorităţii articolelor. Ea poate fi asociată cu preformarea cu zero articole, fiecare sesiune de adăugare de noi articole fiind realizată prin extinderea fişierului.

Adăugarea în acces direct presupune o codificare anterioară (preluarea

numărului relativ din nomenclatorul editat după fiecare creare/adăugare secvenţială) şi se realizează identic cu operaţia de scriere directă prezentată în §6.3.1.

6.3.3 Probleme care utilizează corespondenţa internă dintre chei şi numere relative

Majoritatea aplicaţiilor de gestiune economică utilizează fişiere de date în care articolele trebuie regăsite după valorile unui câmp de identificare, numit cheie. Problema corespondenţei între chei şi numerele relative ale articolelor din fişierul de date se poate rezolva prin intermediul unui fişier binar suplimentar, cu rol de tabelă de indexuri. O astfel de organizare se numeşte indexată. Articolele fişierului tabelă de indexuri au structura din figura 6.11.

IS Cheie Număr relativ (nr)

Figura 6.11 Structura articolului din tabela de indexuri Indicatorul de stare (IS) are rol identic cu cel prezentat în §6.3.1. Cheie este un câmp în care se memorează valoarea cheii articolului existent logic în fişierul de date, al cărui număr relativ corespunzător este memorat în câmpul nr. Articolele tabelei de indexuri sunt, în orice moment, sortate crescător după valorile câmpului cheie. Articolele din fişierul de date sunt memorate aleator. O parte dintre acestea nu-şi regăsesc corespondent în tabela de indexuri, fiind considerate şterse. Orice operaţie de acces la articolele fişierului de date se realizează numai prin intermediul tabelei,


gestionată automat de funcţiile unei biblioteci specializate şi care este netransparentă utilizatorului (bibliotecă utilizator, nu face parte din limbaj). Operaţiile de acces la nivel de fişier sunt deschiderea şi închiderea fişierului de date. La rândul ei, deschiderea poate fi pentru creare (ca fişier nou) sau pentru consultare şi întreţinere (ca fişier vechi). Procedurile realizează, pe lângă operaţiile asupra fişierului de date şi gestionarea automată a tabelei de indexuri: formarea numelui său extern, asignarea numelui fizic la numele logic, deschiderea ca fişier nou sau vechi, închiderea. Operaţiile de gestiune ce se pot realiza cu fişierele de date astfel organizate sunt:

Crearea în acces secvenţial presupune furnizarea articolelor sortate strict crescător după valorile câmpului ales drept cheie. Articolele sunt scrise cu ajutorul funcţiei de scriere în acces secvenţial. Eroarea de cheie invalidă poate apărea la tentativa de scriere a unui articol a cărui cheie este mai mică sau egală decât ultima înscrisă în fişierul de date.

Crearea în acces direct se realizează cu funcţia de scriere în acces direct, articolele fiind furnizate în orice ordine. Eroarea de cheie invalidă apare la tentativa de scriere a unui articol a cărui cheie este egală cu una din cele prezente în fişier.

Consultarea în acces secvenţial presupune regăsirea articolelor în ordinea strict crescătoare a valorilor cheii. Ea se realizează cu ajutorul funcţiei de citire în acces secvenţial, care detectează şi sfârşitul fişierului de date.

Consultarea în acces mixt permite selectarea unui grup de articole, memo-rate logic contiguu în fişier, selecţie realizată pe baza valorilor cheii primului şi ultimului articol din grupul dorit. Accesul mixt presupune poziţionarea pe primul articol prin citirea în acces direct (sau poziţionare şi citire în acces secvenţial), urmată de exploatarea în acces secvenţial, până la găsirea cheii ultimului articol dorit, sau până la sfârşitul fişierului.

Adăugarea de articole se realizează utilizând funcţia de scriere în acces direct. Articolele pot fi furnizate în orice ordine a valorilor cheii. Eroarea de cheie invalidă apare la tentativa de scriere a unui articol a cărui cheie este egală cu una deja existentă.

Modificarea unor câmpuri din articol se realizează în următoarele etape: citirea articolului de modificat (în acces secvenţial sau direct); modificarea, în zona articol corespunzătoare, a câmpurilor dorite, cu

excepţia câmpului cheie; rescrierea articolului, cu procedura de rescriere.

Eroarea de cheie invalidă apare în cazul tentativei de rescriere a unui articol a cărui cheie este diferită de cea a articolului citit anterior.

Ştergerea în acces secvenţial elimină articolul curent din fişierul de date. În general, articolul trebuie mai întâi identificat printr-o citire (în acces secvenţial sau direct) sau prin poziţionare. Procedura returnează eroare în cazul tentativei de ştergere după ultimul articol existent.

Ştergerea în acces direct elimină articolul a cărui cheie este precizată. Operaţia nu trebuie precedată de citirea articolului şi returnează eroare în cazul


furnizării unei chei inexistente în fişier. În aplicaţii, este preferabilă ştergerea în acces secvenţial, deoarece permite (datorită citirii care o precede), vizualizarea articolului şi luarea unei decizii în condiţii de siguranţă. Exemplu: 9. Exemplul următor descrie funcţii, tipuri de date şi variabile publice pentru prelucrarea unui fişier organizat indexat. Pentru aceste exemplu, fişierul de date este format din articole cu următoarea structură:

cheie denumire preţ cantitate

Figura 6.12 Structura articolului din tabela de indexuri

Exemplul poate fi adaptat pentru orice altă structură, modificând corespunzător structura articolului. În acest exemplu, fişierul index va fi o variabilă globală, accesibilă tuturor subprogramelor. Tipurile definite sunt următoarele: typedef struct{ char cheie[7]; char den[35]; float pu; float cant; } ARTICOL; //tipul articol din fisierul de date typedef struct{ char is; char cheie[7]; long nr_rel; } ART_INDEX; //tipul articol din tabela de indexuri FILE* ind; //fisierul index char nume_index[20]; //numele extern al fisierului index

Pentru implementarea operaţiilor de gestiune specifice unui fişier organizat indexat sunt necesare următoarele subprograme:

Funcţia de deschidere a tabelei index ca fişier nou, cu prototipul void new_index(char *nume);

Funcţia primeşte ca parametru numele extern al fişierului de date (nume) şi creează un fişier nou, tabela de indexuri, cu extensia .idx.

Funcţia de deschidere a tabelei de indexuri, pentru consultare şi întreţinere, cu prototipul

void open_index(char *nume);

Funcţia primeşte ca parametru numele extern al fişierului de date (nume), şi deschide ca existentă tabela de indexuri, cu extensia .idx.

Funcţia de închidere a tabelei de indexuri, cu prototipul void closeindex();


Funcţia realizează închiderea tabelei de indexuri asociate fişierului de date.

Funcţia pentru citirea în acces secvenţial a unui articol din fişierul de date, cu prototipul int ReadSec(fisier f,articol *a); Funcţia are ca parametri numele intern al fişierului de date şi adresa unde se depune articolul citit, dacă acest lucru este posibil şi returnează

- 1, dacă citirea a fost posibilă; - 0, în caz contrar.

Citirea unui articol din fişierul de date este realizată prin intermediul tabelei de indexuri, astfel: este citit un articol din tabelă, de la poziţia curentă a pointerului de fişier şi apoi este citit articolul cu numărul relativ dat de câmpul nr_rel al articolului citit din fişierul de indexuri. Dacă, în tabela de indexuri, pointerul de fişier indică sfârşitul de fişier, atunci citirea nu este posibilă şi funcţia returnează valoarea 0. Prin apelul repetat al funcţiei ReadSec, dacă tabela de indexuri are poinetrul plasat înaintea primului articol, sunt obţinute articolele din fişierul de date în ordinea strict crescătoare a valorii cheii.

Funcţia pentru citirea în acces direct a unui articol din fişierul de date, cu prototipul int ReadKey(fisier f,articol *a,char *Key); Funcţia are ca parametri numele intern al fişierului de date, adresa unde se depune articolul citit, dacă acest lucru este posibil, precum şi cheia articolului care va fi citit şi returnează

- 1, dacă citirea a fost posibilă; - 0, în caz contrar.

Funcţia apelează modulul de căutare binară în tabela de indexuri a cheii Key, SeekKey. Atunci când cheia este găsită, citeşte articolul cu numărul relativ corespunzător articolului din tabela de indexuri şi returnează valoarea 1, altfel returnează valoarea 0.

Funcţia pentru scrierea în acces secvenţial a unui articol în fişierul de date, cu prototipul int WriteSec(fisier f,articol a); Funcţia are ca parametri numele intern al fişierului de date şi articolul ce va fi scris, dacă acest lucru este posibil, şi returnează

- 1, dacă scrierea a fost posibilă; - 0, în caz contrar.

Funcţia adaugă un articol în fişierul de date, concomitent cu extinderea tabelei de indexuri cu o nouă înregistrare, a cărei cheie este mai mare decât cele existente. În cazul în care cheia este mai mică sau egală cu a ultimului articol din tabelă, este returnată valoarea 0, corespunzătoare situaţiei în care scrierea nu este posibilă.


Funcţia pentru scrierea în acces direct a unui articol în fişierul de date, cu prototipul int WriteKey(fisier f,articol a); Funcţia are ca parametri numele intern al fişierului, articolul ce va fi scris, dacă acest lucru este posibil, şi returnează

- 1, dacă scrierea a fost posibilă; - 0, în caz contrar.

Funcţia adaugă un articol la sfârşitul fişierului de date. Cheia acestuia, a.cheie, poate avea orice valoare (care nu există deja în tabela de indexuri). Iniţial, tabela se extinde cu un nou articol şi apoi este reordonată (prin apelul funcţiei Sort). În cazul în care cheia articolului de scris este deja prezentă în tabela de indexuri, articolul nu este scris în fişier şi funcţia returnează valoarea 0. Căutarea cheii în tabela de indexuri pentru stabilirea posibilităţii scrierii este realizată prin apelul funcţiei SeekKey.

Funcţia pentru ştergerea în acces secvenţial a unui articol, cu prototipul int DeleteSec(); Funcţia returnează

- 1, dacă ştergerea a fost posibilă; - 0, în caz contrar.

Funcţia şterge logic articolul curent din fişierul de date. Ştergerea se realizează fizic în tabela de indexuri. Iniţial, indicatorul de stare este setat pe 0 şi apoi se elimină articolul din tabelă, prin apelul funcţiei Sort. Funcţia returnează valoarea 0, corespunzătoare situaţiei de eroare, dacă pointerul curent al tabelei de indexuri indică marcatorul de sfârşit de fişier.

Funcţia pentru ştergerea în acces direct a unui articol, cu prototipul int DeleteKey(char *Key); Funcţia primeşte ca parametru de intrare cheia articolului care va fi şters şi returnează

- 1, dacă ştergerea a fost posibilă; - 0, în caz contrar.

Funcţia şterge logic din fişierul de date articolul a cărui cheie este primită ca parametru. Ştergerea este realizată fizic din tabela de indexuri, analog ştergerii în acces secvenţial. Funcţia returnează valoarea 0, corespunzătoare situaţiei de eroare, dacă Key nu este regăsită în tabela de indexuri. Căutarea este realizată prin apelul funcţiei SeekKey. Pentru implementarea funcţiilor descrise mai sus, sunt utilizate următoarele funcţii auxiliare:

Funcţia pentru sortarea tabelei de indexuri, cu eliminarea articolelor cu stare 0, cu prototipul void Sort(); Funcţia realizează sortarea articolelor tabelei de indexuri, crescător după câmpul cheie, precum şi ştergerea fizică a tuturor articolelor cu indicator de stare 0.


Funcţia pentru căutarea articolului cu cheie dată, cu prototipul int SeekKey(char *Key) Funcţia primeşte ca parametru de intrare cheia articolului căutat şi returnează

- 1, dacă articolul a fost găsit; - 0, în caz contrar.

Funcţia realizează căutarea binară în tabela de indexuri, după câmpul cheie. Dacă articolul cu cheia Key este găsit, funcţia lasă pointerul de fişier pe acel articol (o citire secvenţială ulterioară determinând obţinerea articolului corespunzător din fişierul de date). Textul sursă care implementează toate aceste funcţii C este prezentat în continuare (în exemplele care urmează, aceste text va fi considerat salvat în fişierul index1.cpp).

#include <stdio.h> #include <string.h> #define fisier FILE* typedef struct{ char cheie[7]; char den[35]; float pu; float cant; } ARTICOL; //tipul articol din fisierul de date typedef struct{ char is; char cheie[7]; long nr_rel; } ART_INDEX; //tipul articol din tabela index fisier ind; //fisierul index char nume_index[20]; //numele extern al fisierului index void Sort() { ART_INDEX a,b; fisier ind1; long i,j; ind1=fopen("temp.idx","wb+"); rewind(ind); fread(&a,sizeof(a),1,ind); while(!feof(ind)) { if(a.is)fwrite(&a,sizeof(a),1,ind1); fread(&a,sizeof(a),1,ind); } fclose(ind); fseek(ind1,0,SEEK_END); long n=ftell(ind1)/sizeof(a); for(i=0;i<n-1;i++) { fseek(ind1,i*sizeof(a),SEEK_SET); fread(&a,sizeof(a),1,ind1); for(j=i+1;j<n;j++) { fseek(ind1,j*sizeof(a),SEEK_SET); fread(&b,sizeof(a),1,ind1); if(strcmp(a.cheie,b.cheie)>0) { fseek(ind1,i*sizeof(a),SEEK_SET); fwrite(&b,sizeof(a),1,ind1); fseek(ind1,j*sizeof(a),SEEK_SET);


fwrite(&a,sizeof(a),1,ind1); } } } rewind(ind1); ind=fopen(nume_index,"wb+"); fread(&a,sizeof(a),1,ind1); while(!feof(ind1)) { if(a.is)fwrite(&a,sizeof(a),1,ind); fread(&a,sizeof(a),1,ind1); } fclose(ind1); remove("temp.idx"); } /* cautarea articolului cu cheia Key si plasarea pointerului de fisier in tabela de indexuri pe articolul respectiv*/ int SeekKey(char *Key) { long ls=0, ld, m, n; ART_INDEX a; int gasit=0; fseek(ind,0,SEEK_END); n=ftell(ind)/sizeof(ART_INDEX); ld=n-1; while((ls<=ld)&&(!gasit)) { m=(ls+ld)/2; fseek(ind,m*sizeof(a),SEEK_SET); fread(&a,sizeof(a),1,ind); if(strcmp(a.cheie,Key)==0) gasit=1; else if(strcmp(a.cheie,Key)>0) ld=m-1; else ls=m+1; } if(gasit) fseek(ind,m*sizeof(a),SEEK_SET); return gasit; } void new_index(char *nume) { strcpy(nume_index,nume); strcat(nume_index,".idx"); ind=fopen(nume_index,"wb+"); } void open_index(char *nume) { strcpy(nume_index,nume); strcat(nume_index,".idx"); ind=fopen(nume_index,"rb+"); } void close_index() { fclose(ind); } int ReadSec(fisier f,ARTICOL *a) { ART_INDEX a1; int r; fread(&a1,sizeof(a1),1,ind); if(feof(ind))r=0; else { fseek(f,a1.nr_rel*sizeof(*a),SEEK_SET); fread(a,sizeof(*a),1,f); r=1; } return r; }


int ReadKey(fisier f,ARTICOL *a,char *Key) { ART_INDEX a1; int r; if(SeekKey(Key)) { fread(&a1,sizeof(a1),1,ind); fseek(f,a1.nr_rel*sizeof(*a),SEEK_SET); fread(a,sizeof(*a),1,f); r=1; } else r=0; return r; } int WriteSec(fisier f,ARTICOL a) { ART_INDEX a1, ai; long n, nl; int r; fseek(ind,0,SEEK_END); n=ftell(ind)/sizeof(a1); if(n>0) { fseek(ind,(n-1)*sizeof(a1),SEEK_SET); fread(&a1,sizeof(a1),1,ind); if(strcmp(a1.cheie,a.cheie)>0) r=0; else { ai.is=1; strcpy(ai.cheie,a.cheie); fseek(f,0,SEEK_END); n1=ftell(f)/sizeof(a); ai.nr_rel=n1; fseek(ind,0,SEEK_END); fwrite(&ai,sizeof(ai),1,ind); fwrite(&a,sizeof(a),1,f); r=1; } } else r=0; return r; } int WriteKey(fisier f,ARTICOL a) { char Key[7]; ART_INDEX a1; long n; strcpy(Key,a.cheie); if(SeekKey(Key)) r=0; else { a1.is=1; strcpy(a1.cheie,a.cheie); fseek(f,0,SEEK_END); n=ftell(f)/sizeof(a); a1.nr_rel=n; fwrite(&a,sizeof(a),1,f); fseek(ind,0,SEEK_END); fwrite(&a1,sizeof(a1),1,ind); Sort(); r=1; } return r; }


int DeleteSec() { ART_INDEX a1; long pos=ftell(ind); fread(&a1,sizeof(a1),1,ind); if(feof(ind)) r=0; else { fseek(ind,pos,SEEK_SET); a1.is=0; fwrite(&a1,sizeof(a1),1,ind); Sort(); r=1; } return r; } int DeleteKey(char *Key) { int r; if(SeekKey(Key)) r=DeleteSec(); else r=0; return r; }

Exemple 10. Scrieţi programul C pentru crearea în acces direct unui fişier binar cu articole având structura:

cheie denumire preţ cantitate Datele sunt preluate de la tastatură până la apăsarea combinaţiei CTRL/Z pentru câmpul cheie. Fişierul creat este organizat indexat.

#include "index1.cpp" #include <conio.h> void main() { ARTICOL a; char nume[20],nume1[20]; char x[7]; fisier f; clrscr(); printf(" numele fisierului de date in care adaugati:"); fflush(stdin); gets(nume); strcpy(nume1,nume); strcat(nume1,".dat"); f=fopen(nume1,"rb+"); if(f==NULL) { printf("Fisierul va fi creat"); f=fopen(nume1,"wb+"); new_index(nume); } else open_index(nume); printf("\nAdaugarea in acces direct dupa cheie\n"); printf("Introduceti cheia:"); fflush(stdin); gets(a.cheie); while(!feof(stdin)) { printf("Denumire produs:"); fflush(stdin); gets(a.den); printf("Pret produs:"); scanf("%f",&a.pu);


printf("Cantitate:"); scanf("%f",&a.cant); if(WriteKey(f,a)) printf("Articol adaugat"); else printf("Exista articol"); getch(); clrscr(); printf("Introduceti cheia:"); fflush(stdin); gets(a.cheie); } fclose(f); close_index(); getch(); }

11. Se presupune creat şi populat fişierul de date din exemplul anterior. Scrieţi programul C pentru ştergerea acelor articole ale căror chei sunt introduse de la tastatură. Încheierea introducerii datelor este marcată standard.

#include "index1.cpp" #include <conio.h> void main() { ARTICOL a; char nume[20],nume1[20]; char Key[7]; fisier f; char r; int i; clrscr(); printf(" numele fisierului de date din care stergeti:"); fflush(stdin); gets(nume); strcpy(nume1,nume); strcat(nume1,".dat"); f=fopen(nume1,"rb+"); if(f==NULL) printf("Fisierul nu exista!!"); else { open_index(nume); printf("\nStergerea in acces direct dupa cheie\n"); printf("Introduceti cheia:"); fflush(stdin); gets(Key); while(!feof(stdin)) { if(ReadKey(f,&a,Key)) { printf("Articolul:\n"); printf("Denumire:%20s\n",a.den); printf("Pret:%7.2f\n",a.pu); printf("Cantitate:%8.2f\n\n",a.cant); printf("Doriti stergerea?(D/Altceva)"); r=getch(); if(r=='D') { i=DeleteKey(Key); printf("Stergere efectuata"); } else printf("Stergerea nu a fost efectuata"); } else printf("Nu exista articol"); getch();


clrscr(); printf("Introduceti cheia:"); fflush(stdin); gets(a.cheie); } fclose(f); close_index(); getch(); } }

12. Scrieţi programul C pentru afişarea informaţiilor memorate în fişierul creat în exemplul 10. Articolele sunt afişate în ordine crescătoare a câmpului cheie.

#include "index1.cpp" #include <conio.h> void main() { ARTICOL a; char nume[20],nume1[20]; char x[7]; fisier f; clrscr(); printf(" numele fisierului de date care este consultat:"); fflush(stdin); gets(nume); strcpy(nume1,nume); strcat(nume1,".dat"); f=fopen(nume1,"rb+"); if(f==NULL) printf("Fisierul nu exista!!"); else { open_index(nume); while(ReadSec(f,&a)) { printf("Cheie:"); puts(a.cheie); printf("\nDenumire produs:"); puts(a.den); printf("Pret produs:"); printf("7.2%f\n",a.pu); printf("Cantitate:"); printf("%8.2f\n\n",a.cant); getch(); } fclose(f); close_index(); getch(); } }

6.4 Sortarea fişierelor binare memorate dens Operaţia de sortare a unui fişier binar presupune aranjarea articolelor în ordinea crescătoare (descrescătoare) a valorilor unei zone, numită cheie de sortare. În cazul în care cheia de sortare este formată dintr-un singur câmp din cadrul articolului, operaţia se numeşte sortare simplă. Sortarea multiplă presupune aranjarea articolelor după valorile a două sau mai multe câmpuri, alcătuind, prin juxtapunere, cheia de sortare. Juxtapunerea câmpurilor (nu neapărat adiacente în cadrul articolului) se realizează pe lungimea efectivă a lor, alcătuind forma canonică a cheii de sortare. De


exemplu, dacă NUME şi PRENUME sunt două câmpuri distincte, declarate de tip şir de caractere, forma canonică a cheii de sortare după nume şi prenume este dată de lungimea efectivă a fiecărei date de tip şir. Dacă pentru sortarea simplă cheia de sortare poate fi însuşi câmpul din articol, pentru cea multiplă este necesară o zonă auxiliară de memorie, în care se construieşte cheia de sortare, în forma canonică. Sortarea unui fişier se poate realiza cu aducerea lui integrală în memorie (sortare în memorie) sau cu aducerea în memorie a câte unui articol (sortare "direct pe disc"). Indiferent de modul utilizat, sortarea poate fi realizată printr-unul din algoritmii cunoscuţi pentru masivele de date: sortare prin interschimbare, prin selecţie, prin inserţie etc.

Sortarea în memorie este o metodă rapidă şi presupune: citirea întregului fişier în memoria principală, într-o structură internă de date (vector, arbore bina de sortare); sortarea efectivă după cheia de sortare (în cazul folosirii unui vector, operaţia nu este necesară dacă se foloseşte arbore de sortare); recrearea fişierului pe disc. Metoda se poate aplica numai fişierelor reduse ca dimensiuni sau cu lungime mică de articol, dată fiind capacitatea limitată a memoriei interne asociată unui program. Ea poate avea mai multe variante:

Sortarea cu vehicularea întregului articol, presupune memorarea întregului fişier într-un vector de articole. Compararea pentru sortare se va realiza pe câmpul cheie de sortare, însă interschimbarea se realizează la nivelul întregului articol. Exemplu: 13. typedef struct { char grupa; char nume_student[30]; float medie; }STUDENT; void main() { FILE* f; STUDENT x[250], aux; int i,j,n; f=fopen("STUDENT.DAT","rb+"); fseek(f,0,SEEK_END); n:=ftell(f)/sizeof(STUDENT); rewind(f); // citirea fisierului initial in memorie for(i=0;i<n;i++) fread(&x[i],sizeof(STUDENT),1,f); //sortarea for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(x[i].medie>x[j].medie) { aux:=x[i]; //interschimbarea articolelor x[i]:=x[j]; //nu se poate folosi atribuirea mereu x[y]:=aux; } rewind(f);


for(i=0;i<n;i++) fwrite(&x[i],sizeof(STUDENT),1,f); fclose (f); }

Sortarea cu vehicularea cheii şi indexului, presupune memorarea într-un vector numai a valorii cheii de sortare, împreună cu numărul relativ al articolului din fişierul iniţial (indexul). Interschimbarea se va realiza la nivelul cheii de sortare, rezultând în final ordinea în care articolele vor fi scrise în fişier. Deoarece articolele, în întregime, sunt rezidente pe disc, fişierul sortat va fi creat cu un alt nume fizic, în acces secvenţial, preluînd articolele din fişierul iniţial, în acces direct. Cheile de sortare şi indexurile pot fi memorate în vectori distincţi sau într-unul singur, cu elemente de tip articol. Exemplu: 14. typedef struct { char grupa; char nume_student[30]; float medie; }STUDENT; typedef struct { float medie; int index; }CHEIE; void main() { FILE *f,*g; STUDENT y; CHEIE aux,x[250]; int i,j,n; f=fopen("STUDENT.DAT","rb"); fseek(f,0,SEEK_END); n:=ftell(f)/sizeof(STUDENT); rewind(f); g=fopen("STUDENTS.DAT","wb"); // ---------------------------------- for(i=0;i<n;i++) { fread(&y,sizeof(STUDENT),1,f); x[i].medie=y.medie; x[i].index=i; } //------------------------------------- for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(x[i].medie>x[j].medie) { aux=x[i]; x[i]:=x[j]; x[j]:=aux } //-------------------------------------- for(i=0;i<n;i++) { fseek(f,x[i].index*sizeof(STUDENT),SEEK_SET); fread(&y,sizeof(STUDENT),1,f); fwrite(&y,sizeof(STUDENT),1,g); } fclose(f); fclose(g); unlink(f); rename("STUDENTS.DAT","STUDENT.DAT"); }


Sortarea numai cu vehicularea indexului este o metodă mai bună decât precedenta, deoarece micşorează timpul de execuţie, prin eliminarea interschimbării valorilor cheii de sortare (mai ales când aceasta este multiplă). Valorile cheii de sortare şi numărului relativ corespunzător indexului se memorează în vectori distincţi. Comparaţiile se realizează pentru valorile cheii, dar interschimbarea se efectuează numai pentru indexuri. Se va crea un alt fişier fizic. Exemplu: 15. typedef struct { char grupa; char nume_student[30]; float medie; }STUDENT; void main() { FILE *f,*g; float x[250]; int index[250]; int i,j,n; STUDENT y; f=fopen("STUDENT.DAT","rb"); fseek(f,0,SEEK_END); n:=ftell(f)/sizeof(STUDENT); rewind(f); g=fopen("STUDENTS.DAT","wb"); //------------------------------------------ for(i=0;i<n;i++) { fread(&y,sizeof(STUDENT),1,f); x[i]=y.medie; index[i]=i; } //------------------------------------------ for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) if(x[i]>x[j]) { aux=index[i]; index[i]=index[j]; index[j]=aux } //------------------------------------------- for(i=0;i<n;i++) { fseek(f,index[i]*sizeof(STUDENT),SEEK_SET); fread(&y,sizeof(STUDENT),1,f); fwrite(&y,sizeof(STUDENT),1,g); } fclose(f); fclose(g) }

Sortarea pe disc se aplică fişierelor mari, la care este imposibilă aducerea în memoria principală chiar şi a minimului de informaţii necesare sortării. În acest caz, operaţia se va realiza "direct" pe mediul magnetic, cu aducerea în memorie doar a două articole (pentru comparaţii) şi scrierea în acces direct în acelaşi fişier, prin utilizarea numărului relativ al articolelor prelucrate. Timpul de prelucrare va fi substanţial mai mare decât la metodele de sortare în memorie, deoarece operaţiile de intrare/ieşire sunt costisitoare din punct de vedere al resursei timp calculator.


Se poate aplica oricare din algoritmii de sortare cunoscuţi, cu menţiunea că indicii i şi j vor fi utilizaţi pentru controlul numărului relativ al articolelor în fişier. Exemple: 16. Sortarea prin interschimbare do { vb=0; for(i=0;i<nr_art-1;i++) { fseek(f,sizeof(STUDENT)*i,SEEK_SET); fread(&x,sizeof(STUDENT),1,f); fread(&y,sizeof(STUDENT),1,f); if(x.medie>y.medie) { fseek(f,sizeof(STUDENT)*i,SEEK_SET); fwrite(&y,sizeof(STUDENT),1,f); fwrite(&x,sizeof(STUDENT),1,f); vb=1; } while(vb); 17. Sortare prin selecţie for(i=0;i<nr_art-1;i++) { fseek(f,sizeof(STUDENT)*i,SEEK_SET); fread(&x,sizeof(STUDENT),1,f); for(j=i+1;j<nr_art;j++) { fseek(f,sizeof(STUDENT)*j,SEEK_SET); fread(&y,sizeof(STUDENT),1,f); if(x.medie>y.medie) { fseek(f,sizeof(STUDENT)*i,SEEK_SET); fwrite(&y,sizeof(STUDENT),1,f); fseek(f,sizeof(STUDENT)*j,SEEK_SET); fwrite(&x,sizeof(STUDENT),1,f); } } }

6.5 Interclasarea fişierelor binare memorate dens Interclasarea este operaţia prin care, din două sau mai multe mulţimi ordonate, se obţine o nouă mulţime, ordonată după acelaşi criteriu. Interclasarea fişierelor apare ca necesitate în aplicaţiile economice, mai ales în faza de post-populare a fişierelor mari de date, create simultan pe submulţimi de mai mulţi utilizatori şi necesitând, în final, reunirea acestora într-unul singur. Condiţia apriori interclasării este ca toate fişierele parţiale să fie sortate după valorile aceluiaşi câmp, pe baza căruia se va realiza, prin comparări succesive, operaţia de interclasare. Câmpul poartă denumirea de cheie de interclasare. Interclasarea a n fişiere se poate realiza simplu prin aplicarea de n-1 ori a operaţiei de interclasare a două fişiere (figura 6.12).


1

Fişier 1

n432...

Fişier 2

Fişier 3

Fişier n-1

...

Interclasare 1 ………..

Fişier final

Interclasare 2 ………………………...

Interclasare 3 …………………………………………...

Interclasare 3 ………………………………………………………………………………………………………….

Figura 6.13 Interclasarea a n fişiere Se obţin astfel n-1 fişiere intermediare (fişier i), din care numai ultimul se păstrează, celelalte (împreună cu fişierele iniţiale) se şterg, fie în finalul procesului, fie la sfârşitul fiecărei etape intermediare (recomandat). Interclasarea a două fişiere este similară operaţiei aplicate pentru doi vectori. Dimensiunea fişierului rezultat este suma dimensiunilor fişierelor iniţiale. Exemplu: 18. Se prezintă structura principială a unui program pentru interclasarea a două fişiere binare. Cheile de interclasare se află în câmpul c aparţinând articolelor art_1 şi art_2, corespunzătoare fişierelor de intrare f şi g, considerate populate dens. { //--------------------------------- //citire nume externe ale fisierelor //--------------------------------- f=fopen(nume_fisier_intrare_1, "rb"); g=fopen(nume_fisier_intrare_2, "rb"); h=fopen(nume_fisier_iesire, "wb"); fread(&art_1,sizeof(tip_articol),1,f); fread(&art_2,sizeof(tip_articol),1,g); while((!feof(f)&&(!feof(g))) if(art_1.c>art_2.c) { fwrite(&art_1,sizeof(tip_articol),1,h); fread(&art_1,sizeof(tip_articol),1,f); }


else { fwrite(&art_2,sizeof(tip_articol),1,h); fread(&art_2,sizeof(tip_articol),1,g); } while(!feof(f)) { fwrite(&art_1,sizeof(tip_articol),1,h); fread(&art_1,sizeof(tip_articol),1,f); } while(!feof(g)) { fwrite(&art_2,sizeof(tip_articol),1,h); fread(&art_2,sizeof(tip_articol),1,g); } fclose(f); fclose(g); fclose(h) }

6.6 Prelucrarea masivelor memorate în fişiere binare Una dintre aplicaţiile des întâlnite în lucrul cu fişiere este memorarea masivelor de date de dimensiuni foarte mari, care fac imposibilă aducerea lor integrală în memoria internă. Problema principală a prelucrării masivelor (vectori, matrice etc.) memorate în fişiere binare, o constituie determinarea poziţiei unui anumit element de masiv în cadrul fişierului. Indiferent de numărul de dimensiuni ale masivului şi de modalităţile de memorare a elementelor sale în cadrul fişierului, legătura între elementul de masiv care se referă şi numărul relativ al articolului care îl conţine se realizează pe baza funcţiei rang. În cazul masivelor memorate în fişiere, prelucrarea acestora depinde de unele caracteristici particulare:

numărul de dimensiuni ale masivului; ordinea de memorare în fişier (în ordine lexicografică sau invers lexicografi-

că); modul de memorare (dens sau nedens); ordinea de parcurgere a masivului.

6.6.1 Prelucrarea vectorilor

De regulă, vectorii se memorează dens. Numărul relativ al articolului depinde de rangul elementului în cadrul vectorului, astfel:

nr_relativ = rang(xi)+1 = i+1, pentru i=0..n-1, dacă articolul cu numărul relativ 0, fie nu este utilizat (caz în care dimensiunea vectorului este n = dimensiune fişier-1), fie memorează numărul efectiv de componente ale vectorului;

nr_relativ = rang(xi) = i, pentru i=0..n, dacă vectorul se memorează începând cu primul articol (caz în care dimensiunea vectorului este n =dimensiunea fişierului). Exemplu: 19. Să se determine media aritmetică a elementelor unui vector foarte mare, memorat într-un fişier binar.


#include<stdio.h> void main() { FILE* vector; float element, medie; long i,n; vector=fopen("VECTOR.DAT","rb"); fseek(vector,0,SEEK_END); n=ftell(f)/sizeof(float); rewind(f); medie=0; for(i=0;i<n;i++) { fread(&element,sizeof(float),1,vector); medie+=element; } medie/=n; printf("\nMedia: %7.3f",medie); fclose(vector); }

6.6.2 Prelucrarea matricelor O matrice poate fi memorată într-un fişier binar nedens (similar memorării în MP) sau dens, în ordine lexicografică sau invers lexicografică. Numărul relativ al elementului aij se determină pe baza funcţiei rang, astfel:

rang(aij) = i * nr_coloane + j, în cazul memorării lexicografice, unde nr_coloane este fie numărul coloanelor efective (populare densă), fie numărul coloanelor rezervate (populare nedensă);

rang(aij) = j * nr_linii + i, în cazul memorării invers lexicografice, unde nr_linii este fie numărul liniilor efective (populare densă), fie numărul liniilor rezer-vate (populare nedensă). Fie m şi n numărul liniilor, respectiv coloanelor efective şi mr şi nr numărul liniilor, respectiv coloanelor rezervate (mr şi nr corespund dimensiunilor maxime din declaraţia unui masiv aflat în memoria principală). Pentru ca fişierul să conţină informaţii complete despre matrice, trebuie să memoreze, pe lângă elementele ei, şi:

m (sau n), în cazul memorării dense. Când se memorează m, n se determină împărţind dimensiunea fişierului (mai puţin primul articol, unde se află m) la m; când se memorează n, m se determină împărţind dimensiunea fişierului (mai puţin primul articol, unde se află n) la n. Funcţia rang depinde de m sau n, după cum matricea este memorată invers lexicografic sau lexicografic;

n şi nr, în cazul memorării nedense în ordine lexicografică. m se determină împărţind dimensiunea fişierului (mai puţin primele două articole, unde se află n şi nr) la nr, iar mr nu are relevanţă. Funcţia rang depinde de nr;

m şi mr, în cazul memorării nedense în ordine invers lexicografică. N se determină împărţind dimensiunea fişierului (mai puţin primele două articole, unde se află m şi mr) la mr, iar nr nu are relevanţă. Funcţia rang depinde de mr. Funcţia rang se calculează şi se utilizează numai dacă problema de rezolvat implică parcurgerea matricei în altă ordine decât cea în care este memorată în fişier, deci consultarea acestuia se realizează în acces direct.


Exemple: 20. Să se afişeze elementul maxim de pe fiecare coloană a unei matrice de dimensiuni mxn, memorate dens, într-un fişier binar, în ordine lexicografică. Primul articol conţine numărul de coloane.

• Observaţie: primul articol are dimensiune diferită de celelalte: numărul de coloane este de tip întreg iar elementele matricei sunt reale. Din dimensiunea totală a fişierului, primii sizeof(int) octeţi sunt ocupaţi de numărul de coloane, restul constituie matricea propriu-zisă. La calcularea poziţiei unui element în matrice trebuie ţinut cont de faptul că matricea nu începe la începutul fişierului, ci după sizeof(int) octeţi.

#include<stdio.h> void main() { FILE *f; float max, element; long i,j,r,m,n; f=fopen("MATRICE.DAT", "rb"); fread(&n,sizeof(int),1,f); //citire numar de coloane fseek(f,0,SEEK_END); m=(ftell(f)-sizeof(int))/(sizeof(float)*n); for(j=0;j<n;j++) { //pozitonare pe primul element din coloana j fseek(f,j*sizeof(float)+sizeof(int),SEEK_SET); fread(&element,sizeof(float),1,f); max=element; for(i=1;i<m;i++) { r=i*n+j; //rangul elementului in matrice fseek(f,r*sizeof(float)+sizeof(int),SEEK_SET); fread(&element,sizeof(float),1,f); if(element>max) max=element; } printf("\Maximul pe coloana %2d este %7.3f",j,max); } fclose(f); }

21. Să se determine elementul maxim de pe fiecare coloană a unei matrice de dimensiuni m x n, memorată nedens într-un fişier binar, în ordine lexicografică. Primele două articole conţin numărul de coloane efective şi, respectiv, numărul rezervat de coloane. Rezolvarea este similară cu exemplul anterior, cu următoarele modificări:

• din dimensiunea totală a fişierului, primii 2*sizeof(int) octeţi sunt ocupaţi de dimensiunile matricei (număr de coloane efectiv respectiv rezervat), iar restul constituie matricea propriu zisă. La calcularea poziţiei unui element în matrice trebuie ţinut cont de faptul că matricea nu începe la începutul fişierului, ci după 2*sizeof(int) octeţi.

• La calcularea rangului unui element (şi implicit a poziţiei sale în fişier) se foloseşte numărul de coloane rezervare, nu numărul de coloane efective.

06. Algoritmi de Prelucrare a Fisierelor Binare

Documents

Transcript of 06. Algoritmi de Prelucrare a Fisierelor Binare