给定权值(A:5,B:29,C:7,D: 8, E:14,F:23,G:3, H:11 建立哈夫曼树,输出哈夫曼编码;对上述给定的哈夫曼树及得到的哈夫曼编码,试输入一串二进制编码,输出它的哈夫曼译码。
要求:将哈夫曼树的结构定义为一个一维数组,每个元素含有四顶:权值、双亲、左、右。权值由键盘输入;二进制编码时,往左走编码为0,往右走编码为1:译码就是将输入的编码还原成对应的字符。
以上好多人用的用的是c++有人给改成c语言嘛,不会呀
给定权值(A:5,B:29,C:7,D: 8, E:14,F:23,G:3, H:11 建立哈夫曼树,输出哈夫曼编码;对上述给定的哈夫曼树及得到的哈夫曼编码,试输入一串二进制编码,输出它的哈夫曼译码。
要求:将哈夫曼树的结构定义为一个一维数组,每个元素含有四顶:权值、双亲、左、右。权值由键盘输入;二进制编码时,往左走编码为0,往右走编码为1:译码就是将输入的编码还原成对应的字符。
以上好多人用的用的是c++有人给改成c语言嘛,不会呀
#include<stdio.h>
#define Maxleaf 30
#define Maxnode 1000
#define Max 100000
#define Maxsize 100
typedef struct //定义结构体
{
char ch; //定义字符型的结点名
float weight; //定义一个整型权值变量
int lchild,rchild,parent; //定义左、右孩子及双亲指针
}hufmtree;
typedef struct
{
char bits[Maxsize]; //定义一个字符型的数组存储结点的编码
int start; //标志字符串起点
char ch; //存储结点的名称
}codetype;
void huffman(hufmtree tree[],int n) //哈夫曼树的创建
{
int i,j,p1,p2;
float small1,small2,f;
char c;
int m=2*n-1; //总的结点数目
for(i=0;i<m;i++) //结点信息的初始化
{
tree[i].parent=0;
tree[i].lchild=-1;
tree[i].rchild=-1;
tree[i].weight=0.0;
}
for(i=0;i<n;i++) //输入叶子结点的结点名和权值
{
printf("第%d个元素的结点:",i+1);
scanf("%c",&c);
getchar();
printf("输入该节点的权值:");
scanf("%f",&f);
getchar();
tree[i].ch=c;
tree[i].weight=f;
}
for(i=n;i<m;i++) //找出剩余结点中的权值最小的两个结点组合
{
p1=0;p2=0;
small1=Max;small2=Max;
for(j=0;j<i;j++)
if(tree[j].parent==0) //如果该结点不存在双亲
if(tree[j].weight<small1) //结点的权值小于small1时
{
small2=small1;
small1=tree[j].weight;
p2=p1;
p1=j;
}
else if(tree[j].weight<small2) //结点的权值大于small1但是小于small2
{
small2=tree[j].weight;
p2=j;
}
tree[p1].parent=i;
tree[p2].parent=i;
tree[i].lchild=p1;
tree[i].rchild=p2;
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}
void huffmancode(codetype code[],hufmtree tree[],int n) //哈夫曼的编码函数
{
int i,c,p;
codetype cd; //定义一个临时变量
for(i=0;i<n;i++) //从下往上遍历哈夫曼树,进行编码
{
cd.start=n; //编码的结束位置
cd.ch=tree[i].ch; //将哈夫曼结构体中的结点名赋给存储编码的结构体中的结构名
c=i;
p=tree[i].parent;
while(p!=0) //当p是根结点的双亲时跳出循环
{
cd.start--;
if(tree[p].lchild==c) //如果是它的左孩子
cd.bits[cd.start]='0'; //则输出0
else
cd.bits[cd.start]='1'; //否则就是右孩子输出1
c=p;
p=tree[p].parent;
}
code[i]=cd; //将临时变量中的值存入结构体数组
}
}
void decode(hufmtree tree[],int m) //译码函数
{
int i,j=0,k=0;
char b[Maxsize];
char endflag='#';
i=m-1;
getchar();
gets(b); //读入编码
printf("输出哈夫曼译码:\n");
while(b[j]!='#')
{
if(b[j]=='0') //如果编码是0
i=tree[i].lchild; //将该结点左孩子的序号赋给i
else
{
if(b[j]=='1')
i=tree[i].rchild; //如果编码是1,将该结点右孩子的序号赋给i
else
printf("ERROR\n");
}
if(tree[i].lchild==-1) //如果该结点左孩子的序号等于-1,即根结点
{
printf("%c",tree[i].ch); //输出该结点名
i=m-1; //回到根结点
}
j++;
}
printf("\n");
if(tree[i].parent!=0)
printf("\nERROR\n");
}
void Menu()
{
printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");
printf("* ********哈夫曼编码/译码器******** *\n");
printf("* 1.创建哈夫曼树; *\n");
printf("* 2.进行哈夫曼编码; *\n");
printf("* 3.进行哈夫曼译码; *\n");
printf("* 4.退出; *\n");
printf("◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆\n");
}
int main()
{
int i,j,n,m;
int choose;
hufmtree tree[Maxnode];
codetype code[Maxleaf];
Menu();
while(1)
{
printf("\n请输入要进行的功能:");
scanf("%d",&choose);
switch(choose)
{
case 1:
printf("请输入元素个数:");
scanf("%d",&n);
getchar();
huffman(tree,n); //调用哈夫曼创建函数
printf("成功建立哈夫曼树!\n");
break;
case 2:
printf("请输出哈夫曼编码:\n");
huffmancode(code,tree,n); //调用哈夫曼编码函数
for(i=0;i<n;i++) //输出结点对应的哈夫曼编码
{
printf("%c:",code[i].ch);
for(j=code[i].start;j<n;j++)
printf("%c",code[i].bits[j]);
printf("\n");
}
break;
case 3:
m=2*n-1;
printf("请输入编码,以#为结束标志:\n");
decode(tree,m); //调用译码函数
break;
case 4:
return 0;
}
}
return 0;
}