Februar 2007 – resenja zadataka



B1.

#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, min; /*najveci i najmanji br.pojava etikete*/

char szMin_Etik[MAX]; /*najredja 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;  

   }

min=max;

    fclose(dat);

   

 

 printf("\nNajredje etiketa je: %s sa brojem pojava %d\n", szMin_Etik, min);

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

       if (min > k->broj) {min=k->broj; strcpy(szMin_Etik,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);  

}

A2.

unsigned long int BitMin(unsigned long int n)

{

unsigned long pom=0;

int br1=0;

int wl=8*sizeof(unsigned long);

unsigned long int maska;

for(maska=1<<(wl-1); maska; maska=maska>>1)

if (n&maska) br1++;

x=~(~x<<br1);

return x;

}



A3.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define znak(cifra)  ((cifra) +'0')
#define  cifra(x)     ((x)-'0')

void itoa(int n, char s[]); //NIJE implementirana, za potpun rad programa
//dodati kod iz K&R
void saberi(char *a1, int n, char *a2, int m, char *s, int *ns);   /*a1+a2->s */ 
/*Kako u ovom zadatku koristimo nisku cifara , u potprogramima nisu bili nuzni
n,m, ali ih prenosimo da bi kod bio jasniji i da bi se mogao primeniti i ako
se radi sa npr. (int *) , umesto (char *) */
char* reverse( char s[] ) ;
main(int argc, char *argv[])
{
  unsigned long f[43];
  char * ostatak [57];
  int i,n,m;
  
   f[0]=f[1]=1;
   for(i=2; i<43; i++) f[i]=f[i-1]+f[i-2];
   for(i=0;i<43; i++) printf(“%ld”, f[i]);

   itoa(f[41], ostatak[0]);  //videti k&r za implementaciju
   itoa(f[42], ostatak[1]);   

    for(i=2; i<57; i++) {
       n=strlen(ostatak[i-2]); m=strlen(ostatak[i-1]);
      nzbir= (n>m ? n : m) +1;

     ostatak[i]=(char *)malloc(nzbir*sizeof(char) );
saberi( reverse(ostatak[i-2]) ,n, reverse(ostatak[i-1]),m,ostatak[i],&nzbir);
printf("\n%s+%s=  %s\n\n", reverse(ostatak[i-2]),ostatak(i-1), reverse(ostatak[i]));
     
    }         
   

   

for(i=2; i< 57; i++)
free(ostatak[i]);
return 0; 
}
void saberi(char *a1, int n, char *a2, int m, char *s, int *ns)
{
   int prenos;  /*prenos u susedni razred cifara, a koji je nastao
                        pri sabiranju cifri oba broja tekuceg razreda */
   int c;      /*rezultat sabiranja tekuce cifre prvog broja i tekuce cifre drugog broja*/
   int i;      /*brojac u petlji */
   prenos=0;
    /*sabiranje velikih brojeva se odvija implementacijom algoritma naucenom u mladjim razredima osnovne skole */
    /*Sabiraju se cifre oba broja iz tekuceg razreda,  pocev od razreda jedinica ,ka razredima vece tezine. */
    /*Vodi se racuna o eventualnom nastalom prenosu u sledeci razred cifara, /*
    /*kao i da ako je neki od brojeva "kraci",  postavljaju mu se zamisljene nule  kao cifre tekuceg razreda .*/ 
    /*Te zamisljene  nule su vodece nule,  i zato ne uticu na izmenu vrednosti broja */
   
for(i=0; i<*ns; ++i) {
      c= (i<n ? cifra(a1[i]) : 0) + (i<m ? cifra(a2[i]) : 0) + prenos;
      s[i]= znak(c % 10) ;               /*formira se cifra rezultata ,kao vrednost arapske cifre u masinskom setu znakova */
      prenos= c < 10 ? 0 : 1;                  /* prenos=c/10; */
   }    //kraj for petlje
   
    if(prenos > 0) {       
      s[*ns]=znak(prenos);
      *ns=*ns+1;
   }
   s[*ns]='\0';  /*zbog rada sa niskom cifara */
}     //kraj potprograma
char* reverse( char s[] ) 
{ 
  int indeks,br; /* brojacke promenljive */ 
  char  Temp;/* posrednik u razmeni dva karaktera sa iz leve i desne polovine stringa */ 
   br=strlen(s)-1;
     for( indeks=0; indeks< br; indeks++, br-- ) 
 {   Temp=s[indeks];   s[indeks]=s[br];   s[br]=Temp;  } 
 return s; 
} 



B4.

#include <stdio.h>

#include <string.h>


int zameni(char *p, char *q)

{

int n=0, pom;

int l=strlen(p);

char *pok;

while ( (pok=strstr(q,p)) != NULL)

{

pom=pok-q;

strcpy(q+pom, pok+l);

n++;

}


pom=n;

while (pom--) strcat(q,p);


return n;

}


main()

{

char p[]="abra";

char q[]="abrakadabra";

int n;

n=zameni(p,q);

printf("\n n= %d q=%s\n", n,q);


}