API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Sep 13th, 2017
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.24 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!