ACADEMIA DE STUDII ECONOMICE

FACULTATEA DE CIBERNETICa, STATISTICa si INFORMATICA ECONOMICA

Structuri de date

PROIECT

SISTEM PROGRAMABIL DE PRELUCRARE A DATELOR

SISTEM PROGRAMABIL DE PRELUCRARE A DATELOR

Introducere:

Obiectivul proiectului este acela de a permite rularea unor comenzi ce vor efectua prelucrari asupra unor fisiere de date. Aceste fisiere sunt de tip text si pot avea dimensiunea de pana la 2 GB. Programul permite optimizarea regasirii datelor cu ajutorul fisierelor index.

Necesitatea proiectului este data de nevoia simularii lucrului cu baze de date prin intermediul limbajelor de programare. Acest proiect realizeaza implementarea unor comenzi standard folosite de sistemele de gestiune a bazelor de date, cum ar fi: CREATE, OPEN, INSERT, DELETE, SELECT, INDEX, etc.

Utilitatea economica este aceea de a permite gestionarea grupelor de studenti in cadrul unei facultati. Pentru fiecare student se memoreaza trei caracteristici: codul studentului, numele acestuia si grupa din care face parte. Programul este util pentru facilitarea lucrului cu un numar mare de studenti in cadrul secretariatului unei facultati.

Mijloacele de realizare: Limbajul de programare folosit pentru realizarea proiectului este limbajul C. Mediul de dezvoltare a aplicatiei a fost Microsoft Visual Studio 6.0, iar compilatorul folosit a fost Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86.

Structura programului:

Programul face referire la articole de tip "student" cu urmatoarea structura:

Typedef struct student;

In program se utilizeaza doar doua tipuri de date: numeric (date te tip int) si sir de caractere (date te tip char).

Acest program preia comenzile (datele de intrare) dintr-un fisier text specificat ca parametru in linia de comanda. Acest fisier are denumirea: instructiuni1.txt, putand fi creat prin editare propriu-zisa (cu Notepad). Programul sursa va executa secvential instructiunile primite, operand modificarile sau regasirile asupra datelor din celelalte fisiere.

Structura sistemului este prezentata in urmatoarea figura:

Figura 1.

De exemplu, daca fisierul instructiuni1.txt are urmatoarea structura:

CREATE studenti.csv Cod NUMERIC, Nume CHAR(120), Grupa NUMERIC;

INSERT 1, Ionescu Ion, 1022;

INSERT 2, Popescu Gheorghe, 1230;

INSERT 3, Vasilescu Dan, 1567;

In acest caz, programul realizeaza crearea fisierului text studenti.csv cu urmatorul continut:

1, Ionescu Ion, 1022

2, Popescu Gheorghe, 1230

3, Vasilescu Dan, 1567

Programul citeste continutul fisierului de comenzi si in momentul detectarii cuvintelor cheie CREATE si INSERT va apela doua proceduri: prima, care realizeaza crearea fisierului gol studenti.csv , si cea de-a doua care realizeaza popularea acestuia cu cele 3 articole.

Programul afiseaza intr-o fereastra cmd toate comenzile pe care le-a primit (continutul fisierului de comenzi instructiuni1.txt). Aceasta fereastra este prezentata in figura 2:

Figura 2.

Fisierul studenti.csv este un fisier de tip text care se deschide cu editorul Microsoft Excel.

Continutul acestuia este prezentat in Figura 3:

Figura 3.

Structurile de date utilizate intern:

Programul utilizeaza urmatoarele structuri de date: fisiere, structuri arborescente (arbori binari de cautare), liste si cozi.

Fisierul este o colectie de date omogene stocate pe un suport de memorie externa.

Indiferent de limbajul de programare folosit, operatiile necesare pentru prelucarea fisierelor sunt urmatoarele:

Descrierea fisierului;

Asignarea fisierului intern (numele logic) la unul extern;

Deschiderea fisierului;

Operatii de acces la date;

Inchiderea fisierului.

In limbajul C exista doua niveluri de abordare a lucrului cu fisiere: nivelul inferior de prelucrare (fara gestiunea automata a zonelor tampon de intrare/iesire) si nivelul superior de prelucrare (se folosesc functii specializate de gestiune a fisierelor). Functiile de prelucrare la nivel superior a fisierelor trateaza fluxul de octeti acordandu-i o semnificatie oarecare. Putem spune ca, din punct de vedere al prelucrarii, la acest nivel ne putem referi la fisiere text si fisiere binare.

Fisierul de intrare instructiuni1.txt si fisierele de iesire sunt fisiere text cu urmatoarele caracteristici:

fiecare linie contine o singura inregistrare si se termina cu caracterele standard CR LF.

campurile dintr-o linie sunt separate prin virgula.

in cadrul sirurilor de caractere, ca de exemplu in campul Nume, spatiile sunt semnificative.

ordinea inregistrarilor din fisierele de date nu este importanta.

Arborii binari de cautare reprezinta un caz particular al arborilor binari, in care fiecare nod contine o informatie distincta numita cheie, cu proprietatea ca, pentru fiecare nod t, toate nodurile din subarborele stang au cheia mai mica decat cheia lui t si toate nodurile din subarborele drept au cheia mai mare decat cheia lui t.

Principalele operatii care se aplica asupra arborilor binari de cautare sunt: cautarea unui nod in arbore, inserarea unui nod, stergerea unui nod si parcurgerea arborelui.

Programul are implementate urmatoarele proceduri: crearea arborelui binar, inserarea unui nou nod in arbore si cele trei modalitati de parcurgere (preordine, inordine si postordine).

Continutul acestor proceduri este prezentat in partea de Anexe a acestui material.

Listele simplu inlantuite sunt structuri dinamice de date care contin un anumit numar de noduri, fiecare nod avand urmatoarea structura:

In cazul listei implementate in acest program, un nod al listei are urmatoarea structura:

struct infoutil ;

struct nodel ;

Principalele operatii elementare care se aplica asupra structurii de lista simplu inlantuita sunt urmatoarele: crearea listei, afisarea ei, inserarea unui nod pe o anumita pozitie, inserarea inaintea sau dupa un nod cu informatie data, stergerea unui nod al listei, etc.

Coada este un caz particular de lista care are urmatoarele caracteristici: inserarea unui nou element se face numai la sfarsit, iar stergera unui nod se face intotdeauna de pe pima pozitie.

In acest program este implementata urmatoarea structura de tip coada:

struct queue ;

Descrierea implementarii operatiilor de baza:

Programul implementeaza un set de instructiuni care trebuie execuate in ordinea in care apar in fisierul de comenzi. Exista trei tipuri de instructiuni:

Instructiuni pentru manipularea fisierelor: CREATE, OPEN, INDEX.

Instructiuni pentru modificarea datelor: INSERT, UPDATE, DELETE.

Instructiunea SELECT pentru regasirea informatiilor dintr-un fisier.

Instructiunea CREATE are sintaxa:

CREATE nume fisier nume_camp tip ( , nume_camp tip);

Aceasta creaza un fisier de date nou fara nici o inregistrare (un fisier text de lungime 0 cu numele specificat ca parametru). Instructiunea este implementata prin intermediul urmatoarei functii:

FILE* createFileComm(char* comm, queue* qFStr) else if (nrTok > 2) else

}

token = strtok(NULL, seps);

}

return f;

Functia realizeaza prelucrarea liniei care contine cuvantul CREATE din fisierul de comenzi astfel: cu ajutorul functiei strtok este impartita linia respectiva in cuvinte (stringuri) separate, si apoi este prelucrat fiecare string in parte. Se stie ca al doilea cuvant este numele fisierului care va fi creat. Este creata apoi coada qFStr care contine trei noduri avand informatiile utile urmatoare:

primul nod: Cod NUMERIC

al doilea nod: Nume CHAR(120)

al treilea nod: Grupa NUMERIC

Comanda OPEN are urmatoarea sintaxa:

OPEN nume fisier nume_camp tip ( , nume_camp tip);

Ea realizeaza deschiderea in vederea citirii si actualizarii a unui fisier existent. Seteaza fisierul primit ca parametru ca fiind fisier curent. Comanda OPEN este implementata in program prin urmatoarea functie:

FILE* openFileComm(char* comm, queue* qFStr) else if (nrTok > 2) else

}

token = strtok(NULL, seps);

}

return f;

Aceasta functie este foarte asemanatoare cu functia createFileComm , singura diferenta fiind aceea ca fisierul se deschide acum pentru citire si actualizare.

Instructiunea INSERT are sintaxa:

INSERT valoare_camp (, valoare_camp);

Comanda adauga o linie noua in fisierul de date studenti.csv. Nu se verifica daca o inregistrare care urmeaza sa fie inserata exista deja in fisierul de date. In program, inserarea se realizeaza prin urmatoarea procedura:

void insertValuesComm(char* comm, FILE* f)

Aceasta procedura realizeaza separarea liniei care trebuie inserata de separatorul ; " , iar apoi realizeaza adaugarea acestei linii in fisierul de date.

Instructiunea UPDATE are sintaxa:

UPDATE valoare_camp (, valoare_camp);

Aceasta comanda modifica o linie din fisierul de date, actualizand in acelasi timp si fisierul index. Comanda realizeaza urmatoarele operatii:

cauta inregistrarea de modificat dupa primul camp (campul Cod).

va inlocui valorile existente cu valorile primite ca parametru.

Acest lucru se realizeaza in program prin procedura:

void updateValuesComm(char* comm)

fgets(s,100,f);}

fputs('n',g);

fclose(f);fclose(g);

f=fopen('studenti.csv','w');

g=fopen('temp.csv','r');

rewind(g);rewind(f);

fgets(s,100,g);

while(!feof(g))

fclose(f);fclose(g);

indexComm();}

Updatarea unei linii in fisierul de date se realizeaza in aceasta procedura prin copierea tuturor celorlalte linii de dinaintea liniei de updatat intr-un fisier temporar, apoi se copiaza linia updatata tot in fisierul temporar, in continuarea celorlalte, si se reia copierea celorlalte linii de dupa linia de modificat in acelasi fisier temporar. In final se realizeaza scrierea fisierului temporar peste fisierul de date.

Comanda DELETE are urmatoarea sintaxa:

DELETE valoare-camp

Aceasta comanda sterge o inregistrare din fisierul curent, actualizand in acelasi timp si fisierul index. Valoarea specificata este valoarea campului Cod a randului de sters, care este si cheie primara.

In program stergerea se realizeaza prin urmatoarea procedura:

void deleteValuesComm(char* comm)

fputs('n',g);fclose(f);fclose(g);

f=fopen('studenti.csv','w');g=fopen('temp.csv','r');

rewind(g);rewind(f);

fgets(s,100,g);

while(!feof(g))

fclose(f);fclose(g);

indexComm(); }

Procedura de stergere se aseamana foarte mult cu cea de updatare, in sensul ca stergerea se realizeaza tot prin copierea intr-un fisier temporar a tuturor liniilor din fisierul de date, diferite de linia de sters, pentru ca apoi sa se realizeze scrierea fisierului temporar peste fisierul de date.

5. Implementare parser:

Parserul sau interpretorul de comenzi are rolul de a prelua comenzile din fisierul de comenzi instructiuni1.txt si de a apela procedurile sau functiile specificate in acel fisier.

Parsarea fisierului de comenzi este realizata in program prin urmatoarea procedura:

void parseAndExecuteCommandsFile(char* fPathComm)

}

fclose(fcommands);

}

return;

Procedura realizeaza citirea linie cu linie a fisierului de comenzi si pentru fiecare linie se verifica primele 4, 5 sau 6 caractere care descriu numele comenzii la care se refera linia respectiva. Dupa ce se identifica respectiva comanda, se apeleaza procedura care o implementeaza avand ca parametrii celelalte caractere din linia care descrie comanda.

6. Descriere indexare, selectie si optimizari:

Instructiunea INDEX are urmatoarea sintaxa:

INDEX nume_camp;

Comanda construieste un fisier index pentru campul specificat (in acest caz construieste fisierul index.csv pentru campul Cod), si indexeaza toate datele existente din fisierul curent dupa campul specificat.

Toate operatiile de actualizare executate asupra fisierului de date actualizeaza si acest fisier index.

Instructiunea este implementata in program prin urmatoare procedura:

void indexComm(void)

fclose(f);

fclose(g);

Aceasta procedura realizeaza copierea fisierului de date studenti.csv in fisierul index.csv , cu deosebirea ca in fisierul index, in fata fiecarei inregistrari se pune un numar de ordine.

Instructiunea SELECT are urmatoarea sintaxa:

SELECT nume_camp operator valoare_camp (, nume_camp operator valoare_camp) INTO nume_fisier;

Aceasta comanda va crea un fisier de date nou cu aceeasi structura cu cel existent, in care se vor inscrie numai inregistrarile care verifica conditiile specificate. Operatorii folositi pentru compararea datelor sunt "<, >, =". Fisierul de date nou are numele nume fisier, specificat in sintaxa comenzii.

Functia care realizeaza acest lucru este urmatoarea:

FILE *selectValuesComm(char *comm)

else if (strcmp(token,'Nume')==0)

token1 = strtok(NULL,separ);

}

}

token = strtok(NULL,seps);

}

token3= strtok(comm1,seps);

while (token3 != NULL)

token3=strtok(NULL,seps);

}

if (var==1)

fclose(g);

}

else if (var==2)

tt = strtok(NULL,separ1);}

fgets(s,100,g);}

fclose(g); }

return f;}

Functia realizeaza selectarea inregistrarilor din fisierul de date in urmatoarele doua cazuri:

cand Cod este cuprins intre o valoare minima si una maxima (de exemplu Cod>2,Cod<5);

cand Nume este mai mare ca o anumita valoare ( de exemplu Nume>C). In acest caz va memora in fisierul nou creat toate inregistrarile care au prima litera a numelui mai mare decat C.

Se foloseste functia strtok pentru separarea numelui campului de operator si de valoarea campului. Se memoreaza in variabilele cod1, cod2 si cod3 valorile campurilor din sintaxa instructiunii SELECT. Apoi se citeste fisierul de date linie cu linie si se verifica daca linia respectiva are cimpul Cod cuprins intre cod1 si cod2 sau campul Nume mai mare decat cod3. Daca da se memoreaza linia respectiva in fisierul nou creat. Daca nu se trece la linia urmatoare din fisierul de date si se continua verificarea.

Concluzii:

In urma elaborarii acestui proiect am ajuns la urmatoarele concluzii:

este destul de facil sa se implementeze intr-un limbaj de programare operatiile folosite de sistemele de gestiune a bazelor de date pentru a lucra cu volume mari de date stocate in fisiere.

odata implementate operatiile respective, programul poate rula cu orice tipuri de date facandu-se modificari minore asupra denumirilor de campuri.

se pot utiliza concomitent diferite structuri de date care sa conduca la rezultatul scontat.

desi utilizarea fisierelor memorate pe suportul extern conduce la incetinirea rularii aplicatiei, se asigura prin intermediul acestor fisiere o securitate a datelor in cazul caderilor de sistem sau tensiune. Astfel se evita pierderea datelor.

Bibliografie:

[ROSC03 Ion Gh. Rosca, Bogdan Ghilic Micu, Catalina Lucia Cocianu, Marian Stoica, Cristian Uscatu - Programarea calculatoarelor. Stiinta invatarii unui limbaj de programare. Teorie si aplicatii, Editura ASE, Bucuresti, 2003.

[ZAHA02] - M. D. Zaharia - Structuri de date si algoritmi. Exemple in limbajele C si C++, Editura Albastra, Cluj-Napoca, 2002.

[CRAU02] - M. Craus, C. Barsan - Structuri de date si algoritmi, Editura "Gh. Asachi", Iasi, 2002.

[NEGR00] - L. Negrescu - Limbajele C si C++, vol. 1, 2, Editura Albastra, Cluj-Napoca, 2000.

Anexe:

Codul sursa al programului este urmatorul:

#include <stdio.h>

#include <malloc.h>

#include <string.h>

struct information ;

struct BinaryTreeNode ;

struct infoutil ;

struct nodel ;

struct queue ;

BinaryTreeNode* createNode(information inf, BinaryTreeNode* l, BinaryTreeNode* r)

BinaryTreeNode* insertNode(BinaryTreeNode* root, information info) else    

} else

} else

}

}

}

void writeRLeftRight(BinaryTreeNode* root)

void writeLeftRRight(BinaryTreeNode* root)

void writeLeftRightR(BinaryTreeNode* root)

void put(queue* q, infoutil info)

infoutil get(queue* q) else

void printTheQueue(queue* q)

void parseAndExecuteCommandsFile(char*);

FILE* createFileComm(char*, queue*);

FILE* openFileComm(char* comm, queue* qFStr);

void insertValuesComm(char* comm, FILE* f);

void updateValuesComm(char* comm);

void deleteValuesComm(char* comm);

FILE* selectValuesComm(char*);

void indexComm(void);

int main(int argc, char** argv) else printf('n Utilizare:n TheProject01.exe FisierDeComenzi.txt ');

return 0;

void parseAndExecuteCommandsFile(char* fPathComm)

}

fclose(fcommands);

}

return;

FILE* createFileComm(char* comm, queue* qFStr) else if (nrTok > 2) else

}

token = strtok(NULL, seps);

}

return f;

FILE* openFileComm(char* comm, queue* qFStr) else if (nrTok > 2) else

}

token = strtok(NULL, seps);

}

return f;

void insertValuesComm(char* comm, FILE* f)

void updateValuesComm(char* comm)

fgets(s,100,f);

}

fputs('n',g);

fclose(f);

fclose(g);

f=fopen('studenti.csv','w');

g=fopen('temp.csv','r');

rewind(g);

rewind(f);

fgets(s,100,g);

while(!feof(g))

fclose(f);

fclose(g);

indexComm();

void deleteValuesComm(char* comm)

fputs('n',g);

fclose(f);

fclose(g);

f=fopen('studenti.csv','w');

g=fopen('temp.csv','r');

rewind(g);

rewind(f);

fgets(s,100,g);

while(!feof(g))

fclose(f);

fclose(g);

indexComm();

FILE *selectValuesComm(char *comm)

else if (strcmp(token,'Nume')==0)

token1 = strtok(NULL,separ);

}

}

token = strtok(NULL,seps);

}

token3= strtok(comm1,seps);

while (token3 != NULL)

token3=strtok(NULL,seps);

}

if (var==1)

fclose(g);

}

else if (var==2)

tt = strtok(NULL,separ1);

}

fgets(s,100,g);

}

fclose(g);

}

return f;

void indexComm(void)

fclose(f);

fclose(g);