//Implementacija pomoću polja
 
    #define GRESKA -1
 
    struct tzivotinja {
    int sifra;
    char vrsta[50], naziv[75];
    float cijena;
    short d, m, g; //datum
    };
 
    struct tLista {
    tzivotinja el[1000];
 
    int k;
    };
 
    typedef int Element;
 
    typedef tLista Lista;
    typedef tzivotinja Zivotinja;
 
 
    bool operator==(Zivotinja z1, Zivotinja z2) {
    if(z1.sifra != z2.sifra)	return false;
    else if(z1.cijena != z2.cijena)	return false;
    else if(z1.sifra != z2.sifra) return false;
    else if(z1.sifra != z2.sifra) return false;
    else if(z1.d!=z2.d || z1.m!=z2.m || z1.g!=z2.g)	return false;
    return true;
    }
 
    Element FirstL(Lista* L) {
    return 0;
    }
    Element EndL(Lista* L) {
    return L->k;
    }
 
    Element NextL(Element p, Lista* L) {
    if(p==EndL(L))
    return GRESKA;
    return p+1;
    }
    Element PreviousL(Element p, Lista* L) {
    if(p==FirstL(L))
    return GRESKA;
    return p-1;
    }
 
    Element LocateL(Zivotinja x, Lista* L) {
    for(int i=0; i<L->k; i++)
    if(L->el[i] == x)
    return i;
    return EndL(L);
    }
    bool InsertL(Zivotinja x, Element p, Lista* L) {
    if(p<0 || p>L->k) return 0;
    int i=L->k;
    L->k++;
    while(i>p) { L->el[i] = L->el[i-1]; i--; }
    L->el[p] = x;
    return 1;
    }
 
    bool DeleteL(Element p, Lista* L) {
    if(p<0 || p>L->k) return 0;
    int i=p+1;
    while(i<L->k) { L->el[i-1] = L->el[i]; i++; }
    L->k--;
    return 1;
    }
    Zivotinja RetrieveL(Element p, Lista* L) {
    return L->el[p];
    }
 
    void DeleteAllL(Lista* L) {
    L->k = 0;
    }
    void InitL(Lista* L) {
    L->k = 0;
    }
 
 
 
    //Implementacija pomoću pokazivaca
 
    struct tzivotinja {
    int sifra;
    char vrsta[50], naziv[75];
    float cijena;
    short d, m, g; //datum
    };
 
    struct tElement {
    tzivotinja z;
 
    tElement* sljedeci;
    };
 
    typedef tElement* Element;
 
    typedef tElement Lista;
    typedef tzivotinja Zivotinja;
 
 
    bool operator==(Zivotinja z1, Zivotinja z2) {
    if(z1.sifra != z2.sifra)	return false;
    else if(z1.cijena != z2.cijena)	return false;
    else if(z1.sifra != z2.sifra) return false;
    else if(z1.sifra != z2.sifra) return false;
    else if(z1.d!=z2.d || z1.m!=z2.m || z1.g!=z2.g)	return false;
    return true;
    }
 
    Element FirstL(Lista* L) {
    return L;
    }
 
    Element EndL(Lista* L) {
    Element tren = L;
    while(tren->sljedeci)
    tren=tren->sljedeci;
 
    return tren;
    }
 
    Element NextL(Element p, Lista* L) {
    if(p->sljedeci)
    return p->sljedeci;
    return GRESKA;
    }
 
    Element PreviousL(Element p, Lista* L) {
    if(p==FirstL(L) )
    return GRESKA;
 
    Element tren = FirstL(L);
    while(tren->sljedeci!=p)
    tren=tren->sljedeci;
 
    return tren;
    }
 
    Element LocateL(Zivotinja x, Lista* L) {
    Element tren=L;
    while(tren->sljedeci) {
    if(tren->sljedeci->z == x)
    return tren;
    tren=tren->sljedeci;
    }
    return EndL(L);
    }
 
    bool InsertL(Zivotinja x, Element p, Lista* L) {
    if(p==NULL) return 0;
    Element novi = new tElement;
    memcpy(novi, &x, sizeof(Zivotinja) );
    novi->sljedeci = p->sljedeci;
    p->sljedeci = novi;
    return 1;
    }
 
    bool DeleteL(Element p, Lista* L) {
    if(p==NULL) return 0;
    Element tren = p->sljedeci;
    p->sljedeci = tren->sljedeci;
    delete tren;
    return 1;
    }
    Zivotinja RetrieveL(Element p, Lista* L) {
    return p->sljedeci->z;
    }
 
    void DeleteAllL(Lista* L) {
    if(!L->sljedeci) return;
    Element prev = L->sljedeci;
    for(Element tren=prev->sljedeci; tren!=NULL; tren=(prev=tren)->sljedeci)
    delete prev;
    delete prev;
    L->sljedeci = NULL;
    }
    void InitL(Lista* L) {
    L->sljedeci = NULL;
    }
 
    //Glavni program
    #include <iostream>
    #include <cstring>
 
    #include "lista_polje.h"
    //#include "lista_pokazivaci.h"
 
    using namespace std;
 
 
 
    bool Dodaj(Lista* L) {
    static int sifra = 123;
 
    Zivotinja* z = new Zivotinja;
 
    cout << "Nova zivotinja" << endl;
    cout << "Sifra = " << sifra << endl << endl;
    z->sifra = sifra++;
 
    cin.ignore();
    cout << "Naziv: ";
    cin.getline(z->naziv, 75);
 
    cout << "Vrsta: ";
    cin.getline(z->vrsta, 50);
 
    cout << "Cijena: ";
    cin >> z->cijena;
 
    cout << endl << "Datum" << endl;
    cout << "Dan: ";
    cin >> z->d;
 
    cout << "Mjesec: ";
    cin >> z->m;
 
    cout << "Godina: ";
    cin >> z->g;
 
    return InsertL(*z, EndL(L), L);
    }
 
 
 
    void Ispis1(Lista* L) {
    cout << "Ispis liste od zadnjeg elementa" << endl;
 
    Zivotinja z;
    Element tren = EndL(L);
 
    tren = PreviousL(tren, L);
 
    while(tren!=GRESKA) {
 
    z = RetrieveL(tren, L);
 
    cout << "Sifra: " << z.sifra << endl;
    cout << "Naziv: " << z.naziv << endl;
    cout << "Vrsta: " << z.vrsta << endl;
    cout << "Cijena: " << z.cijena << endl;
    cout << "Datum: " << z.d << "." << z.m << "." << z.g << "." << endl;
 
    cout << endl;
 
    tren = PreviousL(tren, L);
    }
    }
    void Ispis2(Lista* L) {
    Zivotinja z;
 
    int b = 0;
 
    Element tren = FirstL(L);
 
    while(tren != EndL(L)) {
 
    z = RetrieveL(tren, L);
    int datum = z.d + z.m * 100 + z.g * 10000;
 
 
    if(datum>20120923) {
 
    cout << "Sifra: " << z.sifra << endl;
    cout << "Naziv: " << z.naziv << endl;
    cout << "Vrsta: " << z.vrsta << endl;
    cout << "Cijena: " << z.cijena << endl;
    cout << "Datum: " << z.d << "." << z.m << "." << z.g << "." << endl;
 
    cout << endl;
 
    b++;
    }
 
    tren = NextL(tren, L);
    }
 
    cout << "Ukupan broj ispisanih zivotinja: " << b << endl;
    }
 
 
 
    int Brisanje1(Lista* L) {
    char naziv[75];
 
    cin.ignore();
 
    cout << "Naziv: ";
    cin.getline(naziv, 75);
 
    Zivotinja z;
 
    for(Element tren=FirstL(L); tren!=EndL(L); tren=NextL(tren, L)) {
    z = RetrieveL(tren, L);
 
    if(strlen(naziv) == strlen(z.naziv)) {
    int n =strlen(naziv);
 
    int ne=0;
 
    for(int i=0; i<n; i++) {
    if(naziv[i] != z.naziv[i])
    ne=1;
 
    }
 
    if(ne==0) {	
    int ok = DeleteL(LocateL(z, L), L);
 
    if(ok==-1)
    return 0;
 
    else
    return 1;
    }
    }
    }
    return 0;
    }
    int Brisanje2(Lista* L) {
    char vrsta[50];
 
    cin.ignore();
 
    cout << "Vrsta: ";
    cin.getline(vrsta, 50);
 
    int b = 0;
    Zivotinja z;
    Element tren=FirstL(L);
 
    while(tren!=EndL(L)) {
    z = RetrieveL(tren, L);
 
    if(strlen(vrsta) == strlen(z.vrsta)) {
    int n=strlen(vrsta), ne=0;
 
    for(int i=0; i<n; i++) {
    if(vrsta[i] != z.vrsta[i])
    ne=1;
    }
 
    if(ne==0) {
    if(DeleteL(LocateL(z, L), L)==1) {
    b++;
 
    continue;
    }
    }
    }
    tren = NextL(tren, L);
    }
 
    cout << "Broj izbrisanih zivotinja: " << b << endl;
    if(b>0)
    return 1;
    else
    return 0;
    }
 
 
 
    bool z1z2(Zivotinja z1, Zivotinja z2) {
    if(z1.cijena<z2.cijena) return true;
 
    if(z1.cijena==z2.cijena) {
    int manji = (strlen(z1.naziv)<strlen(z2.naziv)) ? strlen(z1.naziv) : strlen(z2.naziv);
 
    for(int i=0; i<manji; i++) {
    if(z1.naziv[i]>z2.naziv[i])
    return false;
 
    else if(z1.naziv[i]<z2.naziv[i])
    return true;
    }
    }
 
    return false;
    }
 
 
 
    void Spoji(Zivotinja p[], int i, int sred, int j) {
    int a=i, b=sred+1, c=0;
    Zivotinja* p2 = new Zivotinja[j-i+1];
 
    while(a<=sred && b<=j)
    if(z1z2(p[a], p[b]))
    p2[c++]=p[a++];
    else p2[c++]=p[b++];
 
    if(a>sred)
    while(b<=j)
    p2[c++]=p[b++];
    else while(a<=sred)
    p2[c++]=p[a++];
 
 
    for(int m=i; m<=j; m++)
    p[m] = p2[m-i];
 
 
    delete[] p2;
    }
    void Sort(Zivotinja zivotinje[], int i, int j) {
    if(i<j) {
    int sred = (i+j) / 2;
 
    Sort(zivotinje, i, sred);
    Sort(zivotinje, sred+1, j);
    Spoji(zivotinje, i, sred, j);
    }
    }
 
 
    void SortiranjeListeZivotinja(Lista* L) {
    int b=0;
    for(Element tren=FirstL(L); tren!=EndL(L); tren=NextL(tren, L)) {
    b++;
    }
    Zivotinja* z = new Zivotinja[b];
    Element nova = FirstL(L);
 
    int i = 0;
    while(nova != EndL(L)) {
 
    z[i] = RetrieveL(nova, L);
    i++;
 
    nova=NextL(nova, L);
    }
 
    DeleteAllL(L);
 
    Sort(z, 0, b-1);
 
    for(int i=0; i<b; i++) {
 
    InsertL(z[i], FirstL(L), L);
    }
 
    delete[] z;
    }
 
    int main() {
    Lista* L = new Lista;
    InitL(L);
    short izbor;
 
    do {
 
    cout << endl << " Izbornik " << endl;
    cout << " 1. Dodavanje zivotinju" << endl;
    cout << " 2. Ispis" << endl;
    cout << " 3. Brisanje" << endl;
    cout << " 4. Sortiranje" << endl;
    cout << " 0. Izlaz" << endl;
    cout << "Vas izbor: ";
    cin >> izbor;
 
    switch(izbor) {
    case 1: {
    int ok = Dodaj(L);
    if(ok==1) {
    cout << endl << "Unos je dodan u listu." << endl;
    }
    break;
    }
 
 
    case 2: {
    int iz;
 
    do {
    cout << "1. Ispis liste" << endl;
    cout << "2. Ispis zivotinja dostavljenih poslije 23.9.2012." << endl;
    cout << "Vas izbor: ";
    cin >> iz;
 
    switch(iz) {
    case 1: Ispis1(L);
    case 2: Ispis2(L);
    default: cout << "Pogresan unos." << endl;
    }
    }while(iz!=1 && iz!=2);
 
    break;
    }
 
 
 
    case 3: {
    int iz;
 
    do {
    cout << " 1. Brisanje zivotinje (naziv)" << endl;
    cout << " 2. Brisanje zivotinja (vrsta)" << endl;
    cout << "Vas izbor: ";
    cin >> iz;
 
    switch(iz) {
    case 1: {
    int ok = Brisanje1(L);
 
    if(ok==1) {
    cout << "Brisanje je uspjesno obavljeno." << endl;
    }
 
    break;
    }
 
    case 2: {
    int ok = Brisanje2(L);
 
    if(ok) {
    cout << "Brisanje je uspjesno obavljeno." << endl;
    }
 
    break;
    }
    default: cout << "Pogresan unos." << endl;
    }
    }while(iz!=1 && iz!=2);
 
    break;
    }
 
 
    case 4:
    SortiranjeListeZivotinja(L);
    break;
 
    case 0:
    break;
 
 
    default:
    cout << "Pogresan unos." << endl;
    }
 
    } while(izbor!=0);
 
    return 0;
    }