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.   


/*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 */

}