|

楼主 |
发表于 2017-4-6 20:25:09
|
显示全部楼层
本帖最后由 000 于 2017-4-6 20:26 编辑
贴一个二叉堆的基本吧实现,有注释的- #include <stdio.h>
- #include <tchar.h>
- #include <stdlib.h>
- #include <errno.h>
- #include <string.h>
- struct Heap
- {
- int capacity;
- int size;
- int *c;
- };
- typedef struct Heap * h_point;
- //-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- // binary heap
- // Left 2i
- // Right 2i+1
- // Father i/2
- //-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
- h_point
- Initialize(int MaxSize)
- {
- h_point head = (h_point)malloc(sizeof(struct Heap));
- if (errno)
- printf("%s", strerror(errno));
- head->c = (int *)malloc(sizeof(int)*(MaxSize + 1));
- if (errno)
- printf("%s", strerror(errno));
- head->capacity = MaxSize;
- head->size = 0;
- head->c[0] = 0xcccccccc;
- return head;
- }
- bool
- IsFull(h_point head)
- {
- return head->size == head->capacity ? 1: 0;
- }
- int
- IsEmpty(h_point head)
- {
- return head->size == 0 ? head->c[0] : 0;
- }
- void
- Insert(int x, h_point head)
- {
- int i;
- if (IsFull(head))
- printf("FULL");
- for (i = ++head->size; head->c[i/2] > x; i /= 2)
- head->c[i] = head->c[i / 2];
- head->c[i] = x;
- }
- int DeleteMin(h_point head)
- {
- int i, child;
- int Min, Last;
- if (IsEmpty(head))
- printf("Empty");
- Min = head->c[1];
- Last = head->c[head->size--]; //删除节点户籍
- for (i = 1; i * 2 <= head->size; i = child) // i 为根节点
- {
- child = i * 2; //以i为根的左节点
- if (child != head->size && head->c[child + 1] < head->c[child]) //左节点小于右节点,此时右节点前移到删除的根节点处完成删除
- ++child;
- if (Last > head->c[child])
- head->c[i] = head->c[child];
- else
- break;
- }
- head->c[child] = Last;
- return Min;
- }
- int _tmain(int argc,_TCHAR *argv[])
- {
- FILE *fp;
- fp = fopen("in.txt", "r");
- h_point head = Initialize(10);
- for (int i = 0; i < 10; ++i)
- {
- int j;
- fscanf(fp, "%d", &j);
- Insert(j, head);
- }
- for (int i = 1; i <= 10; ++i)
- printf("%d ", head->c[i]);
- int i = DeleteMin(head);
- printf("\n Min is : %d\n", i);
- for (int i = 1; i <= head->size; ++i)
- printf("%d ", head->c[i]);
- return 0;
- }
复制代码
|
|