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;
}