SHARE
TWEET

Untitled

a guest Sep 13th, 2017 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Progetto realizzato da: Fabrizio Siciliano
  2. Algoritmi per l'informatica
  3. Matricola 843770
  4. Codice Persona 10522031*/
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. typedef struct albero{
  9.     struct albero *right, *left, *padre;
  10.     char *path;
  11. }tree;
  12. typedef struct node{
  13.     struct node *testa, *padre, *left, *right;
  14.     char *file; int figli; int check;
  15.     char nome[255];
  16. }nodo;
  17. void create_dir(nodo *);
  18. void create(nodo *, int);
  19. int write(char *,char *, nodo *);
  20. void insert(nodo*, nodo*);
  21. void read(char *, nodo *);
  22. void delete(nodo *);
  23. void delete_r(nodo *);
  24. void find(nodo*, char*, char*, tree*);
  25. nodo *move(nodo*, char *);
  26. nodo* cancella(nodo *, nodo *);
  27. void cancella_ricorsiva(nodo *);
  28. void inorder_tree_walk(tree *);
  29. void tree_insert(tree *, char*);
  30. nodo* tree_minimum(nodo*);
  31. nodo* tree_successor(nodo*);
  32. int main (){
  33.     char *comando, *par1, *par2;
  34.     int conta_caratteri = 0, i=0, j, k, stampati;
  35.     nodo *head;
  36.     head = (nodo*) malloc(sizeof(nodo));
  37.     head->padre = NULL; head->testa = NULL; head->left = NULL; head->right = NULL; head->file = NULL; head->figli = 0; head->check = 0;
  38.     while(1){
  39.         comando = (char*)calloc(30, sizeof(char));
  40.         scanf("%s", comando);
  41.         conta_caratteri += strlen(comando);
  42.         if (strcmp(comando,"create_dir")==0){
  43.             create(head, 0);
  44.         }
  45.         else if (strcmp(comando,"create")==0){
  46.             create(head, 1);
  47.         }
  48.         else if (strcmp(comando,"write")==0){
  49.             par1 = (char*)calloc(255, sizeof(char));
  50.             par2 = (char*)calloc(255, sizeof(char));
  51.             scanf("%s", par1);
  52.             scanf("%[^\n]", par2);
  53.             conta_caratteri += strlen(par1);
  54.             conta_caratteri += strlen(par2);
  55.             stampati = write(par1, par2,head);
  56.             if(stampati!=0)
  57.                 printf(" %d", stampati);
  58.             free(par1);
  59.             free(par2);
  60.         }
  61.         else if (strcmp(comando,"find")==0){
  62.             par1 = (char*)calloc(255, sizeof(char));
  63.             scanf("%s", par1);
  64.             conta_caratteri += strlen(par1);
  65.             find(head, par1, NULL, NULL);
  66.             free(par1);
  67.         }
  68.         else if (strcmp(comando,"read")==0){
  69.             par1 = (char*)calloc(255, sizeof(char));
  70.             scanf("%s", par1);
  71.             conta_caratteri += strlen(par1);
  72.             read(par1, head);
  73.             free(par1);
  74.         }
  75.         else if (strcmp(comando,"delete")==0){
  76.             delete(head);
  77.         }
  78.         else if (strcmp(comando,"delete_r")==0){
  79.             delete_r(head);
  80.         }
  81.         else if (strcmp(comando, "exit")==0){
  82.             free(head);
  83.             free(comando);
  84.             break;
  85.         }
  86.         free(comando);
  87.         //printf("\n");
  88.     }
  89.     return 0;
  90. }
  91. nodo *move(nodo*x, char *stringa){
  92.     if(x==NULL)
  93.         return x;
  94.     if(strcmp(x->nome, stringa)==0)
  95.         return x;
  96.     if(strcmp(x->nome, stringa)>0)
  97.         return move(x->left, stringa);
  98.     else
  99.         return move(x->right, stringa);
  100. }
  101. void create(nodo *head, int venafro){
  102.     nodo *ptr=head,*newnodo;
  103.     int i=0;
  104.     char *percorso[255], *p, path[255*255];
  105.     scanf("%s", path);
  106.     for (p = strtok(path, "/"); p; p = strtok(NULL, "/")){
  107.         percorso[i]=(char*)malloc(strlen(p)*sizeof(char));
  108.         strcpy(percorso[i], p);
  109.         i++;
  110.     }
  111.     percorso[i]=NULL;
  112.     for(i=0; percorso[i]!=NULL && ptr!=NULL; i++){
  113.         if(ptr->check==1){
  114.             printf("no\n");
  115.             return;
  116.         }
  117.         head=ptr;
  118.         ptr=move(ptr->testa, percorso[i]);
  119.     }
  120.     if(percorso[i]==NULL && ptr==NULL && head->figli<1024){
  121.         newnodo=(nodo*)malloc(sizeof(nodo));
  122.         strcpy(newnodo->nome, percorso[i-1]);
  123.         newnodo->check=venafro;
  124.         newnodo->file=NULL;
  125.         newnodo->figli=0;
  126.         head->figli+=1;
  127.         insert(head, newnodo);
  128.         newnodo->testa=NULL;
  129.         printf("ok\n");
  130.         return;
  131.     }
  132.     else{
  133.         printf("no\n");
  134.         return;
  135.     }
  136. }
  137. void insert(nodo*T, nodo*z){
  138.     nodo *y = NULL, *x= T->testa;
  139.     while(x!=NULL){
  140.         y=x;
  141.         if(strcmp(z->nome, x->nome)<0)
  142.             x = x->left;
  143.         else
  144.             x = x->right;
  145.     }
  146.     z->padre=y;
  147.     if(y==NULL)
  148.         T->testa = z;
  149.     else{
  150.         if(strcmp(z->nome, y->nome)<0)
  151.             y->left = z;
  152.         else
  153.             y->right = z;
  154.     }
  155. }
  156. int write(char *path,char *string, nodo * head){
  157.     nodo *ptr; int i=0, len; char *percorso[255], *p;
  158.     ptr = head;
  159.     for (p = strtok(path, "/"); p; p = strtok(NULL, "/")){
  160.         percorso[i]=(char*)malloc(strlen(p)*sizeof(char));
  161.         strcpy(percorso[i], p);
  162.         i++;
  163.     }
  164.     percorso[i]=NULL;
  165.     string = strtok(string, "\"");
  166.     string = strtok(NULL, "\"");
  167.     len = strlen(string);
  168.     for(i=0; percorso[i]!=NULL; i++){
  169.         if(percorso[i+1]==NULL){
  170.             if(ptr->testa)
  171.                 ptr = ptr->testa;
  172.             else{printf("no");return 0;}
  173.             while(ptr!=NULL){
  174.                 if(strcmp(ptr->nome, percorso[i])<0){
  175.                     ptr = ptr->left;
  176.                 }
  177.                 else if(strcmp(ptr->nome, percorso[i])>0){
  178.                     ptr = ptr->right;
  179.                 }
  180.                 else if(strcmp(ptr->nome, percorso[i])==0){
  181.                     if(ptr->file!=NULL){
  182.                         ptr->file = realloc(ptr->file, len);
  183.                         strcpy(ptr->file, string);
  184.                         printf("ok");
  185.                         return len;
  186.                     }
  187.                     else{
  188.                         printf("no");
  189.                         return 0;
  190.                     }
  191.                 }
  192.             }
  193.             printf("no");
  194.             return 0;
  195.         }
  196.         else if(percorso[i+1]!=NULL){
  197.             if(ptr->testa)
  198.                 ptr = move(ptr->testa, percorso[i]);
  199.             else{
  200.                 printf("no");
  201.                 return 0;
  202.             }
  203.             if(ptr==NULL){
  204.                 printf("no");
  205.                 return 0;
  206.             }
  207.         }
  208.     }
  209. }
  210. void read(char *path, nodo *head){
  211.     nodo *ptr; char *percorso[255], *p; int check=0, i = 0;
  212.     ptr = head;
  213.     for (p = strtok(path, "/"); p; p = strtok(NULL, "/")){
  214.         percorso[i]=(char*)malloc(strlen(p)*sizeof(char));
  215.         strcpy(percorso[i], p);
  216.         i++;
  217.     }
  218.     percorso[i]=NULL;
  219.     for(i=0; percorso[i]!=NULL; i++){
  220.         if(percorso[i+1]==NULL){
  221.             ptr = ptr->testa;
  222.             while(ptr!=NULL){
  223.                 if(strcmp(ptr->nome, percorso[i])<0)
  224.                     ptr = ptr->left;
  225.                 else if(strcmp(ptr->nome, percorso[i])>0)
  226.                     ptr = ptr->right;
  227.                 else if(strcmp(ptr->nome, percorso[i])==0){
  228.                     if(ptr->file!=NULL){
  229.                         printf("contenuto %s", ptr->file);
  230.                         return;
  231.                     }
  232.                     else{
  233.                         printf("no");
  234.                         return;
  235.                     }
  236.                 }
  237.             }
  238.             printf("no");
  239.             return;
  240.         }
  241.         else if(percorso[i+1]!=NULL){
  242.             if(ptr->testa)
  243.                 ptr = move(ptr->testa, percorso[i]);
  244.             else{
  245.                 printf("no");
  246.                 return;
  247.             }
  248.             if(ptr==NULL){
  249.                 printf("no");
  250.                 return;
  251.             }
  252.         }
  253.     }
  254. }
  255.  
  256. void delete(nodo *head){
  257.     nodo *ptr=head;
  258.     int i=0;
  259.     char *percorso[255], *p, path[255*255];
  260.     scanf("%s", path);
  261.     for (p = strtok(path, "/"); p; p = strtok(NULL, "/")){
  262.         percorso[i]=(char*)malloc(strlen(p)*sizeof(char));
  263.         strcpy(percorso[i], p);
  264.         i++;
  265.     }
  266.     percorso[i]=NULL;
  267.     for(i=0; percorso[i]!=NULL && ptr!=NULL; i++){
  268.         if(ptr->check==1){
  269.             printf("no\n");
  270.             return;
  271.         }
  272.         head=ptr;
  273.         ptr=move(ptr->testa, percorso[i]);
  274.     }
  275.     if(percorso[i]==NULL && ptr!=NULL && ptr->testa==NULL){
  276.         ptr=cancella(head, ptr);
  277.         head->figli-=1;
  278.         if(ptr->file!=NULL)
  279.             free(ptr->file);
  280.         free(ptr);
  281.         printf("ok\n");
  282.         return;
  283.     }
  284.     else{
  285.         printf("no\n");
  286.         return;
  287.     }
  288. }
  289.  
  290. nodo* cancella(nodo *T, nodo *z){
  291.     nodo *x, *y, *ptr = T;
  292.     if(z->left==NULL || z->right == NULL)
  293.         y = z;
  294.     else
  295.         y = tree_successor(z);
  296.     if(y->left != NULL)
  297.         x = y->left;
  298.     else x = y->right;
  299.     if(x!=NULL)
  300.         x->padre = y->padre;
  301.     if(y->padre == NULL)
  302.         T->testa = x;
  303.     else if(y == y->padre->left)
  304.         y->padre->left = x;
  305.     else
  306.         y->padre->right = x;
  307.     if(y!=z){
  308.         strcpy(z->nome, y->nome);
  309.         z->testa=y->testa;
  310.         z->figli=y->figli;
  311.         z->check=y->check;
  312.         z->file=y->file;
  313.     }
  314.     return y;
  315. }
  316. nodo *tree_successor(nodo*x){
  317.     nodo *y;
  318.     if(x->right != NULL)
  319.         return tree_minimum(x->right);
  320.     y = x->padre;
  321.     while(y!=NULL && strcmp(x->nome, y->right->nome)==0){
  322.         x = y;
  323.         y = y->padre;
  324.     }
  325.     return y;
  326. }
  327. nodo* tree_minimum(nodo*x){
  328.     while(x->left!=NULL)
  329.         x = x->left;
  330.     return x;
  331. }
  332.  
  333. void delete_r(nodo *head){
  334.     nodo *ptr=head;
  335.     int i=0;
  336.     char *percorso[255], *p, path[255*255];
  337.     scanf("%s", path);
  338.     for (p = strtok(path, "/"); p; p = strtok(NULL, "/")){
  339.         percorso[i]=(char*)malloc(strlen(p)*sizeof(char));
  340.         strcpy(percorso[i], p);
  341.         i++;
  342.     }
  343.     percorso[i]=NULL;
  344.     for(i=0; percorso[i]!=NULL && ptr!=NULL; i++){
  345.         if(ptr->check==1){
  346.             printf("no\n");
  347.             return;
  348.         }
  349.         head=ptr;
  350.         ptr=move(ptr->testa, percorso[i]);
  351.     }
  352.     if(percorso[i]==NULL && ptr!=NULL){
  353.         cancella_ricorsiva(ptr->testa);
  354.         ptr->testa=NULL;
  355.         ptr=cancella(head, ptr);
  356.         head->figli-=1;
  357.         if(ptr->file!=NULL)
  358.             free(ptr->file);
  359.         free(ptr);
  360.         printf("ok\n");
  361.         return;
  362.     }
  363.     else{
  364.         printf("no\n");
  365.         return;
  366.     }
  367. }
  368.  
  369. void cancella_ricorsiva(nodo *x){
  370.     if(x==NULL)
  371.         return;
  372.     cancella_ricorsiva(x->right);
  373.     cancella_ricorsiva(x->left);
  374.     cancella_ricorsiva(x->testa);
  375.     if(x->file!=NULL)
  376.         free(x->file);
  377.     free(x);
  378.     return;
  379. }
  380.  
  381. void find(nodo *root, char* risorsa, char*percorso, tree *R){
  382.     nodo *ptr; int i;
  383.     ptr = root->testa;
  384.     if(ptr!=NULL){
  385.         if(strcmp(ptr->nome, risorsa)==0){
  386.             if(percorso==NULL)
  387.                 percorso = (char*)malloc(sizeof(char)*strlen(ptr->nome)+1);
  388.             else
  389.                 percorso = realloc(percorso, strlen(percorso)+strlen(ptr->nome)+1);
  390.             strcat(percorso,"/");
  391.             strcat(percorso, ptr->nome);
  392.             if(R == NULL)
  393.                 R = (tree*)malloc(sizeof(tree));
  394.             tree_insert(R, percorso);
  395.             if(ptr->file == NULL && ptr->testa!=NULL){
  396.                 if(percorso==NULL) percorso = (char*)malloc(sizeof(char)*strlen(ptr->nome)+1);
  397.                 else percorso = realloc(percorso, strlen(percorso)+strlen(ptr->nome)+1);
  398.                 strcat(percorso, "/");
  399.                 strcat(percorso, ptr->nome);
  400.                 find(ptr->testa, risorsa, percorso, R);
  401.             }
  402.         }
  403.         else if(ptr->file == NULL && ptr->testa!=NULL){
  404.             if(percorso==NULL) percorso = (char*)malloc(sizeof(char)*strlen(ptr->nome)+1);
  405.             else percorso = realloc(percorso, strlen(percorso)+strlen(ptr->nome)+1);
  406.             strcat(percorso, "/");
  407.             strcat(percorso, ptr->nome);
  408.             find(ptr->testa, risorsa, percorso, R);
  409.         }
  410.         if(ptr->left)
  411.             find(ptr->left, risorsa, percorso, R);
  412.         if(ptr->right)
  413.             find(ptr->right, risorsa, percorso, R);
  414.     }
  415.     else return;
  416.     if(R==NULL){
  417.         printf("1no");
  418.         return;
  419.     }
  420.     else{
  421.         printf("ok");
  422.         inorder_tree_walk(R);
  423.         return;
  424.     }
  425. }
  426.  
  427. void tree_insert(tree *T, char *string){
  428.     tree *z, *y = NULL, *x = T;
  429.     z = (tree*)malloc(sizeof(tree));
  430.     z->left = NULL; z->right = NULL; z->path = (char*)malloc(sizeof(char)*strlen(string)); strcpy(z->path, string); z->padre = NULL;
  431.     while(x!=NULL){
  432.         y=x;
  433.         if(strcmp(z->path, x->path)<0)
  434.             x = x->left;
  435.         else x = x->right;
  436.     }
  437.     if(y==NULL)
  438.         T = z;
  439.     else if(strcmp(z->path, y->path)<0){
  440.         z->padre = y;
  441.         y->left = z;
  442.     }
  443.     else{
  444.         z->padre = y;
  445.         y->right = z;
  446.     }
  447.     return;
  448. }
  449.  
  450. void inorder_tree_walk(tree *x){
  451.     inorder_tree_walk(x->left);
  452.     printf("\n%s",x->path);
  453.     inorder_tree_walk(x->right);
  454.     free(x->path);
  455.     free(x);
  456. }
RAW Paste Data
Top