求教一个C语言数据结构的编程【Huffman树】
答案:2 悬赏:60 手机版
解决时间 2021-02-14 08:56
- 提问者网友:萌卜娃娃
- 2021-02-13 12:13
要求:1由用户输入一些符号和各个符号对应的概率后,可以按左0右1输出每个符号的Huffman编码;2由用户输入任意长度0,1数字串,可以输出解码
最佳答案
- 五星知识达人网友:你哪知我潦倒为你
- 2021-02-13 12:53
霍夫曼编码问题,和我以前数据结构的一个上机题很类似,不过没有解码功能
上机题:设电文字符集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());
}
上机题:设电文字符集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[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());
}
全部回答
- 1楼网友:西岸风
- 2021-02-13 14:00
树和二叉树:
二叉树是树的一种,还可以有三叉树、四叉树、……,以及混合叉树。
不过一般只讨论二叉树,这是最典型、最有用的数据结构。
huffman树是一类带权路径长度最短的二叉树,在哈夫曼树中,权值越大的结点离根结点越近。
假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
(3)从森林中删除选取的两棵树,并将新树加入森林;
(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。
huffman树编码:以根为出发点,依次向下走到各个叶子结点为止。往下走时,选择走哈夫曼树的左分支生成0,走右分支则生成代码1,根结点到叶子结点路径上的0、1序列即为相应字符的编码。
这样讲可能有点抽象,你可以找本书,结合书上的图来看会更清楚一点。
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯