Laborator 6

Exercitiu aplicativ

Fie un fisier continand codurile COR (Clasificarea Ocupatiilor din Romania) in ordine crescatoare. Fiecarei ocupatii ii corespunde o linie din fisier: codul COR (<999999), urmat de un spatiu, apoi denumirea ocupatiei. Fisierul se gaseste aici.

Se cere, sa se implementeze, urmatoarele cerinte, respectand ordinea cerintelor si folosind o singura structura de tip tablou:

a. Sa se caute folosind cautarea prin interpolare denumirea unei anumite ocupatii date de la tastatura prin cod.

b. Sa se ordoneze si sa afiseze intr-un fisier separat toate ocupatiile in ordine alfabetica (a->z).

c. Sa se afiseze toate ocupatiile care incep cu cuvantul "ministru".

d. Sa se ordoneze crescator, dupa cod, doar acele ocupatii care ocupa in tablou pozitii pare, fara insa a afecta pozitiile impare din tablou si sa se afiseze intr-un fisier separat tabloul astfel ordonat.

e. Sa se ordoneze tabloul in felul urmator: pe primele pozitii se afla ocupatiile cu coduri pare si pe pozitiile din urma se afla ocupatii cu coduri impare si sa se afiseze intr-un fisier separat tabloul astfel ordonat.

Observatii:

- Numarul maxim de inregistrari din fisier este de 5000

- Nu se permite folosirea unei a doua structuri de date de tip tablou pentru niciuna din cerinte.

- Se va puncta si eficienta fiecarei implementari in termeni O(f(n)).

Rezolvare

#include <stdio.h>

#include <stdlib.h>

#define NR_OCUPATII_MAX 5000

struct ocupatii

{

int id;

char nume[150];

}cor[NR_OCUPATII_MAX];

int nr_ocupatii=0;

void citire()

{

FILE *f;

f=fopen("FisierTest.txt","r");

if(f==NULL)

{

printf("Eroare la deschiderea fisierului de intrare");

exit(1);

}

nr_ocupatii=0;

while(!feof(f))

{

fscanf(f,"%d ",&cor[nr_ocupatii].id);

fgets(cor[nr_ocupatii].nume,150,f);

strtok(cor[nr_ocupatii].nume,"\n");

nr_ocupatii++;

}

fclose(f);

}

void afisare(char mesaj[])

{

int i;

FILE *g;

g=fopen(mesaj,"w");

if(g==NULL)

{

printf("Eroare la deschiderea fisierului de iesire");

exit(1);

}

for(i=0;i<nr_ocupatii;i++)

fprintf(g,"%d %s\n",cor[i].id,cor[i].nume);

/*Am inclus si codul numeric, nu doar denumirea ocupatiilor..*/

fclose(g);

}

void interpolare(int cod)

{

int m,s,d;

s=0;

d=nr_ocupatii-1;

do{

m=s+((cod-cor[s].id)*(d-s))/(cor[d].id-cor[s].id);

if(cod>cor[m].id)

s=m+1;

else

d=m-1;

}while((s<d)&&(cor[m].id!=cod)&&(cor[d].id!=cor[s].id)&&(cod>=cor[s].id)&&(cod<=cor[d].id));

if((cor[m].id==cod)&&(m<nr_ocupatii))

printf("Ocupatia ce are codul %d este: %s",cod,cor[m].nume);

else

printf("Nu exista ocupatia cu codul cerut.");

}

int binara(char nume[])

{

int s=0,d=nr_ocupatii-1,gasit=0,m;

while((s<=d)&&(!gasit))

{

m=(s+d)/2;

if(strncmp(cor[m].nume,nume,strlen(nume))==0)

gasit=1;

else

if(strncmp(cor[m].nume,nume,strlen(nume))<0)

s=m+1;

else

d=m-1;

}

if(gasit)

return m;

else

return -1;

}

void cautare_meserie(char nume[])

{

int i=binara(nume),j=i+1;

if(i==-1)

{

printf("Nu exista meseria cautata");

exit(1);

}

printf("Meserii ce incep cu '%s':\n",nume);

while(strncmp(cor[i].nume,nume,strlen(nume)))

{

printf("%s\n",cor[i].nume);

i--;

}

while(strncmp(cor[j].nume,nume,strlen(nume)))

{

printf("%s\n",cor[j].nume);

j++;

}

}

void sortare_alfabetica(int s,int d)

{

int i=s,j=d;

char x[150];

strcpy(x,cor[(s+d)/2].nume);

do{

while(strcmp(cor[i].nume,x)<0)

i++;

while(strcmp(cor[j].nume,x)>0)

j--;

if(i<=j)

{

char temp[150];

int aux;

strcpy(temp,cor[i].nume);

strcpy(cor[i].nume,cor[j].nume);

strcpy(cor[j].nume,temp);

aux=cor[i].id;

cor[i].id=cor[j].id;

cor[j].id=aux;

i++;j--;

}

}while(i<=j);

if(s<j)

sortare_alfabetica(s,j);

if(d>i)

sortare_alfabetica(i,d);

}

void sortare_pozitii_pare()

{

int i,s=0,aux;

char temp[150];

do{

s=0;

for(i=0;i<nr_ocupatii-2;i=i+2)

if(cor[i].id>cor[i+2].id)

{

strcpy(temp,cor[i].nume);

strcpy(cor[i].nume,cor[i+2].nume);

strcpy(cor[i+2].nume,temp);

aux=cor[i].id;

cor[i].id=cor[i+2].id;

cor[i+2].id=aux;

s=1;

}

}while(s!=0);

}

void sortare_pare_primele()

{

int i,s=0,aux;

char temp[150];

do{

s=0;

for(i=0;i<nr_ocupatii-1;i++)

if((cor[i].id%2!=0)&&(cor[i+1].id%2==0))

{

strcpy(temp,cor[i].nume);

strcpy(cor[i].nume,cor[i+1].nume);

strcpy(cor[i+1].nume,temp);

aux=cor[i].id;

cor[i].id=cor[i+1].id;

cor[i+1].id=aux;

s=1;

}

}while(s!=0);

}

int main()

{

printf("Hello world!\n");

int cod;

char nume[150];

/*a*/

citire();

printf("Introduceti codul: ");scanf("%d",&cod);

interpolare(cod);

/*b*/

sortare_alfabetica(0,nr_ocupatii-1);

afisare("COR_ord_alfabetic.txt");

/*c*/

printf("\nIntroduceti cuvantul cautat: ");scanf("%s",nume);

cautare_meserie(nume);

/*d*/

sortare_pozitii_pare();

afisare("COR_ord_par.txt");

/*e*/

sortare_pare_primele();

afisare("COR_ord_par_primele.txt");

return 0;

}

Optimizat:

#include <stdio.h>

#include <stdlib.h>

#define NR_OCUPATII_MAX 5000

struct ocupatii

{

int id;

char nume[150];

}cor[NR_OCUPATII_MAX];

int nr_ocupatii=0;

void citire()

{

FILE *f;

f=fopen("FisierTest.txt","r");

if(f==NULL)

{

printf("Eroare la deschiderea fisierului de intrare");

exit(1);

}

nr_ocupatii=0;

while(!feof(f))

{

fscanf(f,"%d ",&cor[nr_ocupatii].id);

fgets(cor[nr_ocupatii].nume,150,f);

strtok(cor[nr_ocupatii].nume,"\n");

nr_ocupatii++;

}

fclose(f);

}

void afisare(char mesaj[])

{

int i;

FILE *g;

g=fopen(mesaj,"w");

if(g==NULL)

{

printf("Eroare la deschiderea fisierului de iesire");

exit(1);

}

for(i=0;i<nr_ocupatii;i++)

fprintf(g,"%d %s\n",cor[i].id,cor[i].nume);

/*Am inclus si codul numeric, nu doar denumirea ocupatiilor..*/

fclose(g);

}

void swap(int i, int j)

{

char temp[150];

int aux;

strcpy(temp,cor[i].nume);

strcpy(cor[i].nume,cor[j].nume);

strcpy(cor[j].nume,temp);

aux=cor[i].id;

cor[i].id=cor[j].id;

cor[j].id=aux;

}

void interpolare(int cod)

{

int m,s,d;

s=0;

d=nr_ocupatii-1;

do{

m=s+((cod-cor[s].id)*(d-s))/(cor[d].id-cor[s].id);

if(cod>cor[m].id)

s=m+1;

else

d=m-1;

}while((s<d)&&(cor[m].id!=cod)&&(cor[d].id!=cor[s].id)&&(cod>=cor[s].id)&&(cod<=cor[d].id));

if((cor[m].id==cod)&&(m<nr_ocupatii))

printf("Ocupatia ce are codul %d este: %s",cod,cor[m].nume);

else

printf("Nu exista ocupatia cu codul cerut.");

}

int binara(char nume[])

{

int s=0,d=nr_ocupatii-1,gasit=0,m;

while((s<=d)&&(!gasit))

{

m=(s+d)/2;

if(strncmp(cor[m].nume,nume,strlen(nume))==0)

gasit=1;

else

if(strncmp(cor[m].nume,nume,strlen(nume))<0)

s=m+1;

else

d=m-1;

}

if(gasit)

return m;

else

return -1;

}

void cautare_meserie(char nume[])

{

int i=binara(nume),j=i+1;

if(i==-1)

{

printf("Nu exista meseria cautata");

exit(1);

}

printf("Meserii ce incep cu '%s':\n",nume);

while(strncmp(cor[i].nume,nume,strlen(nume))==0)

{

printf("%s\n",cor[i].nume);

i--;

}

while(strncmp(cor[j].nume,nume,strlen(nume))==0)

{

printf("%s\n",cor[j].nume);

j++;

}

}

void sortare_alfabetica(int s,int d)

{

int i=s,j=d;

char x[150];

strcpy(x,cor[(s+d)/2].nume);

do{

while(strcmp(cor[i].nume,x)<0)

i++;

while(strcmp(cor[j].nume,x)>0)

j--;

if(i<=j)

{

swap(i,j);

i++;j--;

}

}while(i<=j);

if(s<j)

sortare_alfabetica(s,j);

if(d>i)

sortare_alfabetica(i,d);

}

void sortare_pozitii_pare()

{

int i,s=0,aux;

char temp[150];

do{

s=0;

for(i=0;i<nr_ocupatii-2;i=i+2)

if(cor[i].id>cor[i+2].id)

{

swap(i,i+2);

s=1;

}

}while(s!=0);

}

void sortare_pare_primele()

{

int i=0,j=nr_ocupatii-1;

do{

while(cor[i].id%2==0)

i++;

while(cor[j].id%2==1)

j--;

if(i<=j)

{

swap(i,j);

i++;j--;

}

}while(i<=j);

}

int main()

{

printf("Hello world!\n");

int cod;

char nume[150];

/*a*/

citire();

printf("Introduceti codul: ");scanf("%d",&cod);

interpolare(cod);

/*b*/

sortare_alfabetica(0,nr_ocupatii-1);

afisare("COR_ord_alfabetic.txt");

/*c*/

printf("\nIntroduceti cuvantul cautat: ");scanf("%s",nume);

cautare_meserie(nume);

/*d*/

sortare_pozitii_pare();

afisare("COR_ord_par.txt");

/*e*/

sortare_pare_primele();

afisare("COR_ord_par_primele.txt");

return 0;

}