complessità funzioni del fun.h del progetto dev c++

#include "fun.h"
/*DANIELE PUOI FARE IL COMPLESSO */
void check_exit(struct strada rotatoria[N_P],int* time, int* log){ //Funzione di uscita delle macchine
   int i;
   if (*log!=0){
        FILE *fp=fopen("log_uscite.txt", "a");
        for(i=1;i<6;i++) // Controlliamo i N_S posti che intersecano le strade con la rotatoria
            if(rotatoria[(i*3-1)].car!=NULL && rotatoria[(i*3-1)].car->destinazione==(i-1)){//Le strade si intersecano nella rotatoria nei punti 2-N_S-8-11-N_P la destinazione ? espressa da un numero N 0<=N<=4
                fprintf(fp,"Tempo %d - L'auto %d uscira' all'uscita %d \n",*time,rotatoria[(i*3-1)].car->targa,rotatoria[(i*3-1)].car->destinazione);
                free(&(rotatoria[(i*3-1)].car)); // Liberiamo l'indrizzo della macchina
                rotatoria[i*3-1].car=NULL; // Segnaliamo che quel posto della rotatoria, ? ora vuoto
        }
        fclose(fp);
    }
    else{
        for(i=1;i<6;i++) // Controlliamo i N_S posti che intersecano le strade con la rotatoria
            if(rotatoria[(i*3-1)].car!=NULL && rotatoria[(i*3-1)].car->destinazione==(i-1)){//Le strade si intersecano nella rotatoria nei punti 2-N_S-8-11-N_P la destinazione ? espressa da un numero N 0<=N<=4
                printf("Tempo %d - L'auto %d uscira' all'uscita %d \n",*time,rotatoria[(i*3-1)].car->targa,rotatoria[(i*3-1)].car->destinazione);
                free(&(rotatoria[(i*3-1)].car)); // Liberiamo l'indrizzo della macchina
                rotatoria[i*3-1].car=NULL; // Segnaliamo che quel posto della rotatoria, ? ora vuoto
            }
    }
}

comp_1 - check exit
{
    TEMPO
    La complessità di tempo dipende dal numero di elementi che si controllano nei cicli for sia che log sia 0 che sia diverso da 0;
    dati n elementi da controllare, la complessità asintotica di tempo è O(n).
    SPAZIO
    La struttura dati utilizzata per l'algoritmo si basa su un array di struct (monodimensionale) per cui la complessità di spazio è pari
    alla sua dimensione ( O(N_P) )
}

/*DANIELE PUOI FARE IL COMPLESSO */
void check_enter(struct strada rotatoria[N_P], struct strada *confluenti[N_S]){ //Funzione di entrata delle macchine
   int i;
   for (i=1;i<6;i++)
       if(confluenti[i-1]!=NULL)
           if(rotatoria[(i*3-1)].car==NULL){
               rotatoria[(i*3-1)].car=confluenti[i-1]->car;
               struct strada *tmp=(struct strada*)&confluenti[i-1]; //Salviamo il top in una variabile temporanea
               confluenti[i-1]=confluenti[i-1]->next; // Il prossimo pezzo di strada diventa il top
               free(tmp); // Svuotiamo al variabile temporanea
           }


}

comp_2 - check enter
{
    TEMPO
    La complessità di tempo dipende dal numero di elementi che si controllano nel ciclo for;
    dati n elementi da controllare, la complessità asintotica di tempo è O(n).
    SPAZIO
    La struttura dati utilizzata per l'algoritmo si basa su un array di struct (monodimensionale), ed inoltre la variabile temporanea creata
    viene deallocata subito per cui la complessità di spazio è pari alla dimensione dell'array    ( O(N_P) )
}

/*DANIELE PUOI FARE IL COMPLESSO */
void shift_L(struct strada rotatoria[N_P]){ //Funzione che simula la circolazione, in senso antiorario, della rotatoria
   int x;
   struct strada a;
   a=rotatoria[0];
   for (x=0;x<14;x++)
       rotatoria[x]=rotatoria[x+1];
   rotatoria[14]=a;

}

comp_3 - shift L
{
    TEMPO
    La complessità di tempo dipende dal numero di elementi che si controllano nel ciclo for;
    dati n elementi da controllare, la complessità asintotica di tempo è O(n).
    SPAZIO
    La struttura dati utilizzata per l'algoritmo si basa su un array di struct (monodimensionale) per cui la complessità si spazio è pari
    alla sua dimensione ( O(N_P) )
}

/*Inserisce nella strada N[0-4] una nuova macchina in coda
Se nessuna macchina ? presenta la testa viene reindirizzata a quella macchina.
*/
/*DANIELE PUOI FARE IL COMPLESSO */
void new_car(struct strada *road){
    int x=0;
    road->car=malloc(sizeof(struct macchina));
    printf("Inserire destinazione: [0-4]\n");
    while(x<0 || x>4 || scanf("%d",&x)!=1){
        while (getchar() != '\n');
        printf("Input non valido, reinserire la destinazione\n");
        scanf("%d", &x);
    }
    road->car->destinazione=x;
    printf("Inserire targa:\n");
    scanf("%d",&(road->car->targa));
}

comp_4 - new car
{
    TEMPO
    L'algoritmo prende in input un numero e controlla se esso è valido (cioè se è compreso tra 0 e 4, inclusi).
    La complessità di tempo dell'algoritmo dipende da quante volte si inserisce un numero illegale, arrivando ad una costante.
    SPAZIO
    Nell'algoritmo si alloca semplicemente una singola struct, perciò la complessità spaziale è costante.
}

/*DANIELE PUOI FARE IL COMPLESSO */
void stampa_lista(struct strada *head){ //Funzione che stampa tutte le macchine presenti in una strada
    if(head!=NULL){
        printf("%d/%d-->", head->car->destinazione, head->car->targa);
        stampa_lista(head->next);
    }
    else
        printf("fine coda\n");
}

comp_5 - stampa lista
{
    TEMPO
    L'algoritmo stampa in modo ricorsivo una lista presa in input; la sua complessità temporale dipende da quanti elementi ci sono nella lista.
    Con n elementi, la complessità asintotica di tempo è O(n).
    SPAZIO
    Nell'algoritmo non vengono allocate o create variabili ma viene solo letta una lista come parametro, perciò la complessità di spazio dell'algoritmo
    è O(n) con n dimensione ipotetica della lista.
}

void new_road(struct strada *head[N_S], int numero_strada){ //Funzione utilizzata per inizializzare le strade
    struct strada *tmp=head[numero_strada];
    if (head[numero_strada]== NULL){
        head[numero_strada]=(struct strada *)malloc(sizeof(struct strada));
        new_car(head[numero_strada]);
        head[numero_strada]->next=NULL;
        return;
    }
    while(tmp->next!=NULL)
        tmp=tmp->next;
    tmp->next=(struct strada *)malloc(sizeof(struct strada));
    tmp->next->next=NULL;
    tmp=tmp->next;
    new_car(tmp);
}

comp_6 - new road
{
    TEMPO
    La funzione controlla se ci sono elementi nell'array di puntatori a struct head[N_S]; se non è così, si alloca una struct e si richiama la funzione
    new_car che ha complessità costante. Poi si scorre la lista finchè non si trova la coda e poi si richiama la funzione new_car.
    Al più, la complessità asintotica di tempo corrisponde a O(n) dato dallo scorrere della lista avvenuto nel ciclo while, dove n è la dimensione
    ipotetica della lista.
    SPAZIO
    La funzione prende in input un array di struct e crea nuovi elementi sia che l'if sia valutato vero e sia dopo in ciclo while.
    Al più, la complessità asintotica di spazio corrisponde alla dimensione effettiva dell'array e cioè è un O(N_S).
}

/*DANIELE PUOI FARE IL COMPLESSO */
void stampa_situazione(struct strada *confluenti[N_S], struct strada rotatoria[N_P]){ //Funzione di stampa della situazione presente nella rotatoria
    int i;
    system("cls");
    printf(" ");
    for (i=0;i<N_S;i++){
        printf("      |");
        if(confluenti[i] !=NULL)
            printf("CAR");
        else printf("___");
            printf("| ");
    }
    printf("\n");
    for (i=0;i<N_P;i++)
        printf("----");
    printf("\n");
    for (i=0;i<N_P;i++)
        if (rotatoria[i].car!=NULL)
            printf("%d%d ", rotatoria[i].car->destinazione, rotatoria[i].car->targa);
    else
        printf("___ ");
    printf("<--\n");
    for (i=0;i<N_P;i++)
        printf("----");
    printf("\n");
    for (i=0;i<N_P;i++)
        printf("   |");
    printf("\n");
    for (i=0;i<N_P;i++)
        printf(" %X  ",i+1);
    printf("\n");
    for (i=0;i<N_S;i++){
        printf("Ingressi futuri strada %d: ",i);
        stampa_lista(confluenti[i]);
        printf("\n");
    }
    printf("\n\n\n");
}

comp_7 - stampa situazione
{
    TEMPO
    Nell'algoritmo vengono usati più volte dei cicli for per scorrere e stampare gli elementi degli array di struct, ma mai in modo innestato,
    perciò la complessità asintotica di tempo è O(N_P + N_S).
    SPAZIO
    Nell'algoritmo non vengono create variabili aggiuntive, ma si fa uso di array di struct presi in input come parametri.
    Perciò la complessità di spazio dell'algoritmo è pari alla somma delle dimensioni dei due array arrivando a O(n) con n = N_P + N_S.
}

/*DANIELE PUOI FARE IL COMPLESSO */
void RCG(struct strada rotatoria[N_P]){// Random Car Generator
   int i;
   srand(time(NULL));
   for(i=0;i<N_P;i++){
       free(rotatoria[i].car);
       rotatoria[i].car=NULL;
   }
   printf("\nGenerazione casuale rotatoria");
   int check;
   for (i=0;i<N_P;i++){
       if(rand()%N_S>=rand()%N_S){
           rotatoria[i].car=(struct macchina *)malloc(sizeof(struct macchina));
           rotatoria[i].car->destinazione=rand()%N_S;
           check=rand()%100;
            (check<10) ? check*=10 : 0;// Controlla che nessuna targa sia inferiore a 10
           rotatoria[i].car->targa=check;
           Sleep(200);
           printf(".");
       }
   }
   printf("\n");
}

comp_8 - rcg
{
    TEMPO
    La complessità di tempo dipende dal numero di elementi che si controllano nei due cicli for;
    la complessità totale è la somma delle complessità dei due cicli for, cioè O(N_P).
    SPAZIO
    La struttura dati utilizzata per l'algoritmo si basa su un array di struct (monodimensionale) per cui la complessità si spazio è pari
    alla sua dimensione ( O(N_P) )
}

/*DANIELE PUOI FARE IL COMPLESSO */
struct strada *rimuovi_elem(struct strada* head, int targa, int *trovato){ //Funzione che cerca e rimuove una macchina con una certa targa in una strada
   if(head!=NULL){
       struct strada *tmp;
       if(head->car->targa==targa){
           free(head->car);
           tmp=head->next;
           free(head);
           *trovato=1;
           return tmp;
       }
       head->next=rimuovi_elem(head->next, targa, trovato);
   }
   return head;
}

comp_9 - rimuovi elem
{
    TEMPO
    L'algoritmo rimuove, agendo in modo ricorsivo, un elemento da una lista;
    perciò la complessità asintotica temporale dipende da quanti elementi ci sono nella lista, nel caso peggiore è O(n) dove n è il numero di elementi.
    SPAZIO
    L'algoritmo si basa su una struttura dati della forma di una lista; la complessità di spazio per cui è O(n) dove n è il numero di nodi.
}

/*DANIELE PUOI FARE IL COMPLESSO */
void remove_car(struct strada *confluenti[N_S]){ //Funzione che cerca e rimuove una macchina con una certa targa nelle varie strade
    int targa, i, trovato=0;
    printf("\nInserire la targa della macchina da rimuovere:");
    scanf("%d",&targa);
    for(i=0;i<N_S;i++){
       confluenti[i]=rimuovi_elem(confluenti[i], targa, &trovato);
       if(trovato==1)
            return;
    }
    printf("Macchina non trovata\n");
}

comp_10 - remove car
{
    TEMPO
    Nell'algoritmo c'è un ciclo for in cui si richiama ad ogni iterazione la funzione rimuovi_elem;
    la complessità asintotica complessiva dell'algoritmo dipende dal numero di confronti effettuati nel ciclo e cioè dalla dimensione dell'array di struct
    ossia O(N_S).
    SPAZIO
    La struttura dati utilizzata per l'algoritmo si basa su un array di struct (monodimensionale) per cui la complessità si spazio è pari
    alla sua dimensione ( O(N_S) )
}

/*DANIELE PUOI FARE IL COMPLESSO */
void read_file(struct strada rotatoria[N_P]){ //Funzione che legge una situazione iniziale da file
    int i, x, t=0;
    FILE *fp=fopen("situazione.txt", "r");
    for(i=0;i<N_P;i++){
       free(rotatoria[i].car);
       rotatoria[i].car=NULL;
    }
    if(fp!=NULL){
        printf("\nCaricamento rotatoria");
        for(i=0; i<N_P; i++){
            fscanf(fp, "%d", &x);
            if(x>0){
                while(x>=100){
                    x=x-100;
                    t++;
                }
                rotatoria[i].car=malloc(sizeof(struct macchina));
                rotatoria[i].car->targa=x;
                rotatoria[i].car->destinazione=t;
                x=t=0;
                Sleep(200);
                printf(".");
            }
        }
        printf("\n");
        fclose(fp);
    }else
        printf("Impossibile aprire il file\n");
}

comp_11 - read file
{
    Nell'algoritmo si apre un file e si legge ciò che c'è dentro;
    la complessità dipende da se esiste il file;
    se non esiste, essa è uguale a O(N_P) che deriva dal primo for, mentre se viene aperto il file, ad essa va sommata la complessità derivante dal ciclo
    for che a sua volta richiama un ciclo while che termina appena il controllo viene soddisfatto, cioè subito.
    La complessità asintotica temporale totale nel caso peggiore (file aperto) è uguale a:
    O(N_P) + O(N_P)= O(N_P).
    SPAZIO
    La complessità asintotica di spazio dipende dalla struttura dati utilizzata e cioè un array di struct monodimensionale. Perciò essa
    corrisponde a O(N_P).
}

void save_file(struct strada rotatoria[N_P]){ //Funzione che salva la situazione attuale in un file
    int i;
    FILE *fp=fopen("situazione.txt", "w");
    if(fp!=NULL){
        printf("\nSalvataggio rotatoria");
        for (i=0; i<N_P; i++){
            if (rotatoria[i].car!=NULL)
                fprintf(fp, "%d%d ", rotatoria[i].car->destinazione, rotatoria[i].car->targa);
            else
                fprintf(fp, "0 ");
        }
        printf("\n");
        fclose(fp);
        system("notepad.exe situazione.txt");
    }else
        printf("Impossibile aprire il file\n");
}

comp_12 - save file
{
    TEMPO
    La funzione legge i dati presenti nell'array di struct e li salva in un file, se è possibile aprirlo in scrittura;
    perciò la complessità asintotica di spazio nel caso peggiore (file aperto) dipende dalla dimensione dell'array (N_P)
    arrivando al più a O(N_P).
    SPAZIO
    L'algoritmo scorre i dati presenti in un array di struct e li scrive se è possibile su un file di testo;
    al più, la complessità asintotica di spazio arriva a O(N_P) dove N_P è la dimensione dell'array.
}

/*DANIELE PUOI FARE IL COMPLESSO */
void pulizia(struct strada rotatoria[N_P], struct strada *confluenti[N_S]){ //Funzione utilizzata per deallocare tutte le strutture allocate
    pulizia_rotatoria(rotatoria);
    pulizia_strada(confluenti[0]); //Richiamando la funzione in questo modo senza utilizzare un for, sono state risparmiate 6 iterazioni, ovvero i controlli del for
    pulizia_strada(confluenti[1]);
    pulizia_strada(confluenti[2]);
    pulizia_strada(confluenti[3]);
    pulizia_strada(confluenti[4]);
}

comp_13 - pulizia
{
    TEMPO
    La funzione è scritta apposta per non inserire cicli, in questo modo si accede ai dati in modo diretto, come è possibile fare con un array.
    Per cui, la complessità asintotica di tempo è costante.
    SPAZIO
    L'algoritmo non introduce nuove variabili, ma si basa solamente sull'array dato come parametro alla funzione, per cui la complessità asintotica
    di spazio dipende esclusivamente dalla dimensione dell'array e cioè O(N_P).
}

/*DANIELE PUOI FARE IL COMPLESSO */
void pulizia_rotatoria(struct strada rotatoria[N_P]){ //Funzione utilizzata per deallocare le macchine presenti nella rotatoria
    int i;
    for(i=0;i<N_P;i++){
       free(rotatoria[i].car);
       rotatoria[i].car=NULL;
   }
}

comp_14 - pulizia rotatoria
{
    TEMPO
    Il ciclo for presente nell'algoritmo scorre ad uno ad uno gli elementi dell'array di struct dato in input alla funzione;
    perciò la complessità di tempo totale è O(N_P) dove N_P è la dimensione dell'array.
    SPAZIO
    L'algoritmo scorre gli elementi dell'array di struct senza ricorrere all'uso e alla creazione di variabili aggiuntive per cui la complessità
    asintotica di spazio totale dipende esclusivamente dalla dimensione dell'array dato in input, ossia O(N_P) con N_P dimensione dell'array.
}

/*DANIELE PUOI FARE IL COMPLESSO */
void pulizia_strada(struct strada *head){ //Funzione utilizzata per deallocare le strade e le macchine in esse contenute
    if(head!=NULL){
        pulizia_strada(head->next);
        free(head->car);
        free(head);
    }
}

comp_15 - pulizia strada
{
    TEMPO
    La funzione dealloca gli elementi dalla lista concatenata data in input, per cui, essendo essa anche ricorsiva, al più si ha una complessità
    asintotica di tempo pari al numero di nodi in esso presenti, e cioè con n elementi si ha un O(n).
    SPAZIO
    L'algoritmo scorre semplicemente in modo ricorsivo i nodi in una lista concatenata, in modo ricorsivo, per deallocarli, per cui la complessità
    asintotica di spazio è al più O(n) con n ipotetico numero di nodi nella lista.
}

void impostazioni(int *N, int *W, int *log, struct strada rotatoria[N_P]){ //Funzione utilizzata per aggiungere delle modifiche rispetto al menù principale
     system("cls");
     printf("1 - Numero simulazioni\n2 - Tempo tra ogni istantanea(s)\n3 - Genera casualmente una situazione nella rotatoria\n4 - Salva situazione rotatoria\n5 - Attiva o disattiva l'exit log delle macchine\n");
     int S=0;
     scanf("%d", &S);
     switch(S){
          case 1:
          printf("\nInserire il numero di simulazioni da effettuare: ");
          scanf("%d", N);break;
          case 2:
          printf("\nOgni quanto tempo vuoi che vengano scattate le istantanee? (s)");
          scanf("%d", W);break;
          case 3:
            RCG(rotatoria);break;
          case 4:
            save_file(rotatoria);break;
          case 5:
              if(*log==0)
                *log=1;
              else *log=0;
              break;
      }
      system("cls");
 }

 comp_16 - impostazioni
 {
    TEMPO
    La funzione fa scegliere all'utente un'azione da compiere ed in base ad essa esegue un comando, tra cui anche la chiamata della funzione RCG o
    della funzione save_file; poichè RCG ha complessità O(N_P) e save_file O(N_P), e poichè le altre sono semplici istruzioni atomiche, allora
    la complessità asintotica di tempo nel caso peggiore corrisponde alla chiamata di una delle due funzioni e cioè a O(N_P).
    SPAZIO
    Come nella complessità temporale, anche la complessità spaziale asintotica corrisponde, nel caso peggiore della chiamata di una delle due funzioni,
    a O(N_P).
 }