Suggest a feature
×

Welcome to TagMyCode

Please login or create account to add a snippet.
 

Fattoria - Progetto di Algoritmi e Strutture Dati

0
0
 
0
Language: C
Posted by: Massimo Zappino
Added: Feb 15, 2011 8:45 AM
Views: 240
Tags: algorithm fattoria
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5.  
  6.  
  7. #define DIM_STRING 10
  8. #define MAX_VERTICI 10
  9.  
  10. /*##############################################################*/
  11. /*                      STRUTTURE DATI                          */
  12. /*##############################################################*/
  13.  
  14. typedef struct specie
  15. {
  16.     struct specie *next;
  17.     char stringa[DIM_STRING+1];
  18.     struct adiacenza *ad;
  19. }
  20. specie;
  21.  
  22. typedef struct adiacenza
  23. {
  24.     struct specie *specie;
  25.     struct adiacenza *next;
  26. }
  27. adiacenza;
  28.  
  29. typedef struct animale
  30. {
  31.     struct animale *next;
  32.     struct specie *specie;
  33.     int x;
  34.     int y;
  35. }
  36. animale;
  37.  
  38. typedef struct recinto
  39. {
  40.     int val;
  41.     int num_vertici;
  42.     struct vertice * vertici;
  43.     struct recinto * next;
  44.     struct recinto * prev;
  45. }
  46. recinto;
  47.  
  48. typedef struct vertice
  49. {
  50.     int x;
  51.     int y;
  52.     struct vertice * next;
  53. }
  54. vertice;
  55.  
  56. typedef struct bitmap
  57. {
  58.     animale * a;
  59.     int del;
  60. }
  61. bitmap;
  62.  
  63. #define MAX_ARGS 21
  64. struct comando                  /* gestore linea comandi */
  65. {
  66.     char * nome;
  67.     char * argv[MAX_ARGS+1];
  68.     int argc;
  69. };
  70.  
  71. /*##############################################################*/
  72. /*              PROTOTIPI FUNZIONI AUSILIARIE                   */
  73. /*##############################################################*/
  74.  
  75. void cancella_lista_vertici(recinto *nodo);
  76. void cancella_lista_recinti();
  77. void cancella_lista_animali();
  78. void cancella_lista_adiacenze(specie *nodo);
  79. void cancella_lista_specie();
  80. void cancella_campo();
  81. specie* inserisci_specie(char *stringa);
  82. void inserisci_animale(int x, int y, specie *spec);
  83. void inserisci_recinto(int val,vertice *vertici, int num_vertici);
  84. int cancella_recinto(recinto *nodo);
  85. void riordina_recinto();
  86. vertice * inserisci_vertice(int x, int y, vertice* t_vertice);
  87. int posizione_punto(int xA, int yA, int xB, int yB, int xC, int yC);
  88. int nel_recinto(int a, int b, recinto *r_tmp);
  89. int relazione_errata(specie *specie1, char *s2);
  90. void visita_grafo(specie *specie1, bitmap bit[]);
  91.  
  92. /*##############################################################*/
  93. /*              PROTOTIPI FUNZIONI PRINCIPALI                   */
  94. /*##############################################################*/
  95.  
  96. void crea();
  97. int inserisci(int a, int b, char *s, int verbose);
  98. void inserisci_random(int a, int b, int c, int d, int n, char *s);
  99. void elimina(int a, int b);
  100. void ordina(char * s1, char * s2);
  101. void recinta(int argc, char* argv[]);
  102. void elimina_recinto(int a, int b);
  103. void mostra_recinto(int r);
  104. void mostra_campo();
  105. void seleziona();
  106.  
  107. /*##############################################################*/
  108. /*              PROTOTIPI FUNZIONI DI GESTIONE DEL MAIN         */
  109. /*##############################################################*/
  110. void parse_command(struct comando *command, char *linea);
  111.  
  112. /*##############################################################*/
  113. /*                      VARIABILI GLOBALI                       */
  114. /*##############################################################*/
  115.  
  116. specie *t_specie = NULL;        /* puntatore alla testa della lista Specie */
  117. animale *t_animale = NULL;      /* puntatore alla testa della lista Animale */
  118. animale *c_animale = NULL;      /* puntatore alla coda della lista Animale */
  119. recinto *t_recinto = NULL;      /* puntatore alla testa della lista Recinto */
  120. recinto *c_recinto = NULL;      /* puntatore alla coda della lista Recinto */
  121. int num_animali = 0;            /* contatore elementi animali della lista */
  122. int num_recinti = 0;            /* contatore recinti nel campo */
  123.  
  124. /*##############################################################*/
  125. /*                      FUNZIONI AUSILIARIE                     */
  126. /*##############################################################*/
  127.  
  128. /* Dealloca la memoria occupata dalla lista dei vertici associata al recinto nodo */
  129. void cancella_lista_vertici(recinto *nodo)
  130. {
  131.     vertice *tmp = nodo->vertici;
  132.     vertice *tmp1 = NULL;
  133.  
  134.     /* scorre la lista e cancella tutti i suoi elementi */
  135.     while(tmp!=NULL)
  136.     {
  137.         tmp1=tmp->next;
  138.         free(tmp);
  139.         tmp=tmp1;
  140.     }
  141. }
  142.  
  143. void cancella_lista_recinti()
  144. {
  145.     recinto *tmp = t_recinto;
  146.     recinto *tmp1 = NULL;
  147.  
  148.     /* scorre la lista e cancella tutti i suoi elementi */
  149.     while(tmp!=NULL)
  150.     {
  151.         tmp1=tmp;
  152.         cancella_lista_vertici(tmp);
  153.         free(tmp);
  154.         tmp=tmp1->next;
  155.     }
  156.     t_recinto=NULL;
  157.     num_recinti=0;
  158. }
  159.  
  160. void cancella_lista_animali()
  161. {
  162.     animale *tmp = t_animale;
  163.     animale *tmp1 = NULL;
  164.  
  165.     /* scorre la lista e cancella tutti i suoi elementi */
  166.     while(tmp!=NULL)
  167.     {
  168.         tmp1=tmp->next;
  169.         free(tmp);
  170.         tmp=tmp1;
  171.     }
  172.     t_animale = NULL;
  173.     num_animali=0;
  174. }
  175.  
  176. /* Dealloca la memoria occupata dalla lista dei vertici associata al recinto nodo */
  177. void cancella_lista_adiacenze(specie *nodo)
  178. {
  179.     adiacenza *tmp = nodo->ad;
  180.     adiacenza *tmp1 = NULL;
  181.  
  182.     /* scorre la lista e cancella tutti i suoi elementi */
  183.     while(tmp!=NULL)
  184.     {
  185.         tmp1=tmp->next;
  186.         free(tmp);
  187.         tmp=tmp1;
  188.     }
  189. }
  190.  
  191. void cancella_lista_specie()
  192. {
  193.     specie *tmp = t_specie;
  194.     specie *tmp1 = NULL;
  195.  
  196.     /* scorre la lista e cancella tutti i suoi elementi */
  197.     while(tmp!=NULL)
  198.     {
  199.         tmp1=tmp->next;
  200.         cancella_lista_adiacenze(tmp);
  201.         free(tmp);
  202.         tmp=tmp1;
  203.     }
  204.     t_specie = NULL;
  205. }
  206.  
  207.  
  208. void cancella_campo()
  209. {
  210.     cancella_lista_animali();
  211.     cancella_lista_specie();    /* cancella la lista di adiacenze associata */
  212.     cancella_lista_recinti();   /* cancella la lista vertici associata */
  213.     printf("Campo inizializzato\n");
  214. }
  215.  
  216. specie* inserisci_specie(char *stringa)
  217. {    /* inserimento in testa */
  218.     specie *tmp;
  219.  
  220.     /* Alloca il nodo "specie" */
  221.     tmp = (specie*)malloc(sizeof(specie));
  222.     tmp->next=NULL;
  223.     tmp->ad=NULL;
  224.     strcpy(tmp->stringa,stringa);
  225.  
  226.     if(t_specie==NULL) /* lista vuota */
  227.     {
  228.         t_specie=tmp;
  229.         return tmp;
  230.     } else
  231.     {
  232.         tmp->next=t_specie;
  233.         t_specie=tmp;
  234.         return tmp;
  235.     }
  236. }
  237.  
  238. void inserisci_animale(int x, int y, specie *spec)
  239. {    /* inserimento in coda */
  240.     animale *tmp;
  241.  
  242.     tmp = (animale*)malloc(sizeof(animale));
  243.     tmp->next=NULL;
  244.     tmp->x=x;
  245.     tmp->y=y;
  246.     tmp->specie=spec;
  247.  
  248.     if(t_animale==NULL || c_animale==NULL)
  249.     {
  250.         t_animale=tmp;
  251.         c_animale=tmp;
  252.     }
  253.     else
  254.     {
  255.         c_animale->next=tmp;
  256.         c_animale=tmp;
  257.     }
  258.     num_animali++;
  259. }
  260.  
  261. void inserisci_recinto(int val,vertice *vertici, int num_vertici)
  262. {    /* inserimento in coda: lista doppia */
  263.     recinto *tmp;
  264.  
  265.     tmp = (recinto*)malloc(sizeof(recinto));
  266.     tmp->val=val;
  267.     tmp->num_vertici=num_vertici;
  268.     tmp->vertici=vertici;
  269.  
  270.     if(t_recinto==NULL || c_recinto==NULL)
  271.     {
  272.         tmp->next=NULL;
  273.         tmp->prev=NULL;
  274.         c_recinto=tmp;
  275.         t_recinto=tmp;
  276.     }
  277.     else
  278.     {
  279.         tmp->next=NULL;
  280.         tmp->prev=c_recinto;
  281.         c_recinto->next=tmp;
  282.         c_recinto=tmp;
  283.     }
  284. }
  285.  
  286. /* Elimina un nodo recinto e riordina la lista */
  287. int cancella_recinto(recinto *nodo)
  288. {
  289.     /* se la lista contiene un solo elemento */
  290.     if(nodo==c_recinto && nodo == t_recinto)
  291.     {
  292.         c_recinto=NULL;
  293.         t_recinto=NULL;
  294.         cancella_lista_vertici(nodo);
  295.         free(nodo);
  296.         return 1;
  297.     }
  298.     /* se il nodo è la testa della lista */
  299.     else if(nodo==t_recinto)
  300.     {
  301.         nodo->next->prev=NULL;
  302.         t_recinto=nodo->next;
  303.         cancella_lista_vertici(nodo);
  304.         free(nodo);
  305.         return 1;
  306.     }
  307.     /* se il nodo è la coda della lista */
  308.     else if(nodo==c_recinto)
  309.     {
  310.         nodo->prev->next=NULL;
  311.         c_recinto=nodo->prev;
  312.         cancella_lista_vertici(nodo);
  313.         free(nodo);
  314.         return 1;
  315.     }
  316.     else
  317.     {
  318.         nodo->prev->next=nodo->next;
  319.         nodo->next->prev=nodo->prev;
  320.         cancella_lista_vertici(nodo);
  321.         free(nodo);
  322.         return 1;
  323.     }
  324. }
  325.  
  326. void riordina_recinto()
  327. {
  328.     recinto *tmp = t_recinto;
  329.     int i=1;
  330.  
  331.     /* Scorre la lista dei recinti e riassegna a ciascun nodo un numero
  332.      progressivo fino a raggiungere il valore dei recinti totali (num_recinti) */
  333.     while(tmp!=NULL)
  334.     {
  335.         tmp->val=i;
  336.         tmp=tmp->next;
  337.         i++;
  338.     }
  339. }
  340.  
  341. vertice * inserisci_vertice(int x, int y, vertice* t_vertice)
  342. {    /* inserimento in coda */
  343.     vertice *tmp,*tmp1;
  344.  
  345.     tmp = (vertice*)malloc(sizeof(vertice));
  346.     tmp->next=NULL;
  347.     tmp->x=x;
  348.     tmp->y=y;
  349.  
  350.     if(t_vertice==NULL)
  351.     { /* lista vuota */
  352.         t_vertice=tmp;
  353.     }
  354.     else
  355.     {
  356.         tmp1=t_vertice;
  357.         while (tmp1!=NULL)
  358.         {
  359.             if(tmp1->next==NULL)
  360.             {
  361.                 tmp1->next=tmp;
  362.                 break;
  363.             }
  364.             tmp1=tmp1->next;
  365.         }
  366.     }
  367.     return t_vertice;
  368. }
  369.  
  370. /* Prende in ingresso tre punti definiti da coppie ordinate di numeri
  371. e verifica la posizione del terzo punto C rispetto alla retta AB.
  372. Restituisce 0 se i tre punti sono allineati, <0 se il punto si trova
  373. alla destra della retta e >0 se si trova alla sinistra della retta */
  374. int posizione_punto(int xA, int yA, int xB, int yB, int xC, int yC)
  375. {
  376.     return (xC-xA)*(yB-yA)-(yC-yA)*(xB-xA);
  377. }
  378.  
  379. /* Verifica che i punti a,b siano all'interno del recinto r_tmp */
  380. int nel_recinto(int a, int b, recinto *r_tmp)
  381. {
  382.     /* Un punto giace in un poligono convesso se per ogni lato il punto
  383.     si trova alla destra della retta (ab) per vertici allineati in senso orario*/
  384.     vertice *v_tmp=r_tmp->vertici;
  385.     int i=0;
  386.     int v[r_tmp->num_vertici*2]; /* alloca un array di dimensione (num_vertici*2) */
  387.  
  388.     /* controlla che il punto (a,b) sia interno a tutti i lati del poligono */
  389.     while(v_tmp!=NULL)  /* pone i valori della lista "vertici" nell'array */
  390.     {
  391.         v[i]=v_tmp->x;
  392.         v[i+1]=v_tmp->y;
  393.         v_tmp=v_tmp->next;
  394.         i=i+2;
  395.     }
  396.  
  397.     for(i=1;i<r_tmp->num_vertici;i++)
  398.     {   /* se il punto è all'esterno del poligono */
  399.         if(posizione_punto(v[i*2-2],v[i*2-1],v[i*2+0],v[i*2+1],a,b)<0)
  400.             return 0;
  401.     }
  402.     if(posizione_punto(v[i*2-2],v[i*2-1],v[0],v[1],a,b)<0)
  403.         return 0;
  404.  
  405.     return 1;
  406. }
  407.  
  408. /* Funzione ricorsiva: ricompone il percorso del grafo
  409. se trova una stringa ugale a s2 solleva errore */
  410. int relazione_errata(specie *specie1, char *s2)
  411. {
  412.     adiacenza *tmpad=NULL;
  413.  
  414.     if(specie1->ad!=NULL)
  415.     {   /* segue il percorso per ogni nodo della lista adiacenza di s1 */
  416.         tmpad=specie1->ad;
  417.         while(tmpad!=NULL)
  418.         {       /* se le due stringhe sono uguali allora c'è un ciclo */
  419.             if(!strcmp(s2,tmpad->specie->stringa))
  420.                 return 1;
  421.             if(relazione_errata(tmpad->specie,s2))
  422.                 return 1;
  423.             tmpad=tmpad->next;
  424.         }
  425.     }
  426.     return 0;
  427. }
  428. /* Funzione ricorsiva: percorre il cammino del grafo a partire dal nodo specie1
  429. e marca tutti gli animali nella bitmap che devono essere eliminati */
  430. void visita_grafo(specie *specie1, bitmap bit[] )
  431. {
  432.     adiacenza *tmpad=NULL;
  433.     int i;
  434.  
  435.     if(specie1->ad!=NULL)
  436.     {   /* segue il percorso per ogni nodo della lista adiacenza */
  437.         tmpad=specie1->ad;
  438.         while(tmpad!=NULL)
  439.         {
  440.             /* sfoglia l'array bitmap */
  441.             for(i=0;bit[i].a!=NULL;i++)
  442.             {   /* se l'animale presente nella bitmap è da eliminare viene marcato */
  443.                 if(!bit[i].del)
  444.                 {       /* se l'animale non è marcato */
  445.                     if(!strcmp(bit[i].a->specie->stringa,tmpad->specie->stringa))
  446.                         bit[i].del=1;
  447.                 }
  448.             }
  449.             visita_grafo(tmpad->specie, bit);
  450.             tmpad=tmpad->next;
  451.         }
  452.     }
  453.     return;
  454. }
  455.  
  456. void mostra_grafo()
  457. {
  458.     specie *tmp;
  459.     adiacenza *tmpad=NULL;
  460.  
  461.     tmp=t_specie;
  462.     while(tmp!=NULL)
  463.     {
  464.         tmpad=tmp->ad;
  465.         printf("| %s |-> ",tmp->stringa);
  466.         while(tmpad!=NULL)
  467.         {
  468.             printf("%s -> ",tmpad->specie->stringa);
  469.             tmpad=tmpad->next;
  470.         }
  471.         printf("\n");
  472.         tmp=tmp->next;
  473.     }
  474. }
  475.  
  476. /*##############################################################*/
  477. /*                      FUNZIONI PRINCIPALI                     */
  478. /*##############################################################*/
  479.  
  480. void crea()
  481. {
  482.     cancella_campo();
  483. }
  484.  
  485. int inserisci(int a, int b, char *s, int verbose)
  486. {
  487.     animale *a_tmp = t_animale;
  488.     specie *s_tmp = t_specie;
  489.     specie *ptr_specie;
  490.     int presente_specie=0;
  491.  
  492.     while(a_tmp!=NULL)
  493.     {   /* Scorre la lista animali e verifica se le coordinate sono occupate */
  494.         if(a_tmp->x==a && a_tmp->y==b)
  495.         {
  496.             if (verbose)
  497.                 fprintf(stderr, "errore: le coordinade (%d, %d) sono già  occupate\n",a,b);
  498.             return 0;
  499.         }
  500.         a_tmp=a_tmp->next;
  501.     }
  502.  
  503.     while(s_tmp!=NULL)
  504.     {
  505.         /* Se specie è presente */
  506.         if(!strcmp(s,s_tmp->stringa))
  507.         {
  508.             presente_specie=1;
  509.             ptr_specie=s_tmp;
  510.             break;
  511.         }
  512.         s_tmp=s_tmp->next;
  513.     }
  514.     if(!presente_specie)
  515.     {
  516.         inserisci_specie(s);
  517.         ptr_specie = t_specie;
  518.     }
  519.     inserisci_animale(a,b,ptr_specie);
  520.     if (verbose)
  521.         printf("inserito:\t%d\t%d\t%s\n",a,b,s);
  522.     return 1;
  523.  
  524. }
  525.  
  526. void inserisci_random(int a, int b, int c, int d, int n, char *s)
  527. {
  528.     int x, y;
  529.     int i = 0;
  530.  
  531.     /* Può entrare in un ciclo infinito se tutte le posizioni
  532.     nel range (ab)(cd) sono occupate */
  533.     while (i<n)
  534.     {
  535.         x=rand()%(c-a+1)+a;
  536.         y=rand()%(b-d+1)+d;
  537.         i=i+inserisci(x,y,(char*)s,0);
  538.     }
  539. }
  540.  
  541. void elimina(int a, int b)
  542. {
  543.     animale *a_tmp, *canc;
  544.  
  545.     a_tmp = t_animale;
  546.     if(a_tmp!=NULL)
  547.     { /* Se è presente almeno un elemento */
  548.         if(a_tmp->x==a && a_tmp->y==b)  /* cancellazione in testa */
  549.         {
  550.             canc=a_tmp;
  551.             if(canc->next==NULL)        /* se è l'ultimo nodo */
  552.                 c_animale=NULL; /* aggiorna la coda */
  553.             a_tmp=a_tmp->next;
  554.             free(canc);
  555.             num_animali--;
  556.             t_animale=a_tmp;    /* aggiorna il puntatore alla testa */
  557.             return;
  558.         }
  559.  
  560.         while(a_tmp->next!=NULL)
  561.         {
  562.             if(a_tmp->next->x==a && a_tmp->next->y==b)
  563.             {
  564.                 canc=a_tmp->next;
  565.                 if(canc==c_animale)             /* se è l'ultimo nodo */
  566.                     c_animale=a_tmp;    /* aggiorna la coda */
  567.                 a_tmp->next=canc->next;
  568.                 free(canc);
  569.                 num_animali--;
  570.                 return;
  571.             }
  572.             a_tmp=a_tmp->next;
  573.         }
  574.     }
  575.     fprintf(stderr, "%d,%d:\tanimale non trovato\n",a,b);
  576. }
  577.  
  578. void ordina(char * s1, char * s2)
  579. {
  580.     specie *tmp, *specie1, *specie2;
  581.     adiacenza *tmpad;
  582.     int is_in_s1=0;
  583.     int is_in_s2=0;
  584.  
  585.     /* Controlla che le due stringhe siano diverse */
  586.     if(!strcmp(s1,s2))
  587.     {
  588.         fprintf(stderr,"errore: le stringhe immesse sono uguali\n");
  589.         return;
  590.     }
  591.     /* Ottieni i puntatori ai nodi delle due stringhe passate
  592.        se non esistono vengono aggiunti */
  593.     tmp=t_specie;
  594.     while(tmp!=NULL)
  595.     {
  596.         if(!strcmp(tmp->stringa,s1))
  597.         {
  598.             is_in_s1=1;
  599.             specie1=tmp;
  600.         }
  601.         if(!strcmp(tmp->stringa,s2))
  602.         {
  603.             is_in_s2=1;
  604.             specie2=tmp;
  605.         }
  606.         if(is_in_s1==1 && is_in_s2==1) /* Le due stringhe sono state trovate */
  607.             break;
  608.         tmp=tmp->next;
  609.     }
  610.     if(!is_in_s1)
  611.         specie1=inserisci_specie(s1);
  612.     if(!is_in_s2)
  613.         specie2=inserisci_specie(s2);
  614.  
  615.     /* Controlla l'esistenza della relazione */
  616.     tmpad=specie2->ad;
  617.     while(tmpad!=NULL)
  618.     {
  619.         if(!strcmp(tmpad->specie->stringa,specie1->stringa))
  620.         {
  621.             fprintf(stderr,"errore: la relazione è già esistente\n");
  622.             return;
  623.         }
  624.         tmpad=tmpad->next;
  625.     }
  626.  
  627.     if(relazione_errata(specie1, s2))
  628.     {
  629.         fprintf(stderr,"-1\n");
  630.         return;
  631.     }
  632.     printf("\n");
  633.  
  634.     /* Lista di adiacenza */
  635.     if(specie2->ad==NULL)
  636.     {   /* Non esiste nessun nodo adiacente */
  637.         tmpad = (adiacenza *)malloc(sizeof(adiacenza));
  638.         tmpad->specie=specie1;
  639.         tmpad->next = NULL;
  640.         specie2->ad=tmpad;
  641.     }
  642.     else
  643.     {   /* Esiste almeno un nodo adiacente */
  644.         tmpad = (adiacenza *)malloc(sizeof(adiacenza));
  645.         tmpad->next=specie2->ad;        /* primo nodo della lista adiacenza */
  646.         tmpad->specie=specie1;
  647.         specie2->ad=tmpad;
  648.     }
  649.     /* mostra_grafo(); */
  650. }
  651.  
  652. void recinta(int argc, char* argv[])
  653. {
  654.     int i;
  655.     vertice * t_vertice = NULL;
  656.  
  657.     /* controlla che non ci siano 3 vertici allineati */
  658.     for(i=1;i<=(argc-1)/2;i++)
  659.     {
  660.         if(i>=3)
  661.         {
  662.             /* controlla se siano allineati gli ultimi 2 vertici con il primo */
  663.             if(i == (argc-1)/2) /* se è l'ultimo vertice */
  664.             {
  665.                 if(!posizione_punto(
  666.                             atoi(argv[i*2-1]),atoi(argv[i*2]),          /* ultimo vertice */
  667.                             atoi(argv[3]),atoi(argv[4]),                /* secondo vertice */
  668.                             atoi(argv[1]),atoi(argv[2])                 /* primo vertice */
  669.                         ))
  670.                 {
  671.                     fprintf(stderr,"errore: sono stati immessi tre o più vertici allineati\n");
  672.                     return;
  673.                 }
  674.             }else
  675.                 if(!posizione_punto(
  676.                             atoi(argv[(i-2)*2-1]),atoi(argv[(i-2)*2]),  /* vertice A */
  677.                             atoi(argv[(i-1)*2-1]),atoi(argv[(i-1)*2]),  /* vertice B */
  678.                             atoi(argv[i*2-1]),atoi(argv[i*2])))         /* vertice C */
  679.                 {
  680.                     fprintf(stderr,"errore: sono stati immessi tre o più vertici allineati\n");
  681.                     return;
  682.                 }
  683.         }
  684.     }
  685.     /* assegna ai nodi della lista i valori delle coordinate */
  686.     for(i=1;i<=(argc-1)/2;i++)
  687.     {
  688.         t_vertice=inserisci_vertice(atoi(argv[i*2-1]),atoi(argv[i*2]),t_vertice);
  689.     }
  690.     /* inserisco in coda un nodo alla lista RECINTI con il numero progressivo num_recinti++ */
  691.     inserisci_recinto(++num_recinti,t_vertice,(argc-1)/2);
  692. }
  693.  
  694. void elimina_recinto(int a, int b)
  695. {
  696.     recinto *r_tmp = t_recinto;         /* puntatore alla testa della lista recinto */
  697.  
  698.     /* scorre i nodi nella lista dei recinti */
  699.     while(r_tmp!=NULL)
  700.     {
  701.         /* verifica che a,b siano interni al recinto r_tmp */
  702.         if(nel_recinto(a,b,r_tmp))
  703.         {
  704.             printf("cancello recinto: %d\n",r_tmp->val);
  705.             /* cancella il nodo selezionato */
  706.             if(cancella_recinto(r_tmp))
  707.                 num_recinti--;  /* decrementa il numero di recinti totali */
  708.         }
  709.         r_tmp=r_tmp->next;
  710.     }
  711.     riordina_recinto();
  712. }
  713.  
  714. void mostra_recinto(int r)
  715. {
  716.     recinto *r_tmp = t_recinto;
  717.     animale *a_tmp = t_animale;
  718.     animale *buffer[num_animali+1];
  719.     int i=0;
  720.     int count = 0;
  721.  
  722.     while(r_tmp!=NULL)          /* scorre la lista recinto */
  723.     {
  724.         if(r==r_tmp->val)       /* recinto trovato */
  725.         {   /* scorre la lista degli animali */
  726.             while(a_tmp!=NULL)
  727.             {
  728.                 if(nel_recinto(a_tmp->x,a_tmp->y,r_tmp))
  729.                 {       /* salva l'output in una struttura temporanea */
  730.                     buffer[i]=a_tmp;
  731.                     i++;
  732.                     count++;
  733.                 }
  734.                 a_tmp=a_tmp->next;
  735.             }
  736.             buffer[i]=NULL;     /* sentinella */
  737.  
  738.             printf("%d\n",count);
  739.             for(i=0;buffer[i]!=NULL;i++)
  740.             {
  741.                 printf("%d,\t%d,\t%s\n",buffer[i]->x, buffer[i]->y,buffer[i]->specie->stringa);
  742.             }
  743.             return;
  744.         }
  745.         r_tmp=r_tmp->next;
  746.     }
  747.     /* se siamo qui non è stato trovato nessun recinto con valore r */
  748.     fprintf(stderr,"nessun recinto con valore %d\n",r);
  749.  
  750. }
  751.  
  752. void mostra_campo()
  753. {
  754.     animale *a_tmp = t_animale;
  755.  
  756.     printf("%d\n",num_animali);
  757.     while(a_tmp!=NULL)
  758.     {
  759.         printf("%d,\t%d,\t%s\n",a_tmp->x,a_tmp->y,a_tmp->specie->stringa);
  760.         a_tmp=a_tmp->next;
  761.     }
  762. }
  763.  
  764. void seleziona()
  765. {
  766.     recinto *r_tmp = t_recinto;
  767.     animale *a_tmp;
  768.     bitmap bit[num_animali+1];
  769.     int i;
  770.  
  771.     /* scorre la lista dei recinti */
  772.     while(r_tmp!=NULL)
  773.     {
  774.         /* svuota buffer */
  775.         bit[0].a=NULL;
  776.         i=0;
  777.        
  778.         /* scorre la lista degli animali */
  779.         a_tmp = t_animale;
  780.         while(a_tmp!=NULL)
  781.         {       /* salva la lista degli animali presenti nel recinto in una struttura temporanea */
  782.             if(nel_recinto(a_tmp->x,a_tmp->y,r_tmp))
  783.             {
  784.                 bit[i].a=a_tmp;
  785.                 bit[i].del=0;
  786.                 i++;
  787.             }
  788.             a_tmp=a_tmp->next;
  789.         }
  790.         bit[i].a=NULL;  /* sentinella */
  791.  
  792.         /* per ogni animale nel recinto */
  793.         for(i=0;bit[i].a!=NULL;i++)
  794.         {
  795.             if(!bit[i].del) /* se l'animale non è marcato */
  796.                 visita_grafo(bit[i].a->specie,bit);
  797.         }
  798.  
  799.         /* Cancella tutti gli animali marcati da eliminare */
  800.         for(i=0;bit[i].a!=NULL;i++)
  801.         {
  802.             if(bit[i].del==1)
  803.                 elimina(bit[i].a->x,bit[i].a->y);
  804.         }
  805.         /* fine recinto */
  806.         r_tmp=r_tmp->next;
  807.     }
  808. }
  809.  
  810. /*##############################################################*/
  811. /*              FUNZIONI DI GESTIONE DEL MAIN                   */
  812. /*##############################################################*/
  813.  
  814. /* costruisce la riga di comando e separa il nome del comando e i suoi argomenti */
  815. void parse_command(struct comando *command, char *linea)
  816. {
  817.     char *token;
  818.     char *s;
  819.  
  820.     s = linea;
  821.     /* cancella gli eventuali spazi bianchi all'inizio della stringa */
  822.     while(isspace(*s))
  823.         s++;
  824.     if(!*s)
  825.     {
  826.         command->nome=NULL;
  827.         return;
  828.     }
  829.     /* legge il primo token */
  830.     token = strtok(linea, " ");
  831.     command->nome = token;
  832.     command->argv[0] = token;
  833.  
  834.     /* legge i token successivi */
  835.     token = strtok(NULL, " ");
  836.     command->argc = 1;
  837.     while (token)
  838.     {
  839.         command->argv[(command->argc)++] = token;
  840.         token = strtok(NULL, " ");
  841.     }
  842.     /* la lista degli argomenti termina con sentinella */
  843.     command->argv[command->argc] = NULL;
  844. }
  845.  
  846. /*##############################################################*/
  847. /*                      FUNZIONE MAIN                           */
  848. /*##############################################################*/
  849.  
  850. #define MAX_COMMAND 512
  851. int main()
  852. {
  853.     struct comando command;
  854.     char stringa[MAX_COMMAND+1];
  855.     int i;
  856.  
  857.     printf("Massimo Zappino\t\t   Matricola: 608655\t\t   20/04/2005\n");
  858.     printf("\t\tLaboratorio di Algoritmi e Strutture Dati\n\n");
  859.     printf("\t\t\t   * FATTORIA *\n\n\n");
  860.  
  861.     while(1)
  862.     {
  863.         /* ripulisce gli argomenti del comando */
  864.         for(i=0;i<MAX_ARGS;i++)
  865.             command.argv[i]=NULL;
  866.  
  867.         /* prompt */
  868.         printf("[fattoria >]$ ");
  869.         /* acquisisce la stringa da standard input */
  870.         if (fgets(stringa, MAX_COMMAND+1, stdin)==NULL)
  871.             exit(0);
  872.  
  873.         stringa[strlen(stringa)-1] = '\0';      /* elimina il line-feed dalla stringa */
  874.         parse_command(&command,stringa);        /* effettua il parsing dei comandi */
  875.  
  876.         /* Gestione comandi */
  877.         if(command.nome!=NULL)
  878.         {
  879.             /* crea */
  880.             if(!strcmp(command.nome,"c"))
  881.             {
  882.                 crea();
  883.             }
  884.  
  885.             /* inserisci */
  886.             else if(!strcmp(command.nome,"i"))
  887.             {
  888.                 if(command.argc<4)
  889.                     fprintf(stderr, "Uso comando errato\n");
  890.                 else
  891.                     inserisci(atoi(command.argv[1]), atoi(command.argv[2]), (char*)command.argv[3],1);
  892.             }
  893.  
  894.             /* inserisci_random */
  895.             else if(!strcmp(command.nome,"ir"))
  896.                 if(command.argc<7)
  897.                     fprintf(stderr, "Uso comando errato\n");
  898.                 else
  899.                     inserisci_random(atoi(command.argv[1]), atoi(command.argv[2]),atoi(command.argv[3]), atoi(command.argv[4]),atoi(command.argv[5]), (char*)command.argv[6]);
  900.  
  901.             /* elimina */
  902.             else if(!strcmp(command.nome,"e"))
  903.                 if(command.argc<3)
  904.                     fprintf(stderr, "Uso comando errato\n");
  905.                 else
  906.                     elimina(atoi(command.argv[1]), atoi(command.argv[2]));
  907.  
  908.             /* ordina */
  909.             else if(!strcmp(command.nome,"o"))
  910.                 if(command.argc<3)
  911.                     fprintf(stderr, "Uso comando errato\n");
  912.                 else
  913.                     ordina(command.argv[1], command.argv[2]);
  914.  
  915.             /* recinta */
  916.             else if(!strcmp(command.nome,"r"))
  917.                 if((command.argc<7) | (command.argc>21))
  918.                     fprintf(stderr, "Uso comando errato\n");
  919.                 else
  920.                     recinta(command.argc,command.argv);
  921.  
  922.             /* elimina_recinto */
  923.             else if(!strcmp(command.nome,"er"))
  924.                 if(command.argc<3)
  925.                     fprintf(stderr, "Uso comando errato\n");
  926.                 else
  927.                     elimina_recinto(atoi(command.argv[1]), atoi(command.argv[2]));
  928.  
  929.             /* mostra_recinto */
  930.             else if(!strcmp(command.nome,"mr"))
  931.                 if(command.argc<2)
  932.                     fprintf(stderr, "Uso comando errato\n");
  933.                 else
  934.                     mostra_recinto(atoi(command.argv[1]));
  935.  
  936.             /* mostra_campo */
  937.             else if(!strcmp(command.nome,"mc"))
  938.                 mostra_campo();
  939.  
  940.             /* seleziona */
  941.             else if(!strcmp(command.nome,"s"))
  942.                 seleziona();
  943.  
  944.             /* fine */
  945.             else if(!strcmp(command.nome,"f"))
  946.             {
  947.                 fflush(stdin);
  948.                 return EXIT_SUCCESS;
  949.             }
  950.  
  951.             /* mostra grafo relazioni */
  952.             else if(!strcmp(command.nome,"mg"))
  953.             {
  954.                 mostra_grafo();
  955.             }
  956.  
  957.             /* comando errato */
  958.             else
  959.                 fprintf(stderr, "comando errato: %s\n",command.nome);
  960.         }
  961.     }
  962. }
  963.  

Write a comment

To post comments, please log in or register.