C语言实现堆数据结构和基本操作

lccpcc

1. #include <stdlib.h>
   
2. #include <stdbool.h>
   
3. #include <assert.h>
   
4. #include <string.h>
   
5. 
   
6. typedef int HPDateType;
   
7. 
   
8. typedef struct Heap
   
9. {
   
10.     HPDateType *a;
    
11.     int size;
    
12.     int capacity;
    
13. } HP;
    
14. 
    
15. void HeapInit(HP *php, HPDateType *a, int n);
    
16. void HeapDestroy(HP *php);                    
    
17. void HeapPush(HP *php, HPDateType x);     
    
18. void HeapPop(HP *php);                       
    
19. HPDateType HeapTop(HP *php);              
    
20. int HeapSize(HP *php);                     
    
21. bool HeapEmpty(HP *php);                 
    
22. void HeapPrint(HP *php);                  
    
23. void AdjustUp(HP *st, int child);         
    
24. void AdjustDown(HP *st, int praent);           
    
25. void Swap(int *p1, int *p2);               
    
26. void HeapSort(HP *php);                  
    
27. 
    
28. 
    
29. </div><div yne-bulb-block="code" data-theme="default" style="white-space:pre-wrap;" data-language="c">int main(int argc, char **argv)
    
30. {
    
31.     HP st;
    
32.     int a[] = {15, 18, 28, 34, 65, 19, 49, 25, 37, 27};
    
33.     int n = sizeof(a) / sizeof(a[0]);
    
34. 
    
35.     printf("\ntest HeapInit(), HeapPrint():\n");
    
36.     HeapInit(&st, a, n);
    
37.     HeapPrint(&st);
    
38. 
    
39.     printf("\ntest HeapPush(&st, 8):\n");
    
40.     HeapPush(&st, 8);
    
41.     HeapPrint(&st);
    
42. 
    
43.     printf("\ntest HeapPush(&st, 88):\n");
    
44.     HeapPush(&st, 88);
    
45.     HeapPrint(&st);
    
46. 
    
47.     printf("\ntest HeapPop(&st):\n");
    
48.     HeapPop(&st);
    
49.     HeapPrint(&st);
    
50. 
    
51.     printf("\ntest HeapPop(&st):\n");
    
52.     HeapPop(&st);
    
53.     HeapPrint(&st);
    
54. 
    
55.     printf("\n对堆进行排序：\n");
    
56.     HeapSort(&st);
    
57.     HeapPrint(&st);
    
58. 
    
59. 
    
60.     /* 销毁堆 */
    
61.     HeapDestroy(&st);
    
62. 
    
63.     if(st.a == NULL)
    
64.         printf("\n销毁堆成功\n");
    
65. 
    
66.     return 0;
    
67. }
    
68. 
    
69. // 交换
    
70. void Swap(int *p1, int *p2)
    
71. {
    
72.     int temp = *p1;
    
73.     *p1 = *p2;
    
74.     *p2 = temp;
    
75. }
    
76. 
    
77. // 向上调整算法
    
78. void AdjustUp(HP *st, int child)
    
79. {
    
80.     int parent = (child - 1) / 2;
    
81. 
    
82.     while (child > 0)
    
83.     {
    
84.         if (st->a[child] < st->a[parent])
    
85.         {
    
86.             Swap(&st->a[child], &st->a[parent]);
    
87.             child = parent;
    
88.             parent = (child - 1) / 2;
    
89.         }
    
90.         else
    
91.         {
    
92.             break;
    
93.         }
    
94.     }
    
95. }
    
96. 
    
97. // 向下调整算法
    
98. void AdjustDown(HP *st, int praent)
    
99. {
    
100.     int child = praent * 2 + 1;
     
101. 
     
102.     while (child < st->size)
     
103.     {
     
104.         if (child + 1 < st->size && st->a[child + 1] < st->a[child])
     
105.         {
     
106.             child++;
     
107.         }
     
108. 
     
109.         if (st->a[child] < st->a[praent])
     
110.         {
     
111.             Swap(&st->a[child], &st->a[praent]);
     
112.             praent = child;
     
113.             child = praent * 2 + 1;
     
114.         }
     
115.         else
     
116.         {
     
117.             break;
     
118.         }
     
119.     }
     
120. }
     
121. 
     
122. void HeapInit(HP *php, HPDateType *a, int n)
     
123. {
     
124.     if (php == NULL)
     
125.         return;
     
126. 
     
127.     php->a = (HPDateType *)calloc(1, sizeof(HPDateType) * n);
     
128. 
     
129.     if (php->a == NULL)
     
130.         exit(EXIT_FAILURE);
     
131. 
     
132.     memcpy(php->a, a, sizeof(HPDateType) * n);
     
133.     php->capacity = n;
     
134.     php->size = n;
     
135. 
     
136.     int i;
     
137. 
     
138.     //建小堆
     
139.     for (i = (php->size - 2) / 2; i >= 0; i--)
     
140.         AdjustDown(php, i);
     
141. }
     
142. 
     
143. void HeapDestroy(HP *php)
     
144. {
     
145.     if (php == NULL)
     
146.         return;
     
147. 
     
148.     free(php->a);
     
149.     php->a = NULL;
     
150.     php->size = 0;
     
151.     php->capacity = 0;
     
152. }
     
153. 
     
154. //在堆里面插入一个数，并且让它的结构还是一个堆
     
155. void HeapPush(HP *php, HPDateType x)
     
156. {
     
157.     if (php == NULL)
     
158.         return;
     
159. 
     
160.     /* 如果堆的空间满了，就用realloc()重新扩大堆的数组空间的大小 */
     
161.     if (php->size == php->capacity)
     
162.     {
     
163.         HPDateType *temp = (HPDateType *)realloc(php->a, sizeof(HPDateType) * php->capacity * 2);
     
164.         if (temp == NULL)
     
165.             exit(EXIT_FAILURE);
     
166. 
     
167.         php->a = temp;
     
168.         php->capacity = php->capacity * 2;
     
169.     }
     
170. 
     
171.     php->a[php->size] = x;
     
172.     php->size++;
     
173. 
     
174.     AdjustUp(php, php->size - 1);
     
175. }
     
176. 
     
177. //删除堆的顶的数据，并且让它的结构还是一个堆
     
178. void HeapPop(HP *php)
     
179. {
     
180.     if (php == NULL)
     
181.         return;
     
182. 
     
183.     if (HeapEmpty(php))
     
184.         return;
     
185. 
     
186.     int end = php->size - 1;
     
187. 
     
188.     Swap(&php->a[0], &php->a[end]);
     
189.     php->size--;
     
190. 
     
191.     AdjustDown(php, 0);
     
192. }
     
193. 
     
194. //返回堆顶的数据
     
195. HPDateType HeapTop(HP *php)
     
196. {
     
197.     if (php == NULL)
     
198.         return;
     
199. 
     
200.     if (HeapEmpty(php))
     
201.         return;
     
202. 
     
203.     return php->a[0];
     
204. }
     
205. 
     
206. //返回堆里面数据的个数
     
207. int HeapSize(HP *php)
     
208. {
     
209.     if (php == NULL)
     
210.         return;
     
211. 
     
212.     return php->size;
     
213. }
     
214. 
     
215. //判断堆是否为空
     
216. bool HeapEmpty(HP *php)
     
217. {
     
218.     if (php == NULL)
     
219.         return;
     
220.     return (php->size == 0);
     
221. }
     
222. 
     
223. //将堆打印出来
     
224. void HeapPrint(HP *php)
     
225. {
     
226.     int i;
     
227.     int m = 1, n = 0;
     
228. 
     
229.     printf("\n从上到下输出堆的内容：\n");
     
230. 
     
231.     for (i = 0; i < php->size; i++)
     
232.     {
     
233.         printf("%d ", php->a[i]);
     
234.         if (i == n)
     
235.         {
     
236.             putchar('\n');
     
237.             m = m * 2;
     
238.             n += m;
     
239.         }
     
240.     }
     
241. 
     
242.     printf("\n\n");
     
243. }
     
244. 
     
245. void HeapSort(HP *php)
     
246. {
     
247.     int t = php->size;
     
248. 
     
249.     while (php->size != 0)
     
250.     {
     
251.         HeapPop(php);
     
252.     }
     
253. 
     
254.     php->size = t;
     
255. }
     
256. </div></article>

复制代码