/*
    71c__vezane_liste.c 
    -----
    Program ucitava imena i stavlja ih u vezanu listu tako da imena u listi
    uvijek budu sortirana.
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
 
typedef struct __node {
    char *ime;
    struct __node *next;
} node;
 
int main ( void )
{
    node *glava, *pomocni, *prethodnik, *trenutni;
    char temp[100];
 
    /* inicijalizacija liste */
    glava=NULL;
 
    /* ucitavamo imena sve dok se ne ucita 0 */
    while (1)
    {
        printf ("Unesi ime (0 za kraj): ");
        scanf ("%s", temp);
 
        if (!strcmp(temp, "0")) break;
 
        pomocni=(node *) malloc(sizeof(node));
        pomocni->ime=(char *) malloc(sizeof(char)*(strlen(temp)+1));
        strcpy (pomocni->ime, temp);
 
        /* sad treba pronaci mjesto u listi gdje treba staviti ucitano ime */
        trenutni=glava; prethodnik=NULL;
        while (trenutni!=NULL && strcmp(trenutni->ime, pomocni->ime) < 0)
        {
            /* uocimo da nas tzv. lijeno izvrednjavanje uvjeta u while petlji
               "spasava" od mogucnosti dereferenciranja NULL pointer-a */
            prethodnik=trenutni; trenutni=trenutni->next;
        }
 
        if (prethodnik==NULL)
        {
            /* treba dodati na pocetak liste (koja je mozda i prazna) */
            pomocni->next=glava; glava=pomocni;
        }
        else
        {
            /* treba ubaciti iza prethodnik-a, a ispred trenutni (koji je 
               mozda NULL */
            pomocni->next=trenutni;
            prethodnik->next=pomocni;
        }
    }
 
    /* ispisujemo listu cvor po cvor */
    printf ("Sortirana lista: ");
    for (pomocni=glava; pomocni!=NULL; pomocni=pomocni->next)
        printf ("%s ", pomocni->ime);
 
    /* oslobadjanje memorije */
    while (glava!=NULL)
    {
        pomocni=glava; glava=glava->next;
        free (pomocni->ime); free (pomocni);
    }
 
    return 0;   
}