/* Stampanje svih razlicitih reci sa ulaza sa brojem njihovog pojavljivanja*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
/* duzina reci*/
#define DUZINA 30


typedef struct slog_tag
{
   char *rec;
   short broj;
   struct slog_tag *sled;
} slog;

int uzmi_rec(char *, int);
void stavi_rec(char *);

/* Pokazivac na prvi elemenat liste (slog)- spoljasnja promenljiva*/
slog *prva;

main()
{
   char rec[DUZINA];
   slog *x, *t;
   /*Alocira se prostor za prvu rec u listi */
   prva = (slog *)malloc(sizeof(slog));
   /*Pretpostavimo da je bar jedna rec na ulazu */
   uzmi_rec(rec, DUZINA);
   /*Alociranje prostora za rec */
   prva->rec = (char *)malloc(strlen(rec)+1);
   /* Kopiranje sadrzaja u strukturu*/
   strcpy( prva->rec, rec);
   /*Broj pojavljivanja reci se postavlja na 1 */
   prva->broj = 1;
   prva->sled = NULL;

   /* Ucitavanje reci se obavlja u "mrtvoj petlji" sve dok se ne pojavi EOF*/
   while( 1 )
   {
      /* Uzima se sledeca rec */
      int kraj = uzmi_rec(rec, DUZINA);
      /* Rec se stavlja u listu ukoliko nije prazna rec */
      if (strlen(rec))
         stavi_rec(rec);
      /* Ukoliko je rec prazna - iskace se iz "mrtve" petlje */
      if(kraj == EOF) break;
   }
   /* Stampa se lista i oslobadja memorija */
   x = prva;
   while( x != NULL )
   {
      printf("REC \t\t\"%s\" \t\t SE POJAVLJUJE %d PUTA\n", x->rec, x->broj);
      t = x;
      x = x->sled;
      free(t);
   }
return 0;
}

int uzmi_rec(char *s, int lim)
{
   char c, i = 0;
   /* Preskacu se svi znaci do slova ili cifre */
   while( !isalnum(c = s[0] = getchar()) && c!=EOF);

   /* Ukoliko je procitani znak EOF */
   if( c==EOF )
   {
      /* Vraca se prazna rec */
      s[0] = '\0';
      return EOF;
   }

   /* Ucitaj ostatak reci: (u s[0] se vec nalazi prvo slovo)*/
   while( (c = getchar()) != EOF && isalnum(c) && i < lim)
      s[++i] = c;

     /* Zavrsetak niske \0 */
     s[++i] =  '\0';

     /* Ako se stiglo do kraja vraca se EOF */
     if( c==EOF ) return EOF;

     /* Inace se vraca duzina reci */
     return i;
}

/* Funkcija ubacuje rec u sortiranu listu reci ili povecava za jedan
   broj pojavljivanja te reci ukoliko se ona vec nalazi u listi*/
void stavi_rec(char *s)
{
   slog *p = prva;
   /* Napredujemo sve dok su reci liste leksikografski "manje" od nove reci*/
   while(p != NULL && (strcmp(p->rec, s) < 0) )
      p = p->sled;

   /*Ukoliko je nova rec veca od prethodne a manja od sledece tu je treba
     umetnuti */
   if( p == NULL || (strcmp(p->rec, s) > 0) )
   {
      slog *q, *nova = (slog *)malloc(sizeof(slog));
      /* Inicijalizacija novog sloga */
      nova->rec = (char *)malloc(strlen(s) + 1);
      strcpy(nova->rec, s);
      nova->broj = 1;

      /* Povezivanje novog sloga sa ostatkom liste */
      /* q pokazuje na pocetak liste */
      q = prva;

      /* Novi slog treba ubaciti na pocetak liste - specijalan slucaj */
      if(q == p)
      {
         nova->sled = prva;
	 prva = nova;
      }
      /*Inace  upisujemo novu ispred p ili na kraj liste - kod je isti:*/
      else
      {  /* Pomeramo q da pokazuje neposredno ispred p*/

         while(q->sled != p)
            q = q->sled;
         /*Ubacujemo novu da bude izmedju q i p */
	 q->sled = nova;
	 nova->sled = p;
         /* Umetanje radi i kada je p == NULL */
      }
   }
   /* Inace (strcmp(p->rec, s) == 0) tj. rec vec postoji u listi */
   else
     /* Broj pojavljivanja reci se uvecava za 1 */
     (p->broj)++;
}