model proiect stucturi de date
TRANSCRIPT
Facultatea de Cibernetica, Statistica si Informatica EconomicaCatedra de Informatica EconomicaDisciplina: Structuri de date
PROIECT
Administare evidenta studenti
Adoliu Alexandru 1053
Bucuresti, 2010
1
Cuprins
1. Introducere.................................................................................... 32. Definire problema……………………………………………….. 43. Datele de intrare…………………………………………………. 54. Formule de calcul si alegerea structurii de date eficiente……….. 65. Rezultate afisate sau stocate…………………………………….. 76. Algoritmi utilizati………………………………………………... 87. Concluzii…………………………………………………………. 9BIBLIOGRAFIEAnexa 1 texte sursa
2
1. Introducere
Obiectivul proiectului este alegeerea structurii eficiente destinate rezolvarii problemei de pentru administrarea evidentei in cadrul unei institutii de invatamant. Pentru rezolvarea acestei probleme au fost create 3 structuri de date. Fiecare structura avand per asamblu diferite grade de eficenta in functie de rezultatul cautat. Pentru prelucrarea date la nivel de iesire si intrare pe suport fizic se foloseste structura de tip lista simplu inlantuita, cat si pentru adaugari si eliminari de persoane.Pentru a cauta un element cea mai buna solutie reprezinta memorarea a elementelor listei simplu inlatuite intr-un arbore binar de cautare. Structura arborelui binar garanteaza eficenta in cautarea dupa elementul cheie.Pentru parcugerea tuturor elementelor din lista se foloseste un masiv unidimensional definit dinamic, fiind cea mai eficenta modalitate, cat si pentru intergogarea rapid a fiecarui element.Fiecare element se constituie din : nume (char[20]) ,cnp ( char [14]), nota1 (int) , nota2 (int) , nota3 (int) , nota4 (int) si media(float).La introducerea de date se face testare pentru validitatea codului numeric personal pentru ca elementele sa fie salvate corespunzator in lista. Salvarea pe suport fizic se face fara elementul de tip float media, acesta fiind calculat la restaurare de pe suportul fizic. La contruirea acestui proiect a fost consultata o bibliografie formata din patru carti carti si doua site-uri
3
2. Definirea problemei
Membri asupra carora se fac operatii de prelucrare, nu au restrictii de volum, dar se poate estima ca numarul total nu depaseste 50.La reconstructia de pe suport fizic au loc operatii de calcul pentru elementul media(float), salvarea lui pe suport nefiind eficenta, dat fiind faptul ca rezulta din operatii cu alte date de identificare. Coletia de date se configureaza modul de grupare a datelor se face in structuri omogene. Proiectul asigura salvarea/restaurarea pe/de pe suport fizic, adaugarea unui element , stergea unui element, gasirea dupa codul numeric personal unui element cu vizualizarea pe monitor a elementelor sale, stergerea studentilor cu o nota mai mica ca 5, si calculul mediei generale a intregii comunitati de studenti
4
3. Datele de intrare
Intializarea structurii se face prin citirea din fisierul „date.in”, a elementelor nume, cnp, si patru note, elementul media fiind rezultat in urma prelucarii notelor. Fisierul „date.in” contine pe fiecare linie elementele: nume (char[20]) ,cnp ( char [14]), nota1 (int) , nota2 (int) , nota3 (int) si nota4 (int). Programul citeste si memoreaza elementele pana la terminarea parcurgerii fisierului.Programul ingaduie introducerea de noi elemente se poate face si de la tastatura, dar verifica si valaditatea codului numeric personal. Pentru structura arbore binar si pentru masivul unidimensional se fac transformari din lista simplu inlantuita prelund elementele listei.
5
4. Formule de calcul si alegerea structurii de date eficiente
Structura de date cea mai eficenta pentru rezolvarea problemei este lista simplu inlatuita, deoarece asigura flexibilitate fosirii memoriei fata de masivul unidimensional. Dat fiind faptul ca pe masura avansarii in timp for exista coduri numerice personale cat mai recente, memorarea in arbore binar fiind in dezavantajos pentru subarborii drepti vor devenii din ce in ce mai numerosi.Arborele binar faciliteaza cautarea in functie de cheia aleasa (codul numeric persoanal), insa returnarea elementului/elementelor cautat dupa un nume, este necesara parcurgerea in intregime a arborelui.
6
5. Rezultate afisate sau stocate
Fiecare optiune a problemei are ca rezultat afisarea unui mesaj de tip text aflat in corpul void main() si in in interiorul functiilor (ex: cout<<"\nS-a citit din fisier!\n"; cout<<"\n CNP incorect!\nCNP : "; cout<<"\nS-a salvat in fisier!\n"<<endl; etc.). Cat si mesaje de tipul : constanta text alaturat cu valoare variabila in functie de structura curenta : cout<<"\nMedia generala este : "<<calcMedia(nrStudenti,v)<<endl;.La nivelul scrierii de date in fisier, nu se scrie nimic altceva decat valorile elementelor pentru a facilita recostituirea fara prelucrare de text.
7
6. Algoritmi utilizati
Proiectul foloseste algoritmi de verificare a codului numeric personal si de compararea de doua siruri de caractere. Primul are doua variante de valori care sa fie returnate 0 si 1 (0 pentru cod invalit si respectiv 1 pentru cod valid). Algoritmul secund compara alfabetic doua siruri de caractere si returneaza valorile:
-1 pentru sirul intai mai mic ca sirul
Algoritmii care se construiesc sunt de rutina. Exista putine cazuri in care algoritmii sunt originali si mai ales conduc la solutionarea unor probleme de exceptie.In acest caz trebuie sa se elaboreze di demonstratiile prin care se arata ca intr-adevar, algoritmii sunt cei cautati.
8
7. Concluzii
Modificarea structurii elementelor indiduale (de exemplu : adaugare de detaliu, eliminare detaliu) trebuie insotita de modificarea cosului sursa cat si de operatiuni de modificare a fisierului salvat pe disc
9
Bibliografie
Memorare pe suport fizic SMEUREANU Ion, DARDALA Marian PROGRAMAREA ORIENTATA OBIECT in LIMBAJ C++Editura CISON, Bucuresti, 2002
Operatii cu masive unidimensionale
IVASC Cornelia, PRUNA MonaTEHNICI DE PROGRAMARE (aplicatii de laborator)Editura PETRION, Bucuresti, 1999
Operatii cu lista simplu inlatuita
ROSCA Ion Gh., GHILIC-MICU Bogdan, COCIANU Catalina-Lucia, STOICA Marin, USCATU CristianProgramarea calculatoarelor : stiinta invatarii unui limbaj de programare : teorie si aplicatiiEditura ASE, Bucuresti, 2003
Operatii cu arborii binari IVAN Ion, IONITA Catalin, BOJA Catalin, POPA Marius, POCOVNICU Adrian, MILODIN DanielPRACTICA DEZVOLTARII SOFTWARE ORIENTATA PE STRUCTURI DE DATEEditura ASE, Bucuresti, 2004
10
#include<stdio.h>#include<string.h>#include<malloc.h>#include<iostream>#include<conio.h>using namespace std;
typedef struct student{
char nume[20];char cnp[14];int nota1,nota2,nota3,nota4;float media;student* urm;
};
typedef struct Arbore_Student{
char nume[20];char cnp[14];//cheieint nota1,nota2,nota3,nota4;float media;Arbore_Student* right;Arbore_Student* left;
};
struct VectorMedia{
char nume[20];float media;
};
Arbore_Student* creaza_nod(char numeF[20],char cnpF[14], int nota1F,int nota2F,int nota3F,int
nota4F, float mediaF, Arbore_Student* left, Arbore_Student*
right) {
Arbore_Student* temp = (Arbore_Student*)malloc(sizeof(Arbore_Student));
strcpy(temp->cnp,cnpF);strcpy(temp->nume,numeF);temp->nota1=nota1F;temp->nota2=nota2F;temp->nota3=nota3F;temp-
>nota4=nota4F;temp->media=mediaF;temp->left=left;temp->right=right;return temp;
}int compara_sir_de_caractere(char sir1[],char sir2[],int lungime){
for(int i=0;i<lungime;i++) if (sir1[i]<sir2[i]) return -1;else if(sir1[i]>sir2[i]) return 1;return 0;
}Arbore_Student* insereaza_nod(Arbore_Student* rad,
char numeF[20],char cnpF[14], int nota1F,int nota2F,int nota3F,int
nota4F,
11
float mediaF) {
Arbore_Student* aux = NULL;if (!rad) {return
creaza_nod(numeF,cnpF,nota1F,nota2F,nota3F,nota4F,mediaF, NULL, NULL);} else {
aux = rad;while (1) {
if ( compara_sir_de_caractere(cnpF,rad->cnp,13)==-1) {
if (rad->left) {rad = rad->left;} else {
rad->left = creaza_nod(numeF,cnpF,nota1F,nota2F,nota3F,nota4F,mediaF,NULL,NULL);
return aux;}
} else {
if (compara_sir_de_caractere(cnpF,rad->cnp,13)==1) {
if (rad->right) {rad = rad->right;} else {
rad->right = creaza_nod(numeF,cnpF,nota1F,nota2F,nota3F,nota4F,mediaF,NULL,NULL);
return aux;}
} else {
return aux;}
}}
}}
Arbore_Student* init_arbore_stud(student* cap,Arbore_Student* rad){
student* aux;aux=cap;while (aux) {
rad = insereaza_nod(rad, aux->nume,aux->cnp,aux->nota1,aux->nota2,aux->nota3,aux->nota4,aux->media);
aux=aux->urm;}return rad;
}void init_lista_stud(student** cap){
int i;student *p, *q;char numeS[20];char cnpS[14];char sirdecar[10]; int n1,n2,n3,n4;
12
float mediaS;int afis[13];FILE *f;f=fopen("date.in","r");
fscanf(f,"%s",numeS);fscanf(f,"%s",cnpS);fscanf(f,"%i",&n1);fscanf(f,"%i",&n2);fscanf(f,"%i",&n3);fscanf(f,"%i",&n4);mediaS=(n1+n2+n3+n4)/4;
(*cap)=(student*)malloc(sizeof(student));strcpy((*cap)->nume,numeS);strcpy((*cap)->cnp,cnpS);(*cap)->nota1=n1;(*cap)->nota2=n2;(*cap)->nota3=n3;(*cap)->nota4=n4;(*cap)->media=mediaS;(*cap)->urm=NULL;p=(*cap);
while (!feof(f)){
fscanf(f,"%s",numeS);fscanf(f,"%s",cnpS);fscanf(f,"%i",&n1);fscanf(f,"%i",&n2);fscanf(f,"%i",&n3);fscanf(f,"%i",&n4);mediaS=(n1+n2+n3+n4)/4;
q=(student*)malloc(sizeof(student));strcpy(q->nume,numeS);strcpy(q->cnp,cnpS);q->nota1=n1;q->nota2=n2;q->nota3=n3;q->nota4=n4;q->media=mediaS;q->urm=NULL;p->urm=q;p=q;
}
fclose(f);}
student* adauga(student* cap,char* n,char cnp1[],int n1,int n2,int n3,int n4){
student* nou;nou=(student*)malloc(sizeof(student));strcpy(nou->nume,n);int i=0;while (i<14){ nou->cnp[i]=cnp1[i]; i++;}nou->nota1=n1;nou->nota2=n2;nou->nota3=n3;nou->nota4=n4;nou->media=(n1+n2+n3+n4)/4;nou->urm=NULL;if (cap==NULL) return nou;else
13
{student *t;t=cap;while (t->urm) t=t->urm;t->urm=nou;return cap;
}}int verificaCNP(char cnp[]){
int vector[14];// vector asociat caracterelor din char cnp/ prima faza va fi sex/an/luna/zi , apoi fiecare caracter
int i;int b=1;vector[0]=(int)cnp[0]-48;//valorea ascii 48 este 0if ((vector[0]<1)||(vector[0]>2)) {b=0;}//valori asociate sexuluivector[1]=( (int)cnp[1]-48)*10 + (int)cnp[2]-48; //anul nasteriivector[2]=( (int)cnp[3]-48)*10 + (int)cnp[4]-48; //luna nasteriivector[3]=( (int)cnp[5]-48)*10 + (int)cnp[6]-48; //ziua nasteriiif ((vector[2]<1) || (vector[2]>12)) {b=0;}//luna 1-12if ((vector[3]<1) ||(vector[3]>31)) b=0;if (((vector[2]==2)&&(vector[1]%4==0)) && (vector[3]>29)) {b=0;}if (((vector[2]==2)&&(vector[1]%4!=0)) && (vector[3]>28)) {b=0;}if ((vector[2]=4)&&(vector[3]>30)) {b=0;}if ((vector[2]=6)&&(vector[3]>30)) {b=0;}if ((vector[2]=9)&&(vector[3]>30)) {b=0;}if ((vector[2]=11)&&(vector[3]>30)) {b=0;}for(i=1;i<13;i++) {
vector[i]=(int)cnp[i]-48;if ((vector[i]<0)||(vector[i]>9)) {b=0;}
}return b;}
void scrieInFis(student *cap){FILE *f;f=fopen("date.in","w+");student* t;t=cap;while(t){fprintf(f,"%s\n%s\n%i\n%i\n%i\n%i\n",t->nume,t->cnp,t->nota1,t-
>nota2,t->nota3,t->nota4);t=t->urm;}fclose(f);
}int compS(char* n1,char* n2){
int i=0;if (strlen(n1)!=strlen(n2)) return 0;else while (i<(int)strlen(n1)) {if (n1[i]!=n2[i]) return 0;i++;}return 1;
}student* stergeDupaNume(student *cap,char* n){ student *aux, *p; if (cap==NULL){printf("\nEroare: lista e vida\n");return NULL;} else if (compS(cap->nume,n)==1){aux=cap;cap=cap->urm; free(aux);return cap;} else
{ p=cap;while(p->urm!=NULL)
14
{if (p->urm != NULL && compS(p->urm->nume,n)==1)
{aux=p->urm;p->urm=aux->urm; // adica p->urm=p-
>urm->urm;free(aux);
}p=p->urm;
}return cap;}
}student* stergeNeprom(student *cap){ student *aux, *p; if (cap==NULL){printf("\nEroare: lista e vida\n");return NULL;}
else if ((((cap->nota1<5)&&(cap->nota2<5))&&(cap->nota3<5))&&(cap->nota4<5)){aux=cap;cap=cap->urm; free(aux);return cap;} else
{ p=cap;while(p->urm!=NULL){
if (p->urm != NULL && ((((p->nota1<5)&&(p->nota2<5))&&(p->nota3<5))&&(p->nota4<5)))
{aux=p->urm;p->urm=aux->urm; // adica p->urm=p-
>urm->urm;free(aux);
}p=p->urm;
}return cap;}
}void print(student *cap){
student* t;t=cap;while (t){
cout<<"NUME : "<<t->nume<<"\t CNP : "<<t->cnp<<"\t media : "<<t->media<<endl;
t=t->urm;}
}void cautaAB(Arbore_Student* r,char *cnpC){
Arbore_Student *aux;aux=r;while(aux&&(compara_sir_de_caractere(aux->cnp,cnpC,13)!=0)){if (compara_sir_de_caractere(cnpC,aux->cnp,13)==-1) aux=aux->left;else if (compara_sir_de_caractere(cnpC,aux->cnp,13)==1) aux=aux-
>right;};if (aux&&(compara_sir_de_caractere(aux->cnp,cnpC,13)==0))
cout<<"NUME : "<<aux->nume<<"\t CNP : "<<aux->cnp<<"\t media : "<<aux->media<<endl;
else cout<<"\nNodul cautat nu exista in arbore!\n";
}int numaraStudenti(student *cap)
15
{int k;student *t;t=cap;k=0;while (t){k++;t=t->urm;}return k;
}void incarcaVector(student *cap,VectorMedia *v){
student *t;int k=0;t=cap;while (t) {
v[k].media=t->media;strcpy(v[k].nume,t->nume);t=t->urm;k++;
}}
float calcMedia(int n,VectorMedia v[]){
float m=0;int i;for(i=0;i<n;i++) m+=v[i].media;m=m/n;return m;
}void meniu(){
cout<<"\n1. Citeste din fisier"<<endl;cout<<"2. Adauga student"<<endl;cout<<"3. Salveaza in fisier"<<endl;cout<<"4. Sterge dupa nume"<<endl;cout<<"5. Afisare listei de studenti pe monitor"<<endl;cout<<"6. Sterge studentii cu restante"<<endl;cout<<"7. Transfer lista in Arbore Binar"<<endl;cout<<"8. Cauta in arbore dupa cnp"<<endl;cout<<"9. Calculeaza media folosind vectorul de articole"<<endl;cout<<"\n0. IESIRE!"<<endl;
cout<<"\n Optiunea Dumneavoatra =";}void main(){
student *a;Arbore_Student *arb_stud;VectorMedia *v;int nrStudenti;a=NULL;meniu();char optiune='1';while (optiune!='0'){
cin>>optiune;if(((optiune>='0')&&(optiune<='9'))||(optiune=='n')){
switch(optiune){
16
case '1':init_lista_stud(&a);cout<<"\nS-a citit din fisier!\n";getch();meniu();break;
case '2':cout<<"\nIntroduceti datele: ";char n[20];cout<<"\nNume : ";cin>>n;char cnpS[14];cout<<"\nCNP :
";scanf("%s",cnpS);//1850522330522while (verificaCNP(cnpS)!=1) {cout<<"\n CNP
incorect!\nCNP : ";scanf("%s",cnpS);}int n1,n2,n3,n4;cout<<"\nNota 1 : ";scanf("%i",&n1);cout<<"\
nNota 2 : ";scanf("%i",&n2);cout<<"\nNota 3 : ";scanf("%i",&n3);cout<<"\
nNota 4 : ";scanf("%i",&n4);float m;m=(n1+n2+n3+n4)/4;a=adauga(a,n,cnpS,n1,n2,n3,n4);cout<<"\n Student adaugat\n";getch();meniu();break;
case '3': scrieInFis(a);cout<<"\nS-a salvat in fisier!\n"<<endl;getch();meniu();break;
case '4':cout<<"\nIntroduceti numele studentului propus
catre eliminare :";cin>>n;a=stergeDupaNume(a,n);getch();meniu();break;
case '5':print(a);getch();meniu();break;
case '6':a=stergeNeprom(a);getch();meniu();break;
case '7':arb_stud=NULL;arb_stud=init_arbore_stud(a,arb_stud);getch();meniu();break;
case '8':cout<<"\nIntroduceti CNP persoanei cautate:";cin>>n;cautaAB(arb_stud,n);getch();
17
meniu();break;
case '9':
v=(VectorMedia*)malloc(numaraStudenti(a)*sizeof(VectorMedia));incarcaVector(a,v);nrStudenti=numaraStudenti(a);cout<<"\nMedia generala este :
"<<calcMedia(nrStudenti,v)<<endl;getch();meniu();break;
case '0': break;
}
}else cout<<"Optiunea nu este in meniu!Mai incearca"<<endl;
}
}
18