ACADEMIA DE STUDII ECONOMICE

FACULTATEA DE CIBERNETICa, STATISTICa si INFORMATICA ECONOMICA

Structuri de date

PROIECT

ORAR

CUPRINS

Introducere ...............  pag. 2

Descrierea problemei ............ pag. 3

Structura programului pag. 4

Structuri de date utilizate .......... pag. 5

Proceduri de prelucrare ........... pag. 8

Concluzii .................pag. 11

Bibliografie ................pag. 12

1. INTRODUCERE

1.1 Obiectivul problemei :

Aceasta aplicatie informatica are ca obiectiv gestionarea cat mai buna a orarului unei facultati pentru un an de studiu. Prin intermediul ei se poate genera o varianta de orar la un moment dat, variantele de orar ale unui profesor la un moment dat si variantele posibile de orar pentru o anumita grupa la un moment dat.

1.2 Necesitatea :

Aceasta aplicatie, pe langa generarea orarului (in loc de orar poate fi orice alta structura care se doreste sa aibe inregistrari,unice, adica sa nu se regaseasca in cele afisate anterior.) realizeaza si implementarea diferitelor operatii pe structurile alese: adaugarea unui nou nod in lista si in arbore bianr de cautare, cautarea unui element dupa cheie unica in arbore si in lista, stergerea unei inregistrari din lista si arbore. De asemenea mai realizeaza si diferite tipuri de conversii, cum ar fi: din fisier in arbore binar de cautare si din arbore in fisier, din fisier in lista simplu inlantuita si din lista simpla in fisier, din fisier in vector memorati dinamic.

1.3 Mijloace de realizare :

Aplicatia a fost realizata in Microsoft Visual Studio 6.0 (Microsoft Visual C++ 6.0).

Datele de intrare, dupa ce acestea au fost in prealabil validate, s-au incarcat in fisierele binare corespunzatoare celor 4 structuri:prof.dat, materii.dat, grupe.dat si sali.dat, apoi aceste fisiere au fost convertite in structuri de tip arbore binar de cautare, lista sumplu inlantuita, respectiv masiv unidimensional memorat dinamic astfel incat resuresele sa fie alocate corespunzator si sa permita prelucrarie cat mai eficiente.

Aplicatia este realizata in Microsoft Visual Studio 6.0 mai precis Microsoft Visual C++ 6.0

2. DESCRIEREA PROBLEMEI

Avand de rezolvat problema generarii unei variante de orar al unei facultati, am definit cele 4 structuri initiale (pentru profesori, materii, grupe si sali) cu structurile arborescente aferente, urmand apoi procesul introducerii datelor in fosiere binare nu inaintea ca acestea sa fie valide. Pentru a verifica acest lucru am realizat o functie care verifica daca un sir de caractere dat de la tastatura este numeric sau nu. In caz afirmativ, pe langa aceasta conditie , se mai verifica si unicitatea codurilor de inregistrare (programul nu ma lasa sa introduc doua coduri identice) .

Pe langa operatiile de adaugare de noi inregistrari in liste si arbori, cautari dupa cheie si stergere de elemente din lista si arbore identificate dupe codul unic de inregistrare, aplicatia genereaza si o varianta a unui orar la o anumita ora (adica grupele, salile si profesorii trebuie sa nu coincida; materiile pot coincide deoarece pot exista mai multi profesori de aceeasi matarie), pentru un anumit profesor (adica ce variante de orar ar putea avea din cele care indeplinesc conditiile ) si pentru o anumita grupa.

Pentru generarea orarului am facut conversii fin cele 4 fisiere de intrare in vectori alocati dinamic si am obtinut un vector vect_o de tip orar (care contine urmatoarele campuri:codul grupei, denumirea materiei, codul salii si numele profesorului). Pentru a ajunge la acest vector trebuie sa punem o serie de filtre inregistrarilor din fisiere, cum ar fi:tipul profesorului trebuie sa fie egal cu tipul materiei (adica un profesor preda materia respetiva), numarul de studenti ai unei grupe sa fie mai mic decat numarul de locuri di sala, numarul maxim de ore al profesorului trebuie sa fir mai mic decat numarul de ore care ar trebui sa se faca la disciplina respectiva.

3. STRUCTURA PROGRAMULUI

Aplicatia denumita proiect_orar.cpp este structurata astfel: mai intai sunt definite structurile folosite in program (pentru profesori, materii, grupe si sali) si structurile arborescente aferente acestora (arbore_profesor, arbore_materii, arbore_grupe, arbore_sali), plus o structura noua orar (care ne va ajuta la generarea orarului), apoi sunt definite functiile care lucreaza cu structurile: profesorilor (functii pentru introducerea inregistrarilor, de afisare a datelor initiale din fisiere, de adaugare a unui nod in arbore, de conversie a fisierului in arbore, de parcurgere a arborelui, de afisare a continutului arborelui in fisier text, de cautare dupa codul unic de inregistrare, de stergere a unui nod din arbore, de conversie a fisierului in vector de tip structura profesor), materiilor (functii pentru introducerea inregistrarilor, de afisare a datelor initiale din fisiere, de adaugare a unui nod in arbore, de conversie a fisierului in arbore, de parcurgere a arborelui, de afisare a continutului arborelui in fisier text, de cautare dupa codul unic de inregistrare, de stergere a unui nod din arbore, de conversie a fisierului in vector de tip structura profesor), grupelor (functii pentru introducerea inregistrarilor, de afisare a datelor initiale din fisiere, de adaugare a unei noi inregistrari in lista, de parcuregere a listei, de afisare a continutului listei in fisier text, cautare a unei inregistrari dupa codul unic de inregistrare,de conversie a fisierului in lista simplu inlantuita, de stergere a unei informatii din lista identificata prin codul unic de inregistrare ) si salilor (functii pentru introducerea inregistrarilor, de afisare a datelor initiale din fisiere, de adaugare a unei noi inregistrari in lista, de parcuregere a listei, de afisare a continutului listei in fisier text, cautare a unei inregistrari dupa codul unic de inregistrare,de conversie a fisierului in lista simplu inlantuita, de stergere a unei informatii din lista identificata prin codul unic de inregistrare ).

Toate aceste functii se gasesc apelate in meniul aplicatiei, care contine o instructiune switch cu un grup de 28 actiuni particularizate pentru cele 4 structuri.

Ramurile principale de la care au fost apoi particularizate toate ramificatiile sunt urmatoarele:

- CREAREA FISIERELOR (de creare a celor 4 fisiere)

- AFISAREA INFORMATIILOR (de afisare a continuitui arborelui)

- ADAUGAREA DE NOI INREGISTRARI (adaugarea unui nod in arbore)

- CAUTARI DUPA CODUL UNIC DE INREGISTRARE (de cautare dupa cod)

- STERGERI DUPA CODUL UNIC DE INREGISTRARE (de stergere a unei inregistrari identificata prin codul unic de inregistrare)

- GENERARE ORAR (genereaza o varianta de orar pentru o singura ora si determina costul unei asemenea variante prin insumarea salariilor profesorilor care se considera ca au ora la momentul respectiv, genereaza variantele de orar pentru o anumita grupa si pentru un anumit profesor)

- GENERARE DE RAPOARTE TEXT (inainte de incheierea sesiunii de lucru cu aplicatia, se fac actualizarile fisierelor initiale sub forma de rapoarte in fisiere text , dand posibilitatea utilizatorului de a denumi fisierul in care vor aparea inregistrarile tastand comanda: afisare nume_fisier.txt in meniul aplicatiei)

4. STRUCTURI DE DATE UTILIZATE

Pentru rezolvarea aplicatiei am folosit urmatoarele tipuri de structuri si anume :

structuri simple de tip articol

arbori binari de cautare

liste simplu inlantuite

masive unidimensionale memorate dinamic

1 ) Articolele sunt constituite prin compunerea mai multor tipuri de date date fundamentale, rezultand ansambluri eterogene de elemente de baza, sau elemente agregate.

Necesitatea utilizarii articolelor deriva din complexitatea obiectului real, care este identificat si descries de o multime de caracteristici unice. Lipsa unui indicator agregat care sa insumeze intr-o singura valoare, nivelurile tuturor caracteristicilor si care sa fie memorat intr-o variabila de tip fundamental (integer, float, char, double, bool), este suplinita de structura de date de tip articol. Aceasta este o multime de caracteristici ce sunt implementate prin intermediul tipurilor elementare de date sau prin intermediul altor articole.

In continuare vom prezenta structurile folosite efectiv de programul proiect_orar.cpp si anume :

In plus mai avem un articol de tip orar cu urmatoarea structura:

struct orar

Arborii binari de cautare sunt arbori binari in care nodurile sunt memorate ordonat in functie de o cheie. Toate nodurile din arbore au in subarborele stang noduri care au chei mai mici si in subarborele drept chei mai mari.

Arborii de cautare permit regasirea rapida a informatiilor (O(log n)) atat timp cat

arborele este echilibrat. In cazul cel mai defavorabil, timpul de cautare este identic cu cel

al unei liste simplu inlantuite.

Operatiile de baza pe un arbore de cautare sunt urmatoarele:

Cautare  - Se compara cheia cu nodul curent. Daca este mai egala, am gasit nodul, daca

este mai mica cautam in subarborele stang, altfel cautam in subarborele drept.

Cautarea se opreste cand nodul a fost gasit sau s-a atins baza arborelui.

Adaugare - Se cauta folosind algoritmul de cautare pozitia in arbore si se aloca memoria

si se face legatura cu nodul parinte.

Stergere - Se cauta nodul de sters si se sterge nodul. Subarborele drept este avansat in

locul nodului sters, iar subarborele stang este mutat ca fiu al celui mai mic

element din subarborele drept.

Lista simplu inlantuita reprezinta o multime dinamica de structuri recursive de acelasi tip, numite noduri, pentru care este definita o singura relatie de ordine cu ajutorul unor pointeri din compunerea acestora. De obicei aceasta relatie este cea de succesor, adica fiecare nod contine un pointer a carui valoare reprezinta adresa nodului urmator din lista.

Intr-o lista simplu inlantuita exista intotdeauna un nod care u mai are succesor, precum si un nod care nu este succesorul nici unui alt nod. Aceste noduri constituie capetele liste simplu inlantuite. Pentru gestionarea acestui tip de lista se definesc 2 pointeri cap si ultim pentru a referi nodurile terminale ale listei. Daca specificarea inceputului listei pri poiterul cap este obligatorie, utilizarea pointerului de sfarsit ultim este optionala, insa eficienta atunci cand se doreste crearea listei in ordine naturala printr-o insertie a noilor noduri la sfarsitul acesteia.

Listele simplu inlantuite sunt structuri de date dinamice omogene. Spre deosebire de masive, listele nu sunt alocate ca blocuri omogene de memorie, ci ca elemente

separate de memorie. Fiecare nod al listei contine, in afara ce informatia utila, adresa

urmatorului element. Aceasta organizare permite numai acces secvential la elementele

listei.

Pentru accesarea listei trebuie cunoscuta adresa primului element (numita capul

listei); elementele urmatoare sunt accesate parcurgand lista.

In cazul in care elemenul este ultimul din lista, pointerul urmator va avea valoarea

NULL.

Principalele operatii cu liste sunt:

Parcurgere si afisare lista

Lista este parcursa pornind de la pointerul spre primul element si avansand folosind

pointerii din structura pana la sfarsitul listei (pointer NULL).

Inserare element

Inserarea unui element se poate face la inceputul sau la sfarsitul listei.

a) Inserare la inceput

Acesta este cazul cel mai simplu: trebuie doar alocat elementul, legat de primul

element din lista si repozitionarea capului listei:

b) Inserare la sfarsitul listei

In acest caz trebuie intai parcursa lista si dupa aceea adaugat elementul si legat de

restul listei. De asemenea, trebuie avut in vedere cazul in care lista este vida.

c) inserare dupa un element dat inserare in interior

Cautare element

Cautarea unui element dintr-o lista presupune parcurgerea listei pentru identificarea

nodului in functie de un criteriu. Cele mai uzuale criterii sunt cele legate de pozitia in

cadrul listei si de informatiile utile continute de nod. Rezultatul operatiei este adresa

primului element gasit sau NULL.

a) Cautarea dupa pozitie

Se avanseaza pointerul cu numarul de pozitii specificat:

b) Cautarea dupa valoare

Se parcurge lista pana la epuizarea acesteia sau identificarea elementului:

Stergere element

a) Stergerea unui element din interiorul listei (diferit de capul listei)

In acest caz avem nevoie de adresa predecesorului elementului de sters. Se modifica

legaturile in sensul scurtcircuitarii elementului de sters, dupa care se elibereaza

memoria corespunzatoare elementului de sters:

b) Stergerea unui element de pe o anumita pozitie

Daca elementul este primul din lista, atunci se modifica capul listei, altfel se cauta

elemental si se sterge folosind functia definite anterior:

c) stergerea dupa o valoare

Se cauta predecesorul elementului si se foloseste functia de stergere element:5

5. PROCEDURI   SI FUNCTII DE PRELUCRARE

In programul proiect_orar apar definite urmatoarele functii si proceduri:

- int valid(char s[20],int &num - o functie pentru validarea caracterelor numerice (returneaza 1 daca sirul introdus de la tastatura este valid si 0 in caz contrar )

- void creare_fisier_profesori(FILE *f,profesor prof) - prin intermediul careia se realizeaza introducerea inregistrarilor pentru profesori

- void afisare_fisier_profesori(FILE *f,profesor prof) - pentru afisare datelor initiale din fisierul: profesori

- arbore_profesor *adaugare_profesor(arbore_profesor *rad_prof,profesor prof) - adaugarea unui nod in arbore pentru profesor

void fisier_prof_to_arbore(arbore_profesor *&rad_prof - realizeaza conversie de fisier in arbore pentru profesori

- void parcurgere_profesori(arbore_profesor *rad_prof) - parcurgerea arborelui pentru profesori (parcurgea in inordinr de la arbori binari)

- void parcurgere_profesori_text(arbore_profesor *rad_prof,FILE *f) - parcurgerea arborelui pentru profesori si afisare in fisier text

- arbore_profesor *cauta_profesor(arbore_profesor *rad_prof,int cod_p) - cautare profesor dupa cod

- void stergere_prof(int x,arbore_profesor *&p) stergerea unui nod din arborele pentru profesori

- void fisier_vect_p(profesor *&vect_p) - conversie din fisierul pentru profesori in vectorul vect_p

- void creare_fisier_materii(FILE *f,materii mat) - introducerea inregistrarilor pentru materii

- void afisare_fisier_materii(FILE *f,materii mat) - afisarea datelor initiale din fisierul: materii

- arbore_materii *adaugare_materie(arbore_materii *rad_mat,materii mat) - adaugarea unui nod in arbore pentru materii

-void fisier_materii_to_arbore(arbore_materii *&rad_mat)- conversie de fisier in arbore pentru materii

void parcurgere_materii(arbore_materii *rad_mat) - parcurgerea arborelui pentru materii

- void parcurgere_materii_text(arbore_materii *rad_mat,FILE *f) - parcurgerea arborelui pentru materii si afisare in fisier text

- arbore_materii *cauta_materie(arbore_materii *rad_mat,int cod_m) - cautare materie dupa cod

- void stergere_mat(int x,arbore_materii *&p) - sterg nod materii

- void fisier_vect_m(materii *&vect_m) - conversie din fisierul pentru materii in vectorul vect_m

- void fisier_vect_gr(grupe *&vect_gr) - conversie din fisierul pentru grupe in vectorul vect_gr

- void creare_fisier_grupe(FILE *f,grupe gr) - ntroducerea inregistrarilor pentru grupe

- void afisare_fisier_grupe(FILE *f,grupe gr) - afisare datelor initiale din fisierul: grupe

- void adaugare_grupe(lista_grupe *&lista_gr,grupe inf) - adaugarea unei noi inregistrari in lista grupelor

- void parcurgere_grupe(lista_grupe *lista_gr) - parcurgerea listei pentru grupe

- int sterge_grupe(struct lista_grupe *&rad_gr,int a) - stergerea unei grupe dupa cod

-void creare_fisier_sali(FILE *f,sali s) - introducerea inregistrarilor pentru sali

- void afisare_fisier_sali(FILE *f,sali s) - afisare datelor initiale din fisierul: sali

- void adaugare_sali(lista_sali *&lista_s,sali inf) -adaugarea unei noi inregistrari petru sali

- void parcurgere_sali(lista_sali *lista_s) - parcurgerea listei pentru sali

- void fisier_vect_s(sali *&vect_s) - conversie din fisierul pentru sali in vectorul vect_s

- lista_sali *cauta_sala(lista_sali *lista_s,int cod_s)- cautarea unei sali dupa cod

-void lista_fisier_sali(FILE *f,lista_sali *lista_s) - conversie lista in fisier pentru sali

- void fisier_sali_to_lista(lista_sali *&lista_s) - conversie lista din fisier pentru sali

- void afis_text_profesori(FILE *f,FILE *g - afisare profesori in fisier text

void vector(int nr_p,int nr_m,int nr_gr,int nr_s,profesor *vect_p,materii *vect_m,grupe *vect_gr,sali *vect_s,orar *&vect_o,int &numar) - crearea vectorului pentru generarea orarului

- void orarul(int nr_p,profesor *vect_p,orar *vect_o,int numar) - generarea unei variante posibile de orar

- void orarul_profesorilor(orar *vect_o,int numar) - generarea unei variante pisibile pentru orarul profesorilor

- void orarul_grupelor(orar *vect_o,int numar) - generarea unei variante posibile pentru orarul unei grupe

- void cost_orar(int nr_p,profesor *vect_p,orar *vect_o,int numar) - generarea unei variante posibile de orar)

-void meniu() - este o procedura care afiseaza meniul atata timp cat nu se introduce 0 de la tastatura. Dupa afisarea meniului, utilizatorul isi poate alege varianta dorita din cele de pe ecran, iar dupa executare apare din nou meniul in eventualitatea ca acesta va mai dori testarea unei optiuni din meniu.

6. CONCLUZII

Programul realizat reprezinta varianta optima pentru rezolvarea problemei, deoarece asigura din punct de vedere fizic cea mai buna si rapida metoda de stocare a datelor: fisierul; si cea mai buna alternativa de regasire a datelor: arborele.

Fisierul binar reprezinta o metoda eleganta de stocare a informatiei, regasirea acesteia realizandu-se secvential, indexat sau in acces direct, in functie de necesitate si de cantitatea de informatie. In acest caz s-a ales accesul de tip direct-secvential la date, ceea ce ofera o performanta medie in procesul de regasire a datelor, a vitezei, a memoriei ocupate si al gradului de complexitate al programarii. Intr-adevar, accesul indexat ar fi fost indicat, dar in cazul acestui exemplu, in care informatia stocata e infima si timpul de acces ne fiind foarte important (deoarece nu se lucreaza cu mii de inregistrari), s-a ales metoda mai facila din punct de vedere a programarii.

Programul realizat reprezinta varianta optima pentru rezolvarea problemei, deoarece asigura din punct de vedere fizic cea mai buna si rapida metoda de stocare a datelor: fisierul; si cea mai buna alternativa de regasire a datelor: arborele. Folosind arborii, procesul de cautare al unui cuvant in arbore necesita, de obicei, mai putini pasi. In fiecare nod se realizeaza o ramificare, deoarece se continua cautarea fie in subarborele stang, fie in cel drept, fie se constata ca nodul respectiv contine chiar cuvantul cautat.

BIBLIOGRAFIE

[ SMEU01] Ion SMEUREANU, Marian DARDALA,"Programare in limbajul C/C++

Editura Cison, Bucuresti 2001