/*

Unos brojeva u nerastuce sortiranu listu.

*/


#include <stdio.h>
#include <stdlib.h>


struct cvor {
                int podatak;                // sadrzaj cvora
                struct cvor *sledeci;       // i pointer na sledeceg clana
            };
typedef struct cvor CVOR;                   // jedan cvor liste CVOR
typedef CVOR* PCVOR;                        // pointer na listu CVOR


// Prikazuje sadrzaj cvorova liste glava
void prikazi_listu(char *tekst, PCVOR glava)
{
    printf("\n%s",tekst);

    if(glava == NULL)
        printf(" prazna. \n");
    else
        while(glava) {
            printf("%4d",glava->podatak);
            glava = glava->sledeci;
        }
    printf("\n");
}


void dodaj_broj_na_kraj(PCVOR *glava,int broj) {
    PCVOR novi;
    PCVOR tek;

    // Moramo da pazimo da li je lista prazna ili ne.
    // Ako je glava = NULL onda je isto kao da ubacujemo na pocetak.
    novi = (PCVOR)malloc(sizeof(CVOR));
    novi -> podatak = broj;
    novi -> sledeci = NULL;

    if(*glava == NULL)  // onda je element jedini i prvi
        *glava = novi;
    else  {              // ako element nije prvi
        tek=*glava;
        while(tek->sledeci != NULL)
            tek=tek->sledeci;
        tek->sledeci=novi;
    }
}


// formira listu
void formiraj_nerastucu_listu(PCVOR *glava)
{
    dodaj_broj_na_kraj(glava,14);
    dodaj_broj_na_kraj(glava,12);
    dodaj_broj_na_kraj(glava,10);
    dodaj_broj_na_kraj(glava,8);
    dodaj_broj_na_kraj(glava,6);
    dodaj_broj_na_kraj(glava,4);
    dodaj_broj_na_kraj(glava,2);

}


void napravi_novi_cvor(PCVOR *novi,int broj)
{
    *novi=(PCVOR)malloc(sizeof(CVOR));

    if(*novi == NULL){
        printf("\n Nije uspela rezervacija memorije za novi cvor. \n");
        exit(1);
    }

    (*novi)->podatak = broj;
    (*novi)->sledeci = NULL;
}


void dodaj_cvor_na_pocetak(PCVOR *glava,PCVOR novi)
{
    if(*glava != NULL)
        novi->sledeci=*glava;

    *glava=novi;
}


// Brise celu listu glava.
// Brisemo cvor po cvor tako sto ustvari stalno brisemo prvi cvor.
void obrisi_celu_listu(PCVOR *glava)
{
   PCVOR tek = *glava;
   while ( tek ){
      tek = tek->sledeci;
      free (*glava);
      *glava = tek;
   }
}


void dodaj_broj_u_nerastuce_sortiranu_listu(PCVOR *glava, int broj)
{
    PCVOR prethodni, tek, novi;

    //napravi_novi_cvor(&novi,broj);    // formiramo novi cvor sa podatkom broj
    novi = (PCVOR)malloc(sizeof(CVOR));
    novi->podatak = broj;
    novi->sledeci = NULL;

    tek = *glava;                       // tek postaje prvi cvor glava

    if(broj >= tek->podatak){           // onda cvor novi dodajemo na pocetak liste
        //dodaj_cvor_na_pocetak(glava,novi);
        if(*glava != NULL)
            novi->sledeci=*glava;
        *glava=novi;
    }else{
        // dok ne nadjemo mesto dodavanja ili do kraja liste, prelazimo na sledeci cvor
        while ( broj <= tek->podatak  &&  tek->sledeci!=NULL ){
            prethodni = tek;            // sadasnji tekuci postaje prethodni
            tek = tek->sledeci;         // prelazimo na sledeci cvor
        }
                                        // na mesto cvora tek dodajemo cvor novi
        if(tek->sledeci==NULL){         // ako smo na poslednjem cvoru
            //dodaj_cvor_na_kraj(glava,novi);
            tek->sledeci = novi;
            novi->sledeci = NULL;
        }else{                          // ako nismo na poslednjem cvoru
            prethodni->sledeci = novi;
            novi->sledeci = tek;
        }
    }
}


int main(void)
{
    PCVOR glava = NULL;     // deklarisemo listu (OBAVEZNO =NULL)

    formiraj_nerastucu_listu(&glava);
    prikazi_listu(" Lista: ",glava);

    dodaj_broj_u_nerastuce_sortiranu_listu(&glava,7);
    dodaj_broj_u_nerastuce_sortiranu_listu(&glava,15);
    dodaj_broj_u_nerastuce_sortiranu_listu(&glava,1);
    dodaj_broj_u_nerastuce_sortiranu_listu(&glava,17);
    dodaj_broj_u_nerastuce_sortiranu_listu(&glava,3);
    prikazi_listu(" Lista: ",glava);

    obrisi_celu_listu(&glava);
    prikazi_listu(" Lista: ",glava);

    return 0;
}