题面
实验三 哈夫曼树。实验目的及要求：1、要求学生掌握树和二叉树的基本概念；2、要求学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法；3、认识哈夫曼树、哈夫曼编码的作用和意义；4、能够建立一个哈夫曼树，并输出哈夫曼编码，正确调试程序。本题要求实现一个创建哈夫曼树的函数，根据输入的n个结点的权值，创建一棵哈夫曼树。例如输入5 2 3 5 7 8，其中第一个数值5，表示5个结点，2 3 5 7 8分别表示这5个结点的权值，中间用空格分开，则该函数应该输出5(2,3),10(5,5),15(7,8),25(10,15),注意：生成的结点之间用“,”分开。
函数接口定义：
在这里描述函数接口。例如：
void CreatHuff(HuffmanTree *HT, int *w, int n);
裁判测试程序样例：
在这里给出函数被调用进行测试的例子。例如：
#include <stdio.h>
#include <string.h>
#include <malloc.h>
typedef struct
{
int weight; // 结点权值?
int parent, lc, rc; // 双亲结点和左 右子节点
} HTNode, *HuffmanTree;
void Select(HuffmanTree *HT, int n, int *s1, int *s2)
{
int minum,i; // 定义一个临时变量保存最小值?
for(i=1; i<=n; i++) // 以下是找到第一个最小值
{ if((*HT)[i].parent == 0)
{ minum = i;
break;
}
}
for(i=1; i<=n; i++)
{ if((*HT)[i].parent == 0)
if((*HT)[i].weight < (*HT)[minum].weight)
minum = i;
}
*s1 = minum; // 以下是找到第二个最小值，且与第一个不同
for( i=1; i<=n; i++)
{ if((*HT)[i].parent == 0 && i != *s1)
{ minum = i;
break;
}
}
for( i=1; i<=n; i++)
{ if((*HT)[i].parent == 0 && i != *s1)
if((*HT)[i].weight < (*HT)[minum].weight)
minum = i;
}
*s2 = minum;
}
void CreatHuff(HuffmanTree *HT, int *w, int n);
int main()
{
HuffmanTree HT;
int *w, n, wei,i;
//printf("input the number of node
");
scanf("%d", &n);
//w = new int[n+1];
w=(int *) malloc ((n+1) * sizeof(int));
//printf("
input the %dth node of value
", n);
for(i=1; i<=n; i++)
{
scanf("%d", &wei);
w[i] = wei; }
CreatHuff(&HT, w, n);
return 0;
}
/* 请在这里填写答案 */
测试样例
输入
5 2 3 5 7 8
输出
5(2,3),10(5,5),15(7,8),25(10,15),
注意
只能C！！！
c 语言 error: expected ';', ',' or ')' before '&' token
问题：
编译的时候报:error: expected ';', ',' or ')' before '&' token
原因：
C语言中是不存在引用的，也就是说C语言中&表示的不是引用，仅仅是取地址符。
解决:
第一种：用指针来取代引用，在主函数中传进地址
第二种：将代码保存成.cpp文件(c++中支持引用)
正确代码
#include <stdio.h>
#include <string.h>
#include <maloc.h>
//#include<iostream>
//using namespace std;
typedef struct
{
int w,f,lc,rc; // 权值 双亲结点和左 右子节点
}node,*tree;
void q(tree*HT,int n,int*s1,int*s2)
{
int mi;
for(int i=1;i<=n;i++) // 找到第一个最小值
{
if(!(*HT)[i].f)
{
mi=i;
break;
}
}
for(int i=1;i<=n;i++)
{
if((*HT)[i].f==0&&((*HT)[i].w<(*HT)[mi].w))
mi=i;
}
*s1=mi; // 找到第二个与第一个不同的最小值
for(int i=1;i<=n;i++)
{
if((*HT)[i].f==0&&i!=*s1)
{
mi=i;
break;
}
}
for(int i=1;i<=n;i++)
{
if((*HT)[i].f==0&&i!=*s1&&((*HT)[i].w<(*HT)[mi].w))
mi=i;
}
*s2=mi;
}
void build(tree*HT,int*w,int n);
int main()
{
int*a,n,x;
scanf("%d",&n);
a=(int*)malloc((n+1)*sizeof(int)); //c++:w = new int[n+1];
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[i]=x;
}
tree HT;
build(&HT,a,n);
return 0;
}
void build(tree*HT,int*w,int n) /* 答案 */
{
int m=n*2-1,s1,s2;
(*HT)=(node*)malloc((m+1)*sizeof(node)); //HT=new Nodee[m+1];
for(int i=1;i<=n;i++)
{
(*HT)[i].w=w[i];
(*HT)[i].f=(*HT)[i].lc=(*HT)[i].rc=0;
}
for(int i=n+1;i<=m;i++)
(*HT)[i].w=(*HT)[i].f=(*HT)[i].lc=(*HT)[i].rc=0;
for(int i=n+1;i<=m;i++)
{
q(HT,i-1,&s1,&s2); // ss(&HT,i-1,&s1,&s2);
(*HT)[s1].f=(*HT)[s2].f=i;
(*HT)[i].lc=s1,(*HT)[i].rc=s2;
(*HT)[i].w=(*HT)[s1].w+(*HT)[s2].w;
printf("%d(%d,%d),",(*HT)[i].w,(*HT)[s1].w,(*HT)[s2].w);
}
printf("
");
}