1. z-a drvo je
binarno drvo koje se konstruiše na sledeći način: na neparnim nivoima drveta, levo dete
je veće od svojih roditelja,
a na parnim nivoima drveta je, pak levo
dete manje ili jednako svojim
roditeljima. Sastaviti
program koji od
karaktera niske zadate iz komandnog
reda formira z-a drvo i štampa
ga infiksnim (in-order) obilaskom čvorova. Na
primer, za ulaznu reč abrakadabra na
izlazu je niska aaaaarkdrbb.
#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>
typedef struct
drvo drvo; /* z-a drvo */
struct drvo
{ /* cvor drveta*/
char c; /* karakter komandne linije */
drvo
*l,*d;
};
void ubaci(drvo
k*, char c, int i); /*unosi karakter 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,n; /* brojacka promenljiva, duzina arg. komandne
linije */
/*inicijalizacije */
n
= strlen(argv[1]);
koren = NULL;
/*
ucitavanje karaktera iz kom. linije u z-a drvo */
for(i=0;i<n;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);
/*
stampa z-a drvo*/ infiks(koren);
printf("\n"); oslobodi(koren);
}
/* main */
void ubaci(drvo
*cv, char c, int nivo)
{
if( (nivo % 2 == 1 && c > cv->c) ||
(nivo % 2 == 0
&& c <= cv->c) )
if(cv->l == NULL)
/* ici levo */
{
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
if(cv->d == NULL)
/* ici desno */
{
cv->d = malloc(sizeof(drvo));
cv->d->c = c;
cv->d->l
= NULL;
cv->d->d = NULL;
}
else ubaci(cv->d, c, nivo+1);
}
/* ubaci */
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);
}
}
/* oslobodi */
2. Napisati C program koji ce iz datoteke ulaz.htm prepisati nazive međusobno različitih etiketa (bez atributa) u binarno stablo pretrage, a na standardni izlaz ispisati:
1) ukupan
broj čvorova drveta, ako je
kao parametar komandne linije zadata opcija -n
2) ukupan
broj listova drveta, ako je
kao parametar komandne linije zadata opcija -l
3) štampati
sadržaj drveta u infiksnom poretku, ako je kao
parametar komandne linije zadata opcija
-p
4) štampati
dubinu drveta, ako je kao
parametar komandne linije zadata opcija
–d
Obezbediti
da program radi i kada su
prisutni svi opcioni argumenti.
Pretpostaviti da naziv etikete nije
duži od
30 karaktera.
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXREC 31
#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 brlist(drvo *k); /* vraca broj listova stabla
*/
int brcvorova(drvo *k); /* vraca broj cvorova stabla
*/
int dubina(drvo *k); /* vraca dubinu 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, leaf=FALSE, printt=FALSE,depth=FALSE; /*indikatori postojanja opcija u komandnoj liniji */
ulaz=fopen("ulaz.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
'n': node = TRUE; break;
case 'l': leaf = TRUE; break;
case
'p': printt=TRUE; break;
case 'd': depth=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 broja listova stabla
*/
if (leaf) printf("\nListova: %d", brlist(koren));
/*stampanje sadrzaja stabla*/
if (printt) treeprint(koren);
/*stampanje dubine stabla */
if (depth) printf("\nDubina: %d", dubina(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 && isalpha(c) && i < lim)
{s[i] = toupper(c); i++; }
s[++i] = '\0'; /*
zavrsiti nisku */
if( c==EOF ) return EOF;
return i;
}
int brlist(drvo *cv)
{
if(cv==NULL) return 0;
else if(cv->levo==NULL && cv->desno==NULL) return 1;
else return brlist(cv->levo)
+ brlist(cv->desno);
}
int brcvorova(drvo *c)
{
if(c == NULL)
return 0;
else return 1+brcvorova(c->levo)+brcvorova(c->desno);
}
int dubina ( drvo *k) /* nalazi
max rastojanje od korena do listova BSP*/
{ int levo, desno, rezultat;
if (k==NULL)
return 0;
else
{ levo=dubina(k->levo);
desno=dubina(k->desno);
if (levo > desno) rezultat=levo+1;
else rezultat=desno+1;
return rezultat;
}
}
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 */
}
IV
TOK
1. Datoteka
slova.dat sadrži podatke o matrici u čijem svakom polju se čuva po
jedan znak. Na početku datoteke se nalaze broj vrsta i broj kolona
matrice, a potom sledi jedno po jedno slovo (bez razmaka). Svaka vrsta tabele
nalazi se u zasebnom redu datoteke. Kažemo da datoteka sadrži reč ako se
znaci reči pojavljuju na susednim poljima matrice (susedna polja jednom
polju su polje levo, desno, gore, dole, gore-levo, gore-desno, dole-levo i
dole-desno). Napisati program koji za reč koja se zadaje kao parametar
komandne linije ispisuje na standardni izlaz izveštaj da li se reč pojavljuje u opisanoj matrici, na
kojoj poziciji i u kom pravcu.
Izlazni
izveštaj treba da bude oblika "Rec ... se pojavljuje od pozicije (... ,
...) u smeru ..." (pri čemu smer može biti "gore",
"dole", "levo", "desno", "gore-levo",
"gore-desno", "dole-levo" ili "dole-desno")
odnosno
"Rec
... se ne pojavljuje u matrici".
2.
Definisati tip skup kao strukturu
koja se sastoji od niza
(elementi skupa) i jednog celog
broja (kardinalnost skupa).
Pod skupom će se podrazumevati kolekcija sa ne više
od 100 međusobno različitih celobrojnih članova koji su uređeni u rastućem poretku. Svaka operacija nad skupovima
mora očuvati ova svojstva.
(a) Napisati f-ju void prosticin(int broj, skup * cinioci)
koja nalazi sve različite proste činioce broj i smešta ih
u promenljivu cinioci.
(b) Napisati f-ju void unija(skup *s1, skup *s2, skup * rezultat) koja izračunava uniju dva skupa.
(c) Napisati f-ju void prosti(FILE *f, skup
* skupcin,skup
*komplem) koja u skupcin smešta sve proste
činioce brojeva datoteke f, a u skup komplem sve proste brojeve
u opsegu od 1 do maksimalnog broja datoteke f koji se ne nalaze u skupu
skupcin.