HEAP

SUBMITTED BY: bitcoinsachen

DATE: Dec. 14, 2016, 10:07 p.m.

FORMAT: C

SIZE: 4.7 kB

Raw Download

HITS: 821

Report
  1. #ifndef HEADER_H_INCLUDED
  2. #define HEADER_H_INCLUDED
  3. #include <string.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. typedef struct entry__s
  7. {
  8. char songtitle[256], interpreter[256];
  9. } entry_t;
  10. typedef struct heap__s
  11. {
  12. entry_t *entries;
  13. long size;
  14. long next;
  15. } heap_t;
  16. heap_t *create_heap(long size);
  17. void delete_heap(heap_t *heap);
  18. long compare(heap_t *heap, long index, char songtitle[], char interpreter[]);
  19. long is_empty(heap_t *heap, long index);
  20. void insert_entry(heap_t *heap, char songtitle[], char interpreter[]);
  21. long search_entry(heap_t *heap, char songtitle[], char interpreter[]);
  22. void print_entry(heap_t *heap, long index);
  23. void print(heap_t *heap);
  24. long count_entries(heap_t *heap);
  25. long count_entries_with_songtitle(heap_t *heap, char songtitle[]);
  26. void up_heap(heap_t *heap, long index);
  27. void down_heap(heap_t *heap, long index);
  28. #endif // HEADER_H_INCLUDED
  29. #include "header.h"
  31. heap_t *create_heap(long size)
  32. {
  33. heap_t *new = malloc(sizeof(heap_t));
  34. new->next = 1;
  35. new->size = size + 1;
  36. new->entries = calloc(new->size, sizeof(entry_t));
  37. return new;
  38. }
  40. void delete_heap(heap_t *heap)
  41. {
  42. heap->next = 0;
  43. heap->size = 0;
  44. free(heap->entries);
  45. heap->entries = 0;
  46. }
  48. long compare(heap_t *heap, long index, char songtitle[], char interpreter[])
  49. {
  50. if (index < heap->size && index < heap->next)
  51. {
  52. return strcmp(heap->entries[index].songtitle, songtitle) + strcmp(heap->entries[index].interpreter, interpreter);
  53. }
  54. else
  55. {
  56. return strcmp("", songtitle) + strcmp("", interpreter);
  57. }
  58. }
  60. long is_empty(heap_t *heap, long index)
  61. {
  62. return !compare(heap, index, "", "");
  63. }
  65. void insert_entry(heap_t *heap, char songtitle[], char interpreter[])
  66. {
  67. if (heap->size <= heap->next)
  68. {
  69. heap->size = 2*(heap->size - 1) - 1;
  70. heap->entries = realloc(heap->entries, heap->size * sizeof(entry_t));
  71. }
  72. while (!is_empty(heap, heap->next++));
  73. strcpy(heap->entries[heap->next - 1].songtitle, songtitle);
  74. strcpy(heap->entries[heap->next - 1].interpreter, interpreter);
  75. }
  77. long search_entry(heap_t *heap, char songtitle[], char interpreter[])
  78. {
  79. unsigned long i;
  80. for (i = 1; i < heap->next; i++)
  81. {
  82. if ((strcmp(heap->entries[i].interpreter, interpreter) == 0) && (strcmp(heap->entries[i].songtitle, songtitle) == 0))
  83. return i;
  84. }
  85. return -1;
  86. }
  88. void print_entry(heap_t *heap, long index)
  89. {
  90. if (index < heap->size)
  91. {
  92. fprintf(stdout, "[%ld]\t", index);
  93. fprintf(stdout, "%s\t", heap->entries[index].songtitle);
  94. fprintf(stdout, "%s\n", heap->entries[index].interpreter);
  95. }
  96. }
  98. void print(heap_t *heap)
  99. {
  100. unsigned long i;
  101. fprintf(stdout, "\n");
  102. for (i = 0; i < heap->size; i++)
  103. {
  104. print_entry(heap, i);
  105. }
  106. fprintf(stdout, "Next:\t%ld\n", heap->next);
  107. }
  109. long count_entries(heap_t *heap)
  110. {
  111. return heap->next - 1;
  112. }
  113. long count_entries_with_songtitle(heap_t *heap, char songtitle[])
  114. {
  115. unsigned long i, count = 0;
  116. for (i = 0; i < heap->next; i++)
  117. {
  118. if (!strcmp(heap->entries[i].songtitle, songtitle))
  119. count++;
  120. }
  121. return count;
  122. }
  123. void up_heap(heap_t *heap, long index)
  124. {
  125. }
  126. void down_heap(heap_t *heap, long index)
  127. {
  128. long last = heap->next - 1;
  129. if (2 * index <= last)
  130. {
  131. entry_t temp = heap->entries[index];
  132. while (2 * index <= last)
  133. {
  134. long next = index * 2;
  135. if ((next < last) && (strcmp(heap->entries[next + 1].songtitle, heap->entries[next].songtitle) > 0))
  136. next++;
  137. if (strcmp(temp.songtitle, heap->entries[next].songtitle) >= 0)
  138. break;
  139. memcpy(&heap->entries[index], &heap->entries[next], sizeof(entry_t));
  140. index = next;
  141. }
  142. memcpy(&heap->entries[index], &temp, sizeof(entry_t));
  143. }
  144. }
  145. #include "source.c"
  146. int main()
  147. {
  148. heap_t *heap = create_heap(12);
  149. insert_entry(heap, "B", "1");
  150. insert_entry(heap, "E", "2");
  151. insert_entry(heap, "I", "3");
  152. insert_entry(heap, "S", "4");
  153. insert_entry(heap, "P", "5");
  154. insert_entry(heap, "I", "6");
  155. insert_entry(heap, "E", "7");
  156. insert_entry(heap, "L", "8");
  157. insert_entry(heap, "H", "9");
  158. insert_entry(heap, "E", "10");
  159. insert_entry(heap, "A", "11");
  160. insert_entry(heap, "P", "12");
  161. print(heap);
  162. unsigned long i;
  163. for (i = heap->next - 1; i > 0; i--)
  164. down_heap(heap, i);
  165. print(heap);
  166. delete_heap(heap);
  167. free(heap);
  168. return 0;
  169. }
comments powered by Disqus