关于哈夫曼编码的问题!急啊!!!
#include
using namespace std;
struct HTNode
{
int weight; //权值
int parent; //父节点
int lchild; //左孩子节点
int rchild; //右孩子节点
};
typedef HTNode *HuffmanTree;
typedef char **HuffmanCode;
void select(HuffmanTree HT,int n,int &s1,int &s2)
{
//选择两个最小值,将他们的位序输出到s1,s2
int m=0,k=0;
for(k=1;k<=n;++k) //得到第一个父节点为零的节点
{
if(0==HT[k].parent)
{
m=HT[k].weight;
s1=k;
break;
}
}
for(;k<=n;++k) //得到最小值
{
if(0==HT[k].parent && HT[k].weight<m)
{
m=HT[k].weight;
s1=k;
}
}
for(k=1;k<=n;++k) //得到第一个父节点为零的节点
{
if(k!=s1 && 0==HT[k].parent)
{
m=HT[k].weight;
s2=k;
break;
}
}
for(;k<=n;++k) //求得次小元
{
if(0==HT[k].parent && k!=s1 && HT[k].weight<m)
{
m=HT[k].weight;
s2=k;
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{
//w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
if(n<=1)
{
exit(0);
}
int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用
HuffmanTree p;
int i;
for(p=HT+1,i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
int s1=0,s2=0;
for(i=n+1;i<=m;++i)
{
//建赫夫曼树,在HT[1..i-1]选择parent为0且weight最小的两个节点,其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到跟逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
//分配n个字符编码的头指针向量
char * cd;
cd=(char *)malloc(n*sizeof(char));
//分配求编码的工作空间
cd[n-1]='\0'; //编码结束符
int start;
int c=0,f=0;
for(i=1;i<=n;++i)
{
//逐个字符求赫夫曼编码
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
{
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]); //从cd复制编码(串)到HC
}
free(cd); //释放工作空间
}
void main()
{
int *w; //用于存储序列权值
int n=0,i=0; //存储字符序列权值的个数
cout<<"请输入字符序列权值的个数:";
cin>>n;
w=(int *)malloc(n * sizeof(int));
cout<<"请输入字符序列的权值:";
for(i=0;i<n;++i) //输入字符序列权值
{
cout<<endl<<i+1<<" ";
cin>>w[i];
}
cout<<endl<<endl<<endl;
HuffmanTree HT; //存储赫夫曼树
HuffmanCode HC; //存储编码表
HuffmanCoding(HT,HC,w,n); //构建赫夫曼树,得到赫夫曼编码
cout<<"字符序号"<<""<<"字符权值"<<""<<"赫夫曼编码"<<endl;
for(i=1;i<=n;++i) //输出赫夫曼编码
{
cout<<i<<""<<w[i-1]<<""<<HC[i]<<endl<<endl;
}
cout<<endl;
}
我自己编的,已经在在线平台上测试通过,可以输出需要的字符总个数个数,你稍微改一下即可.实现代码,c++,运行环境:VC 6.0/Dev
------------------------------------------------------------
#include
using namespace std;
using std::fixed;
#include
using std::setprecision;
#include
#include
#include
#include
struct node
{
int times;
struct node *child1;
struct node *child2;
friend bool operator<( const node &a,const node &b )
{
return ( a.times < b.times );
}
friend bool operator>( const node &a1,const node &b1 )
{
return ( a1.times > b1.times );
}
};
int main()
{
priority_queue,greater > que;
char a;
char string1[4] = {'0'};
int letter[28] = {0};
bool judge = 1;
while( judge )
{
int count = 0;
int i,j,k;
memset( letter,0,sizeof(letter) );
while( que.size() > 0 )
que.pop();
while( ( a = cin.get() ) != '
' )
{
if( count <= 3 )
string1[count] = a;
count++;
if( a == '_' )
letter[27]++;
if( a != '_' )
{
k = a-'A'+1;
letter[k]++;
}
}
if( count == 3 && string1[0] == 'E' && string1[1] == 'N' && string1[2] == 'D' )
{
judge = 0;
break;
}
int count1 = 0;
for( i = 1;i <= 27;i++ )
{
if( letter[i] > 0 )
{
node p;
p.times = letter[i];
p.child1 = NULL;
p.child2 = NULL;
que.push(p);
count1 += letter[i];
}
}
if( que.size() == 1 )
{
cout<<count1*8<<' '<<count1<<" 8.0"<<endl;
continue;
}
int total = 0;
node *t1,*t2,*t3;
while( que.size() >= 2 )
{
t1 = new node;
t2 = new node;
*t1 = que.top();
que.pop();
*t2 = que.top();
que.pop();
t3 = new node;
t3->times = t1->times + t2->times;
t3->child1 = t1;
t3->child2 = t2;
que.push( *t3 );
total += ( t1->times + t2->times );
}
if( total != 0 )
{
double t = 1.0*8*count/total;
cout<<8*count1<<' '<<total<<' '<<setprecision(1)<<fixed<<t<<endl;
}
}
return 0;
}
1001000
1000101
1000011
1001000
1010101
1000001
01001110
1011010
1001001
这是二进制的编码 应该是对应十进制的
72
69
67
72
85
65
78
90
73
这么大的数字对应的明显不是字母表,如果没有猜错的话对应当应该是ASCLL码表
这九个数字对应的ASCLL码是:
H
E
C
H
U
A
N
Z
I
连起来应该就是答案了:HECHUANZI
虽然我不知道什么意思 但是应该是一个人名 HE CHUAN ZI
这什么破密码 绕这么多弯子 40分是不是太少了一点 出于人道主义还是加点分吧
1111
哈夫曼编码问题 大神救我~
CreateHT创建哈夫曼树的代码有点问题,修改如下 void CreateHT(HTNode ht[],int n){ int i,k,lnode,rnode; int min1,min2; for(i=0;i<2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) { min1=min2=32767; lnode=rnode=-1; ...
哈夫曼编\/译码器问题:C语言版的数据结构,我急啊!那位朋友帮帮忙,结果必 ...
问题是:哈夫曼编\/译码器问题:利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接... 问题是:哈夫曼编\/译码器问题:利用哈夫曼编码进行信息通讯可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端...
哈夫曼编码问题~~~高手进。。急急急急
\/\/w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC if(n<=1){ exit(0);} int m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); \/\/0号单元未用 HuffmanTree p;int i;for(p=HT+1,i=1;i<=n;++i,++p,++w){ p->weight=*w;p->...
急!哈夫曼编码的问题!!!
我这里有对输入一行数字进行哈夫曼编码的程序,我花了好长时间去对一行字符串编码,但没能成功,把程序发给你,让我门一起研究试试看。include <stdio.h> include <stdlib.h> include <string.h> include <malloc.h> define maxnum 1000 define MAX 100 int W[MAX];typedef struct {int weight;...
哈夫曼编码问题,高手帮我
include<ctype.h> int n;struct node{ int w;int flag;char c;struct node *plink,*llink,*rlink;char code[50];}*num[100],*root;FILE *fp;char tmpcode[50];int t=0;void main(void){ int i;void settree(void); \/\/建立树 void code(void); \/\/对文件编码 void decode...
哈夫曼编码中码长的方差对实际编码系统有什么影响
哈夫曼编码,左子树默认为0,右子树默认为1,得到的编码如下:A:100 B:01 C:1011 D:11 E:1010 F:00 编码的码长是:8*3 + 12 * 2 + 5*4 + 20 * 2 + 4*4 + 11 * 2 = 146 频率是W=,可以根据这个算出每个符号的使用概率。Huffman编码的基本思想就是:对于使用频率比较高的...
怎样构造哈夫曼树?
问题四:如何构造哈夫曼树,详细点 要方法 还是要代码 问题五:哈夫曼树的构造算法 5分 \/*--- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在 Win-TC 下测试通过 * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 ...
、一个具有3个符号的信源有多少种可能的哈夫曼编码?急
一个具有3个符号的信源有8种可能的哈夫曼编码。赫夫曼编码的具体方法:先按出现的概率大小排队,把两个最小的概率相加,作为新的概率 和剩余的概率重新排队,再把最小的两个概率相加,再重新排队,直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率,读出时由该符号开始一直走到最后的...
题目:哈夫曼编码系统 设计任务:
题目:哈夫曼编码系统 设计任务: 题目:哈夫曼编码系统设计任务:从键盘输入一串电文字符能输出对应的哈夫曼编码。同时,能翻译由哈夫曼编码生成的代码串,输出相应的电文字符串。设计要求:(1)从终端读入字符集大小n... 题目:哈夫曼编码系统设计任务: 从键盘输入一串电文字符能输出对应的哈夫曼编码。同时,能翻译由哈夫曼...
C++课程设计:哈夫曼编码器
C++课程设计:哈夫曼编码器 【问题描述】:利用哈夫曼树实现编码并译码的系统。【基本要求】:从终端读入一段字符集,系统自动统计出字符的个数n以及各个字符出现的次数w作为权值,建立哈夫曼树,并将哈夫曼树以... 【问题描述】:利用哈夫曼树实现编码并译码的系统。【基本要求】:从终端读入一段字符集,系统自动统计...
顾楠丽智: 两个最小的编码没有左右之分.是不同,哈夫曼编码不是唯一的,但是它们的WPL(带权路径长度)都是一样的.如果,最下面有两个二叉树,那么也不用考虑左右的问题,你只将最下面两个二叉树当作两个节点就可以了.记住:哈夫曼编码不...
乌兰察布市18732151160: 求解,关于数据结构的哈夫曼编码的问题 - ?
顾楠丽智: 方案一应该指的就是下面那个图了.下面那个图是一棵二进制的哈夫曼树,其中因为是二进制编码,所以使用的是0\1的边.那么对于每一个叶子节点来说,从根节点到叶子节点走过的边就是这个数字的编码.那么举一个例子,比如频数=2的也就是最...
乌兰察布市18732151160: 求助有关哈夫曼树编码的问题?急! - ?
顾楠丽智: 我去年数据结构课程设计做的就是这个,具体什么意思也忘得差不多了 反正做了好多天的 把这段代码复制给你void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC, LNode &L,int n){ //构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC ...
乌兰察布市18732151160: 一道关于哈夫曼编码的题该怎么做? - ?
顾楠丽智: 首先,亲请记住,无论是数学题政治题C语言,任何情况下都不可以选“以上都不是”.哈夫曼编码是非常经典的一种变长编码方案.我偷个懒,方法描述如下:首先,将符号按照概率由大到小排队.编码时,从最小概率的两个符号开始,可选...
乌兰察布市18732151160: 哈夫曼编码是怎么回事啊? - ?
顾楠丽智: 哈夫曼编码是一种编码方式,是可变字长编码(VLC)的一种.以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称"熵编码法"),用于数据的...
乌兰察布市18732151160: 数据结构题目,关于哈弗曼编码,用C语言来做(非常急的,谢谢了) - ?
顾楠丽智: void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) { // w存放n个字符的权值(均>0),构造哈夫曼树HT, // 并求出n个字符的哈夫曼编码HC int i, j, m, s1,s2; char *cd; int p; int cdlen; if (n m = 2 * n - 1; HT = (HuffmanTree)...
乌兰察布市18732151160: 哈夫曼编码是一种可变长,信源中某符号发生概率越低,其码长越 - --怎么? - ?
顾楠丽智: 哈夫曼编码的原理是:一个符号发生频率越高,其码长越短,反之则越长.很好理解:要使总长最短,出现越多次的符号的编码就要越短.打个不恰当的比方,现在用的最多的几个汉字“个”“的”“们”“什”“么”什么的笔画不是都很少吗?这就是文字演变的规律,也就是哈夫曼编码的原理.
乌兰察布市18732151160: 急求 多媒体技术中哈夫曼编码的码长和熵的计算公式,大学阶段的.不要C里面的,就是要两个公式. 谢谢了 - ?
顾楠丽智: 展开全部1:码长是否是平均码长?如果是,码长=(所有种类字符累加(字符出现的次数*该字符哈夫曼编码是的长度))/所有字符的个数 例:字符串aabbb a编码为10011 -----5位 b编码为010011 -------6位 码长=(2*5+3*6)/5 (分母5代表aabbb的长度为5)2:信息熵:信息熵Eta=累加(Pi*log2(1/Pi))(i从1累加到n,Pi表示对应第i个字符在字符串中出现的概率,如字符“a”在长度为1000的字符串中出现6次,为第一个字符,则P1=6/1000)
乌兰察布市18732151160: 哈夫曼树每个字符可以有不同的编码方式,但是每个字符的编码长度是一样的吗? - ?
顾楠丽智: 主可以去看看最优二叉树的编码问题. 1、哈夫曼编码 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,...
乌兰察布市18732151160: 有关哈夫曼编码的问题!(请高手帮帮忙,谢谢了哦!)?
顾楠丽智: 提问者只给了7个字母的权值,故,按7个字母求解. 由于各人不同,所构造的哈夫曼编码可能不同,先给出一种编码形式 a 0101 b 10 c 01000 d 00 e 01001 f 11 g 011 二进制表示易知. 与二进制比,此方法在保证准确的情况下,比较节省时间空间.