常量介绍:
si:信源符号
psi):该项概率
pi:前i-1项累加概率 ps1)+ps2)+…+psi-1))
li:码长,计算公式[
-logpsi))]+1 ;下取整)
求解步骤:
1、将信源符号按从大到小的顺序排列
2、求码长li
3、求累加概率pi
4、将累加概率pi转换为二进制小数,并根据码长li取小数点后li为作为码字
介绍:
本程序是将原始数据存放到记事本
Data.txt中,记事本应与.cpp文件放入同一文件目录下,然后再程序中读取记事本内数据进行香农编码。
记事本:
介绍:
名称为:Data.txt
内容:第一行:”s psi)”,且内容以空格隔开,注意换行
实例图片:
头文件:
#include
#include
#include
using namespace std;
单链表结构体声明:
typedef struct LinkList //单链表结构体
{
string Mark; //符号s
double P; //概率
double SumP; //累加概率
int CodeLength; //码长
string Codeword; //码字
struct LinkList *Next; //下一结点
}LinkNode;
主函数:
void main) //主函数
{
LinkNode *L,*R,*S,*T; //定义链表节点
L=new LinkNode; //声明
L->CodeLength=0;
L->Mark=L->Codeword=””;
L->P=L->SumP=0;
L->Next=NULL;
ifstream inf“Data.txt”); //获取数据
string s,temp;
int i=0; //标志作用
char InitialData[50]; //用于保存读取出来的数字的数组
while std::getlineinf, s)) //将inf文件中的数字读取到data数组中
{
char *p;
ifi>1) //第二行开始
{
S=new LinkNode;
S->Next=NULL;
}
strcpyInitialData,s.c_str));
p = strtokInitialData, ” “);
whilep) //信原符号、概率、码长
{
ifi>1&&i%2==0) //第一列
{
S->Mark=p;
}
ifi>1&&i%2==1) //第二列
{
temp=p;
S->P=double)atoftemp.c_str));
ifS->P<0)
{
cout<
return;
}
S->CodeLength=int-logS->P)/log2))+1;
}
p = strtokNULL, ” “);
i++;
}
ifi>=4) //排序并算出累加概率
{
T=L->Next;
R=L;
whileT!=NULL)
{
T->SumP=R->SumP+R->P;
ifS->P>T->P&&S->Next==NULL)
{
R->Next=S;
S->Next=T;
S->SumP=R->SumP+R->P;
T->SumP=S->SumP+S->P;
}
R=T;
T=R->Next;
}
ifS->Next==NULL) //S概率最小的情况
{
R->Next=S;
S->SumP=R->P+R->SumP;
}
}
}
ifS->Next==NULL&&S->P+S->SumP)!=1)||R->Next==NULL&&R->P+R->SumP)!=1)) //判断概率格式
{
cout<
return;
}
R=L;
T=R->Next;
double Code;
cout<
whileT!=NULL) //得出码字、输出、销毁链表
{
Code=T->SumP;
forint j=1;j<=T->CodeLength;j++)
{
Code*=2;
ifCode<1)
{
T->Codeword+=”0″;
}
else
{
T->Codeword+=”1″;
Code=Code-intCode);
}
}
cout<Mark<P<SumP<CodeLength<Codeword<
deleteR);
R=T;
T=T->Next;
}
deleteR);
deleteT);
inf.close); //读取完毕后,关闭文件
}
运行结果: