2、构建编码树：根据字符的出现概率，构建一棵二叉树，每个字符对应一个叶子节点。出现概率越高的字符在树中的深度越浅。
3、进行编码：从根节点开始，对于每个字符，向左走表示编码0，向右走表示编码1，直到达到对应的叶子节点。这样，每个字符都可以用一个唯一的二进制码表示。
4、解码：根据编码树和二进制码，可以快速解码出原始文本或数据流。
#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
}
一定要提高悬赏分哟。
＃include<iostream.h>＃include<math.h>
＃include<iomanip.h>
＃include<stdlib.h>
class T
{
public:
T(){}
~T()
void Create()
void Coutpxj()
void Coutk()
void Coutz()
void Print()
protected:
int n
double *p
double *pxj
int *k
double *mz
}
void T::Create()
{
cout<<"请输入信源符号个数:"
cin>>n
p=new double[n]
cout<<"请分别输入这"<<n<<"个概率:\n"
for(int i=0i<ni++)cin>>p[i]
pxj=new double[n]
k=new int[n]
mz=new double[n]
double sum=0.0
for(i=0i<ni++)sum+=p[i]
if(sum!=1.0)
throw 1
else
{
for(i=0i<ni++){
int k=i
for(int j=i+1j<nj++)
if(p[k]<p[j]) k=j
double m=p[i]
p[i]=p[k]
p[k]=m
}
}
}
T::~T()
{
delete p
delete pxj
delete k
delete mz
}
void T::Coutpxj()
{
pxj[0]=0
for(int i=1i<ni++)
{
pxj[i]=0
for(int j=0j<ij++)
pxj[i]+=p[j]
}
}
void T::Coutk()
{
for(int i=0i<ni++)
{
double d=(-1)*(log(p[i])/log(2))
if(d-(int)d>0)k[i]=(int)d+1
elsek[i]=(int)d
}
}
void T::Print()
{
cout<<"Xi"<<setw(8)<<"P(xi)"
<<setw(8)<<"Pa(xj)"
<<setw(8)<<"Ki"
<<setw(8)<<"码字"
<<endl
for(int i=0i<ni++)
{cout<<"X"<<i+1
<<setw(8)<<setprecision(2)<<p[i]
<<setw(8)<<setprecision(2)<<pxj[i]
<<setw(8)<<k[i]<<""
mz[i]=pxj[i]
for(int j=0j<k[i]j++)
{
if(2*mz[i]-1>=0)
{
cout<<1
mz[i]=2*mz[i]-1
}
else
{
cout<<0
mz[i]=2*mz[i]
}
}
cout<<endl
}
double K=0.0,H=0.0,Y
for(i=0i<ni++)
{
K+=(double)p[i]*k[i]
H+=(-1)*p[i]*(log10(p[i])/log10(2.0))
}
Y=H/K
cout<<"平均码长:"<<K<<endl
cout<<"信源熵:"<<H<<endl
cout<<"编码效率:"<<Y<<endl
}
void main()
{
T tint e
try
{
t.Create()
t.Coutpxj()
t.Coutk()
t.Print()
}
catch(int e)
{if(e==1) cout<<"输入错误，请重新运行"}
}
这个是c++版本的，希望对你有用
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）