[LV3] Algoritmi - Rekurzije i stog

#define _CRT_SECURE_NO_WARNINGS

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


#define N 100;

typedef struct stog {
    int Sp = -1;
    int V[1000];
}Stog;

typedef struct stog_PP {
    int x;
    struct stog_PP *sljedeci;
}Stog_PP;

Stog_PP *zadnji = NULL;

int povrh_Rek(int, int);
int povrh_Stog(Stog*, Stog*, int, int);
int povrh_Stog_PP(int, int);
//Stog - niz
int IsEmpty(Stog*);
int IsFull(Stog*);
int Pop(Stog*);
void Push(Stog*, int);
void Clear(Stog*);
//Stog - povezani popis
int IsEmpty_PP();
void Push_PP(int);
int Pop_PP();
void Clear_PP();

int main() {
    int n, m, rez;
    time_t t;
    Stog *s1 = (Stog *)malloc(sizeof(Stog)), *s2 = (Stog *)malloc(sizeof(Stog));
    printf("Unesite broj n:\n");
    scanf("%d", &n);
    m = n / 2;
    t = clock();
    rez = povrh_Rek(n, m);
    t = clock() - t;
    printf("Povrh rekurzijom: REZ: %d | VRIJEME: %dms\n", rez, t);
    t = clock();
    rez = povrh_Stog(s1, s2, n, m);
    t = clock() - t;
    printf("Povrh stogom - niz: REZ: %d | VRIJEME: %dms\n", rez, t);
    t = clock();
    rez = povrh_Stog_PP(n, m);
    t = clock() - t;
    printf("Povrh stogom - povezani popis: REZ: %d | VRIJEME: %dms\n", rez, t);
}

/*===== POVRH (rekurzivna) =====*/
int povrh_Rek(int n, int m)
{
    if (m == n || n == 1 || m == 0) return 1;
    return povrh_Rek(n - 1, m - 1) + povrh_Rek(n - 1, m);
}

/*===== POVRH (stog - niz) =====*/
int povrh_Stog(Stog *s1, Stog *s2, int a, int b)
{
    int n, m;
    Clear(s1);
    Clear(s2);
    Push(s1, a);
    Push(s2, b);
    int povrh = 0;

    do {
        n = Pop(s1);
        m = Pop(s2);
        if (m == n || n == 1 || m == 0) povrh++;
        else {
            Push(s1, n - 1);
            Push(s2, m - 1);
            Push(s1, n - 1);
            Push(s2, m);
        }
    } while (IsEmpty(s1) == 0);
    return povrh;
}
/*===== POVRH (stog - povezani popis) =====*/
int povrh_Stog_PP(int a, int b)
{
    int n, m;
    Clear_PP;
    Push_PP(a);
    Push_PP(b);
    int povrh = 0;
    do {
        m = Pop_PP();
        n = Pop_PP();
        if (m == n || n == 1 || m == 0) povrh = povrh + 1;
        else {
            Push_PP(n - 1);
            Push_PP(m - 1);
            Push_PP(n - 1);
            Push_PP(m);
        }
    } while (IsEmpty_PP() == 0);
    return povrh;
}

/*===== STOG (niz) =====*/
int IsEmpty(Stog *s) {
    if (s->Sp == -1) return 1;
    else return 0;
}

int IsFull(Stog *s) {
    if (s->Sp == 999) return 1;
    else return 0;
}

int Pop(Stog *s) {
    if (IsEmpty(s)) {
        printf("PREKID!\n");
        return -1;
    }
    s->Sp--;
    return s->V[s->Sp + 1];

}

void Push(Stog *s, int x) {
    if (IsFull(s)) {
        printf("PREKID!\n");
        return;
    }
    s->Sp++;
    s->V[s->Sp] = x;
}

void Clear(Stog *s) {
    s->Sp = -1;
}

/*===== STOG (povezani popis) =====*/
int IsEmpty_PP() {
    if (zadnji == NULL) return 1;
    else return 0;
}

int Pop_PP() {
    int x;
    if (IsEmpty_PP()) {
        printf("PREKID!\n");
        return -1;
    }
    x = zadnji->x;
    Stog_PP *temp = (Stog_PP *)malloc(sizeof(Stog_PP));
    temp = zadnji;
    zadnji = zadnji->sljedeci;
    free(temp);
    return x;

}

void Push_PP(int x) {
    Stog_PP *novi = (Stog_PP *)malloc(sizeof(Stog_PP));
    novi->x = x;
    novi->sljedeci = zadnji;
    zadnji = novi;
}

void Clear_PP() {
    while (IsEmpty_PP == 0) {
        Pop_PP();
    }
}