香农编码简单例题_单链表逆序输出c语言

常量介绍:

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)”,且内容以空格隔开,注意换行

实例图片:

3b242732b376c99c7e6f42cb68f03b5e.png3b242732b376c99c7e6f42cb68f03b5e.png

头文件:

#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); //读取完毕后,关闭文件

}

运行结果:

ac76e24e35350699bad92db46c8f7ebb.pngac76e24e35350699bad92db46c8f7ebb.png

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注