API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 15th, 2019
127
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 12.06 KB | None | 0 0
raw download clone embed print report
  1. Alumnos: Ortega(104548), Andrade (104046) corrector Adeodato Grupo G18
  2. #include <stdbool.h>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <stdint.h>
  6. #include <string.h>
  7. #include "heap.h"
  8. #define CAP_I 37
  9. #define PORCENTAJE_REDIMENSION 4
  10.  
  11. struct heap{
  12.     cmp_func_t cmp;
  13.     void** arr;
  14.     size_t cantidad;
  15.     size_t capacidad;
  16. };
  17. int ob_padre(size_t pos){
  18.     return ((int)pos - 1)/2;
  19. }
  20. size_t ob_hijo_i (size_t pos){
  21.     return 2 * pos + 1;
  22. }
  23. size_t ob_hijo_d (size_t pos){
  24.     return 2*pos+2;
  25. }
  26. void swap (void** arr,size_t i,size_t j){
  27.     void* aux = arr[i];
  28.     arr[i] = arr[j];
  29.     arr[j] = aux;
  30. }
  31. void upheap (void** arr,cmp_func_t cmp,size_t inicio,size_t act,size_t final){
  32.     if (act <= inicio || act >= final) return;
  33.     int i = (int)act;
  34.     while (i > (int)inicio){
  35.         int padre = ob_padre(i);
  36.         if (padre <inicio) return;
  37.         if (cmp(arr[i],arr[padre])>0){
  38.             swap(arr,i,padre);
  39.             i = padre;
  40.         }
  41.         else return;
  42.     }
  43.     return;
  44. }
  45. void downheap(void** arr,cmp_func_t cmp,size_t inicio,size_t act,size_t final){
  46.     if (act < inicio || act >= final || inicio == final) return;
  47.     size_t i = act;
  48.  
  49.     while (i < final){
  50.         size_t hijo_d = ob_hijo_d(i);
  51.         size_t hijo_i = ob_hijo_i(i);
  52.         if(hijo_d < final && hijo_i < final){
  53.             size_t aux = 0;
  54.             if (cmp(arr[hijo_d],arr[hijo_i]) > 0){
  55.                 aux = hijo_d;
  56.             }
  57.             else aux = hijo_i;
  58.             if (cmp(arr[aux],arr[i]) > 0 ){
  59.                 swap(arr,aux,i);
  60.                 i = aux;
  61.                 continue;
  62.             }
  63.             else return;
  64.         }
  65.         else if (hijo_d < final){      
  66.             if (cmp(arr[hijo_d],arr[i])>0){
  67.                 swap(arr,i,hijo_d);
  68.                 i = hijo_d;
  69.                 continue;
  70.             }
  71.         }
  72.         else if (hijo_i < final){
  73.             if (cmp(arr[hijo_i],arr[i])>0){
  74.                 swap(arr,i,hijo_i);
  75.                 i = hijo_i;
  76.                 continue;
  77.             }
  78.             return;
  79.         }
  80.         else return;
  81.  
  82.     }
  83.     return;
  84. }
  85.  
  86. void heapify (void** arr,size_t cant,cmp_func_t cmp){
  87.     for (int i = (int)cant - 1 ; i >= 0 ; i--){
  88.         downheap(arr,cmp,0,i,cant);
  89.     }
  90.  
  91. }
  92.  
  93. heap_t *heap_crear_arr(void *arreglo[], size_t n, cmp_func_t cmp){
  94.     heap_t* heap = malloc(sizeof(heap_t));
  95.  
  96.     if(!heap) return NULL;
  97.     void** aux = calloc(n*2,sizeof(void*)*2*n);
  98.  
  99.     if (!aux){
  100.         free(heap);
  101.         return NULL;
  102.     }
  103.     for(int i =0; i<n;i++) aux[i] = arreglo[i];
  104.  
  105.     heapify(aux,n,cmp);
  106.  
  107.     heap->cantidad = n;
  108.     heap->capacidad = n*2;
  109.     heap->arr = aux;
  110.     heap->cmp = cmp;
  111.     return heap;
  112.  
  113. }
  114.  
  115. heap_t *heap_crear(cmp_func_t cmp){
  116.     heap_t* heap = malloc(sizeof(heap_t));
  117.  
  118.     if(!heap) return NULL;
  119.     void** arreglo = calloc(CAP_I,sizeof(void*)* CAP_I);
  120.  
  121.     if (!arreglo){
  122.         free(heap);
  123.         return NULL;
  124.     }
  125.  
  126.     heap->cantidad = 0;
  127.     heap->capacidad = CAP_I;
  128.     heap->arr = arreglo;
  129.     heap->cmp = cmp;
  130.     return heap;
  131. }
  132.  
  133. bool redimensionar (heap_t* heap,size_t num){
  134.     void** arreglo = realloc(heap->arr,sizeof(void*)*num);
  135.     if (!arreglo) return false;
  136.  
  137.     heap->arr = arreglo;
  138.     heap->capacidad = num;
  139.     return true;
  140. }
  141.  
  142. size_t heap_cantidad(const heap_t* heap){
  143.     return heap->cantidad;
  144. }
  145.  
  146. bool heap_encolar(heap_t *heap, void *elem){
  147.  
  148.     if (heap->cantidad == heap->capacidad){
  149.         bool rta = redimensionar(heap,heap->capacidad*2);
  150.  
  151.         if (!rta) return false;
  152.     }
  153.  
  154.     heap->arr[heap->cantidad] = elem;
  155.     upheap(heap->arr,heap->cmp,0,heap->cantidad,heap->cantidad+1);
  156.     heap->cantidad++;
  157.     return true;
  158. }
  159.  
  160. void *heap_ver_max(const heap_t *heap){
  161.     return heap->arr[0];
  162. }
  163.  
  164. void heap_sort(void *elementos[], size_t cant, cmp_func_t cmp){
  165.     heapify(elementos,cant,cmp);
  166.  
  167.     for (int i = (int)cant-1; i>0; i--){
  168.         swap(elementos,0,i);
  169.         downheap(elementos,cmp,0,0,i);
  170.     }
  171. }
  172.  
  173. void heap_destruir(heap_t *heap, void destruir_elemento(void *e)){
  174.     void** arr = heap->arr;
  175.  
  176.     if(destruir_elemento){
  177.         size_t i = 0;
  178.  
  179.         while(i<heap->cantidad){
  180.             destruir_elemento(arr[i]);
  181.             i++;
  182.         }
  183.     }
  184.     free(arr);
  185.     free(heap);
  186. }
  187.  
  188. bool heap_esta_vacio(const heap_t *heap){
  189.  
  190.     if(heap->cantidad == 0) return true;
  191.     return false;
  192. }
  193.  
  194. void *heap_desencolar(heap_t *heap){
  195.  
  196.     if((heap->capacidad >= CAP_I) && ((heap->capacidad) / PORCENTAJE_REDIMENSION >= heap->cantidad)){
  197.         redimensionar(heap,heap->capacidad / 2);
  198.     }
  199.  
  200.     if (heap_esta_vacio(heap)) return NULL;
  201.  
  202.     if (heap->cantidad == 1){
  203.         void* elem = heap->arr[0];
  204.         heap->arr[0] = NULL;
  205.         heap->cantidad = 0;
  206.         return elem;
  207.     }
  208.  
  209.     void* elem = heap->arr[0];
  210.     swap(heap->arr,0,heap->cantidad -1);
  211.     heap->arr[heap->cantidad -1] = NULL;
  212.     heap->cantidad --;
  213.     downheap(heap->arr,heap->cmp,0,0,heap->cantidad);
  214.  
  215.     return elem;
  216. }
  217.  
  218. /************* PRUEBAS ***************/
  219. #include "heap.h"
  220. #include "testing.h"
  221. #include <stddef.h>
  222. #include <stdlib.h>
  223. #include <stdio.h>
  224. #include <string.h>
  225.  
  226. /* Prototipo de función de comparación que se le pasa como parámetro a las
  227.  * diversas funciones del heap.
  228.  * Debe recibir dos punteros del tipo de dato utilizado en el heap, y
  229.  * debe devolver:
  230.  *   menor a 0  si  a < b
  231.  *       0      si  a == b
  232.  *   mayor a 0  si  a > b
  233.  */
  234. int cmp_func(const void *a, const void *b){
  235.     if (*(int*)a < *(int*)b ) return -1;
  236.     if (*(int*)a == *(int*)b ) return 0;
  237.     return 1;
  238. }
  239.  
  240. void** arreglo(){
  241.     void** arr = malloc(sizeof(void*) * 5);
  242.     int* n4 = malloc(sizeof(int));
  243.     int* n2 = malloc(sizeof(int));
  244.     int* n9 = malloc(sizeof(int));
  245.     int* n1 = malloc(sizeof(int));
  246.     int* n20 = malloc(sizeof(int));
  247.     *n4 = 4, *n2 = 2, *n9 = 9, *n1 = 1, *n20 = 20;
  248.     arr[0] = n4;
  249.     arr[1] = n2;
  250.     arr[2] = n9;
  251.     arr[3] = n1;
  252.     arr[4] = n20;
  253.     return arr;
  254. }
  255.  
  256. void pruebas_heap_vacio(){
  257.     heap_t* heap = heap_crear(cmp_func);
  258.     print_test("El heap fue creado correctamente",heap != NULL);
  259.     print_test("No puedo desencolar en una heap vacío",heap_desencolar(heap) == NULL);
  260.     print_test("No puedo ver el máximo de un heap vacío",heap_ver_max(heap) == NULL);
  261.     print_test("La cantidad de un heap vacío es 0",heap_cantidad(heap) == 0);
  262.     print_test("Compruebo si el heap esta vacío",heap_esta_vacio(heap) == true);
  263.     heap_destruir(heap,NULL);
  264.     print_test("El heap fue destruido correctamente",true);
  265. }
  266.  
  267. void pruebas_comportamiento_heap() {
  268.     heap_t* heap = heap_crear(cmp_func);
  269.     int valor1 = 4, valor2 = 3, valor3 = 2, valor4 = 1;
  270.     int* elemento1 = &valor1;
  271.     int* elemento2 = &valor2;
  272.     int* elemento3 = &valor3;
  273.     int* elemento4 = &valor4;
  274.     print_test("Se encolo el elemento1",heap_encolar(heap,elemento1)== true);
  275.     print_test("Se encolo el elemento2",heap_encolar(heap,elemento2)== true);
  276.     print_test("Se encolo el elemento3",heap_encolar(heap,elemento3)== true);
  277.     print_test("Se encolo el elemento4",heap_encolar(heap,elemento4)== true);
  278.     print_test("El maximo del heap es elemento1",heap_ver_max(heap) == elemento1);
  279.     print_test("Desencolo",heap_desencolar(heap) == elemento1);
  280.     print_test("El maximo del heap es elemento2",heap_ver_max(heap) == elemento2);
  281.     print_test("Desencolo",heap_desencolar(heap) == elemento2);
  282.     print_test("El maximo del heap es elemento3",heap_ver_max(heap) == elemento3);
  283.     print_test("Desencolo",heap_desencolar(heap) == elemento3);
  284.     print_test("El maximo del heap es elemento4",heap_ver_max(heap) == elemento4);
  285.     print_test("Desencolo",heap_desencolar(heap) == elemento4);
  286.     print_test("El maximo del heap es NULL",heap_ver_max(heap) == NULL);
  287.     print_test("El heap está vacío",heap_esta_vacio(heap) == true);
  288.     print_test("No puedo desencolar en un heap vacío",heap_desencolar(heap) == NULL);
  289.     print_test("No puedo ver el maximo de un heap vacío",heap_ver_max(heap) == NULL);
  290.     heap_destruir(heap,NULL);
  291.     print_test("El heap fue destruido correctamente",true);
  292. }
  293.  
  294. void prueba_volumen (){
  295.     heap_t* heap = heap_crear(cmp_func);
  296.     int j;
  297.     int* vector = malloc(sizeof(int) * 10000);
  298.     for (int i = 0; i != 10000 ;i++){
  299.         vector[i] = i;
  300.         heap_encolar(heap,&vector[i]);
  301.     }
  302.     print_test("La cantidad en el heap es 1000",heap_cantidad(heap) == 10000);
  303.     for (j = 9999; j >= 0 ;j--){
  304.         bool desencolo_bien = *(int*)heap_desencolar(heap) == j;
  305.         if (desencolo_bien == false){
  306.             print_test("No se pudo desencolar correctamente", false);
  307.         }
  308.         bool comprobar_largo = heap_cantidad(heap) == j;
  309.         if(comprobar_largo == false){
  310.             print_test("Fallo la cantidad del heap", false);
  311.         }
  312.     }
  313.     print_test("Encolar y desencolar 10000 elementos",heap_esta_vacio(heap));
  314.     heap_destruir(heap,NULL);
  315.     free(vector);
  316. }
  317.  
  318. int _strcmp(const void* a,const void* b){
  319.     return strcmp((char*) a,(char*) b);
  320. }
  321.  
  322. void prueba_volumen_iguales(){
  323.     heap_t* heap = heap_crear(_strcmp);
  324.     char* cadenas[] = {"aaaa","abab","acac","adad","afaf","agag","amam","axax","azaz"};
  325.     for (int i = 0; i < 800;i++){
  326.         heap_encolar(heap,cadenas[i%8]);
  327.     }
  328.     int contar = 799;
  329.     while(!heap_esta_vacio(heap)){
  330.  
  331.         int actual = 0;
  332.         if (contar >= 700) actual = 7;
  333.         else if (contar >= 600) actual = 6;
  334.         else if (contar >= 500) actual = 5;
  335.         else if (contar >= 400) actual = 4;
  336.         else if (contar >= 300) actual = 3;
  337.         else if (contar >= 200) actual = 2;
  338.         else if (contar >= 100) actual = 1;
  339.         bool desencolo_bien = (char*)heap_desencolar(heap) == cadenas[actual];
  340.         if (desencolo_bien == false){
  341.             print_test("No se pudo desencolar correctamente", false);
  342.         }
  343.         contar--;
  344.     }
  345.     heap_destruir(heap,NULL);
  346. }
  347. void prueba_destruccion_heap_NULL() {
  348.     heap_t* heap = heap_crear(cmp_func);
  349.     int valor1 = 1, valor2 = 2, valor3 = 3;
  350.     int* elemento1 = &valor1;
  351.     int* elemento2 = &valor2;
  352.     int* elemento3 = &valor3;
  353.     print_test("Se encolo el elemento1",heap_encolar(heap,elemento1) == true);
  354.     print_test("Se encolo el elemento2",heap_encolar(heap,elemento2) == true);
  355.     print_test("Se encolo el elemento3",heap_encolar(heap,elemento3) == true);
  356.     heap_destruir(heap,NULL);
  357.     print_test("El heap ha sido destruido correctamente",true);
  358. }
  359.  
  360. void prueba_destruccion_heap_free() {
  361.     heap_t* heap = heap_crear(cmp_func);
  362.     int* elemento1 = malloc(sizeof(int));
  363.     int* elemento2 = malloc(sizeof(int));
  364.     int* elemento3 = malloc(sizeof(int));
  365.     int* elemento4 = malloc(sizeof(int));
  366.     int* elemento5 = malloc(sizeof(int));
  367.     int* elemento6 = malloc(sizeof(int));
  368.     *elemento1 = 1, *elemento2 = 2, *elemento3 = 4, *elemento4 = 4, *elemento5 = 5, *elemento6 = 6;
  369.     print_test("Se encolo el elemento2",heap_encolar(heap,elemento2) == true);
  370.     print_test("Se encolo el elemento3",heap_encolar(heap,elemento3) == true);
  371.     print_test("Se encolo el elemento5",heap_encolar(heap,elemento5) == true);
  372.     print_test("Se encolo el elemento6",heap_encolar(heap,elemento6) == true);
  373.     print_test("Se encolo el elemento1",heap_encolar(heap,elemento1) == true);
  374.     print_test("Se encolo el elemento4",heap_encolar(heap,elemento4) == true);
  375.     print_test("El máximo es 6",*(int*)heap_ver_max(heap) == 6);
  376.     heap_destruir(heap,free);
  377.     print_test("El heap fue destruido correctamente",true);
  378. }
  379.  
  380. void prueba_crear_arr(){
  381.     void** arr = arreglo();
  382.     heap_t* elem_a_borrar = heap_crear(cmp_func);
  383.     for(size_t i = 0; i < 5; i++){
  384.         heap_encolar(elem_a_borrar,arr[i]);
  385.     }
  386.     heap_t* heap = heap_crear_arr(arr,5,cmp_func);
  387.     print_test("El max del heap es 20",*(int*)heap_ver_max(heap) == 20);
  388.     print_test("Desencolo",*(int*)heap_desencolar(heap) == 20);
  389.     print_test("El max del heap es 9",*(int*)heap_ver_max(heap) == 9);
  390.     print_test("Desencolo",*(int*)heap_desencolar(heap) == 9);
  391.     print_test("El max del heap es 4",*(int*)heap_ver_max(heap) == 4);
  392.     print_test("Desencolo",*(int*)heap_desencolar(heap) == 4);
  393.     print_test("El max del heap es 2",*(int*)heap_ver_max(heap) == 2);
  394.     print_test("Desencolo",*(int*)heap_desencolar(heap) == 2);
  395.     print_test("El max del heap es 1",*(int*)heap_ver_max(heap) == 1);
  396.     print_test("Desencolo",*(int*)heap_desencolar(heap) == 1);
  397.     print_test("El max del heap es NULL",heap_ver_max(heap) == NULL);
  398.     heap_destruir(elem_a_borrar,free);
  399.     heap_destruir(heap,NULL);
  400.     print_test("El heap se destruyo correctamente",true);
  401.     free(arr);
  402. }
  403.  
  404. void prueba_heapsort(){
  405.     void** arr = arreglo();
  406.     bool esta_bien = true;
  407.     heap_sort(arr ,5 ,cmp_func);
  408.     for(int i = 0; i < 4 ; i ++){
  409.         if(*(int*)arr[i] > *(int*)arr[i+1]){
  410.             esta_bien = false;
  411.             break;
  412.         }
  413.     }
  414.     print_test("Se ordeno bien",esta_bien);
  415.     for(int j = 0 ; j < 5; j++ ){
  416.         free(arr[j]);
  417.     }
  418.     free(arr);
  419. }
  420.  
  421. void pruebas_heap_alumno(){
  422.     pruebas_heap_vacio();
  423.     pruebas_comportamiento_heap();
  424.     prueba_volumen();
  425.     prueba_destruccion_heap_NULL();
  426.     prueba_destruccion_heap_free();
  427.     prueba_crear_arr();
  428.     prueba_heapsort();
  429.     prueba_volumen_iguales();
  430. }
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!