Advertisement
ITAsimo456

Lista con funzioni ricorsive

Apr 10th, 2021 (edited)
557
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.50 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct Lista {
  6.     int data;
  7.     Lista* next;
  8. };
  9.  
  10. // Elimina l'intera lista list.
  11. void list_delete(Lista* list) {
  12.     if (list != NULL) {
  13.         list_delete(list->next);
  14.         delete list;
  15.     }
  16. }
  17.  
  18. // Elimina la testa di list e restituisce la nuova testa.
  19. Lista* list_delete_head(Lista* list) {
  20.     Lista* new_head = list->next;
  21.     delete list;
  22.     return new_head;
  23. }
  24.  
  25. // Aggiunge un elemento alla testa di list, o crea una nuova lista se list è NULL.
  26. Lista* list_add_elem(Lista* list, int val) {
  27.     return new Lista { val, list };
  28. }
  29.  
  30. // Aggiunge i primi n_vals valori da vals all'inizio di list, e restituisce la nuova testa.
  31. Lista* list_add_elems(Lista* list, int vals[], int n_vals) {
  32.     if (n_vals > 0) {
  33.         list = list_add_elems(list, vals + 1, n_vals - 1);
  34.         list = list_add_elem(list, vals[0]);
  35.     }
  36.  
  37.     return list;
  38. }
  39.  
  40. // Restituisce il primo nodo in list che ha valore val.
  41. Lista* list_search(Lista* list, int val) {
  42.     if (list == NULL)
  43.         return NULL;
  44.     else if (list->data == val)
  45.         return list;
  46.     else
  47.         return list_search(list->next, val);
  48. }
  49.  
  50. // Stampa list su stdout.
  51. void list_print(Lista* list) {
  52.     if (list != NULL) {
  53.         cout << list->data << " ";
  54.         list_print(list->next);
  55.     }
  56. }
  57.  
  58. // Restituisce la lunghezza di list.
  59. int list_length(Lista* list) {
  60.     if (list == NULL)
  61.         return 0;
  62.     else
  63.         return 1 + list_length(list);
  64. }
  65.  
  66. // Conta le istanze di val in list.
  67. int list_count(Lista* list, int val) {
  68.     if (list == NULL)
  69.         return 0;
  70.     else
  71.         return (list->data == val) + list_count(list->next, val);
  72. }
  73.  
  74. // Cancella elem da list, e restituisce la nuova testa di list.
  75. Lista* list_delete_elem(Lista* list, Lista* elem) {
  76.     if (list != NULL) {
  77.         Lista* next = list->next;
  78.  
  79.         if (list == elem)
  80.             return list_delete_head(list);
  81.  
  82.         if (next != NULL)
  83.             list->next = list_delete_elem(next, elem);
  84.     }
  85.  
  86.     return list;
  87. }
  88.  
  89. // Cancella tutte le istanze di val in list e restituisce la nuova testa di list.
  90. Lista* list_cancella(Lista* list, int val) {
  91.     if (list != NULL) {
  92.         Lista* next = list->next;
  93.  
  94.         if (next != NULL)
  95.             list->next = list_cancella(next, val);
  96.  
  97.         if (list->data == val)
  98.             return list_delete_head(list);
  99.     }
  100.  
  101.     return list;
  102. }
  103.  
  104. // Restituisce la testa di una copia di list.
  105. Lista* list_copia(Lista* list) {
  106.     if (list == NULL)
  107.         return NULL;
  108.  
  109.     Lista* copia_nodo = list_add_elem(NULL, list->data);
  110.     copia_nodo->next = list_copia(list->next);
  111.     return copia_nodo;
  112. }
  113.  
  114. // Elimina l'ultimo elemento di list.
  115. Lista* list_delete_tail_elem(Lista* list) {
  116.     if (list != NULL) {
  117.         if (list->next == NULL)
  118.             return list_delete_head(list); // Restituisce sempre NULL.
  119.  
  120.         list->next = list_delete_tail_elem(list->next);
  121.     }
  122.  
  123.     return list;
  124. }
  125.  
  126. // Inserisce un elemento in list, solo se non esiste già. (aggiunta a set)
  127. Lista* list_add(Lista* list, int val) {
  128.     if (list_search(list, val) == NULL)
  129.         return list_add_elem(list, val);
  130.  
  131.     return list;
  132. }
  133.  
  134.  
  135. // Restituisce la testa di una nuova lista, quale risultato dell'unione insiemistica tra a e b.
  136. Lista* list_union(Lista* a, Lista* b) {
  137.     if (a == NULL && b == NULL)
  138.         return NULL;
  139.  
  140.     Lista* risultato;
  141.  
  142.     if (a == NULL)
  143.         risultato = list_union(NULL, b->next);
  144.     else if (b == NULL)
  145.         risultato = list_union(a->next, NULL);
  146.     else
  147.         risultato = list_union(a->next, b->next);
  148.  
  149.     if (a != NULL)
  150.         risultato = list_add(risultato, a->data);
  151.  
  152.     if (b != NULL)
  153.         risultato = list_add(risultato, b->data);
  154.  
  155.     return risultato;
  156. }
  157.  
  158. // Restituisce la testa di una nuova lista, quale risultato dell'intersezione insiemistica tra a e b.
  159. Lista* list_intersect(Lista* a, Lista* b) {
  160.     if (a == NULL || b == NULL)
  161.         return NULL;
  162.  
  163.     Lista* risultato = list_intersect(a->next, b);
  164.  
  165.     if (list_search(b, a->data))
  166.         risultato = list_add(risultato, a->data);
  167.  
  168.     return risultato;
  169. }
  170.  
  171. // Restituisce la testa di una nuova lista, quale risultato della differenza insiemistica a - b.
  172. Lista* list_difference(Lista* a, Lista* b) {
  173.     if (a == NULL || b == NULL)
  174.         return NULL;
  175.    
  176.     Lista* risultato = list_difference(a->next, b);
  177.  
  178.     if (!list_search(b, a->data))
  179.         risultato = list_add(risultato, a->data);
  180.  
  181.     return risultato;
  182. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement