永发信息网

求教一个C语言数据结构的编程【Huffman树】

答案:2  悬赏:60  手机版
解决时间 2021-02-14 08:56
要求:1由用户输入一些符号和各个符号对应的概率后,可以按左0右1输出每个符号的Huffman编码;2由用户输入任意长度0,1数字串,可以输出解码
最佳答案
霍夫曼编码问题,和我以前数据结构的一个上机题很类似,不过没有解码功能
上机题:设电文字符集D及各字符出现的概率F如下:
D={a,b,c,d,e,f,g,h}(字符数n=8)
F={5,29,7,8,14,23,3,11}(%)
编写完成下列功能的程序:
①构造关于F的Huffman树;
②求出并打印D总各字符的Huffman编码。
程序结构: 类型说明;
构造Huffman树的函数:Huffman_tree(H[m+1]);
求Huffman编码的函数:Huffman_code(code[n+1]);
main()
{ 变量说明;
输入字符集D及频率F;
调用Huffman_tree(H);
调用Huffman_code(code);
打印编码;Y继续,N退出}

运行后,输入8个字符(中间不能有空格,否则将空格视为字符处理),然后输入概率(整数,空格或回车分隔。如果要支持浮点数,要改程序)然后Enter,出现构造的霍夫曼节点和编码,程序如下
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define N 8
#define M 2*N-1
#define MAX 32767
typedef char datatype;
typedef struct
{
int wi;
char data;
int Parent,Lchild,Rchild;
}huffm;
typedef struct
{
char bits[N+1];
int start;
char ch;
}ctype;

void Huffman_tree(huffm H[M+1])
{
int i,j,p1,p2;
int w,s1,s2;
for(i=1;i<=M;i++)
{
H[i].wi=MAX;
H[i].Parent=0;
H[i].Lchild=H[i].Rchild=0;
}
printf("please enter the weight:\n");
for(i=1;i<=N;i++)
{
scanf("%d",&H[i].wi);
}

for(i=N+1;i<=M;i++)
{
p1=p2=0;
s1=s2=MAX;
for(j=1;j<=M;j++)
if(H[j].Parent==0)
if(H[j].wi {
s2=s1;
s1=H[j].wi;
p2=p1; p1=j;
}
else if(H[j].wi H[p1].Parent=H[p2].Parent=i;
H[i].Lchild=p1;
H[i].Rchild=p2;
H[i].wi=H[p1].wi+H[p2].wi;
}
printf("Number\tParent\tLchild\tRchild\n");
for(i=1;i<=M;i++)
printf("%d\t%d\t%d\t%d\n",i,H[i].Parent,H[i].Lchild,H[i].Rchild);

}
void Huffman_code(ctype code[N+1])
{
int i,j,p,s;
char c[N];
huffm H[M+1];
ctype md;
printf("please enter char:\n");

scanf("%s",c);
for(i=1;i<=N;i++)H[i].data=code[i].ch=c[i-1];
Huffman_tree(H);

for(i=1;i<=N;i++)
{
md.ch=code[i].ch;
md.start=N+1;
s=i;
p=H[i].Parent;
while(p!=0)
{
md.start--;
if(H[p].Lchild==s)
md.bits[md.start]='1';
else
md.bits[md.start]='0';
s=p;
p=H[p].Parent;
}
code[i]=md;
}
printf("print the code:\n");
for(i=1;i<=N;i++)
printf("%c\t",code[i].ch);
printf("\n");
for(i=1;i<=N;i++)
{
for(j=code[i].start;j<=N;j++)
printf("%c",code[i].bits[j]);
printf("\t");
}
printf("\n");
}
int Continue()
{ char c;
getchar();
printf("continue? y/n\n");
c=getchar();
if(c=='y') return 1;
else return 0;
}
main()
{
do{

ctype code[N+1];
Huffman_code(code);

}while(Continue());

}
全部回答
树和二叉树: 二叉树是树的一种,还可以有三叉树、四叉树、……,以及混合叉树。 不过一般只讨论二叉树,这是最典型、最有用的数据结构。 huffman树是一类带权路径长度最短的二叉树,在哈夫曼树中,权值越大的结点离根结点越近。 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:    (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);    (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;    (3)从森林中删除选取的两棵树,并将新树加入森林;    (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。 huffman树编码:以根为出发点,依次向下走到各个叶子结点为止。往下走时,选择走哈夫曼树的左分支生成0,走右分支则生成代码1,根结点到叶子结点路径上的0、1序列即为相应字符的编码。 这样讲可能有点抽象,你可以找本书,结合书上的图来看会更清楚一点。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
金凯旅行社地址在什么地方,我要处理点事
上海外联发D9工业园区(富特北路)这个地址在什
一个女人把感情看的很淡为什么
在汇编语言中mov dx,x+2什么意思?x+2什么意思
惠氏奶粉哪个系列最好
求问,仓鼠能吃玫瑰花吗
威廉旅游地址在哪,我要去那里办事
有哪些历史上的名人生活在宜兴
湘东收费站在哪里啊,我有事要去这个地方
我国素有“天然鱼仓”之称的是(  )。A.渤
不知有没有汽车钣金方面的师傅,我车的塑料大
洗饭店厨师工服多少钱
求店名一个,最好是讲风水的与运势有关的。
各车友,前叶子板凹陷,找外面无痕修复好还是
晓英度假村我想知道这个在什么地方
推荐资讯
(22分)阅读材料,完成下列各题。材料一:20
朗逸左右前轮与车翼子板缝隙不一样,大家对此
2018年与2022年世界杯足球赛将分别在“航母”
万达汽车装饰(枣乡大道)地址在哪,我要去那里
从黄家湖到南湖华锦花园中百店坐什么车?
泌阳县羊册镇中心校今年中招成绩
太阳神清之颜价格
农村信用社北关分社(北关路与文化街交叉口东
荠菜饺子吃了咳嗽更厉害,什么原因
高断在什么地方啊,我要过去处理事情
每月打卡工资4000元左右,没有医保社保,现在
四大欠王是什么
正方形一边上任一点到这个正方形两条对角线的
阴历怎么看 ?