题目
思路
通过最小堆模拟哈夫曼树,权值的计算就是删除堆中的两个最小元素,相加,插入最小堆。
平均码长=所有结点的编码总长度/所有结点的总频次
存储的名字是没有用处的,用主函数数组存储就行。
代码:
#include <malloc.h> #include <stdio.h> #include <string.h> #define MinData -100000 typedef struct Heap *MinHeap; struct Heap { int *Elements; //存储堆元素的数组 int size; //堆当前元素个数 int capacity; //堆的最大容量 }; //最小堆的创建 MinHeap create (int n); //插入 void Insert ( MinHeap H, int item ); //删除 int Delete (MinHeap H); int main() { MinHeap H; int n, k, m, flag, item; int weight, pindu; weight = pindu = 0; char name[100]; scanf("%d", &n); H = create (n); int i; for (i=0; i<n; i++) { scanf("%s %d", &name, &item); pindu += item; Insert (H, item); } while(1){ int num1 = Delete(H); int num2 = Delete(H); if(num2 == -1){ //最小堆为空 printf("%.5f", 1.0*weight/pindu); return 0; } int num = num1 + num2; Insert(H, num); weight += num; } return 0; } //最小堆的创建 MinHeap create (int n) { MinHeap H = (MinHeap)malloc(sizeof(struct Heap)); H->Elements = (int*)malloc( (n+1) * sizeof(H->Elements)); H->size = 0; H->capacity = n; H->Elements[0] = MinData; return H; } //插入 void Insert ( MinHeap H, int item ) { int i; i = ++H->size; for ( ; H->Elements[i/2]>item; i/=2){ H->Elements[i] = H->Elements[i/2]; } H->Elements[i] = item; } //删除 int Delete (MinHeap H) { if(H->size == 0){ return -1; } int parent = 0, child = 0, minitem, t; minitem = H->Elements[1]; t = H->Elements[H->size--]; for (parent=1; parent*2<=H->size; parent=child) { child = parent * 2; if ((child != H->size) && (H->Elements[child] > H->Elements[child+1])) child++; if (t < H->Elements[child]){ break; } else H->Elements[parent] = H->Elements[child]; } H->Elements[parent] = t; return minitem; }
最小堆的创建,插入,删除,道理和最大堆的操作集类似,就是更改一下判断条件,复制条件即可。