Osnovi programiranja septembar 2002.
Napomena: drugi i treći zadatak su bili zajednički za prvi i treći tok. Uz rešenja prvog zadatka stoji napomena o rednom broju toka.
2. [40 poena] Neka se pod sažetim rečnikom kompjuterskih termina podrazumeva datoteka sledećeg oblika:
a) prvi red sadrži termin, a naredni redovi sadrže objašnjenje tog termina
b) nakon objašnjenja sledi prazan red, pa sledeći termin
c) termini su poredjani u poretku engleske abecede
d) termini nisu duži od 40 karaktera
Napisati program koji spaja dva sažeta rečnika kompjuterskih termina i to recnik1.dat i recnik2.dat u datoteku recnik.dat oblika navedenog pod a) b) c) d). Ako postoji duplikat termina, ponoviti samo objašnjenje bez termina i objašnjenja istog termina
razdvojiti jednim redom koji sadrži znake '<', '=', '>'.
#include <stdio.h>
void prepisi_objasnjenje( FILE *from,FILE *frez, char *term, char *, int*);
/*zapis objasnjenja termina iz jedne od datoteka (from) u izlaznu datoteku s obzirom na poslednji prepisan termin*/
main()
{
FILE *fexp1, *fexp2, *frez; /*dve ulazne datoteke i jedna izlazna datoteka*/
char termin1[MAX], termin2[MAX], poslednji[MAX]; /*procitani termini iz svake od
ulaznih datoteka i poslednji prepisan termin */
int kraj=0; /*indikator nailaska na kraj neke od ulaznih datoteka*/
/*priprema datoteka za obradu */
fexp1=fopen("recnik1.dat", "r");
fexp2=fopen("recnik2.dat", "r");
frez=fopen("recnik.dat", "w");
if (!fexp1 || !fexp2 || !frez)
{ fprintf(stderr, "Neuspelo otvaranje\n");
exit(EXIT_FAILURE);
}
strcpy(poslednji,"\n"); /*jos uvek nije prepisan nijedan od termina */
/*citanje prvih termina iz prvog i drugog recnika*/
strcpy(termin1,"\n");
strcpy(termin2,"\n");
if (fgets(termin1,MAX,fexp1)==NULL) kraj=1;
if (fgets(termin2,MAX,fexp2)==NULL) kraj=1;
/*objedinjavanje termina i objasnjenja iz oba recnika
se ponavlja do kraja jedne od datoteka */
while (!kraj)
{
if (strcmp(termin1,termin2) <= 0) prepisi_objasnjenje(fexp1,frez, termin1,poslednji,&kraj);
else prepisi_objasnjenje(fexp2, frez, termin2, poslednji,&kraj);
}
/*ako jos nije kraj prve ulazne datoteke, prepisu
se iz nje sva preostala objasnjena*/
while (!feof(fexp1) ) prepisi_objasnjenje(fexp1,frez, termin1, poslednji,&kraj);
/*ako jos nije kraj druge ulazne datoteke, prepisu
se iz nje sva preostala objasnjena*/
while (!feof(fexp2) ) prepisi_objasnjenje(fexp2,frez, termin2, poslednji, &kraj);
fclose (fexp1);
fclose (fexp2);
fclose (frez);
return 0;
}
void prepisi_objasnjenje( FILE *iz,FILE *frez, char *termin, char *p, int *end)
{
char zn, preth; /*tekuci i prethodni znak objasnjenja */
char red[MAX]; /* cuvanje termina ili separatora <=>*/
if (strcmp (termin,p) ) /*ako je termin drugaciji od poslednjeg */
{
if (strcmp(p,"\n") ) /*ako nije u pitanju prvi termin ispisuje se prazan red za razdvajanje jednog termina od sledeceg termina*/
fprintf(frez, "\n");
strcpy(p, termin); /*ispisuje se termin */
strcpy(red,termin); /*zapamti se sta ce se ispisati */
}
else /* ako je termin isti kao poslednji */
/*zapisuje se separator <=> umesto termina */
strcpy(red,"<=>\n");
/* prepis termina/separatora*/
fprintf(frez,"%s", red);
/*prepis objasnjenja*/
preth='.';
while ( (zn = fgetc(iz)) != EOF ) /*prepis objasnjenja do pojave praznog reda */
{ if (zn=='\n' && preth=='\n') break;
fputc(zn, frez);
preth=zn;
}
if (zn==EOF) {fputc('\n', frez); *end=1; }
/* procita se sledeci termin iz te datoteke*/
if (fgets(termin,MAX,iz)==NULL) *end=1;
}
main(int argc, char argv**) {
FILE pd1, pd2;
if( argv = 3 ) /korektan broj argumenata /
if( pd1 = fopen( **++argv, 'r')== NULL ) {
greska(Ne moze da se otvori)
exit(1)
} else if( pd2 = fopen( **++argv, 'r')= NULL ) {
greska(Ne moze da se otvori)
exit(1)
} else { /ucitavanje koordinata/
processFile( pd1, pd2 ); free( pd1 ); free( pd2 );
exit(2)
}
return 3;
}
void processFile(pd1,pd2);
{boolean coord_test;
fscanf(pd1, "%d", mybox.topleft.x, mybox.topleft.y);
fscanf(pd1, "%d", mybox.bottomrt.x); fscanf(pd1, "%d", mybox.bottomrt.y);
coord_test=(bottomrt.x - topleft.x)*(bottomrt.y - topleft.y) > 0;
if (coord_test){ / izracunavanje duzine, visine i povrsine /
width = OFFSET+ bottomrt.x - topleft.x; length = OFFSET + bottomrt.y - topleft.y; Area = width * length;
printf(pd2,"\nPovrsina je %l\n", area); }
}
#include <stdio.h>
int length, width;
long area;
struct coord{
int x;
int y;
};
struct rectangle{
struct coord topleft;
struct coord bottomrt;
} mybox;
main(int argc, char **argv) {
FILE *pd1, *pd2;
if( argc == 3 ) /* korektan broj argumenata */
if( (pd1 = fopen( *++argv, "r" ) ) == NULL ) {
greska(Ne moze da se otvori)
exit(1);
} else if( ( pd2 = fopen( *++argv, "w" ) ) == NULL ) {
greska(Ne moze da se otvori)
exit(1);
} else { /* ucitavanje koordinata */
processFile( pd1, pd2 );
fclose( pd1 );
fclose( pd2 );
exit( 2 );
}
}
void processFile( FILE * pd1, FILE *pd2 ) {
int coord_test;
fscanf(pd1, "%d %d", &mybox.topleft.x, &mybox.topleft.y);
fscanf(pd1, "%d", &mybox.bottomrt.x);
fscanf(pd1, "%d", &mybox.bottomrt.y);
coord_test=(mybox.bottomrt.x - mybox.topleft.x)*(mybox.bottomrt.y - mybox.topleft.y) > 0;
if (coord_test) { /*izracunavanje duzine, visine i povrsine */
width = OFFSET + mybox.bottomrt.x - mybox.topleft.x;
length = OFFSET + mybox.bottomrt.y - mybox.topleft.y;
area = width * length;
}
fprintf(pd2,"\nPovrsina je %ld \n", area);
}
Trazeni broj za s= 0 i t= 1 je: 0 dobijen za 1 koraka u ciklusu
#include <stdio.h>
/*element kruga*/
typedef struct covek_cvor
{ int rbr; /*redni broj plesaca*/
struct covek_cvor *levi, *desni;
}covek;
main(int argc, char **argv)
{ int i; /*brojac u petljama */
int N; /*broj ljudi u krugu */
int M; /*redni broj za izbacivanje */
int neparno; /* indikator smera razbrajanja */
covek *prvi,*p,*pom; /*prvi, tekuci/poslednji i pomocni clan kruga */
if( argc != 3 )
{ fprintf(stderr,"Nekorektan broj parametara u pozivu programa\n");
exit(10);
}
sscanf( argv[1], "%d", &N);
sscanf( argv[2], "%d", &M);
if (N<=0 || M<=0)
{ fprintf(stderr,"Nekorektna vrednost parametara u pozivu programa\n");
exit(10);
}
/*prvi clan liste plesaca u krugu */
prvi=(covek*) malloc(sizeof(covek));
prvi->rbr=1;
p=prvi;
/*formiranje susednih clanova liste */
for(i=2;i<N+1;i++)
{ if ( (p->desni= (covek*) malloc(sizeof(covek) ) ) == NULL)
{ printf("Nema u memoriji dovoljno mesta za malloc\n");
exit(1);
}
p->desni->rbr=i; /*numerisanje kostima plesaca*/
p->desni->levi=p;
p=p->desni; /*priprema za dodavanje sledeceg plesaca u krug */
}
/*zatvaranje kruga */
p->desni=prvi;
prvi->levi=p;
/*pocinje razbrajanje ...*/
/* neparana brojanja idu redom, a parna su sa vracanjem */
neparno=1;
/*izbacivanje M-tog */
while( p) /*tj. dok ima plesaca u krugu */
{
/*ako je brojanje parno...*/
if (neparno < 0)
{ /* ... broji se sa vracanjem (ulevo) */
for(i=1;i<M;i++) prvi=prvi->levi;
/*priprema za naredno brojanje koje pocinje od p */
p=prvi->levi;
}
else /*ako je brojanje parno...*/
{ /* ... broji se unapred (desno) */
for(i=1;i<M;i++) prvi=prvi->desni;
/*priprema za naredno brojanje koje pocinje od p*/
p=prvi->desni;
}
/*ispisuje se redni broj plesaca koji se iskljucuje */
printf("Izbaciti %d\n", prvi->rbr);
/*ako je to poslednji plesac, onda prestaje brojanje */
if (p==prvi) p=NULL;
else /* inace se iskljucuje iz kruga*/
{
pom=prvi;
pom->levi->desni=pom->desni;
pom->desni->levi=pom->levi;
}
/*brisanje iskljucenog elementa*/
free(pom);
/*naredno brojanje pocinje od p...*/
prvi=p;
/*... u suprotnom smeru*/
neparno= (-1) * neparno;
}
}
(* 101. (40 poena)
Napisati PASCAL program koji ucitava niz od
n <=100 celih brojeva i
stampa podniz tog niza ciji zbir elemenata je maksimalan
i koji ne sadrzi susedne elemente niza.
Smatrati da prazan niz ima zbir elemenata nula.
Voditi racuna o efikasnosti reąenja.
*)
(* RESENJE: Neka je a niz od n celih brojeva.
Neka je R=R(A) jedan podniz iz formulacije zadatka koji odgovara nizu
a.
Neka je Ak niz koji se sastoji od prvih k elemenata niza a.
Podniz niza A0 je prazan niz, dok je podniz niza A1 element a[1] ako je a[1]>0.
1. Ako element a[n] ne pripada podnizu R=R(A), onda je R
podniz iz formulacije zadatka koji odgovara nizu An-1.
2. Ako element a[n] pripada podnizu R=R(A), onda je R \ a[n]
podniz iz formulacije zadatka koji odgovara nizu An-2.
Dakle, za i=2..n,vazi da R(Ai) je ili R(Ai-1) ili R(Ai-2)* {a[i]},
tj.
uzima se onaj od podnizova koji ima veci zbir.`
Neka je niz P takav da:
P(i) je suma podniza R(Ai).
Iz gore izlozenog, jasno je da:
P(0)=0,
P(1)=max(0, a[1]),
P(i)=max{ P(i-1), P(i-2) + a[i] }, i=2..n
Iz niza P ce se ispisati resenje R.
*)
PROGRAM ZbirNesusednih (input, output);
VAR a : ARRAY[0..100] OF INTEGER; (* niz celih brojeva koji se
ucitava *)
p : ARRAY[0..100] OF INTEGER; (* niz
iz kog se generise resenje *)
n,i : INTEGER; (* dimenzija niza, brojac
u petlji *)
(*procedura koja ispisuje resenja koristeci rekurziju*)
PROCEDURE ispis(n:INTEGER);
BEGIN
IF n>0 THEN
IF p[n]=p[n-1] THEN ispis(n-1)
ELSE
BEGIN
ispis(n-2);
write(a[n]:5);
END;
END;
(* glavni program *)
BEGIN
readln(n); (*ucitavanje dimenzije niza celih brojeva *)
p[0]:=0; (* slucaj praznog niza *)
FOR i:=1 TO n DO readln(a[i]); (* ucitavanje niza celih brojeva *)
IF a[1]>0 THEN p[1]:=a[1] (* podniz sa 1 clanom *)
ELSE p[1]:=0; (* slucaj praznog podniza *)
(* formiranje clanova niza p *)
FOR i:=2 TO n DO
(* P(i)=max{ P(i-1), P(i-2) + a[i] }, i=2..n
*)
IF p[i-2] + a[i] > p[i-1] THEN
p[i]:=p[i-2]+a[i]
ELSE
p[i]:=p[i-1];
(* ispis resenja, tj. podniza iz formulacije zadatka *)
ispis(n);
END.
102. (40 poena)
Napisati C program koji leksikografski sortira u neopadajućem poretku
linije sa ulaza. Ako je kao argument komandne linije zadat opcioni argument
-n , onda izvršiti numeričko sortiranje. Ako je kao argument komandne linije
zadat opcioni argument -r , onda promeniti redosled sortiranja u nerastući
poredak.
Program treba da radi sa preusmeravanjem standardnog ulaza, a svoj
rezultat treba da upiše u datoteku
sortiran.dat. Obezbediti da program radi i kad su prisutna
oba opciona argumenta -r -n .
Poruke o greškama ispisati na standardni izlaz za poruke o grešci.
Može se pretpostaviti da ukupan broj linija nije veći od 1000, kao
i da dužina svake linije nije veća od 80 karaktera.
103. (40 poena)
Napisati C program koji će u datoteku čiji naziv se zadaje kao
argument komandne linije ispisati nazive n najčešćih etiketa
(tagova, oznaka,..) koji se pojavljuju
u HTML datoteci mojseminarski.htm, gde se broj n zadaje kao argument
komandne linije.
Ako u datoteci nema bar n razlicitih etiketa (tagova,
oznaka, ,..) onda uz odgovarajuću poruku ispisati nazive svih etiketa.
Voditi računa o efikasnosti napisanog programa.
REŠENJA:
100.
a) I nacin (bez upotrebe ternarnog operatora ?: )
i= 0;
while (i <
(max - 1))
{
c = getchar();
if (c == EOF)
break;
else if (c == '\n')
break;
s[i++] = c;
}
II nacin - npr. upotrebom ternarnog operatora
?:
b)
unsigned rightrot(unsigned x, unsigned n)
{
while (n > 0) {
if ((x & 1) == 1)
x = (x >> 1) | ~(~0U >> 1);
else
x = (x >> 1);
n--;
}
return x;
}
102.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXLINES 1000 /* max broj linija */
char *lineptr[MAXLINES]; /* pokazivaci na linije sa ulaza*/
#define MAXLEN 81 /* max duzina linije */
int reverse = FALSE; /* indikator pojave opcionog argumenta ?r */
/* getline: ucitava liniju i vraca njenu duzinu*/
int getline(char s[], int lim)
{
int c; /* znak sa ulaza*/
int i; /* brojac u petlji */
for (i = 0; i < lim - 1 && (c = getchar()) != EOF && c != '\n'; i++)
s[i] = c;
if (c == '\n') {
s[i++] = c;
}
s[i] = '\0';
return i;
}
/* readlines: ucitavanje ulaznih linija limitirane duzine */
/* vraca broj ucitanih linija < maxlines ili -1 u slucaju preobimnog ulaza*/
int readlines(char *lineptr[], int maxlines)
{
int len, nlines; /* duzina linije, broj ucitanih linija sa ulaza*/
char *p, line[MAXLEN];
nlines = 0;
while ((len = getline(line, MAXLEN)) > 0)
if (nlines >= maxlines || (p = malloc(len)) == NULL)
return -1; /* preobiman ulaz*/
else {
line[len - 1] = '\0'; /* izbaci novi red */
strcpy(p, line);
lineptr[nlines++] = p;
}
return nlines;
}
/* writelines: upis linija u datoteku */
void writelines(char *lineptr[], int nlines)
{
int i;
FILE *f;
f= fopen ("sortiran.dat", "w");
if (!f)
{ fprintf(stderr, "Neuspelo otvaranje datoteke sortiran.dat\n");
exit(EXIT_FAILURE);
}
for (i = 0; i < nlines; i++)
fprintf(f, "%s\n", lineptr[i]);
fclose (f);
}
/* poredjenje niski; funkcija se stara i o poredjenju niski
u slucaju da je prisutan opcioni argument -r */
int pstrcmp(const void *p1, const void *p2)
{
char * const *s1 = reverse ? p2 : p1;
char * const *s2 = reverse ? p1 : p2;
return strcmp(*s1, *s2);
}
/* numcmp: poredi numercki dve niske */
int numcmp(const void *p1, const void *p2)
{
char * const *s1 = reverse ? p2 : p1;
char * const *s2 = reverse ? p1 : p2;
double v1, v2;
v1 = atof(*s1);
v2 = atof(*s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
int main(int argc, char *argv[])
{
int nlines; /*broj ucitanih linija na ulazu*/
int numeric = FALSE; /* indikator pojave opcionog argumenta -n */
int i,j; /* brojaci u petlji */
/* test prisustva bilo kog opcionog argumenta */
/* u slucaju da opcioni argumenti nisu prisutni, sortiranje
je leksikografsko u neopadajucem poretku */
/*prosledjivanje argumenata komandne linije */
for (i = 1; i < argc && argv[i][0] == '-'; i++)
{
/*prosledjivanje opcija za reverzno ili/i numericko sortiranje*/
for (j=1; argv[i][j] !='\0'; j++)
{ /* test prisustva opcionih argumenata -n, -r */
switch (argv[i][j]) {
case 'n': numeric = TRUE; break;
case 'r': reverse = TRUE; break;
default:
fprintf(stderr, "Nekorektan opcioni argument '%s'\n", argv[i]);
return EXIT_FAILURE;
}
}
}
/* ucitavanje linija sa ulaza*/
if ((nlines = readlines(lineptr, MAXLINES)) >= 0) {
/* u slucaju uspesnog ucitavanja linija sa ulaza,
vrsi se odgovarajuce sortiranje, prema
zahtevima - numericko ili leksikografsko, neopadajuce ili nerastuce*/
qsort(lineptr, nlines, sizeof(*lineptr), numeric ? numcmp : pstrcmp);
/* upis rezulata sortiranja u datoteku */
writelines(lineptr, nlines);
return EXIT_SUCCESS;
}
else {
fputs("Preobiman ulaz za sortiranje\n", stderr);
return EXIT_FAILURE;
}
}
OSNOVI PROGRAMIRANJA jun 2003. I i II grupa
1. (40) Napisati program koji za dva polinoma stepena ne većeg od 20 unosi koeficijente (realni brojevi), a na standardni izlaz ispisuje:
a) zbir ta dva polinoma
b) vrednost oba polinoma u tački x, koja se zadaje kao argument komandne linije
c) proizvod ta dva polinoma
2. (40) Napisati program koji čita datoteku ulaz.txt i na standardni izlaz ispisuje sve
različite reči (niske do 20 karaktera koje pocinju slovom i ne sadrže blanko, tab, znak prelaza u novi red) koje se pojavljuju u datoteci, sa brojevima redova u
kojima se pojavljuju. Reči ispisati u rastućem leksikografskom poretku.
OBAVEZNO JE PROGRAME PISATI ČITKO I SA POTREBNIM KOMENTARIMA
3. (20)
a) Upotrebom pokazivača umesto indeksa, napisati ekvivalentnu f-ju main
#include <stdio.h>
char ispisFormat[4]="";
main(int argc, char *argv[]) {
char znak;
int i, j, start=0, saNavodnicima=0, saTabom=0;
for (i=1; i< argc && argv[i][0] == '-' ; i++)
for (j=1; znak=argv[i][j]; j++)
switch(znak) {
case 'q': saNavodnicima=1; start=1; break;
case 't': saTabom=1; break; }
j=0;
if (saNavodnicima) ispisFormat[j++]='\"' ;
if (saTabom) ispisFormat[j++]='\t' ;
if (j) ispisFormat[j]='\0';
for(; i<argc; i++) printf("%s%s%s", start? "\"" : "" , argv[i], ispisFormat );
return 0;
}
b) Date su strukture i promenljive
struct point { int d[2]; };
struct rect { struct point corn[2];} rc[2]={ {-1,1,2,3}, {-3,5,6,7}}, *p;
Ispisati vrednosti koje posle izvršenja iskaza
{ p=rc; ++*(p+1)->corn->d; ++p->corn->d[1]; p++; }
imaju izrazi: p->corn->d[1],*rc->corn->d, *p->corn->d, (*rc->corn).d[1]
1.
#include <stdio.h>
#include <stdlib.h>
#define MAXEL 21
typedef struct polinom pol;
/*definicija polinoma - svaki polinom karakterisu stepen i koeficijenti */
struct polinom
{ int stepen;
double koef[MAXEL];
};
void ucitati(pol *p); /* ucitava stepen i koeficijente polinoma u strukturu*/
void zbir ( pol *p, pol * q, pol *s) ; /* resava a) tj. vraca s=p+q */
double Horner (pol *p, float x); /* resava b) tj ispisuje p(x) */
void proizvod ( pol *p, pol * q, pol *t) ; /* resava c) tj. vraca t=p*q */
void ispis(pol *p); /* ispisuje polinom */
main(int argc, char *argv[])
{ pol p, q, r, s; /* p, q su dva polinoma sa ulaza, r je njihov zbir, s je proizvod */
float x; /* realan broj cija vrednost je parametar kom. linije */
/* ucitavanje polinoma p, q, tj. koeficijenata */
ucitati (&p); ucitati (&q);
x=atof(argv[1]); /* argument x */
/* deo pod b) */
printf("\nP(%f) = %lf", x, Horner(&p, x) );
printf("\nQ(%f) = %lf", x, Horner(&q, x) );
/* deo pod a) */
printf("\nZbir je: ");
zbir(&p, &q, &r);
ispis(&r);
/*deo pod c) */
printf("\nProizvod je: ");
proizvod(&p, &q, &s);
ispis(&s);
return 0;
}
void ucitati (pol *p)
{ int i; /* brojacka promenljiva */
/* unos stepena polinoma */
do
{ printf("Stepen polinoma izmedju [0, %d]: ", MAXEL);
fscanf(stdin,"%d",&p->stepen);
} while (p->stepen <0 || p->stepen < MAXEL);
printf("\n");
/* unos koeficijenata polinoma */
for (i=0;i<=p->stepen;i++)
{ printf("x^%d * ",i);
fscanf(stdin,"%lf",&p->koef[i]);
}
}
double Horner (pol *p, float x) /* return (...(((0)*x + p[n]) *x + p[n-1])...)*x +p[0] */
{ int i; /* brojacka promenljiva */
double pom; /* vrednost polinoma p u tacki x pri tekucoj dubini zagrada,
gde dubina najugnjezdenije zagrade jeste 0*/
pom=0;
for (i=p->stepen; i>=0; i--) pom= pom *x + p->koef[i]; /* vrednost u novoj zgradi cija je dubina za 1 manja */
return pom; /* return (...(((0)*x + p[n]) *x + p[n-1])...)*x +p[0] */
}
/* sabiranje polinoma p i q izvodi se sabiranjem koeficijenata jednakog stepena*/
void zbir(pol * p,pol * q, pol *t)
{
int i; /* brojacka promenljiva */
/*postavljanje stepena zbira */
t->stepen=(p->stepen>q->stepen)?p->stepen:q->stepen;
/* formiranje koeficijenata rezultujeceg polinoma */
t->koef[0]=0;
for (i=0; i<=t->stepen; i++)
t->koef[i] = ((i<=p->stepen)?p->koef[i]:0) + ((i<=q->stepen)?q->koef[i]:0);
}
/* proizvod polinoma p i q - svaki koeficijent i = 0.. m+n dobija kao sumu svih p[j]+q[k], gde je j+k=i */
void proizvod(pol* p,pol* q, pol* t)
{ int i,j,k; /* brojacke promenljive */
t->stepen=p->stepen+q->stepen; /*stepen proizvoda dva polinoma jednak je zbiru stepena cinilaca */
/* formiranje i-tog koeficijenta polinoma t sumiranjem prozivoda j-tih koeficijenata iz p i k-tih koeficijenata iz q, gde sumiranje ide po svim j, k tako da i=j+k */
for (i=0;i<=t->stepen;i++)
{
t->koef[i]=0;
for (j=0; j<=p->stepen; j++)
{
k=i-j;
if ((k>=0) && (k<=q->stepen)) t->koef[i] += p->koef[j]*q->koef[k];
} /* for j=0.. */
} /* for i=0.. */
}
/* ispisuje polinom u obliku Ax^0 + Bx^1 + Cx^2 + ..., gde su A,B,C...odgovarajuci koeficijenti*/
void ispis(pol * p)
{ int i; /* brojacka promenljiva */
for (i=0;i<=p->stepen;i++)
if (p->koef[i]!=0) { printf("%.2fx^%d",p->koef[i],i);
if (istepen) printf(" + ");
}
else if (p->stepen == 0) printf("0");
printf("\n");
}
2.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 21
typedef struct drvo_CV drvo; /* BSP uredjeno po recima */
typedef struct redovi_CV redovi; /* lista rednih brojeva linija u kojima se pojavljuje jedna rec*/
struct drvo_CV
{ /* za svaku rec cuva se lista pojavnih redova r */
char rec[MAX];
redovi *r;
drvo *levo,*desno;
};
struct redovi_CV
{ /* cuvaju se redni brojevi linija pojava jedne reci */
int br; /* redni broj linije */
redovi *sl;
};
char getWord(FILE *f, char *s); /* izdvaja rec s iz ulazne datoteke i vraca tekuci karakter ulaza*/
drvo * addTree(drvo*d, char *s, int br); /* unosi rec s koja se pojavila u redu br u BSP d*/
void printTree(drvo *); /* stampa reci (inorder) i redne brojeve linija u kojima su se pojavile bar jednom */
void freeTree(drvo *); /* oslobadja prostor */
main()
{
drvo *koren;
char rec[MAX]; /* tekuca rec sa ulaza */
int brlinije; /* redni broj tekuce linije */
char c; /* tekuci karakter sa ulaza */
FILE *ul;
/* inicijalizacije */
koren = NULL;
brlinije = 1;
ul = fopen("ulaz.txt","rt");
/* citanje sadrzaja datoteke i formiranje BSP-a*/
while(!feof(ul))
{
c = getWord(ul, rec);
if(strlen(rec) > 0) koren=addTree(koren, rec, brlinije);
if(c=='\n') brlinije++; /* postavlja redni broj tekuceg reda */
}
fclose(ul);
printTree(koren);
freeTree(koren);
return 0;
}
char getWord(FILE *fin, char *word)
{ char c; /* tekuci karakter ulazne datotke */
int k; /* tekuca pozicija niske word koja se formira */
/*ignorisati karaktere kojima ne pocinje rec ili ne ulaze u sastav reci*/
while(!isalpha(c = fgetc(fin)) && c!='\n' && !feof(fin)) ;
/*formiranje niske word */
k = 0;
while(c!=' ' && c!= '\t' && c!='\n' && !feof(fin))
{
word[k++] = c;
c = fgetc(fin);
}
word[k] = '\0';
return c;
} /* izdvojrec */
drvo * addTree(drvo *d, char *w, int br)
{ redovi *tek, *pom;
if(d == NULL) /* rec se prvi put pojavila */
{ d = (drvo *)malloc(sizeof(drvo));
strcpy(d->rec, w);
d->levo = NULL;
d->desno = NULL;
/*ubacivanje u listu rednog broja tekuceg reda u kom se rec pojavila*/
d->r = (redovi *)malloc(sizeof(redovi));
d->r->br = br;
d->r->sl = NULL;
}
else /*rec se opet pojavila*/
if(strcmp(w, d->rec) == 0)
{
for(tek=d->r; tek->sl!=NULL; tek=tek->sl)
if(br == tek->br) break; /*ako se rec vec pojavila u istom redu, njegov redni broj se ne ubacuje u listu */
if(br != tek->br)
{ /* ako se rec 1. put pojavila u tekucem redu,
onda dodati taj red */
tek->sl = (redovi *)malloc(sizeof(redovi));
tek = tek->sl;
tek->br = br;
tek->sl = NULL;
}
}
else if(strcmp(w, d->rec) < 0) d->levo=addTree( d->levo, w, br);
else d->desno=addTree(d->desno, w, br);
return d;
}
void freeTree(drvo *d)
{ if(d != NULL)
{ freeTree(d->levo);
freeTree(d->desno);
free(d);
}
}
void printTree(drvo *d)
{ redovi *tekuci;
if(d != NULL)
{ printTree(d->levo);
/* stampati sadrzaj reci*/
printf("%s ",d->rec);
/* stampati listu rednih brojeva linija u kojima se pojavila rec bar jednom*/
for(tekuci=d->r; tekuci!=NULL; tekuci=tekuci->sl)
printf("%d ",tekuci->br);
printf("\n");
printTree(d->desno);
}
}
OSNOVI PROGRAMIRANJA januar 2004. III tok V grupa
1.
a) Napisati nerekurzivnu f-ju int bitcount (unsigned x) koja kao rezultat vraca broj 1-bitova u binarnoj reprezentaciji za x.
b) Napisati rekurzivnu f-ju int bitcount (unsigned x) koja kao rezultat vraca broj 1-bitova u binarnoj reprezentaciji za x.
c) Napisati C program koji sa standardnog ulaza unosi neoznacen ceo broj, a na standardni izlaz ispisuje broj 1-bitova u
binarnoj reprezentaciji tog broja. (20 poena)
2. Napisati C program koji ce u datoteku ciji naziv se zadaje kao argument komandne linije ispisati nazive ne više od n
najčešćih etiketa (tagova, oznaka,..) koji se pojavljuju u HTML datoteci ulaz.htm bar m puta,
gde se brojevi n, m zadaju kao argument komandne linije. Pojava prostog taga npr. <BR> broji se kao jedna pojava.
Pojava slozenog taga npr. <table >...</table> se broji kao jedna pojava. (40 poena)
3. Napisati C program koji ce poslednjih n linija datoteke ulaz.txt ispisati na standardni izlaz sortirane po prvoj reci.
Broj linija nije unapred poznat. Svaka linija sadrzi ne više od 70 karaktera, a svaka rec pripada tacno jednoj liniji.
Broj n se zadaje kao argument komandne linije. Sortiranje izvršiti u u neopadajucem leksikografskom poretku,
sem ako kao opcioni argument komandne linije nije zadata opcija -r, u kom slucaju izvršiti sortiranje u nerastucem
leksikografskom poretku. Program mora biti osetljiv na razliku malih i velikih slova. Pri sortiranju koristiti funkciju
qsort iz standardne biblioteke. Poruke o nekorektnim parametrima komandne linije ispisati na standardnom izlazu za poruke o grešci. (40 poena)
OBAVEZNO JE PROGRAME PISATI ČITKO I SA POTREBNIM KOMENTARIMA !!!
OSNOVI PROGRAMIRANJA januar 2004. Grupa E IV tok
1.
a) Napisati nerekurzivnu f-ju int bitsum (unsigned x) koja koristi bitske operatore i kao rezultat vraca sumu bitova u binarnoj reprezentaciji za x.
b) Napisati rekurzivnu f-ju int bitsum (unsigned x) koja koristi bitske operatore i kao rezultat vraca sumu bitova u binarnoj reprezentaciji za x.
c) Napisati C program koji sa standardnog ulaza unosi neoznacen ceo broj, a na standardni izlaz ispisuje sumu bitova u binarnoj reprezentaciji tog broja. (20 poena)
2. Napisati C program koji ce u datoteku ciji naziv se zadaje kao argument komandne linije ispisati nazive ne više od n najcešcih etiketa (tagova, oznaka,...) koji se pojavljuju u HTML datoteci seminar.htm i njihov broj pojava. Broj n se zadaje kao argument komandne linije. Pojava prostog taga npr. <HR> broji se kao jedna pojava. Pojava slozenog taga npr. <strong >...</strong> se broji kao jedna pojava.
3. Napisati C program koji ce poslednjih n linija datoteke prva.dat ispisati na standardni izlaz sortirane po poslednjoj reci. Broj linija nije unapred poznat. Svaka linija sadrzi ne više od 80 karaktera, a svaka rec pripada tacno jednoj liniji. Prirodan broj n se zadaje kao argument komandne linije. Sortiranje izvršiti u u neopadajucem leksikografskom poretku , sem ako kao opcioni argument komandne linije nije zadata opcija -r, u kom slucaju izvršiti sortiranje u nerastucem leksikografskom poretku. Poruke o nekorektnim parametrima komandne linije ispisati na standardnom izlazu za poruke o grešci. Program mora biti osetljiv na razliku malih i velikih slova. Pri sortiranju koristiti funkciju qsort iz standardne biblioteke. (40 poena)
OBAVEZNO JE PROGRAME PISATI ČITKO I SA POTREBNIM KOMENTARIMA !!!
Rešenja:
#includeint bitcount(unsigned x); main() { unsigned broj; scanf("%u", &broj); printf("Broj 1-ca u %u je %d\n", broj,bitcount(broj) ); }
A34 Kernighan, Ritchie str. 48
int bitcount(unsigned x)
{
int b;
for (b=0; x!= 0; x > > =1)
if (x&01) b++;
return b;
}
B3
int bitcount(unsigned x)
{
if (x)
return (x&01) + bitcount(x/2);
else return 0;
}
B4
int bitcount(unsigned x)
{
if (x)
return (x&01) + bitcount(x > > 1);
else return 0;
}
IV3
#include < stdio.h>
#include < stdlib.h>
#include < string.h>
#include < ctype.h>
#define LINELIMIT 71
void uzmirec (char *linija, char *rec);
int uporedi1(const void *a,const void *b); /*poredjenje linija */
int uporedi2(const void *a,const void *b); /*poredjenje linija */
void greska (char *tekst, char *opc); /* ispis teksta greske u kom. liniji sa pogr. opcijom */
int reverse=0;
/*glavni program */
main(int argc,char *argv[])
{
FILE *in;
int kolicina; /* broj linija za prepis */
char* line; /* pokazivac na liniju */
char ** linepok; /* na linije */
int CountLine; /* brojac linija do kolicine */
int j; /*brojacka promenljiva */
int kraca; /*ukazuje da n prevailazi duzinu datoteke*/
/*ucitavanje broja linija koji ce se prepisati i detektovanje greske medju arg. kom. linije*/
if (argc < 2) greska("Nekorektan poziv programa", argv[0]);
else if (argc==2)
if (isdigit(argv[1][0]) ) sscanf( argv[1], "%d", &kolicina );
else greska("Nekorektan broj linija", argv[1] );
else if (argc >2)
{ if (isdigit(argv[1][0]) )
{sscanf( argv[1], "%d", &kolicina );
if (strcmp(argv[2], "-r")) greska("Nekorektna opcija",argv[2]); else reverse=1;
}
else
if (!strcmp(argv[1], "-r"))
{reverse=1;
if (isdigit(argv[2][0]) ) sscanf( argv[2], "%d", &kolicina );
else greska("Nekorektan parametar", argv[2]);
}
else greska("Nekorektna opcija", argv[1]);
if (argc >3) printf("\nIgnorise se visak parametara kom. linije\n");
}
/* alociranje niza pokazivaca linija */
linepok = (char **) calloc(kolicina+1, sizeof(char*));
if( linepok == NULL )
{ fprintf(stderr, "ne moze da se alocira prostor \n");
exit(1);}
if( (in=fopen("ulaz.txt","r")) == NULL )
{ fprintf(stderr, "ulaz.txt ne moze da se otvori za citanje \n");
exit(1);}
for( j = 0; j < kolicina+1; j++ )
{ linepok[j] = (char *) malloc( LINELIMIT*sizeof(char) );
if( linepok[j] == NULL )
{ fprintf(stderr, "ne moze da se alocira prostor \n");
exit(3);}
}
CountLine = 0; kraca=1;
/*prepis linija */
while( 1)
{
if (CountLine==kolicina+1) /*kako sada niz pokazivaca sadrzi poslednjih n+1 linija*/
{ for (j=0;j < kolicina;j++) strcpy(linepok[j],linepok[j+1]); /*ucitanih do sada,to uklanjamo sadrzaj 1.clan tog niza */
CountLine=kolicina;
kraca=0; /*ulazna datoteka ima ne manje od n linija*/
}
if ( fgets( line, LINELIMIT,in) == NULL )break; /*uzeta je sledeca linija i testiran kraj linija */
strcpy(linepok[CountLine],line); /*cuvanje tekuce linije u nizu od n linija */
CountLine ++;
}
if (kraca) kolicina=CountLine; /*ako je datoteka kraca od n linija*/
/*onda kolicina linija koja se prepisuje i sortira je jednaka broju ucitanih */
if (reverse)
qsort(linepok, kolicina, sizeof(linepok[0]), &uporedi2);
else qsort(linepok, kolicina, sizeof(linepok[0]), &uporedi1);
/* prepis linija na standardni izlaz*/
for( j=0;j < kolicina;j++ ) printf("%s",linepok[j]);
/*oslobadjanje zauzetog prostora za niz pokazivaca linija */
for(j=0;j< = kolicina; j++ ) free(linepok[j]);
free(linepok);
fclose(in);
return 0;
}
int uporedi1(const void *a,const void *b)
{ char s1[LINELIMIT], s2[LINELIMIT];
char *l1= *(char **)a;
char *l2= *(char **)b;
uzmirec(l1,s1); uzmirec(l2,s2);
return strcmp(s1, s2);
}
int uporedi2(const void *a,const void *b)
{
return (-1)*uporedi1(a, b);
}
void uzmirec (char *linija, char *rec)
{
int k=0, j=0;
while (isspace(linija[k]) && linija[k]!='\0') k++;
while (linija[k]!=' ' && linija[k]!='\t' && linija[k]!='\n' && linija[k]!='\0')
{rec[j]=linija[k]; k++; j++;}
rec[j]='\0';
}
void greska (char *tekst, char *opc)
{
fprintf(stderr,"\nGreska: %s %s\n", tekst, opc); exit(3);
}
1. Napisati C
program koji će
iz datoteke prva.htm prepisati nazive međusobno različitih otvarajućih etiketa (bez atributa) u binarno stablo pretrage i potom:
a) štampati sadržaj drveta u infiksnom poretku u datoteci izlaz.txt, ako je kao
parametar komandne linije zadata opcija
-t
b) na standardni izlaz ispisati ukupan broj čvorova drveta, ako je
kao parametar komandne linije zadata opcija -u
Obezbediti da program radi i kada su
prisutni svi opcioni argumenti. Pretpostaviti da naziv otvarajuće
etikete nije duži od
20 karaktera.
Primer: <P
align=”center”> <IMG src=”ul.gif”> <BR> <br> Nova slika </p>
Otvarajuće etikete bez
atributa su: BR, IMG, P
2. Napisati program koji učitava linije sa standardnog ulaza i prepisuje u datoteku izlaz.txt samo
slova svake linije i to u obrnutom poretku. Broj linija na ulazu nije unapred
poznat. Dužina linija na ulazu nije unapred ograničena. Koristiti
povezane liste za čuvanje karaktera koji sačinjavaju liniju.
ULAZ
IZLAZ
Zdravo,
svete!!!
etevsovardZ
Jedan
2 Tri 456... irTnadeJ
1.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXREC 21
#define TRUE 1
#define FALSE 0
typedef struct drvo_tag
{
char *rec; /* rec
teksta */
struct drvo_tag
*levo;
/* leva grana */
struct drvo_tag *desno; /* desna grana */
} drvo;
/* Funkcije
*/
drvo *addtree(drvo *, char *); /* ubacuje rec u drvo */
void treeprint(drvo *);
/* stampa drvo – infiksni poredak za BSP*/
int uzmi_tag(FILE *f, char *s, int k); /* ucitava tagove (do k karaktera) iz datoteke u nisku
s*/
drvo *talloc( void ); /* alokacija cvora BSP */
char *strdpl(char *s); /* kreira kopiju niske s */
void osloboditi( drvo *k); /* oslobadja zauzeti prostor za drvo
*/
int brcvorova(drvo *k); /* vraca broj cvorova stabla
*/
/*glavni
program*/
main(int argc, char *argv[])
{
drvo
*koren;
/*koren stabla pretrazivanja */
char rec[MAXREC]; /*sadrzaj reci sa
ulaza */
FILE *ulaz;
int
i,j;
/* brojacke promenljive
*/
int
node=FALSE, printt=FALSE; /*indikatori postojanja opcija u komandnoj liniji */
ulaz=fopen("prva.htm","rt");
if (ulaz==NULL) exit(1);
/*prosledjivanje
argumenata komandne linije */
for (i = 1; i < argc
&& argv[i][0] ==
'-'; i++)
{ /*prosledjivanje opcija ili niti
jedne korektne opcije ili od jedne do cetiri
opcije*/
for (j=1; argv[i][j] !='\0'; j++)
{ /* test prisustva
opcionih argumenata -n, -l,
-d,-p */
switch (argv[i][j])
{ case
'u': node = TRUE; break;
case 't': printt=TRUE; break;
default: fprintf(stderr, "Nekorektan opcioni argument '%s'\n", argv[i]);
return EXIT_FAILURE;
}
}
}
/*ucitavanje
reci ciji broj pojavljivanja se broji */
koren
= NULL;
while( 1 )
{
int kraj
= uzmi_tag(ulaz,rec,
MAXREC);
/*dodavanje cvora u stablo cvora,
ako rec ne
postoji u stablu */
if
( strlen(rec))
koren = addtree( koren, rec);
if(kraj
== EOF) break; /*ucitavanje
se vrsi do markera kraja */
}
fclose(ulaz);
/*stampanje broja cvorova stabla
*/
if (node) printf("\nCvorova: %d", brcvorova(koren));
/*stampanje sadrzaja stabla*/
if (printt) treeprint(koren);
/*oslobadjanje zauzetog prostora za stablo pretrage */
osloboditi(koren);
return 0;
}
/* addtree
- dodaje cvor sa tekstom
na koji pokazuje
w, na ili ispod p u drvetu*/
drvo *addtree( drvo *p, char *w )
{
int
cond;
if( p == NULL
) /* naisla
nova rec */
{
p
= talloc(); p->rec = strdpl(w);
p->levo = p->desno = NULL;
}
else if ((cond = strcmp(w,p->rec))< 0 ) /*manja rec => levi ogranak*/
p->levo = addtree(p->levo, w);
else if (cond
>0) /*vece =>desni ogranak*/
p->desno = addtree(p->desno, w);
return p;
}
void treeprint(drvo *p) /* treeprint - rekurzivno stampanje drveta*/
{
if( p != NULL )
{
treeprint( p->levo );
printf("%s\n", p->rec );
treeprint( p->desno );
}
}
int uzmi_tag(FILE *f,char s[], int lim)
{ char c;
int i = 0;
/* preskociti sve
znake do znaka <*/
while( ( (c =fgetc(f)) != '<') && c!=EOF);
if( c==EOF ) {s[0] = '\0';
return EOF;} /* prazna
rec i vratiti
EOF */
/* ucitati ostatak
etikete; OBRATITI
PAZNJU DA HTML JE CASE INSENSITIVE, A DA f-ja strcmp
pravi razliku
u velicini slova, tj. <table> i <TaBLE> su 2 pojave iste
etikete*/
while( (c = fgetc(f))
!= EOF && isalnum(c) && i < lim)
{s[i] = toupper(c); i++; }
s[++i] = '\0'; /*
zavrsiti nisku */
if( c==EOF ) return EOF;
return i;
}
int brcvorova(drvo *c)
{
if(c == NULL)
return 0;
else return 1+brcvorova(c->levo)+brcvorova(c->desno);
}
drvo *talloc(void)
{ return (drvo *) malloc(sizeof(drvo));
}
char *strdpl(char *s) /* pravi se kopija niske s */
{ char *p; p = (char *) malloc(strlen(s) + 1 );
if( p != NULL ) strcpy(p,s);
return p;
}
void osloboditi( drvo *k)
{ /*rekurzivno se oslobadja levo i desno podstablo
korena zadatog stabla */
if (k->levo) osloboditi (k->levo);
if (k->desno) osloboditi (k->desno);
free (k); /*brisanje cvora koji predstavlja
koren zadatog stabla */
}
2.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
typedef struct
listica lista;
/*lista karaktera jedne linije sa ulaza*/
struct listica
{ char c; /*karakter linije*/
lista
*sl;
};
main()
{
lista
*poc, *tek, *pom; /*pocetak povezane liste karaktera,
pomocni cvor
pri stampi liste,
pomocni
cvor pri formiranju i oslobadjanju
liste*/
char c; /*tekuci karakter linije sa ulaza*/
FILE *izl;
izl=fopen(“izlaz.txt”, “w”);
/*ocitavanje linije po linije
ulaza do EOF */
while (!feof(stdin))
{
poc=NULL;
c=getchar();
while
(c!= ‘\n’ && !feof(stdin))
{
if (isalpha(c) )
{ /*ubacivanje na pocetak
liste dodavanjem ispred tekuceg pocetka – to je zgodno
zbog kasnijeg
inverznog ispisa*/
pom= (lista*)
malloc(sizeof(lista));
pom->c=c;
pom->sl=poc;
poc=pom;
}
c=getchar();
}
/*stampa liste od
pocetka, tj. stampa slova
tekuce linije u obrnutom poretku */
for(tek=poc; tek!=NULL;
tek=tek->sl) fprintf(izl, “%c”, tek->c);
fprintf(izl, “\n”);
/*oslobadjanje liste*/
for (tek=poc; tek
!=NULL; )
{
pom=tek->sl; free(tek);
tek=pom;
}
} /*while (!feof(…)) */
fclose(izl);
}
OSNOVI
PROGRAMIRANJA II kolokvijum III tok 2005.
1. Napisati C
program koji će
iz datoteke ulaz.htm prepisati nazive međusobno različitih otvarajućih etiketa (bez atributa) u binarno stablo pretrage i potom:
a) na standardni izlaz ispisati ukupan broj čvorova drveta, ako je
kao parametar komandne linije zadata opcija -u
b) štampati sadržaj drveta u infiksnom poretku u datoteci izlaz.txt, ako je kao
parametar komandne linije zadata opcija
-t
Obezbediti da program radi i kada su
prisutni svi opcioni argumenti. Pretpostaviti da naziv otvarajuće
etikete nije duži od
20 karaktera.
Primer: <P
align=”center”> <IMG src=”ul.gif”> <BR>
</p>
Otvarajuće etikete bez
atributa su: BR, IMG, P
2. Napisati
a)
funkciju koja metodom Quick sort sortira u neopadajucem poretku karaktere niske
koja se zadaje kao argument funkcije. Obavezno je koristiti bibliotecku
funkciju qsort.
b)
program koji testira rad funkcija pod a) za sve niske koja se zadaju kao parametri komandne linije
Primer: ULAZ U KOMANDNOJ LINIJI: jedAn
dva tri
IZLAZ na STDOUT: Adejn adv irt
1. Videti rešenje 1. zadatka za I tok
2.
#include<stdio.h>
#include <stdlib.h>
#include <string.h>
void sortiraj(char* p); /*
funkcija pod a) */
int poredi(const void* a,const
void* b);
/* rastojanje a od b
*/
main(int argc,char* argv[])
{
int
i; /*brojacka promenljiva */
/*sortira argv[1], argv[2],… */
for (i=1;i<argc;i++){ sortiraj(argv[i]); printf("%s\n",argv[i]); }
printf("\n");
}
int
poredi(const void* a,const
void* b)
{
return (*(char*)a-*(char*)b);
}
void
sortiraj (char* p)
{
qsort(p,strlen(p),sizeof(char),&poredi);/*koristi se bibliotecka
funkcija qsort*/
}
OSNOVI PROGRAMIRANJA JUN 2005
1. Tekst dužine n
karaktera koji je zapisan u datoteci tekst.txt je potrebno šifrovati. Za
šifrovanje se koristi datoteka kljuc.txt u kojoj je dato m celih brojeva iz intervala [0, 25], pri čemu je m>=n.
Prilikom šifrovanja, šifruju se samo slova engleskog alfabeta (i
velika i mala), dok se ostali karakteri prepisuju neizmenjeni. Karakter ti koji je i-ti po redu u tekstu šifruje se
korišćenjem broja ki
(i-tog broja u ključu) i to tako što se ciklično pomeri po
abecedi za ki mesta.
Napisati program koji na standardni izlaz ispisuje rezultat šifrovanja.
Npr.
Tekst.txt Kljuc.txt
Abc, Xyz. 1 2 3 4 5 6 5 4 3 2 1 0
Se šifruje u Bdf, Ddd.
(20 poena)
2. Napisati
rekurzivnu funkciju void
num2str (int n, char *s) koja konvertuje ceo broj n u nisku s.
(20 poena)
OKRENITE!!!
3.
a) Napisati funkciju
koja poredi dva datuma koji
su zadati kao parametri funkcije.
b) Napisati
program koji od
dve datoteke u kojima su u svakoj
liniji sadrzani datumi u obliku dd. mm. gggg. sortirani u strogo
rastućem poretku formira treću datoteku spojdat.txt
koja sadrži datume iz obe
datoteke sortirane u strogo rastućem poretku. Izostaviti dvostruka pojavljivanja
istog datuma.
Imena prve dve datoteke sa
zadaju kao argumenti komandne linije. Broj linija
nije unapred poznat.
(10
+ 20 poena)
4. Argumenti komandne
linije su nazivi dve datoteke
koje u svakoj liniji sadrže po jednu nisku
sa ne
više od 80 karaktera. Napisati program koji na standardni
izlaz ispisuje sve niske prve
datoteke koje nisu sadržane u drugoj datoteci. Zadatak realizovati korišćenjem
binarnog stabla pretrage.
(30 poena)
OBAVEZNO JE REŠENJA
PISATI ČITKO I SA POTREBNIM KOMENTARIMA!!!
REŠENJA
2.
#include <math.h>
#include <stdio.h>
void num2str (unsigned
n, char *s);
main()
{
int n; char
s[30];
printf("Unesite ceo
broj: ");
scanf("%d", &n);
num2str(n,s);
printf("\nNiska %s\n",s);
getchar();
return 0;
}
void num2str (int n, char *s)
{
static
int i; /*indeks niza
s*/
if
(n/10) num2str(n/10,s);
else
{
i=0;
if (n<0) s[i++]='-'; /*upis predznaka broja */
}
s[i++]=abs(n)%10 + '0'; /*formiranje ASCII i-te cifre broja*/
s[i]='\0';
}
====================================================================================
3.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int poredi(
int d1, int m1, int g1,
int d2, int m2, int g2); /*poredjenje
datuma d1.m1.g1 sa
d2.m2.g2.*/
main (int argc,
char **argv)
{
short
krajdat1=1, krajdat2=1; /*indikatori {0,1} kraja prve, druge
datoteke*/
int d1, m1, g1; /* dan, mesec, godina
prvog datuma */
int d2, m2, g2; /* dan, mesec, godina
drugog datuma */
FILE *ul1, *ul2, *izl;
if
(argc!=3)
{ fprintf(stderr, "Program %s nije korektno pozvan: %s dat1
dat2", argv[0], argv[0]);
exit(1);
}
ul1=fopen(argv[1], "rt");
ul2=fopen(argv[2], "rt");
izl=fopen("spojdat.txt",
"wt");
if (krajdat1!=EOF) krajdat1=fscanf(ul1,
"%d.%d.%d.",&d1,&m1,&g1);
if (krajdat2 != EOF) krajdat2=fscanf(ul2,
"%d.%d.%d.",&d2,&m2,&g2);
/*citanje reda po
reda datoteka i poredjenje datuma
*/
while ( (krajdat1!=EOF) || (krajdat2!=EOF))
/*prepis datma 1. datoteke
u izlaznu */
if (krajdat2==EOF || ( (krajdat1!=EOF)
&& ( (poredi(d1,m1,g1,d2,m2,g2)) <0) )
{
/*datum 1. datoteke je manji, te se prepisuje u 3. datoteku*/
fprintf(izl,
"%d.%d.%d.\n", d1,m1,g1);
krajdat1=fscanf(ul1, "%d.%d.%d.",&d1,&m1,&g1);
}
else
if (krajdat1==EOF || ((krajdat2!=EOF) && (poredi(d1,m1,g1,d2,m2,g2) >0)) )
{
/*datum 2. datoteke je manji, te se prepisuje u 3. datoteku*/
fprintf(izl,
"%d.%d.%d.\n", d2,m2,g2);
krajdat2=fscanf(ul2,
"%d.%d.%d.",&d2,&m2,&g2);
}
else if ( krajdat1!=EOF && krajdat2 !=EOF
&& poredi(d1,m1,g1,d2,m2,g2)==0)
/*oba datuma su
ista, te
se prepisuje ma koji od njih, npr.
datum 1. datoteke*/
/*ali
se zbog eliminacije duplikata, vrsi iscitavanje narednog reda u obe datoteke*/
{
fprintf(izl,
"%d.%d.%d.\n", d1,m1,g1);
krajdat1= fscanf(ul1,
"%d.%d.%d.",&d1,&m1,&g1);
krajdat2=fscanf(ul2,
"%d.%d.%d.",&d2,&m2,&g2);
}
fclose(ul1);
fclose(ul2);
fclose(izl);
return
0;
}
int poredi(
int d1, int m1, int g1,
int d2, int m2, int g2)
{
/*f-ja vraca -1 ako
je d1.m1.g1 < d2.g2.m2.
1 ako je d1.m1.g1 > d2.g2.m2.
0 ako je d1.m1.g1 < d2.g2.m2.
*/
if
(g1<g2) return -1;
else
if (g1>g2) return
1;
else
if
(m1<m2) return -1;
else
if (m1>m2) return
1;
else
if (d1<d2) return -1;
else
if (d1>d2) return
1;
else
return 0;
}
=========================================================================
4.
/*ideja zadatka: staviti niske 2. datoteke u bin. stablo pretrage
i za svaku
rec 1. datoteke
proveriti da li se nalazi u 2. datoteci */
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXREC 81
typedef struct drvo_tag
{
char *rec; /* pokazuje na rec teksta */
struct
drvo_tag *levo; /* leva grana
*/
struct
drvo_tag *desno; /* desna grana */
} drvo;
/* Prototipovi funkcija */
drvo *addtree(drvo *, char *);
drvo* nadji
(char *, drvo *);
drvo *talloc(
void );
char *strdpl(char *);
void osloboditi( drvo *k);
main(int argc, char ** argv)
{
drvo
*koren;
/*koren stabla pretrazivanja */
char
rec[MAXREC];
/*sadrzaj reci iz datoteke
*/
FILE *ul1, *ul2;
ul1=fopen(argv[1], "rt");
ul2=fopen(argv[2], "rt");
/*ucitavanje reci druge datoteke u binarno pretrazivacko stablo */
koren
= NULL;
while(
fgets(rec, MAXREC,ul2) )
/*dodavanje novog cvora u stablo, ako vec rec
nije ubacena u stablo */
koren = addtree(
koren, rec);
/*stampa reci iz
1. datoteke koje se ne sadrze
u 2. datoteci*/
while(
fgets(rec, MAXREC,ul1) )
if (nadji(rec,koren) == NULL) printf("\n%s", rec);
/*oslobadjanje zauzetog prostora za stablo
pretrage */
osloboditi(koren);
fclose(ul1); fclose(ul2);
return
0;
}
/* addtree - dodaje cvor sa tekstom na koji
pokazuje w, na ili ispod p u drvetu*/
drvo *addtree(
drvo *p, char *w )
{
int cond;
if(
p == NULL ) /* naisla nova rec
*/
{
p = talloc();
p->rec = strdpl(w);
p->levo = p->desno = NULL;
}
else if ( (cond = strcmp(w,p->rec)) < 0 ) /* manje => levi ogranak */
p->levo = addtree(p->levo, w);
else
if (cond > 0) /*vece =>desni ogranak*/
p->desno = addtree(p->desno, w);
return
p;
}
drvo* nadji
(char *rec, drvo *koren) /*vraca NULL ako
se rec ne nalazi u stablu*/
{ int cond;
if
(koren==NULL) return
NULL;
if(
(cond=(strcmp(koren->rec, rec))==0)) return koren;
else
if (cond <0) return (rec, koren->levo);
else
return (rec, koren->desno);
}
/* talloc pravi jedan
cvor drveta */
drvo *talloc(void)
{
return (drvo
*) malloc(sizeof(drvo)); }
char *strdpl(char *s) /* pravi se kopija
niske s */
{
char
*p;
p = (char *)
malloc(strlen(s) + 1 );
if(
p != NULL ) strcpy(p,s);
return
p;
/* u postoji
standardna funkcija "strdup" koja obavlja navedene operacije*/
}
void osloboditi( drvo *k)
{
/*rekurzivno se oslobadja levo i desno
podstablo korena zadatog stabla */
if
(k->levo) osloboditi (k->levo);
if
(k->desno) osloboditi (k->desno);
free (k); /*brisanje cvora koji predstavlja koren zadatog stabla
*/
}
III1
Na primer ULAZ:
Osnovi programiranja su moj najdrazi predmet na prvoj godini studija.
Vredno sam ucila,odnosno ucio, tokom leta i zato ocekujem da cu
poloziti ispit iz ovog interesantnog predmeta
bez potrebe da se oslonim na nepostene radnje kao sto su
prepisivanje iz ranije
pripremljenih puskica ili uznemiravanje kolege
da mi dozvoli da prepisem njegova resenja.
n=15 IZLAZ
13 | *
12 | *
11 | *
10 | *
9 | *
8 | *
7 | * * * *
6 | * * * * *
5 | * * * * * *
4 | * * * * * * *
3 | * * * * * * * *
2 | * * * * * * * *
1 | * * * * * * * * * *
+---------------------------------
1 2 3 4 5 6 7 8 9 10 >10
n=9 IZLAZ
9 | *
8 | *
7 | *
6 | *
5 | *
4 | * * * * *
3 | * * * * * *
2 | * * * * * * * *
1 | * * * * * * * *
+---------------------------------
1 2 3 4 5 6 7 8 9 10 >10
#include <stdio.h>
#include <stdlib.h>
#define MAXDUZRECI 10
int main(int argc, char *argv[])
{
int c; /* tekuci karakter sa ulaza */
int ureci = 0; /* indikator boravka tekuceg karakera ulaza
u reci ili van reci */
long zvezda[MAXDUZRECI + 1];
/* zvezda[i] sadrzi broj reci duzine i=1..10,
zvezda[10] sadrzi broj reci cija duzina >10 */
int duzina = 0; /* duzina tekuce reci sa ulaza*/
int n; /* limit visine histograma */
long max=0; /* max niza zvezda */
int pocetak = 1;
int i = 0, broj; /* brojacke promenljive */
FILE * ul;
/* inicijalizacije */
for(i = 0; i <= MAXDUZRECI; i++)
zvezda[i] = 0;
n=atoi(argv[1]) ;
ul=fopen("ulaz.txt", "rt");
/* citanje ulaza i formiranju vrednosti niza zvezda */
while(1)
{
c = fgetc(ul);
if(c == ' ' || c == '\t' || c == '\n' || c == EOF)
{if(ureci == 0)
{
pocetak = 0; ureci = 1;
if(duzina <= MAXDUZRECI)
{
if(duzina> 0)
{
++zvezda[duzina - 1];
if(zvezda[duzina - 1] > max)
max = zvezda[duzina - 1];
}
}
else
{
++zvezda[MAXDUZRECI];
if(zvezda[MAXDUZRECI] > max) max = zvezda[MAXDUZRECI];
}
}
if(c == EOF) break;
}
else
{
if(ureci == 1 || pocetak == 1)
{
duzina = 0;
pocetak = 0;
ureci = 0;
}
++duzina;
}
}
if (max < n) n=max;
/* vertikalno stampa odozgo nadole linije
vertikalnog histograma sve do apcise,
vodeci racuna o razmeri */
for(broj = n; broj > 0; broj--)
{
printf("%4d | ", broj);
for(i = 0; i <= MAXDUZRECI; i++)
if(zvezda[i] * n / max >= broj) printf("* ");
else printf(" ");
printf("\n");
}
/* apcisa */
printf(" +");
for(i = 0; i <= MAXDUZRECI; i++)
{
printf("---");
}
printf("\n ");
for(i = 0; i < MAXDUZRECI; i++)
{
printf("%2d ", i + 1);
}
printf(">%d\n", MAXDUZRECI);
fclose(ul);
return 0;
}
|
IV 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct drvo drvo; /* z-a drvo */
struct drvo {
char c;
drvo *l,*d;
};
void ubaci(drvo *, char c, int i);
/*smesta karakter c u drvo na nivo i */
void infiks(drvo *);
/* stampa drvo */
void oslobodi(drvo *);
/* oslobadja prostor */
void main(int argc, char **argv)
{ drvo *koren;
int i; /* brojacka promenljiva*/
koren = NULL;
/* unos znakova komandne linije u z-a drvo */
for(i=0;i< strlen(argv[1]);i++)
if(koren==NULL)
{
koren = malloc(sizeof(drvo));
koren->c = argv[1][i];
koren->l = NULL;
koren->d = NULL;
}
else ubaci(koren, argv[1][i], 0);
infiks(koren);
oslobodi(koren);
} /* main */
void ubaci(drvo *cv, char c, int nivo)
{
/* konstrukcija levog poddrveta */
if( (nivo % 2 == 1 && c > cv->c) ||
(nivo % 2 == 0 && c <= cv->c) )
if(cv->l == NULL)
{
cv->l = malloc(sizeof(drvo));
cv->l->c = c;
cv->l->l = NULL;
cv->l->d = NULL;
}
else ubaci(cv->l, c, nivo+1);
else
/* konstrukcija levog poddrveta */
if(cv->d == NULL)
{
cv->d = malloc(sizeof(drvo));
cv->d->c = c;
cv->d->l = NULL;
cv->d->d = NULL;
}
else ubaci(cv->d, c, nivo+1);
}
void infiks(drvo *cv)
{
if(cv!=NULL)
{
infiks(cv->l);
printf("%c",cv->c);
infiks(cv->d);
}
}
void oslobodi(drvo *cv)
{
if(cv != NULL)
{
oslobodi(cv->l);
oslobodi(cv->d);
free(cv);
}
}
|
III2
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 21
typedef struct drvo_CV drvo;
/* BSP uredjeno leksikografski po etiketama */
struct drvo_CV
{ /* za svaku etiketu cuvaju se redni brojevi pojavnih redova r */
char rec[MAX];
int prvi, poslednji;
drvo *levo,*desno;
};
void getEtiketa(FILE *f, char *s, int *br);
/* izdvaja etiketu s iz ulazne datoteke
i postavlja vrednosr rednog broja linije br*/
drvo * addTree(drvo*d, char *s, int br);
/* unosi etiketu s koja se pojavila u redu br u BSP d*/
void printTree(drvo *, FILE *);
/* stampa etikete (inorder) i redne brojeve linija
prve i poslednje pojave etiketa*/
void freeTree(drvo *);/* oslobadja prostor */
main(int argc, char *argv[])
{
drvo *koren;
char rec[MAX]; /* tekuca etiketa sa ulaza */
int brlinije; /* redni broj tekuce linije */
//char c; /* tekuci karakter sa ulaza */
FILE *ul, *izl;
/* inicijalizacije */
koren = NULL;
brlinije = 1;
ul = fopen("sem.htm","rt");
izl = fopen(argv[1],"wt");
/* citanje sadrzaja datoteke i formiranje BSP-a*/
while(!feof(ul))
{
getEtiketa(ul, rec, &brlinije);
if(strlen(rec) > 0) koren=addTree(koren, rec, brlinije);
}
fclose(ul);
printTree(koren, izl);
freeTree(koren);
return 0;
}
void getEtiketa(FILE *fin, char *word, int *br)
{ char c; /* tekuci karakter ulazne datotke */
int k; /* tekuca pozicija niske word koja se formira */
/*ignorisati karaktere kojima ne pocinje etikete */
while( ((c = fgetc(fin))!='<') && c!=EOF)
if(c=='\n') *br=*br+1;
/* postavlja redni broj tekuceg reda */;
/* prazna etiketa i vratiti se u pozivajucu jedinicu*/
if (c==EOF) {word[0]='\0'; return;}
/*ucitati ostatak otvorene etiketa bez atributa
i formirati nisku word */
k = 0;
while(isalnum (c = fgetc(fin)) && c!=EOF)
{
word[k++] = tolower(c);
/* zbog potrebe za case insensitive poredjenjem
pri umetanju niske u drvo */
}
word[k] = '\0';
if(c=='\n') *br=*br+1;
/* postavlja redni broj tekuceg reda */;
} /* izdvojrec */
drvo * addTree(drvo *d, char *w, int br)
{
if(d == NULL) /* rec se prvi put pojavila */
{ d = (drvo *)malloc(sizeof(drvo));
strcpy(d->rec, w);
d->prvi=br; d->poslednji=br;
d->levo = NULL;
d->desno = NULL;
}
else /*rec se opet pojavila*/
if( (strcmp(w, d->rec) == 0) ) d->poslednji=br;
else
if(strcmp(w, d->rec) < 0)
d->levo=addTree( d->levo, w, br);
else d->desno=addTree(d->desno, w, br);
return d;
}
void freeTree(drvo *d)
{ if(d != NULL)
{ freeTree(d->levo);
freeTree(d->desno);
free(d);
}
}
void printTree(drvo *d, FILE *f)
{ if(d != NULL)
{ printTree(d->levo, f);
fprintf(f, "%s %d %d\n",d->rec, d->prvi, d->poslednji);
printTree(d->desno, f);
}
}
|
IV2
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 81
int strindex (char *s, char *obrazac);
/* vraca poziciju u nisci s iza one na kojoj se
zavrsava prva pojava niske obrazac
ili
-1 ako se obrazac ne pojavljuje u nisci s*/
main(int argc, char *argv[])
{
char linija[MAX]; /* tekuca linija ulazne datoteke*/
FILE* f;
f=fopen("ulaz.txt", "r");
if (f!=NULL)
{
while (fgets(linija, MAX, f))
if (strindex(linija, argv[1])!=-1) printf("%s", linija);
fclose(f);
}
return 0;
}
int strindex (char *s, char *obrazac)
{ /* Napomena: switch-case grananje u ovom resenju
je pravljeno s namerom da kod bude sto citljiviji,
cime je naruseno svojstvo kompaktnosti;
uociti da se mogla izbeci redudantnost
pojedinih fragmenata koda */
int i, j,k; /*brojacke promenljiva*/
int pojava; /* logicka promenljiva, koristi se pri testu
poredjenja karaktera obrasca sa karakterima niske s*/
for (i=0; s[i]!='\0';i++)
{
for (pojava=1,j=i,k=0; obrazac[k]!='\0' && pojava; j++,k++)
switch (obrazac[k])
{
/* testira (prisustvo sekvence \a u obrascu
i slova u nisci s) ili
(prisustvo sekvence \0 u obrascu
i dekadne cifre u nisci s) */
case '\\': if ( (obrazac[k+1]=='a') && isalpha(s[j]) )
{pojava=1; k++;}
else if ( (obrazac[k+1]=='0') && isdigit(s[j]) )
{pojava=1; k++;}
else pojava=0;
break;
/* testira prisustvo intervala u obrascu i
prisustva alfanumerickog karktera niske s unutar
granica tog intervala, ukljucujuci i same granice*/
case '[':
if ((s[j]>=obrazac[k+1]) && ((s[j]<=obrazac[k+3])))
{pojava=1; k=k+4;}
else pojava=0;
break;
/* preostao je jos treci slucaj,
a to je da je na poziciji k u obrascu
alfanumericki karakter doslovce, te se poredi sa
odgovarajucim karakterom niske s*/
default: pojava= (obrazac[k]==s[j]); break;
}
if (k>0 && (obrazac[k]=='\0')&& pojava ) return (i+k);
/* obrazac je prisutan unutar niske s ako se u unutrasnjem
for ciklusu stiglo do kraja niske obrazac, a indikator
pojava na izlasku iz unutrasnjeg for ciklusa ima istinutu
vrednost*/
}
return -1; /* inace, obrazac nije prisutan unutar niske s */
}
|
III3
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 81
void strOnce (char *s1, char *s2);
main(int argc, char *argv[])
{
char linija[MAX]; /* tekuca linija ulazne datoteke*/
scanf("%s", linija);
strOnce(linija, argv[1]);
printf("%s", linija);
return 0;
}
void strOnce (char *s1, char *s2)
{
int i, j,k, ind; /*brojacke promenljiva*/
for (i=0; s1[i]!='\0';)
{
for (j=i,k=0; (s2[k]!='\0') && (s1[j]==s2[k]); j++,k++) ;
if (k>0 && (s2[k]=='\0') )
{/*izbacen s2 iz s1 i pomicemo s1*/
for (ind=0; s1[j+ind]!='\0'; ind++)
s1[j-k+ind]=s1[j+ind];
i=j-k; s1[i+ind]='\0';
}
else i++;
}
}
|
IV3
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 81
void strrem (char *s1, char *s2);
main(int argc, char *argv[])
{
char linija[MAX]; /* tekuca linija ulazne datoteke*/
scanf("%s", linija);
strrem(linija, argv[1]);
printf("%s", linija);
return 0;
}
void strrem (char *s1, char *s2)
{
int i, j,k; /*brojacke promenljiva*/
int pojava; /* broj pojava karaktera u nisci s2*/
for (i=k=0; s1[i]!='\0';i++)
{
for (j=0, pojava=0; s2[j]!='\0'; j++)
pojava+= (s2[j]==s1[i]);
if (pojava !=1) s1[k++]=s1[i];
}
s1[k]='\0';
}
|
REŠENJA: JGrmuša, MMarić, JTomašević
1. Napisati program koji na
standardni izlaz ispisuje naziv (BEZ ATRIBUTA) najčešće korišćene etikete u datoteci
ulaz.htm. Ako ima više takvih, ispisati ma koju. Koristiti uređeno binarno
stablo. Pretpostaviti da je ulazna datoteka sintaksno korektna.
30 poena
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 31
typedef struct
BSP_cvor
{
char *etiketa; /*naziv
etikete */
int broj; /*broj pojave etikete*/
struct BSP_cvor *levi; /* levi
ogranak */
struct BSP_cvor *desni; /* desni
ogranak */
}
drvo;
/*FUNKCIJE */
/* ucitava etiketu otvaraca iz datoteke u nisku s*/
int uzmi_etiketu(FILE * f, char * s);
/* ubacuje etiketu u drvo */
drvo *ubaci(drvo *, char *);
/* alokacija cvora BSP */
drvo *alociraj( void );
/* kreira kopiju niske */
char *strdpl(char *);
/*poredjenje naziva dve etikete
ignorisuci razliku malih, velikih slova*/
int uporedi(char *, char *);
/* stampa drvo - infiksni poredak
za BSP*/
void infiks(drvo *);
/* oslobadja zauzeti prostor za
drvo */
void osloboditi( drvo *);
int max=0; /*najveci br.pojava etikete*/
char szMax_Etik[MAX]; /*najcesca etiketa*/
main()
{
drvo *koren; /*koren stabla pretrazivanja */
char etiketa[MAX]; /*naziv etikete sa
ulaza */
FILE
*dat;
dat=fopen("ulaz.htm","r");
if (dat==NULL) exit(1);
/*formiranje stabla od ucitanih
razlicitih etiketa */
koren = NULL;
while( 1 )
{ int
kraj = uzmi_etiketu(dat,etiketa);
/*dodavanje cvora u stablo cvora, ako etiketa nije prisutna u
stablu */
if
( strlen(etiketa)) koren = ubaci( koren, etiketa);
if(kraj == EOF) break;
}
fclose(dat);
printf("\nNajcesca etiketa je: %s sa brojem pojava
%d\n", szMax_Etik, max);
osloboditi(koren);
return 0;
}
drvo *alociraj(void)
{ return (drvo *) malloc(sizeof(drvo)); }
drvo *ubaci( drvo *k, char *tag )
{ int test;
if( k == NULL )
{ /* naisao nov naziv */ k = alociraj();
k->etiketa
= strdpl(tag); k->broj=1;
k->levi = k->desni
= NULL;
}
else if ((test = uporedi(tag,k->etiketa))< 0 ) /* idi levo */
k->levi = ubaci(k->levi, tag);
else if
(test >0) /* idi desno */
k->desni = ubaci(k->desni, tag);
else /*ponovljena etiketa*/
{k->broj++;
if (max <
k->broj) {max=k->broj; strcpy(szMax_Etik,k->etiketa); }
}
return k;
}
void infiks(drvo *k)
{
if( k != NULL )
{ infiks( k->levi
);
printf("%s\n", k->etiketa );
infiks( k->desni );
}
}
int uzmi_etiketu(FILE *f,char s[])
{ char c; /*tekuci
ulazni karakter */
int i = 0; /*brojac*/
if ( (c = fgetc(f)) ==
'<')
while (isalnum(c = fgetc(f)) )
s[i++] = c;
s[i] = '\0';
if( c==EOF ) return EOF;
return i;
}
/*poredi etikete e1, e2 tako da
poredjenje bude case insensitive*/
int uporedi(char *e1, char *e2)
{ char pom1[MAX], pom2[MAX];
int i;
for(i=0;e1[i]!='\0';i++) pom1[i]=tolower(e1[i]);
pom1[i]='\0';
for(i=0;e2[i]!='\0';i++) pom2[i]=tolower(e2[i]);
pom2[i]='\0';
return strcmp (pom1, pom2);
}
char *strdpl(char *s)
{ char *pom;
pom = (char *)
malloc(strlen(s) + 1 );
if( pom != NULL
) strcpy(pom,s);
return pom;
}
void osloboditi( drvo *k)
{ if (k->levi) osloboditi (k->levi);
if (k->desni) osloboditi (k->desni);
free (k);
}
2.
a) Napisati
funkciju int poredi(char* p, char* d) koja vraća -1 ukoliko je p<d, 0
ukoliko je p == d a 1 ako je p>d, pri čemu su p i d dva velika
cela neoznačena broja zadata
nizom(niskom) svojih cifara.
b)Argumenti komandne linije su imena dve datoteke koje sadrže cele neoznačene brojeve (po jedan u svakoj liniji, sa maksimalno 1000 cifara) sortirane u rastućem poretku po numeričkoj vrednosti. Broj linija nije unapred poznat. Napisati program koji upisuje sadržaj ove dve datoteke u datoteku Spoj.txt tako da i ona bude sortirana.
(10 + 20 poena)
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXCIF 1000
int getnumber(FILE *fp, char *, int);
int poredi(char *, char *);
int main(int argc, char **
argv)
{
FILE
*ul1, *ul2, *izl;
char
br1[MAXCIF],br2[MAXCIF];
int kraj1,kraj2;
//Indikator da treba uzeti broj iz datoteke inace cuva
podatak o duzini broja
kraj1 = kraj2 = 0;
ul1=fopen(argv[1], "r");
ul2=fopen(argv[2], "r");
izl=fopen("Spoj.txt", "w");
do
{
if(!kraj1)
/* Uzima se broj iz datoteke promenljiva
kraj1 cuva informaciju da li se siglo do
EOF-a prve datoteke*/
kraj1 = getnumber(ul1, br1, MAXCIF);
if(!kraj2)
/* Uzima se broj iz datoteke promenljiva
kraj2 cuva informaciju da li se siglo do
EOF-a druge datoteke*/
kraj2 = getnumber(ul2, br2, MAXCIF);
//Ukoliko jedan od brojeva "nema duzinu" - doslo se do kraja
datoteke i treba
//zaustaviti petlju
if(!strlen(br1)
&& strlen(br2))
{
//Nemamo prvi broj a imamo drugi - upisujem ga i iskacemo
iz petlje
fprintf(izl,"%s",br2);
fprintf(izl,"%c",'\n');
break;
}
if(!strlen(br2)
&& strlen(br1))
{
//Nemamo drugi broj
a imamo prvi - upisujem ga i iskacemo iz petlje
fprintf(izl,"%s",br1);
fprintf(izl,"%c",'\n');
break;
}
if(poredi(br1,br2)
< 0)
{
//Upisije se broj uzet iz prve datoteke
fprintf(izl,"%s",br1);
fprintf(izl,"%c",'\n');
//Inikator da treba uzeti novu rec iz prve datoteke
kraj1 = 0;
}
else
{
//Upisije se broj uzet iz druge datoteke
fprintf(izl,"%s",br2);
fprintf(izl,"%c",'\n');
//Inikator da treba uzeti novu rec iz druge datoteke
kraj2
= 0;
}
}while((kraj1 != EOF)
&& (kraj2 != EOF));
//Provera koja datoteka je prazna da bi prepisali onu drugu
if(kraj2 == EOF)
{
//Treba prepisati prvu
do
{
kraj1 = getnumber(ul1,
br1, MAXCIF);
//Provera da li
broj uzet ili se doslo do kraja
if(strlen(br1))
{
fprintf(izl,"%s",br1);
fprintf(izl,"%c",'\n');
}
}
while(kraj1
!= EOF);
}
else
{
//Treba prepisati drugu
do
{
kraj2 = getnumber(ul2,
br2, MAXCIF);
//Provera da li
broj uzet ili se doslo do kraja
if(strlen(br2))
{
fprintf(izl,"%s",br2);
fprintf(izl,"%c",'\n');
}
}
while(kraj2
!= EOF);
}
//Zatvaranje datoteka
fclose(ul1);
fclose(ul2);
fclose(izl);
return 0;
}
int getnumber(FILE *fp, char num[], int lim)
{
char c, i = 0;
/* Preskace se sve do pojave cifre */
while( !isdigit(c = num[0] =
fgetc(fp)) && c!=EOF);
/* Ukoliko je EOF uzrok izlaska iz petje - vraca se prazna
rec */
if( c==EOF )
{
num[0] = '\0';
return EOF;
}
/* Ucitava se ostatak broja (u s[0]
se vec nalazi prva cifra) */
while( (c = fgetc(fp)) !=
EOF && isdigit(c) && i < lim)
num[++i] = c;
/* Zavsava se niska sa \0 */
num[++i] = '\0';
/* Ukoliko je poslednji ucitani karakter EOF funkcija
vraca EOF kao
signal za kraj ulaza */
if( c==EOF )
return EOF;
/* Inace funkcija vraca duzinu broja */
return i;
}
int poredi(char *p, char *d)
{
if(strlen(p) < strlen(d))
//Ako prvi broj ima manje cifara nego drugi => drugi je
veci
return -1;
else if(strlen(p)
> strlen(d))
//Ako drugi broj ima manje cifara => prvi je veci
return 1;
//Inace strcmp vraca ono sto zelimo
else
if (strcmp(p,d)>0) return 1;
else if
(strcmp(p,d)<0) return -1;
else return 0;
}
3. Napisati program koji sa standardnog ulaza učitava pozitivan ceo broj, a na standardni izlaz ispisuje vrednost tog broja sa razmenjenim vrednostima bitova na poziciji i, j. Pozicije i, j se učitavaju kao parametri komandne linije. Smatrati da krajnji desni bit binarne reprezentacije je 0-ti bit. Pri rešavanju nije dozvoljeno koristiti pomoćni niz niti aritmetičke operatore +,-,/,*,%.
20 poena
#include <stdio.h>
unsigned Trampa(unsigned n, int i, int j);
main(int argc, char **argv)
{
unsigned x; /*broj sa standardnog ulaza ciji se bitovi razmenjuju*/
int i,j; /*pozicije bitova
za trampu*/
/*ocitavanje
parametara komandne linije i broja sa standarnog
ulaza*/
sscanf(argv[1], "%d", &i);
sscanf(argv[2], "%d", &j);
scanf("%u", &x);
printf("\nNakon trampe vrednost unetog broja je
%u\n", Trampa(x,i,j));
}
unsigned Trampa(unsigned n, int i, int j)
{
//ako se bit na poziciji i
razlikuje od bita na poziciji j, treba ih invertovati
if ( ((n>>i)&1) !=
((n>>j)&1) ) n^= (1<<i) | (1<<j);
return n;
}
4.
Sa standardnog
ulaza se učitava niz od n (n<100) tačaka u ravni takvih da nikoje tri tačke
nisu kolinearne. Tačke se zadaju parom svojih koordinata
(celi brojevi). Ispitati da li taj niz tačaka
odredjuje konveksni
mnogougao i rezultat ispisati na standardni izlaz.
#include<stdio.h>
typedef struct
tacka
{
int x;
int y;
} TACKA;
/* F-ja ispituje da li se tacke
T3 i T4 nalaze sa iste strane prave odredjene tackama
T1 i T2.*/
int SaIsteStranePrave(TACKA
T1,TACKA T2, TACKA T3, TACKA T4)
{
int t3 = (T3.y - T1.y)*(T2.x -
T1.x) - (T2.y - T1.y) * (T3.x - T1.x);
int t4 = (T4.y - T1.y)*(T2.x -
T1.x) - (T2.y - T1.y) * (T4.x - T1.x);
return (t3 * t4 > 0);
}
main()
{
TACKA mnogougao[100];
int j,i;
int n;
int konveksan = 1;
do{
printf("Unesite broj temena
mnogougla:\n");
scanf("%d",&n);
if(n<3)
printf("Greska! Suvise malo
tacaka! Pokusajte ponovo!\n");
}
while(n<3);
printf("Unesite koordinate
temena mnogougla takve da nikoja tri temena nisu kolinearna!\n");
for(i=0;i<n;i++)
scanf("%d %d",
&mnogougao[i].x, &mnogougao[i].y);
/* Da bi mnogougao bio konveksan
potrebno (i dovoljno) je da kada se povuce prava kroz bilo koja
dva susedna temena
mnogougla sva ostala temena budu sa iste strane te prave.*/
for(i=0;konveksan&&i<n-1;i++)
{
for(j=0;konveksan&&j<i-1;j++)
konveksan=konveksan && SaIsteStranePrave(mnogougao[i],mnogougao[i+1],mnogougao[j],mnogougao[j+1]);
for(j=i+2;konveksan&&j<n-1;j++)
konveksan=konveksan &&
SaIsteStranePrave(mnogougao[i],mnogougao[i+1],mnogougao[j],mnogougao[j+1]);
if(i!=0&&i!=n-1&&i+1!=0&&i+1!=n-1)
konveksan=konveksan && SaIsteStranePrave(mnogougao[i],mnogougao[i+1],mnogougao[0],mnogougao[n-1]);
}
for(j=1;konveksan&&j<n-2;j++)
konveksan=konveksan &&
SaIsteStranePrave(mnogougao[0],mnogougao[n-1],mnogougao[j],mnogougao[j+1]);
if(konveksan)
printf("Uneti mnogougao jeste
konveksan!\n");
else
printf("Uneti mnogougao nije
konveksan!\n");
}
1. Napisati rekurzivnu funkciju sumaNivoa koja određuje sumu elemenata na N-tom nivou binarnog drveta. Koren tretirati kao 0-ti nivo. 20 poena
int SumaNivoa (int n, drvo *T)
{
if (T)
if (n) return SumaNivoa(n-1,T->levi) + SumaNivoa(n-1,T->desni);
else return T->elem;
else return 0;
}
2. Svaki red datoteke,
čije se ime unosi kao argument
komandne linije, sadrži ime, prezime i broj telefona. Iza imena i prezimena
nalazi se po jedan blanko karakter, a telefoni su zapisani u formatu: pozivni
broj mesta-broj telefona (npr. 011-333888). Napisati program koji generiše HTML
datoteku Beograd.htm koja sadrži tabelu sa podacima o osobama čiji su
telefonski brojevi iz Beograda. Zaglavlje tabele treba da sadrži polja: ime,
prezime i br. telefona. 30 poena
/* Binarno drvo */
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXREC 40
#define MAXBRT 20
//Prototip funkcije za citanje reci
iz file-a
int
getword(FILE *fp, char *, int);
int
main(int argc, char ** argv)
{
FILE *ul, *izl;
char ime[MAXREC], prezime[MAXREC], brt[MAXBRT];
int
kraj;
//Otvaranje datoteke sa podacima
ul=fopen(argv[1], "r");
//Rezultujuca
datoteka
izl=fopen("Beograd.html",
"w");
fprintf(izl,"<HTML><HEAD><TITLE>Telefoni</TITLE></HEAD><BODY>");
fprintf(izl,"<TABLE><TR><TH>Ime</TH><TH>Prezime</TH><TH>Br.
Telefona</TH>");
do
{
/* Uzima se ime iz
datoteke sa najvise MAXREC karaktera
promenljiva kraj cuva informaciju da li se siglo do EOF-a*/
kraj = getword(ul, ime,
MAXREC);
if(kraj == EOF)
break;
/* Uzima se prezime
iz datoteke sa najvise MAXREC karaktera
promenljiva kraj cuva informaciju da li se siglo do EOF-a*/
if(kraj = getword(ul, prezime,
MAXREC) == EOF)
break;
/* Uzima se telefonski
broj iz datoteke
sa najvise MAXBRT cifara
promenljiva kraj cuva informaciju da li se siglo do EOF-a*/
if(kraj = getword(ul, brt,
MAXBRT) == EOF)
break;
//Ako su
podaci kompletni
if(strlen(ime) && strlen(prezime) && strlen(brt))
// i ako
je pozivni broj 011
if((brt[0]=='0') &&
(brt[1]=='1') && (brt[2]=='1'))
//vrsi se upisivanje
podataka u tabelu
fprintf(izl,"<TR><TD>%s</TD>
<TD>%s</TD> <TD>%s</TD></TR>", ime, prezime, brt
);
//Sve do karaja FILE-a
}while(kraj != EOF);
//Upisuju se kontejnerski tagovi i zatvaraju
datoteke ...
fprintf(izl,"</TABLE></BODY></HTML>");
fclose(ul);
fclose(izl);
return 0;
}
/* Funkcija koja uzima
rec sa ulaza
makslimalno lim duzine i vraca
EOF
ukoliko dodje do kraja ulaza */
int
getword(FILE *fp, char s[], int
lim)
{
char c, i = 0;
/* Preskace se sve do pojave slova ili
cifre */
while( !isalnum(c = s[0] = fgetc(fp)) && c!=EOF);
/* Ukoliko je EOF uzrok izlaska iz
petje - vraca se prazna rec */
if( c==EOF )
{
s[0] = '\0';
return
EOF;
}
/* Ucitava se ostatak reci (u s[0] se vec nalazi prvo slovo)
*/
while( (c = fgetc(fp)) != EOF && isalnum(c) && i < lim)
s[++i] = c;
/* Zavsava se niska sa \0 */
s[++i] = '\0';
/* Ukoliko je poslednji
ucitani karakter EOF funkcija
vraca EOF kao signal za kraj
ulaza */
if( c==EOF )
return
EOF;
/* Inace funkcija vraca duzinu niske
*/
return i;
}
3. Napisati
funkciju unsigned Trampa(unsigned n, int
i, int j) koja će razmeniti vrednost bitova na poziciji i, j promenljive n. Smatrati da krajnji desni bit binarne reprezentacije je 0-ti bit. Pri rešavanju nije dozvoljeno
koristiti pomoćni niz niti aritmetičke operatore +,-,/,*,%. 20 poena
unsigned Trampa(unsigned
n, int i, int j)
{
//ako se bit na poziciji i razlikuje od bita
na poziciji j, treba ih invertovati
if (
((n>>i)&1) != ((n>>j)&1) ) n^=
(1<<i) | (1<<j);
return n;
}
4. Sa standardnog
ulaza se unose koordinate četiri tačke A, B, C i D (realni brojevi)
koje pripadaju istoj ravni. Proveriti da li tačka D pripada ili ne pripada
unutrašnjosti trougla ABC (tačke A, B, C nisu kolinearne) i dobijeni
rezultat ispisati na standardni izlaz. 30 poena
#include<stdio.h>
typedef struct
tacka
{
float x;
float y;
} TACKA;
/* F-ja ispituje
da li se tacke T3 i T4 nalaze sa iste strane prave odredjene tackama T1 i T2. Pri
tom, ukoliko neka od tacaka T3 i T4 lezi na odgovarajucoj pravoj smatra se da tacke
nisu sa iste strane te prave. */
int
SaIsteStranePrave(TACKA T1,TACKA T2, TACKA T3, TACKA T4)
{
int t3 = (T3.y - T1.y)*(T2.x - T1.x) -
(T2.y - T1.y) * (T3.x - T1.x);
int t4 = (T4.y - T1.y)*(T2.x - T1.x) -
(T2.y - T1.y) * (T4.x - T1.x);
return (t3 * t4 > 0);
}
main()
{
TACKA A, B, C, D;
printf("Unesite
koordinate temena trougla:\n");
printf("Unesite
koordinate temena A:\n");
scanf("%f %f",
&A.x, &A.y);
printf("Unesite
koordinate temena B:\n");
scanf("%f %f",
&B.x, &B.y);
printf("Unesite
koordinate temena C:\n");
scanf("%f %f",
&C.x, &C.y);
printf("Unesite
koordinate tacke D za koju se ispituje da li pripada trouglu ABC:\n");
scanf("%f %f",
&D.x, &D.y);
if(SaIsteStranePrave(A,B,C,D)
&& SaIsteStranePrave(B,C,A,D) && SaIsteStranePrave(A,C,B,D))
printf("Tacka
D pripada trouglu ABC!\n");
else printf("Tacka
D ne pripada trouglu ABC!\n");
}