7-1 修理牧场 (C语言哈夫曼树)(25 分)
发布时间
阅读量：
阅读量
农夫计划修复牧场的一段围栏，在测量后他确定所需木材数量为N块，并每块木材长度均为整数L个单位。为此他购买了一根足够长且能被分割成N段的具体木材。由于农夫不具备锯割工具，因此他委托他人进行操作，并支付的费用与其切割次数相关联。具体而言，在每一次切割中支付的费用等于被分割出的那一小段木材长度（假设每次切割费用与其长度成正比）。例如，在将一根长20单位的木材分成8、7和5三个部分时：第一刀将一根20单位长的木材切成12和8两部分需花费12单位；第二刀则需再花费8单位将较长的部分切成7和5两段；总计花费为12+8=20单位。然而如果第一次切割将木材分成15和5两部分，则第二次切割需花费15单位才能完成剩余切口；这种情况下总费用则上升至15+5=20单位（总费用高于之前的情况）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
首先提供一个不超过10^4的正整数N作为输入值，请在随后的一行中提供包含在内并确保每个数值都不超过50的正整数序列
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct HuffmanTreeNode{
ElemType data; //哈夫曼树中节点的权值
struct HuffmanTreeNode* left;
struct HuffmanTreeNode* right;
}HuffmanTreeNode,*PtrHuffman;
PtrHuffman createHuffmanTree(ElemType arr[],int max){
PtrHuffman ptrArr[max];
PtrHuffman ptr,pRoot=NULL;
for (int i = 0; i < max; i++){ //初始化结构体指针数组,数组中每一个元素为一个结构体指针类型
ptr = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));
ptr->data = arr[i];
ptr->left = ptr->right = NULL;
ptrArr[i] = ptr;
}
for(int i = 1; i < max; i++)
{ //进行 n-1 次循环建立哈夫曼树
//k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
int k1 = -1, k2;
for(int j = 0; j < max; j++){
if (ptrArr[j] != NULL && k1 == -1){
k1 = j;
continue;
}
if (ptrArr[j] != NULL){
k2 = j;
break;
}
}
//将指针数组中的指针指向的最小值赋值给索引号为k1的,次小值赋值给索引号为k2的
for (int j = k2; j < max; j++){
if(ptrArr[j] != NULL){
if(ptrArr[j]->data < ptrArr[k1]->data){
k2 = k1;
k1 = j;
}else if(ptrArr[j]->data < ptrArr[k2]->data){
k2 = j;
}
}
}
//由最小权值树和次最小权值树建立一棵新树,pRoot指向树根结点
pRoot = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));
pRoot->data = ptrArr[k1]->data + ptrArr[k2]->data;
pRoot->left = ptrArr[k1];
pRoot->right = ptrArr[k2];
ptrArr[k1] = pRoot; //将指向新树的指针赋给ptrArr指针数组中k1位置
ptrArr[k2] = NULL; //k2位置为空
}
return pRoot;
}
ElemType calculateWeightLength(PtrHuffman &ptrTree,int len){
if(ptrTree==NULL){ //空树返回0
return 0;
}else{
if(ptrTree->left==NULL && ptrTree->right==NULL){ //访问到叶子节点
return ptrTree->data * len;
}else{
return calculateWeightLength(ptrTree->left,len+1) + calculateWeightLength(ptrTree->right,len+1); //向下递归计算
}
}
}
int main(){
ElemType arr[];
int max;
scanf("%d",&max);
int i=0;
while(i<max)
scanf("%d",&arr[i++]);
PtrHuffman pRoot = createHuffmanTree(arr,max); //返回指向哈夫曼树根节点的指针
printf("%d",calculateWeightLength(pRoot,0));
fprintf(stdout,"\n");
return 0;
}全部评论 (0)
还没有任何评论哟~