单链表实现香农编码（C++）——二牛原创

常量介绍：

si：信源符号

p(si)：该项概率

pi：前i-1项累加概率 p(s1)+p(s2)+...+p(s(i-1))

li：码长，计算公式[-log(p(si))]+1 ;(下取整)

求解步骤：

1、将信源符号按从大到小的顺序排列

2、求码长li

3、求累加概率pi

4、将累加概率pi转换为二进制小数，并根据码长li取小数点后li为作为码字

c++代码

介绍：

本程序是将原始数据存放到记事本 Data.txt 中，记事本应与.cpp文件放入同一文件目录下，然后再程序中读取记事本内数据进行香农编码。

记事本：

介绍：

名称为：Data.txt

内容：第一行："s p(si)"，且内容以空格隔开，注意换行

实例图片：

头文件：

#include<iostream>
#include<string>
#include<fstream>
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::getline(inf, s)) //将inf文件中的数字读取到data数组中
{
char *p;
if(i>1)     //第二行开始
{
S=new LinkNode;
S->Next=NULL;
}
strcpy(InitialData,s.c_str());
p = strtok(InitialData, " ");
while(p)                        //信原符号、概率、码长
{
if(i>1&&i%2==0)           //第一列
{
S->Mark=p;
}
if(i>1&&i%2==1)     //第二列
{
temp=p;
S->P=(double)atof(temp.c_str());
if(S->P<0)
{
cout<<"错误：概率存在错误，请检查记事本中概率的大小、格式是否正确！！！"<<endl;
return;
}
S->CodeLength=int(-log(S->P)/log(2))+1;
}
p = strtok(NULL, " ");
i++;
}
if(i>=4)      //排序并算出累加概率
{
T=L->Next;
R=L;
while(T!=NULL)
{
T->SumP=R->SumP+R->P;
if(S->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;
}
if(S->Next==NULL)                //S概率最小的情况
{
R->Next=S;
S->SumP=R->P+R->SumP;
}
}
}
if((S->Next==NULL&&(S->P+S->SumP)!=1)||(R->Next==NULL&&(R->P+R->SumP)!=1)) //判断概率格式
{
cout<<"错误：概率存在错误，请检查记事本中概率的大小、格式是否正确！！！"<<endl;
return;
}
R=L;
T=R->Next;
double Code;
cout<<"信源符号\t符号概率\t累加概率\t码长\t码字"<<endl;
while(T!=NULL)                                       //得出码字、输出、销毁链表
{
Code=T->SumP;
for(int j=1;j<=T->CodeLength;j++)
{
Code*=2;
if(Code<1)
{
T->Codeword+="0";
}
else
{
T->Codeword+="1";
Code=Code-int(Code);
}
}
cout<<T->Mark<<"\t\t"<<T->P<<"\t\t"<<T->SumP<<"\t\t"<<T->CodeLength<<"\t"<<T->Codeword<<endl;
delete(R);
R=T;
T=T->Next;
}
delete(R);
delete(T);
inf.close(); //读取完毕后,关闭文件
}