daily pastebin goal
16%
SHARE
TWEET

LASD

a guest Mar 13th, 2018 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -------MAIN--------
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include "libreria_heap.h"
  6. #define MAX 50
  7.  
  8. int scelta_arraysize(void);
  9. void riempi_array(int[], int);
  10. int ricerca(int [], int, int);
  11.  
  12. int main()
  13. {
  14.     int dim_array, heapsize, array[], elem, i, indice_elem = 0;
  15.     dim_array = scelta_arraysize();
  16.     riempi_array(array, dim_array);
  17.     //Costruisco heap:
  18.     heapsize = build_heap(array, dim_array);
  19.     //Stampo heap:
  20.     printf("Heap generato:\n");
  21.     for(i = 0; i < dim_array; i++)
  22.         printf("%d ", array[i]);
  23.     do
  24.     {
  25.         printf("\nQuale elemento vuoi eliminare?\n");
  26.         scanf("%d", &elem);
  27.         indice_elem = ricerca(array, elem, dim_array);
  28.         if (indice_elem == - 1)
  29.         printf("Elemento non presente.\n");
  30.     }while(indice_elem == - 1);
  31.     heapsize = delete_elem(array, heapsize, indice_elem);
  32.     printf("Nuovo heap:\n");
  33.     for(i = 0; i < dim_array; i++)
  34.         printf("%d ", array[i]);
  35.        
  36.     return 0;
  37. }
  38.  
  39. int ricerca(int array[], int elem, int dim_array)
  40. {
  41.     int indice_array;
  42.     for(indice_array = 0; indice_array < dim_array; indice_array++)
  43.     {
  44.         if(array[indice_array] == elem)
  45.             return indice_array;
  46.     }
  47.     return -1;
  48. }
  49.  
  50. int scelta_arraysize(void)
  51. {
  52.     printf("Quanti elementi vuoi inserire nell'array?\n");
  53.     do
  54.     {
  55.         scanf("%d", &dim_array);
  56.         if(dim_array > MAX)
  57.             printf("\nMassima dimensione dell'array e' %d! Inserire dimensione:\n", MAX);
  58.     }while(dim_array > MAX);
  59. }
  60.  
  61. void riempi_array(int array[], int dim_array)
  62. {
  63.     int i, x;
  64.     srand(time(NULL));
  65.     printf("Come vuoi riempire l'array?\n1. Manualmente\n2.Casualmente");
  66.     scanf("%d", &x);
  67.     switch(x)
  68.     {
  69.         case 1:
  70.             printf("Dammi gli elementi dello heap (solo elementi positivi):\n");
  71.             for(i = 0; i < dim_array; i++)
  72.                 scanf("%d", &array[i]);
  73.             break;
  74.         case 2:
  75.             //Riempio l'array con numeri da 1 a 50 scelti da una distribuzione pseudocasuale:
  76.             for(i = 0; i < dim_array; i++)
  77.                 array[i] = rand() % 50 + 1;
  78.             break;
  79.     }
  80.     printf("Array riempito correttamente!\n");
  81.     return;
  82. }
  83.  
  84. ----- libreria_heap.h -----
  85. int left(int);
  86. int right(int);
  87. int parent(int);
  88. void heapify(int [], int, int);
  89. void build_heap(int [], int);
  90. void heapsort(int []);
  91. void swap(int, int, int[]);
  92.  
  93. ----- libreria_heap.c -----
  94. #include <stdio.h>
  95. #include <stdlib.h>
  96. #include "libreria_heap.h"
  97.  
  98. int left(int);
  99. int right(int);
  100. int parent(int);
  101. void heapify(int [], int, int);
  102. void build_heap(int [], int);
  103. void heapsort(int []);
  104. void swap(int, int, int[]);
  105. int delete_elem(int [], int, int);
  106.  
  107. void heapify(int array[], int nodo, int dim_array)
  108. {
  109.     int figlio_sx, figlio_dx, largest, heapsize = dim_array;
  110.     figlio_sx = left(nodo);
  111.     figlio_dx = right(nodo);
  112.     if (figlio_sx < heapsize && A[figlio_sx] > A[nodo])
  113.         largest = figlio_sx
  114.     else
  115.         largest = nodo;
  116.     if (figlio_dx < heapsize && A[figlio_dx] > A[largest])
  117.         largest = figlio_dx
  118.     if(nodo != largest)
  119.     {
  120.         swap(nodo, largest, array);
  121.         heapify(array, largest, dim_array);
  122.     }
  123.     return;
  124. }
  125.  
  126. int build_heap(int A[], int dim_array)
  127. {
  128.     int i, heapsize;
  129.     heapsize = dim_array;
  130.     for (i=ArraySize/2; i>=0; i--)
  131.         heapify(A, i, dim_array);
  132.     return heapsize;
  133. }
  134.  
  135. void heapsort(int A[], int dim_array)
  136. {
  137.     int i, heapsize;
  138.     heapsize = dim_array;
  139.     build_heap(A, dim_array);
  140.     for (i = dim_array - 1; i >= 1; i--) {
  141.         swap(0, i, A);
  142.         heapsize--;
  143.         heapify(A, 0, dim_array);
  144.     }
  145. }
  146.  
  147. void swap(int i, int j, int A[])
  148. {
  149.     int tmp = A[i];
  150.     A[i] = A[j];
  151.     A[j] = tmp;
  152. }
  153.  
  154. int left(int i)
  155. {
  156.     return 2*i + 1;
  157. }
  158.  
  159. int right(int i)
  160. {
  161.     return 2*i + 2;
  162. }
  163.  
  164. int parent(int i)
  165. {
  166.     return (i-1)/2;
  167. }
  168.  
  169. int delete_elem(int array[], int heapsize, int indice_elem)
  170. {
  171.     array[indice_elem] = -1;
  172.     heapify(array, indice_elem, heapsize);
  173.     return heapsize - 1;
  174. }
RAW Paste Data
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
 
Top