%by dynamic
%see also http://www.matlabsky.com
%contact me matlabsky@gmail.com
%2009.2.20
我大概看激御了你下你的两个while循环有可能是死循环，你自己看看
while (j~=0) 这个是永远成立的，因为你的j开始时是3，可是你后面却有一个j=j+1，换句话说这个循环是死循环，除非遇到break语句，但是我没有看见有跳出该循环的break语句
还有while(p<=n) 这个好像也是有问题的，p我禅铅段没有发现直接的改变方法，只有最后的p=q，恩这个还有可能达到循环结束 但是万一你的那个p=q不执行呢
建议仔细检查这段贺誉程序
霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding
tree）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编友拿码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
以下这个简单例子说明了这一过程。
1)．字母A,B,C,D,E已被编码，相应的出现概率如下：
p(A)=0.16,
p(B)=0.51,
p(C)=0.09,
p(D)=0.13,
p(E)=0.11
2)．C和E概率最小，被排在第一棵
二叉树
中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的
哈夫曼编码
可能由相同的数据产生。
3)．各节点相应的概率如下：
p(A)=0.16,
p(B)=0.51,
p(CE)=0.20,
p(D)=0.13
D和A两个节点的好液搭概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。
如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。
4)．剩下节点的概率如下：
p(AD)=0.29,
p(B)=0.51,
p(CE)=0.20
AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。
5)．剩下两个节点相应的概率如下：
p(ADCE)=0.49,
p(B)=0.51
它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。
6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：
w(A)=001,
w(B)=1,
w(C)=011,
w(D)=000,
w(E)=010
图03-02-2
霍夫曼编码例
霍夫曼编码器的编码过程可用例子演示和解释。
下面是另一个霍夫曼编码例子。假定要编码的文本是：
"EXAMPLE
OF
HUFFMAN
CODE"
首先，计算文本中符号出现埋孙的概率（表03-02-2）。
表03-02-2
符号在文本中出现的概率
符号
概率
E
2/25
X
1/25
A
2/25
M
2/25
P
1/25
L
1/25
O
2/25
F
2/25
H
1/25
U
1/25
C
1/25
D
1/25
I
1/25
N
2/25
G
1/25
空格
3/25
最后得到图03-02-3所示的编码树。
图03-02-3
霍夫曼编码树
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive
Huffman
code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended
Huffman
code）允许编码符号组而不是单个符号。
同
香农-范诺编码
一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含
同步码
，在编码之后的码串中都不需要另外添加标记符号，即在
译码
时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error
propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。
#include"iostream.h"#include<iomanip.h>
#include"vector"
#include"algorithm"
#include"math.h"
using namespace std
struct bitree
{//定义结构用于存储编码结果的二叉树结构,在译码时用到
char ch //用于存储世高码符号
char mz //用于存储码字
bitree * lchild
bitree * rchild
}
struct data
{//用于存储相关的信源符号以及其概卜念率
double p
char ch
vector<char>code
int ml
}
bool sortspecial(data dt1,data dt2)
{//用于排序时用
return dt1.p>dt2.p
}
void print2(vector<char>vd)
{//用于打印译码结果
for(int i=0i<vd.size()i++)
cout<<vd[i]<<" "
cout<<endl
}
void read(vector <data>&vd)
{//用于读入相关型返困的信源符号以及概率
int n
while(true)
{
cout<<"请输入信源符号数:"
cin>>n
cout<<"请输入相应的信源符号及其概率:"<<endl
data dt
int i=0
while(i<n)
{
cin>>dt.ch
cin>>dt.p
dt.ml=0
vd.push_back(dt)
i++
}
double sum=0
vector<data>::iterator pit
/* for(pit=vd.begin()pit!=vd.end()pit++)
{
sum+=pit->p
}
if(sum!=1)
{
cout<<"你输入的概率不符合要求,请重新输入."<<endl
sum=0
continue
}*/
sort(vd.begin(),vd.end(),sortspecial)
break
}
}
void append(char ch1,char ch2,bitree *&bt)
{//用于再构造码字二叉树时向其中添加结点
bitree * bit=new bitree
bit->ch=ch1
bit->mz=ch2
bit->lchild=NULL
bit->rchild=NULL
if(ch1=='0')
bt->rchild=bit
else bt->lchild=bit
}
void Creatmz1(vector<data>&vd,int begin1,int end1 ,double pn ,bitree *&bt)
{//进行编码,用递归的方法进行编码
int begin=begin1,end=end1
if(begin==end) return
else if(begin+1==end)
{
return
}
else if(begin+2==end){
vd[begin].code.push_back('0')
vd[begin].ml++
append('0',vd[begin].ch,bt)
vd[end-1].code.push_back('1')
vd[end-1].ml++
append('1',vd[end-1].ch,bt)
return
}
else{
double sum0=0,sum1=0,sum2=0
do{
sum1+=vd[begin].p
sum2=sum1+vd[begin+1].p
begin++
}while(fabs(sum1/pn-0.5)>fabs(sum2/pn-0.5))//用于找到上下两组码的分点使得其概率和近于相同
for(int i=begin1i<begini++){
vd[i].code.push_back('0')
vd[i].ml++
}
if(begin1+1 == begin){
append('0',vd[begin1].ch,bt)
}
else append('0','0',bt)
for(int j=beginj<=end1-1j++){
vd[j].code.push_back('1')
vd[j].ml++
}
if(begin+1 == end1){
append('1',vd[begin].ch,bt)
}
else append('1','0',bt)
Creatmz1(vd,begin1 ,begin,sum1,bt->rchild )//对分点前的进行编码
Creatmz1(vd,begin ,end1,pn-sum1,bt->lchild)//对分点后的进行编码*/
}
}
void print1(vector<data>vd)
{//用于打印编码结果
cout<<"xi"<<setw(8)<<"P(xi)"<<setw(8)<<"码长"
<<setw(8)<<"码字"<<setw(8)<<endl
for(int i=0i<vd.size()i++){
cout<<vd[i].ch<<setw(8)<<vd[i].p<<setw(8)<<vd[i].ml<<setw(8)
for(int j=0j<vd[i].code.size()j++)
cout<<vd[i].code[j]
cout<<setw(8)<<endl
}
}
void clear(bitree * &bt)
{//对二叉树的动态存储空间进行释放
if(bt!=NULL&&bt->lchild!=NULL)
clear(bt->lchild)
if(bt!=NULL&&bt->rchild!=NULL)
clear(bt->rchild)
delete bt
}
bool des_code(vector <char>&vr,vector <char>vt,bitree *bt)
{//用二叉编码树进行解码
if(bt==NULL)
{
cout<<"码树不存在!!!"<<endl
return false
}
int pit=0
bitree * mbt=bt
while ((mbt->lchild!=NULL||mbt->rchild!=NULL)||pit<vt.size())
{
if(mbt->lchild==NULL&&mbt->rchild==NULL&&mbt->mz!='0')
{
vr.push_back(mbt->mz)
mbt=bt
}
if(mbt->lchild!=NULL&&vt[pit]=='1')
{
mbt=mbt->lchild
pit++
}
else if(mbt->rchild!=NULL&&vt[pit]=='0')
{
mbt=mbt->rchild
pit++
}
else if(mbt->lchild!=NULL&&mbt->rchild!=NULL) break
}
if(mbt->lchild!=NULL&&mbt->rchild!=NULL)
{
cout<<"你输入的是一个错误的码序列,请较正后再输入."<<endl
return false
}
else {
vr.push_back(mbt->mz)
return true
}
}
void read1(vector<char>&vd)
{//用于读入要解码的序列
cout<<"请输要译码的序列(以'#'结束):"<<endl
char dt
int i=0
cin>>dt
while(dt!='#')
{
vd.push_back(dt)
cin>>dt
}
}
void print_H_L_R(vector<data>vd)
{//用于计算并打印信息熵,平均码长,效率
double H=0,L=0,R=0
for(int i=0i<vd.size()i++)
{
H+=vd[i].p*(log10(1/vd[i].p)/log10(2))
L+=vd[i].p*(double)vd[i].ml
}
R=H/L
cout<<"此码的信息熵(H)是:"<<H<<endl
cout<<"此码的平均码长(L)为:"<<L<<endl
cout<<"此码的效率(U)为:"<<R<<endl
}
int main()
{
bitree * bt=new bitree
bt->ch = '#'
bt->mz = '*'
bt->lchild=NULL
bt->rchild=NULL
vector <data>vd
vector <char>vr
vector <char>vt
cout<<"************下面将对Fano编,译码的过程进行演示*************"<<endl
cout<<"__________________________________________________________"<<endl
cout<<endl
cout<<"************下面显示编码的过程及相关参数和结果************"<<endl
read(vd)
if(vd.size()==1)
{
vd[0].code.push_back('0')
vd[0].ml++
append('0',vd[0].ch,bt)
}
cout<<endl
Creatmz1(vd,0,vd.size(),1,bt)
cout<<"**************编码结果**************"<<endl
print1(vd)
print_H_L_R(vd)
cout<<endl
cout<<"************ 下面将进行译码过程 *** 作的演示 ************"<<endl
cout<<endl
read1(vt)
if(des_code(vr,vt,bt))
print2(vr)
clear(bt)
return 1
}
一定要提高悬赏分哟。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）