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>
using namespace std
typedef struct
{
int weight
int parent,lchild,rchild
}HTNode,*HuffmanTree
typedef char **HuffmanCode
typedef char *EachHuffcode
void Select(HuffmanTree HT,int length,int &s1,int &s2)
{
//s1 lowest,s2 lower
unsigned int min = 5000
HuffmanTree p = HT
int i
for(i = 1, ++pi <= length ++i,++p)
{
if(p->weight <min &&p->parent == 0)
{
min = p->weight
s1 = i
}
}
min = 5000
p = HT
//Get the second less weight
for(i = 1, ++pi <= length ++i,++p)
{
if(p->weight <min &&p->parent == 0)
{
if( i == s1)//case s1,ignore
continue
min = p->weight
s2 = i
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{
if(n <= 1)
return
int m = 2 * n - 1
HT = new HTNode[m + 1]//0 is not used
HuffmanTree p = HT
int i
for( i = 1, ++pi <= n++i,++p,++w)
{
p->weight = *w//NOte: never use this *p = {*w,0,0,0,0},because *p has already been declared
p->parent = p->lchild = p->rchild = 0
}
for(i <= m++i,++p)
p->weight = p->parent = p->lchild = p->rchild = 0
int s1
int s2
for( i = n + 1i <= m++i)
{
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 = new EachHuffcode[n+1]//0 is not used
char *cd = new char[n]
cd[n-1] = '\0'//the end of each char
int start
for(int i = 1i <= n ++i)
{//get each huff code for h[1] to h[n]
start = n -1
for(int c = i, int f = HT[i].parentf != 0c = f ,f = HT[f].parent)
if(c == HT[f].lchild) cd[--start] = '0'
else cd[--start] = '1'
HC[i] = new char[n - start]//allocate memory for each HT
strcpy(HC[i],&cd[start])
}
delete []cd//don't forget release memory
}
int main(int argc, char* argv[])
{
HuffmanTree hftree = NULL
HuffmanCode hfcode = NULL
int weight[4] = {7,5,2,4}//four node's weight
HuffmanCoding(hftree,hfcode,weight,4)
EachHuffcode *p = hfcode
++p
for (int i = 0i <4++i,++p)
{
cout<<*p<<endl//show each huffman code by each line
}
for(int i = 1i <=4++i)
delete hfcode[i]//release memory
delete []hfcode
delete []hftree
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）