OSNOVI PROGRAMIRANJA II kolokvijum, 2003. III tok

1. Napisati C program koji će 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)štampati sadržaj drveta u infiksnom poretku, ako je kao parametar komandne linije zadata opcija -p

Obezbediti da program radi i kada su prisutna oba opciona argumenta.

Pretpostaviti da naziv etikete nije duži od 30 karaktera.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#define MAX 31

#define TRUE 1

#define FALSE 0

typedef struct BSP_cvor

{

char *etiketa; /*naziv etikete */

struct BSP_cvor *levi; /* levi ogranak */

struct BSP_cvor *desni; /* desni ogranak */

} drvo;

/*FUNKCIJE */

/* ucitava etiketu (do max karaktera) iz datoteke u nisku s*/

int uzmi_etiketu(FILE * f, char * s, int max);

/* ubacuje rec u drvo */

drvo *ubaci(drvo *, char *);

/* alokacija cvora BSP */

drvo *alociraj( void );

/* kreira kopiju niske s */

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 *);

/* vraca broj cvorova stabla */

int brcvor(drvo *);

/* oslobadja zauzeti prostor za drvo */

void osloboditi( drvo *);

main(int argc, char *argv[])

{

drvo *koren; /*koren stabla pretrazivanja */

char etiketa[MAX]; /*naziv etikete sa ulaza */

FILE *dat;

int i,j; /* brojacke promenljive */

int infiksni=FALSE, prebroj=FALSE; /*indikatori postojanja opcija u komandnoj liniji */

dat=fopen("ulaz.htm","r");

if (dat==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 dve opcije*/

for (j=1; argv[i][j] !='\0'; j++)

{ /* proverava se postojanje opcionih argumenata -n, -p */

switch (argv[i][j])

{ case 'n': prebroj = TRUE; break;

case 'p': infiksni=TRUE; break;

default:

fprintf(stderr, "Nekorektna opcija %s u pozivu\n",argv[i]);

return 1;

}

}

/*formiranje stabla od ucitanih razlicitih etiketa */

koren = NULL;

while( 1 )

{ int kraj = uzmi_etiketu(dat,etiketa, MAX);

/*dodavanje cvora u stablo cvora, ako tag ne postoji u stablu */

if ( strlen(etiketa)) koren = ubaci( koren, etiketa);

if(kraj == EOF) break;

}

fclose(dat);

if (infiksni) infiks(koren);

if (prebroj) printf("\nBroj cvorova je: %d\n", brcvor(koren));

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

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[], int lim)

{ char c;

int i = 0;

if ( (c = fgetc(f)) == '<')

while (isalnum(c = fgetc(f)) && (i<lim) ) 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;i<strlen(e1);i++) pom1[i]=tolower(e1[i]);

pom1[i]='\0';

for(i=0;i<strlen(e2);i++) pom2[i]=tolower(e2[i]);

pom2[i]='\0';

return strcmp (pom1, pom2);

}

int brcvor(drvo *k)

{ if (k == NULL) return 0;

else return 1+brcvor(k->levi)+brcvor(k->desni);

}

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. Pod pretpostavkom da u datoteci ulaz.txt broj redova nije veći od 100 i da svaki red ima ne više od 80 karaktera, prepisati sadržaj datoteke ulaz.txt u datoteku izlaz.txt tako da bude sortiran u neopadajućem poretku po prvim rečima iz svake linije. Sortiranje izvršiti korišćenjem funkcije qsort iz standardne biblioteke.

OSNOVI PROGRAMIRANJA II kolokvijum, 2003. IV tok

1. Napisati

a) funkciju koja kreira jednostruku povezanu listu od karaktere niske koja se zadaje kao argument funkcije

b) funkciju koja kao argument prima početak jednostruke povezane liste i ispisuje sadržaj koji se dobija

obilaskom listom u smeru od kraja ka početku. U potprogramu proći najviše jednom kroz datu povezanu listu.

c) program koji testira rad funkcija pod a) b) za nisku koja se zadaje iz komandne linije

2. Napisati C program koji od dve datoteke u kojima su linije sortirane prema rastućem poretku kolacione sekvencije formira treću koja sadrži linije koje postoje u tačno jednoj od dve ulazne datoteke, tako da ona bude takođe sortirana.

Imena sve tri datoteke sa zadaju kao argumenti komandne linije.